Skip to content

Distributed Rate Limiting for Multi-Tenant APIs

Rate limiting is an admission-control policy: it decides whether a caller may start another unit of work within a defined budget. It protects shared dependencies, constrains abusive or misconfigured clients, and gives a multi-tenant service a predictable way to allocate capacity.

The difficult part is not choosing a number such as “100 requests per minute.” It is defining who consumes the budget, what counts as a unit, how bursts behave, how several service instances share state, and what happens when the limiter itself is unavailable.

This chapter designs a distributed limiter for a multi-tenant HTTP API. It compares common algorithms, builds a token-bucket reference implementation in Python, shows an atomic Redis implementation in Lua, and covers HTTP behavior, fairness, failure modes, and operational rollout.

1. Separate rate, concurrency, quota, and backpressure

These controls solve related but different problems:

Control Question it answers Typical mechanism
Rate limit How quickly may this caller start work? Token bucket, fixed window, sliding window
Concurrency limit How many operations may be active at once? Semaphore, worker limit, connection-pool limit
Quota How much may this caller consume over a longer period? Durable usage counter or billing ledger
Backpressure How should producers react when consumers cannot keep up? Bounded queue, flow control, reduced admission
Load shedding Which work should be rejected when the service is saturated? Priority-aware rejection, overload policy

A limit of 20 requests per second does not mean only 20 requests can be in flight. If each request takes two seconds, the service can still have roughly 40 requests active at steady state. A slow database can therefore be overwhelmed even when request rate is within policy.

Use rate limits for caller budgets, concurrency limits for scarce active resources, and backpressure or load shedding for service capacity. They should complement one another rather than being treated as interchangeable settings.

Also distinguish a short-term rate limit from a monthly product quota. A Redis counter can be useful for both, but a billing or credit balance that must survive failover and reconcile exactly belongs in a durable source of truth.

2. Choose an algorithm that matches the contract

The algorithm determines whether bursts are allowed, how precisely a moving window is enforced, and how much state is needed.

Algorithm State per key Strength Cost or failure mode
Fixed window One counter and window Simple, cheap, easy to explain A caller can consume nearly two windows at a boundary
Sliding log One timestamp per accepted request Exact rolling-window count Memory and pruning work grow with request volume
Sliding-window counter Current and previous counters Lower memory with smoother behavior Approximation near the window boundary
Token bucket Token count and last-refill time Explicit burst capacity and average refill rate Requires atomic read-refill-consume when shared
Leaky bucket / GCRA Queue state or theoretical arrival time Smooths or schedules arrivals May add delay; policy is less intuitive to some clients

Fixed window

A fixed window increments a counter for a key such as tenant plus route plus the current minute. It is often sufficient for a coarse daily or per-minute cap.

Its boundary behavior is the important trade-off. With a limit of 100 per minute, a caller can send 100 requests just before the minute changes and another 100 immediately after it changes. The implementation has enforced both windows correctly, but the caller has produced a 200-request burst in a very short interval.

The counter operation itself must be atomic. If the counter is stored in Redis, do not leave a crash window between incrementing it and assigning its expiry. Combine the operations in a script or transaction.

Sliding log

A sliding log stores the timestamp of each accepted request. For a request at time t, remove entries older than t minus the window, count the remaining entries, and accept only if the count is below the limit.

This provides an exact rolling-window count, but it stores one entry per request. A high-volume tenant can create substantial sorted-set state and pruning work. Use it when exactness is worth the storage and write cost, not as the default for every endpoint.

Sliding-window counter

A common approximation keeps the previous window's count and the current window's count. It weights the previous count by the fraction of that window that still overlaps the current rolling window, then adds the current count.

This reduces state to a small number of counters and avoids the sharpest fixed-window boundary burst. It is an estimate, not an exact per-request history. Document that approximation if a contract or billing rule depends on exact counts.

Token bucket

A token bucket has a capacity C and a refill rate r tokens per second. It begins full. A request with cost k is allowed only when at least k tokens are available; accepting the request subtracts k tokens.

