Rate Limiter System Design: Token Bucket to Distributed Scale

Your API works perfectly until one customer retries a failed request a thousand times. Now their traffic competes with everyone else’s, and a small downstream slowdown becomes a shared outage. A rate limiter decides how much work a caller is allowed to start before that work reaches the expensive part of the system.

The algorithm is only one piece. A useful design also specifies whose budget is being spent, where that budget lives, and what happens when the limiter itself fails.

First, write the traffic contract

Imagine a document-processing API with a policy of 100 requests per second per tenant, plus a burst allowance of 200 requests. A request costs one token. These are illustrative design inputs, not measurements from an existing service.

The phrase “100 requests per second” is ambiguous. Does it mean no more than 100 in every rolling second, or a sustained refill rate that allows temporary bursts? Our token-bucket policy means the latter.

Refill rate

100/s

How quickly a tenant earns new tokens.

Bucket capacity

200

The maximum stored burst allowance.

Request cost

1

Tokens spent before starting work.

Before drawing a diagram, settle four questions:

• Identity: tenant, API key, user, IP address, or a combination?
• Scope: one endpoint, an endpoint family, or the entire API?
• Cost: are all requests equally expensive, or should exports cost more than reads?
• Outcome: reject excess work, delay it in a bounded queue, or accept it at a lower service tier?

Use trusted identity from authentication. An arbitrary client header must not let a caller invent fresh buckets. IP limits can help control unauthenticated traffic, but shared networks and rotating IPs make them a poor substitute for tenant fairness.

Compare the five common algorithms

The term leaky bucket is also used for a meter that rejects arrivals rather than buffering them. State which interpretation you mean. Redis provides an algorithm comparison and implementation guide covering these alternatives.

For a fixed-window example, a limit of 100 per minute can admit 100 requests just before 12:01 and another 100 immediately afterward. That is legal under the window rule and surprising under a “smooth traffic” expectation. The contract determines whether it is a bug.

Follow one token bucket over time

A bucket earns tokens at rate $r$, up to capacity $B$. On each request, refill lazily from the last observed time, then check whether the request can pay its cost $c$.

There is no need for a background process that adds a token every ten milliseconds. Time elapsed since the last update tells us the new balance.

For an initially full bucket, the idealized admitted cost over an interval of length $t$ is bounded by $B + rt$. That is why this policy can accept more than 100 requests during one particular second without violating its sustained-rate contract.

Place the limiter before expensive work

Start with gateway enforcement and a shared state store. Tenant rules are configuration; token balances are live state. Cache the rules locally with a version and a refresh policy so a configuration service is not on every request’s critical path.

Multiple gateways must agree on where one tenant’s bucket lives. If ten gateways each independently allow 100 requests per second for the same tenant, their combined allowance can approach 1,000. Local state alone enforces a local limit.

A shared store adds a network dependency to every decision. Budget its latency, set a short timeout, and avoid unbounded retries. A slow limiter should not become a second queue in front of an already busy service.

Make refill, check, and spend atomic

The following pseudocode is a specification of one decision. The entire operation must execute atomically at the owner of the bucket; it is not a sequence of independent client-side Redis calls.

atomic decide(bucket, policy, request_cost, now):
    assert policy.refill_rate > 0
    assert 0 < request_cost <= policy.capacity
    effective_now = max(now, bucket.last_refill)
    elapsed = effective_now - bucket.last_refill
    tokens = min(policy.capacity,
                 bucket.tokens + elapsed * policy.refill_rate)
 
    allowed = tokens >= request_cost
    if allowed:
        tokens = tokens - request_cost
 
    save(tokens, last_refill = effective_now)
    wait = 0 if allowed else
           (request_cost - tokens) / policy.refill_rate
    return allowed, wait

Initialize a missing bucket at its configured capacity. If inactive bucket keys expire, use a lifetime at least long enough for an empty bucket to refill completely; earlier deletion could incorrectly grant a fresh burst. Policy changes need a defined migration rule, such as clamping stored tokens to the new capacity.

Redis scripts can perform the state transition without another command interleaving. Keep scripts short because execution blocks other activity on that server; see the Redis scripting documentation. For a single bucket, one key also keeps the atomic operation within one Redis Cluster hash slot.

Use a consistent time source per owner, and prevent backward clock movement from minting or removing tokens unexpectedly. Failover and persistence settings matter too: atomic execution does not by itself guarantee that a recent debit survives a primary failure.

Explain the distributed tradeoff

Sharding spreads different tenant buckets across owners. It does not automatically spread the traffic for one extremely hot tenant. Every debit for that tenant still competes at the same owner if you require a single exact budget.

A regional allocation works only if capacities and refill rates are split too. Moving quota between regions must not briefly duplicate the same budget. Leases need ownership, expiry, and recovery rules; “sync later” is not enough to preserve a hard cap.

Design the rejection and failure paths

For an actual policy rejection, send 429 Too Many Requests and useful retry guidance. Retry-After is optional in the HTTP specification; this API chooses to include it. Round a calculated subsecond wait upward when using integer seconds.

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Retry-After: 1
Cache-Control: no-store
 
{"error":"rate_limit_exceeded","scope":"tenant:document-api"}

The status and cache restriction are defined in RFC 6585, section 4. A retry time is guidance, not a reservation: another request may consume the next available token. Clients should back off with jitter instead of retrying in lockstep.

If the state store is unavailable, the service has not established that the caller exceeded a quota. Choose a separate failure policy:

• Fail open: preserve access, while accepting overload risk. A bounded local safety limit can reduce that risk.
• Fail closed: protect costly work, while sacrificing availability. Use a service-unavailable response if the cause is infrastructure failure.
• Degrade selectively: keep cheap reads available while rejecting expensive exports.

Rate limiting also does not bound concurrency. If requests become ten times slower, the same admitted rate can create roughly ten times as many in-flight requests. Pair the rate budget with worker-pool limits, deadlines, and a bounded queue where appropriate.

What to test and observe

Monitor allowed requests, policy rejections, decision errors, store latency, hot shards, and active bucket count. Avoid a metric label for every tenant if that creates unbounded cardinality; retain sampled tenant-level diagnostics separately.

Frequently asked questions

Continue the design

A strong rate-limiter answer names its identity, timing model, atomic operation, and failure policy. Practice drawing the allowed and rejected paths, then ask what changes when one tenant sends half of all traffic.

Continue with the rate limiting visual lesson, backpressure, or apply this gateway to a URL shortener design. If the limiter protects your database, the next question is how to reduce legitimate repeated work with caching strategies.