The state is small:

  • Current token balance.
  • Time at which the balance was last updated.

If the bucket currently has T tokens and elapsed time is delta, the new balance is:

min(C, T + r × delta)

The balance is capped at C, so idle time never accumulates an unlimited future burst. The bucket controls the long-run average through r while allowing a burst up to C.

For example, a bucket with capacity 20 and refill rate 5 tokens per second can accept 20 unit-cost requests immediately when full. If it is empty, it needs four seconds to refill 20 tokens. A request that costs 4 tokens consumes the same budget as four ordinary requests.

Token buckets are a strong default for APIs that need both a sustained rate and a deliberate burst allowance.

Leaky bucket and GCRA

A leaky bucket models a queue that drains at a configured rate. Excess arrivals may be delayed until the configured burst allowance is exhausted, after which they are rejected. NGINX documents its request limiter as a leaky-bucket implementation; its burst and delay settings make the choice between smoothing and immediate rejection explicit.

The Generic Cell Rate Algorithm (GCRA) represents the schedule using a theoretical arrival time rather than retaining every request timestamp. It is useful when a smooth rate and compact state matter. Be precise about whether the implementation delays work, rejects it, or merely calculates a retry hint.

3. Define the identity and policy before writing code

A limiter is only as correct as its key. Decide what is being protected and who should share the budget.

A typical authenticated API might use several dimensions:

  • Tenant: prevents one customer from consuming the entire shared service.
  • API credential or service account: isolates integrations within a tenant.
  • User: protects interactive accounts from accidental loops.
  • Route class: gives expensive report generation a different budget from a cheap health or metadata read.
  • Global service guardrail: protects the whole dependency even when every tenant is individually within its plan.

Use authenticated internal identifiers after authentication. An API key identifier or tenant ID is usually a better partition key than a user-supplied name or raw email address.

IP-based limits are still useful before authentication and as a coarse abuse signal. They are not a reliable identity for every authenticated user: many people may share a corporate NAT address, mobile addresses can change, and forwarded-IP headers can be spoofed unless the request came through a trusted proxy that overwrites them.

Normalize route keys. Use a route template such as reports-by-tenant, not the raw URL path containing arbitrary record IDs. Otherwise, an attacker can create unbounded limiter keys by varying path segments.

For sensitive identifiers, use an opaque internal ID or a keyed hash in the Redis key. Avoid putting raw credentials or personal data into key names, metrics, and logs.

Weighted costs

Counting every HTTP request as one unit is often too crude. A GraphQL query, a large export, an image transformation, or an LLM request can cost far more than a small read.

Assign a bounded cost from validated server-side metadata. For an LLM API, the cost might be based on a conservative token estimate or a server-measured usage value. Do not trust a client-supplied cost field without validation; otherwise a caller can under-report expensive work.

The cost model should be explainable and versioned. If the weights change, record the policy version so operators can understand why a caller's remaining budget changed.

4. Local versus distributed enforcement

A process-local counter is fast, but it is not a service-wide limit. With eight API instances, a local allowance of 100 requests per minute can permit close to 800 requests per minute for one caller if traffic is distributed across all eight instances.

There are three common placements:

  1. Edge or gateway limiter: cheaply rejects obvious abuse before application work. A local gateway bucket can protect each proxy, but a per-process limit is not automatically a global tenant limit.
  2. Application limiter: runs after authentication and can use tenant, user, credential, and route information.
  3. Shared global limiter: uses a central store or rate-limit service so all application instances consult the same policy state.

A practical request path is:

  1. Apply a coarse pre-authentication guard at the edge.
  2. Authenticate the caller and resolve a stable tenant or credential identifier.
  3. Determine the route policy and validated request cost.
  4. Evaluate the relevant tenant, credential, and global budgets.
  5. Reject or delay the request before expensive application work if policy denies it.
  6. Apply concurrency and downstream pool limits separately before calling scarce dependencies.

Redis is a common shared store because its atomic commands and Lua scripting can keep the read-refill-decide-update operation together. The trade-off is that the limiter becomes a synchronous dependency on the request path. Its latency, availability, key cardinality, and failure policy must be designed like any other production dependency.

5. A testable in-process token bucket in Python

This implementation is a reference model for understanding token-bucket behavior. It uses a monotonic clock and a lock so concurrent threads in one process cannot spend the same token twice.

It is not a distributed limiter: every process would have its own bucket. Use it for local protection or deterministic tests, not as the only enforcement point for a multi-instance service.

The clock is injected so tests can advance time without sleeping.

from dataclasses import dataclass
from math import ceil, isfinite
from threading import Lock
from time import monotonic
from typing import Callable


@dataclass(frozen=True)
class Decision:
    allowed: bool
    remaining: float
    retry_after_seconds: int | None


class TokenBucket:
    def __init__(
        self,
        capacity: float,
        refill_per_second: float,
        clock: Callable[[], float] = monotonic,
    ) -> None:
        if not isfinite(capacity) or capacity <= 0:
            raise ValueError("capacity must be a finite positive number")
        if not isfinite(refill_per_second) or refill_per_second <= 0:
            raise ValueError("refill rate must be a finite positive number")

        self.capacity = float(capacity)
        self.refill_per_second = float(refill_per_second)
        self._clock = clock
        self._tokens = self.capacity
        self._updated_at = self._clock()
        self._lock = Lock()

    def consume(self, cost: float = 1.0) -> Decision:
        if not isfinite(cost) or cost <= 0:
            raise ValueError("cost must be a finite positive number")

        with self._lock:
            # Never mint tokens if the supplied clock moves backwards.
            now = max(self._clock(), self._updated_at)
            elapsed = now - self._updated_at
            self._tokens = min(
                self.capacity,
                self._tokens + elapsed * self.refill_per_second,
            )
            self._updated_at = now

            # A request larger than the bucket can never become admissible.
            if cost > self.capacity:
                return Decision(False, self._tokens, None)

            if self._tokens >= cost:
                self._tokens -= cost
                return Decision(True, self._tokens, None)

            wait = ceil(
                (cost - self._tokens) / self.refill_per_second
            )
            return Decision(False, self._tokens, max(1, wait))

Run the deterministic tests from the repository root:

python -m unittest discover -s interview-handbook/examples/python/rate_limiter -p 'test_*.py' -v

The tests cover initial capacity, fractional refill, weighted costs, invalid costs, clock rollback, and concurrent consumption. They do not replace an integration test against the shared Redis implementation.

The Redis script integration check is committed as examples/python/rate_limiter/test_redis_script.sh. It exercises refill, rejection, impossible request costs, and concurrent requests against a real Redis server. Run it with Redis and redis-cli available:

bash interview-handbook/examples/python/rate_limiter/test_redis_script.sh

6. Make the shared Redis decision atomic

For a distributed token bucket, every application instance must update the same state without a race. A sequence of separate GET, calculation, and SET commands is unsafe: two requests can read the same balance and both spend it.

A Redis Lua script executes the read-refill-decide-write sequence atomically relative to other commands. The following script uses one hash per policy key and Redis server time so application instances do not calculate refill from unrelated host clocks.

The script is also committed as examples/python/rate_limiter/token_bucket.lua.

-- KEYS[1]: one bucket key
-- ARGV[1]: capacity
-- ARGV[2]: refill tokens per second
-- ARGV[3]: request cost

local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local cost = tonumber(ARGV[3])

if not capacity or capacity <= 0
    or not refill_rate or refill_rate <= 0
    or not cost or cost <= 0 then
    return redis.error_reply("capacity, refill rate, and cost must be positive")
end

if cost > capacity then
    return {0, 0, -1}
end

local clock = redis.call("TIME")
local now = tonumber(clock[1]) + tonumber(clock[2]) / 1000000

local state = redis.call("HMGET", key, "tokens", "updated_at")
local tokens = tonumber(state[1])
local last_refill = tonumber(state[2])

if tokens == nil and last_refill == nil then
    tokens = capacity
    last_refill = now
elseif tokens == nil or last_refill == nil then
    return redis.error_reply("incomplete token bucket state")
end

local elapsed = math.max(0, now - last_refill)
tokens = math.max(0, math.min(capacity, tokens + elapsed * refill_rate))

-- If the wall clock moves backwards, keep the later stored timestamp.
local updated_at = math.max(now, last_refill)
local allowed = 0
local retry_after = 0

if tokens >= cost then
    tokens = tokens - cost
    allowed = 1
else
    retry_after = math.max(1, math.ceil((cost - tokens) / refill_rate))
end

redis.call("HSET", key, "tokens", tokens, "updated_at", updated_at)
redis.call("EXPIRE", key, math.ceil(capacity / refill_rate) + 1)

return {allowed, math.floor(tokens), retry_after}

The return values are:

  1. 1 when the request was allowed, otherwise 0.
  2. Remaining whole tokens, rounded down for a conservative display.
  3. A retry delay in seconds. A value of -1 means the requested cost exceeds the bucket's maximum capacity and can never be satisfied by waiting.

The key expires only after enough idle time for the bucket to refill fully, plus a small safety margin. If the key is absent after that idle period, initializing it as full is correct.

The script is intentionally short and constant-time. Redis scripts block command execution while they run, so do not put loops over unbounded request history inside a script. This example stores fractional token balances as floating-point values for readability. Bound capacities and rates to a safe numeric range; for strict integer accounting, use scaled integer units and explicitly test precision and overflow limits. Do not use floating-point token state as a financial ledger.

Multiple simultaneous policies

A request may need to satisfy a per-credential bucket, a per-tenant bucket, and a global safety bucket. Checking and decrementing them independently can consume the first budget even when the second budget rejects the request.

If all budgets must be all-or-nothing, one atomic operation must:

  1. Refill every applicable bucket.
  2. Check every policy without decrementing any bucket.
  3. If any policy denies, write the refreshed state but do not spend tokens from the other buckets.
  4. If every policy allows, decrement every bucket and return the decision.

In Redis Cluster, keys used by one multi-key script must be in the same hash slot. A hash tag such as {tenant-42} can co-locate that tenant's keys, but it can also concentrate a very large tenant on one slot. If the policies cannot be co-located, use a deliberately designed reservation protocol or a dedicated rate-limit service; do not pretend several independent checks are one atomic decision.

7. Define the HTTP contract

For a caller that exceeded its policy, return HTTP 429 Too Many Requests. RFC 6585 defines this status for a user sending too many requests in a given period. It says the response should explain the condition and may include Retry-After.

Retry-After has two valid forms under RFC 9110: a non-negative number of seconds or an HTTP date. For a token bucket, the delay-seconds form is usually easier to calculate.

HTTP/1.1 429 Too Many Requests
Content-Type: application/problem+json
Cache-Control: no-store
Retry-After: 2

{
  "title": "Rate limit exceeded",
  "detail": "The reports policy has no available capacity."
}

A retry hint is not a promise that the next request will succeed. Another request may consume the available token first, the policy may change, or the service may be overloaded for a separate reason. Clients should use bounded retries, add jitter, and respect the server's overall request deadline.

Do not return 429 for every overload condition. Use 429 when the caller exceeded an identifiable caller or tenant policy. Use 503 when the service is temporarily unable to handle requests because of overload or maintenance; RFC 9110 permits Retry-After with 503 as well. A service may need to shed traffic before it can afford to generate a detailed 429 response during an attack.

The IETF HTTPAPI working group is also developing RateLimit-Policy and RateLimit response fields. As checked on 2 November 2026, draft-ietf-httpapi-ratelimit-headers-11 is an active Internet-Draft, not a published RFC or final standard. Its syntax and semantics may still change. Treat it as evolving guidance, not a stable contract that every client already understands. If you adopt it, version and document the behavior and continue to support a clear 429 response and Retry-After where appropriate.

8. Failure modes and design trade-offs

The limiter is unavailable

Choose fail-open or fail-closed by endpoint and threat model.

  • Fail-open preserves application availability when Redis is down, but callers may bypass quotas and overload expensive dependencies.
  • Fail-closed protects the dependency, but a Redis outage can become an API outage even when the application is healthy.
  • Local emergency limit can reduce the blast radius while the shared store is unavailable, but it is not globally exact and multiplies across instances.

For a public read endpoint, a short fail-open window with a conservative local guard may be acceptable. For a costly model invocation, payment operation, or external provider with strict spend limits, fail-closed or a durable reservation path may be safer. Make the choice per policy, not as one global boolean.

Use short Redis timeouts and a circuit breaker. Do not let requests queue indefinitely waiting for the limiter. Record when the system bypasses or rejects traffic because the limiter itself failed.

Replication and failover can change the effective budget

A shared Redis key gives all instances one decision point while that primary is authoritative. Replication and failover semantics still matter: a promoted replica may not contain the most recent counter updates, depending on the deployment's durability and replication guarantees. That can temporarily permit more traffic than the nominal budget.

For ordinary API protection, a small bounded overage may be acceptable. For financial credits, contractual quotas, or irreversible spend, use a durable ledger or a reservation system with the consistency guarantees the product requires.

A single global key can become a hotspot

A single global bucket is easy to reason about but can serialize a high volume of requests through one key. Sharding the key changes the policy: each shard receives only part of the budget, or the total allowance can exceed the intended global limit if every shard gets a full copy.

Use per-tenant keys for tenant fairness, reserve global protection for a deliberate service guardrail, and load-test hot tenants. A global hard cap across regions requires coordination; regional counters with independent allowances trade exactness for lower latency and availability.

Time is part of the algorithm

Use a monotonic clock for an in-process bucket. A distributed bucket needs a common time source; the Redis script above uses Redis server time instead of each application's local clock.

Server time is still wall-clock time and can be adjusted. The script prevents a backward adjustment from minting tokens by never moving its stored timestamp backwards. A large forward jump can refill the bucket up to its configured capacity, never beyond it. Monitor clock health and keep the capacity small enough that a full refill is an acceptable burst.

Identity and key cardinality can be abused

Do not create keys from arbitrary user-controlled strings or raw URL paths. Normalize routes, validate identity before allocating authenticated buckets, and expire idle state. A pre-authentication IP limiter should also have a bounded key policy and must not trust spoofable forwarded headers.

Avoid putting tenant IDs or API keys in metric labels. High-cardinality labels can overwhelm the monitoring system and expose identifiers. Use aggregate metrics and sampled structured logs for per-tenant investigation.

Retries can turn rejection into a traffic spike

If every client retries at the same boundary, the limiter can create a thundering herd. Return a useful retry delay when it is meaningful, use jitter on client retries, cap attempts, and propagate the remaining end-to-end deadline. Never retry a request indefinitely just because the response was 429 or 503.

9. Roll out and observe the policy

Start in shadow or dry-run mode. Count which requests would be rejected without enforcing the decision. Compare the proposed policy against real tenant traffic, known batch jobs, partner integrations, and expected bursts before turning it on.

A safe rollout sequence is:

  1. Define the protected resource and tenant fairness objective.
  2. Choose the identity key, route class, request cost, capacity, and refill rate.
  3. Run the policy in shadow mode and inspect the distribution of would-be rejections.
  4. Notify affected clients and document retry behavior.
  5. Enforce for a small set of routes or tenants.
  6. Watch rejection rates, latency, dependency saturation, and support signals.
  7. Expand gradually and keep an emergency policy rollback.

Useful signals include:

  • Allowed and denied decisions by policy and outcome.
  • Rate-limit check latency and Redis timeout/error rate.
  • Number of fail-open decisions and local-fallback decisions.
  • 429 and 503 response rates, separated by cause.
  • Tenant-level usage distribution through sampled logs or a top-K report.
  • Downstream connection-pool wait, queue depth, active concurrency, and dependency saturation.

Do not put tenant IDs, user IDs, API keys, or raw IP addresses into metric labels. Use low-cardinality labels such as policy name, route class, and outcome. Keep detailed identity in access-controlled logs with an explicit retention policy.

Test boundary behavior, weighted requests, concurrent calls, clock movement, key expiry, Redis timeouts, failover, tenant isolation, proxy-header handling, and retry storms. A happy-path unit test proves only the arithmetic; the production contract includes the shared store and the clients that react to rejection.

10. Interview questions with reasoned answers

Q1. Why can a per-process rate limiter be wrong behind a load balancer?

Each instance has independent state. A caller routed across N instances can consume close to N times the intended allowance. Use a shared limiter or deliberately allocate a per-instance budget whose aggregate is the intended policy.

Q2. What is the difference between a fixed window and a token bucket?

A fixed window counts requests in discrete intervals and can allow a large burst across a boundary. A token bucket refills continuously up to a capacity, so it explicitly controls both the long-run rate and the maximum burst.

Q3. Why is a check followed by an increment unsafe?

Two concurrent requests can both read the same remaining capacity and both decide to allow. The read, refill, decision, and state update must be one atomic operation, such as a short Redis Lua script.

Q4. Why not use a single IP address as the tenant key?

NAT can group unrelated users, IP addresses can change, and forwarded headers can be spoofed if proxies are not trusted. Use authenticated tenant or credential identity after authentication, with IP limits as a coarse pre-authentication control.

Q5. How would you enforce both per-user and per-tenant limits?

Evaluate both policies for the same request. If the contract requires all-or-nothing consumption, refill and check all buckets first, then decrement all of them only when every policy allows. Independent check-and-decrement calls can consume one budget even when another rejects the request.

Q6. When should an API return 429 rather than 503?

Return 429 when the caller exceeded a defined rate or quota policy. Return 503 when the service itself is temporarily unable to handle requests because of overload or maintenance. A service may use both controls at different layers.

Q7. What happens if Redis fails?

The service must apply an explicit per-policy failure mode: fail-open, fail-closed, or a conservative local fallback. Bound Redis timeouts, use a circuit breaker, and measure bypasses. The correct choice depends on the cost and risk of admitting the request.

Q8. Does a token bucket enforce concurrency?

No. It controls admission rate and burst size. Slow requests can still accumulate in flight. Add a semaphore, worker limit, connection-pool bound, or other concurrency control for scarce resources.

Q9. How do you support expensive requests fairly?

Use validated weighted costs and separate policies for expensive route classes or resource units. Keep the cost model server-controlled, bounded, documented, and observable. For metered financial usage, reconcile against a durable ledger rather than treating a transient rate-limit key as the billing source of truth.

Q10. Can several Redis keys be checked atomically in Redis Cluster?

A multi-key script requires the keys to be in the same hash slot. Hash tags can co-locate a tenant's keys, but may create a hotspot. If policies cannot be co-located, use a reservation protocol or dedicated service and document the consistency trade-off.

11. Design checklist

  • Define whether the control is a rate limit, concurrency limit, quota, or overload policy.
  • Identify the resource being protected and the fairness objective.
  • Choose a stable principal and normalized route key.
  • Select an algorithm based on burst behavior, precision, and state cost.
  • Define weighted request costs where work is not uniform.
  • Make shared state updates atomic across all required policy dimensions.
  • Decide fail-open, fail-closed, and local fallback behavior per policy.
  • Return 429 for caller policy violations and use Retry-After when it is meaningful.
  • Separate caller rejection from service overload and 503 responses.
  • Bound retries, queues, concurrency, and Redis request timeouts.
  • Roll out in shadow mode and monitor false positives and downstream saturation.
  • Use a durable ledger for financial or contractual quotas that require stronger guarantees.

References