Designing a distributed rate limiter

A rate limiter is a counter and a comparison, which is why people underestimate it. The difficulty is that the counter has to be shared by a hundred servers in three regions, updated a million times a second, correct enough to bill against, and read in less than a millisecond — and it must never be the reason the system goes down. The reliability article introduced the algorithms as one tool among many; this one builds the service.

The map

Read this first when short on time. Every branch is a section below.

What a limiter must do, and at what size

A rate limiter does three jobs that are easy to confuse. It protects capacity, keeping total load inside what the system can serve. It enforces a plan, making a paid quota mean something. And it isolates tenants, so one customer's runaway script does not consume everybody else's service. The first is about the system, the second about money, and the third about fairness — and they want different algorithms, different accuracy and different failure behaviour, which is why a real deployment runs several limiters rather than one.

Checks        1,000,000 per second at peak
Rules         3-5 evaluated per request (global, tenant, user, route)
Keys          ~10 million distinct subjects active in a window
State         ~100 B per key (counter, window start, TTL) -> ~1 GB
Latency       budget +1 ms at p99 for the whole check
              in-datacenter round trip ~0.5 ms -> one store call, not five
Correctness   a few percent over the limit is fine
              under the limit is not, when a customer paid for it

The latency line is the constraint that shapes the design. A limiter sits in front of every request, so its own cost is added to every request; a budget of one millisecond means one network round trip, which means the several rules for a request must be evaluated in a single call rather than one call each.

The correctness line is the one worth arguing about early. Exactness is expensive and, for a capacity limit, pointless — the number 1,000 requests per second was itself a guess, so a limiter that sometimes admits 1,015 is not wrong in any meaningful sense. For a billed quota the asymmetry flips: letting a customer slightly over is a rounding error, cutting them off early is a support ticket. Stating the tolerance and its direction up front decides most of the later choices.

The algorithms, and exactly how each one behaves

Five algorithms, in order of increasing quality and decreasing simplicity. The differences only become visible at the boundaries, which is exactly where load arrives.

Fixed window. Keep one counter per key per window and reset it when the window rolls. It is one increment and one comparison, and it has a well-known flaw: a client that sends its whole allowance at the end of one window and again at the start of the next pushes twice the limit through in a moment straddling the boundary.

Sliding window log. Store the timestamp of every request, drop those older than the window, and count what is left. It is exactly right, and it costs memory proportional to the traffic it is permitting — a client allowed 5,000 requests an hour needs 5,000 timestamps. Correct, and rarely affordable.

Sliding window counter. The practical compromise: keep the current window's counter and the previous one's, and estimate the rate over the trailing window by weighting the previous count by how much of it still overlaps.

estimate = previous_count x overlap_fraction + current_count

At 10:01:15 with a 60 s window:
  45 s of the previous window still overlaps -> overlap_fraction = 0.75
  previous_count = 80, current_count = 30
  estimate = 80 x 0.75 + 30 = 90    -> under a limit of 100, allow

It assumes the previous window's requests were spread evenly, which is not true, so it can be slightly wrong in both directions. Published measurements at very large scale put the error in the thousandths of a percent of requests — two counters and one multiplication for effectively exact behaviour.

Token bucket. A bucket holds up to capacity tokens and refills at rate tokens per second; a request takes one token or is rejected. This is the only algorithm on the list that models burst and sustained rate as separate numbers, which is usually what a product actually wants: 100 requests per second sustained, but a burst of 500 is fine. Implementation is two numbers per key — token count and last refill time — with refill computed lazily at read time rather than by a background job.

GCRA. The generic cell rate algorithm is a leaky bucket expressed as a single timestamp. Instead of counting tokens it tracks the theoretical arrival time of the next permitted request: each request costs an emission interval of time, and a burst tolerance says how far ahead of that schedule a client may run. One value per key, no counters, and the smoothest output of the five.

Where to enforce

A limit can be applied at three places, and the useful design applies it at all three with different strictness, because each layer knows something the others do not.

flowchart TD
  C["client"] --> E["edge: per IP, coarse, cheap"]
  E --> G["gateway: per tenant and per route, the plan limits"]
  G --> S["service: per dependency, concurrency and cost"]
  S --> D[["database or downstream"]]
  E -. "drops floods before they cost anything" .-> X["rejected"]
  G -. "enforces what the customer paid for" .-> X
  S -. "protects the thing that actually breaks" .-> X

The edge sees the raw connection and nothing else — no tenant, no route semantics — but it is the only place that can reject a flood before it costs any money, since everything past it consumes capacity. Its limits are coarse and per IP or per token.

The gateway knows who the caller is and what they are asking for, so it is the natural home for plan limits: a thousand requests a minute on this endpoint for this plan. This is where the interesting limiter lives, and the rest of the article is mostly about it.

The service knows what a request actually costs. A search that scans a million rows and a key lookup are one request each to the gateway and a thousandfold difference here, which is why service-level protection is usually a concurrency limit rather than a rate limit: at most N requests in flight against this dependency, regardless of arrival rate. Concurrency limits self-adjust to the work's real cost in a way that rate limits cannot.

Making one limit work across many nodes

Here is the actual problem. The limit is global — a thousand requests a minute for this tenant — and the traffic arrives at a hundred nodes, each seeing a fraction of it. Something has to reconcile them, and every option trades accuracy against latency.

The central store is the right default because it is the only one that is both simple and correct, and because half a millisecond is affordable at a gateway. The local-only option deserves its bad reputation: the even split is exactly wrong in the common case, since load balancing is per connection and a single client's traffic rarely spreads evenly.

Where local decisions become attractive is at very high rates for very large tenants, and there the fix for the even-split problem is quota redistribution: nodes periodically report usage to a coordinator, which reallocates the global allowance in proportion to demand, so idle nodes give up their share to busy ones. It converges within a few reporting intervals and removes the store from the request path entirely.

flowchart TD
  subgraph Central["Central counter"]
    direction LR
    N1["node A"] --> ST[["shared counter"]]
    N2["node B"] --> ST
  end
  subgraph Lease["Quota lease"]
    direction LR
    M1["node A holds 200"] --> CO["coordinator"]
    M2["node B holds 800"] --> CO
  end
  Central ~~~ Lease

The counter store

The store holds one small record per active key, is read and written on every request, and must apply the check and the update as one indivisible step.

That last point is the whole reason this needs care. The obvious implementation — read the counter, compare it, write it back — is a race: two nodes read 999 simultaneously, both decide to allow, and both write 1,000. Under load that race is not rare, it is the normal case. The fix is to push the entire decision into the store as a single atomic operation: a small server-side script that reads the counter, applies the algorithm, writes the new state, sets the expiry and returns both the verdict and the remaining allowance.

-- one atomic call: token bucket refill, spend, and report
-- KEYS[1] = bucket key   ARGV = rate, capacity, now_ms, cost
local state    = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens   = tonumber(state[1]) or tonumber(ARGV[2])
local ts       = tonumber(state[2]) or tonumber(ARGV[3])
local elapsed  = math.max(0, tonumber(ARGV[3]) - ts) / 1000
tokens = math.min(tonumber(ARGV[2]), tokens + elapsed * tonumber(ARGV[1]))

local allowed = tokens >= tonumber(ARGV[4])
if allowed then tokens = tokens - tonumber(ARGV[4]) end

redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', ARGV[3])
redis.call('PEXPIRE', KEYS[1], 60000)
return { allowed and 1 or 0, math.floor(tokens) }

Three details in that script matter beyond the algorithm. The refill is computed from elapsed time on read, so there is no background job and an idle key costs nothing. The expiry is reset on every write, so keys for subjects that stop sending traffic disappear on their own — which is what keeps ten million keys from becoming a hundred million. And now_ms is passed in or taken from the store's own clock rather than each caller's, because a node whose clock is a few seconds off would otherwise shift its window boundaries and quietly get a different limit.

Key naming follows from the rules: rl:{tenant}:{rule}:{window}, with the tenant in a hash tag so that all of one tenant's rules land on the same shard and can be evaluated in one pipelined call. Point operations only — a limiter must never scan.

How wrong is it allowed to be?

Every performance decision here buys speed with accuracy, so it is worth stating what accuracy is actually needed — in a design, in one sentence, before the choices are made.

Exactness across regions is not merely expensive but impossible in the sense that matters: a global counter that is correct at all times requires consensus on every request, and no limiter will pay tens of milliseconds for that. What is achievable is exactness within a region and approximation across them, which is why global limits are usually enforced per region with the allowance divided, and only reconciled afterwards for billing.

Within a region, the tolerances that work in practice: a capacity limit may overshoot by a few percent, because the number was an estimate anyway. A billed quota must never undershoot — cutting a paying customer off early is worse than letting them have a little extra. And an abuse limit should be strict but is allowed to be slow, since a scraper throttled two seconds late has not achieved much.

Multi-tenant fairness

One limit per tenant is not enough, because tenants are not the only thing that needs protecting. A real system evaluates a hierarchy, cheapest first, and the first rejection ends the evaluation.

flowchart TD
  R["request arrives"] --> G{Global capacity left?}
  G -- no --> S["429, shed by priority"]
  G -- yes --> T{Tenant quota left?}
  T -- no --> S
  T -- yes --> U{User limit left?}
  U -- no --> S
  U -- yes --> E{Route limit left?}
  E -- no --> S
  E -- yes --> A["admit, decrement all four"]

The noisy neighbour problem is what the tenant level exists for: without it, one customer's retry storm consumes the shared pool and everyone else sees errors caused by someone they have never heard of. Per-tenant caps on a shared resource are the fix, and they work best as a share rather than a fixed number — a tenant may use up to their weighted share when the system is busy, and more than it when it is idle.

When the global limit is the one being hit, rejection should not be uniform. Shed by priority: reject the batch export before the interactive request, the free tier before the paid one, and never the health check or the payment callback. This makes the limiter a load-shedding mechanism as well as a fairness one, and it needs request priority to be known at the gateway, which means the API has to carry it.

Telling the client

A limiter that rejects silently, or with a generic error, produces clients that retry immediately and make everything worse. The response is part of the design.

HTTP/1.1 429 Too Many Requests
Retry-After: 12
RateLimit-Limit: 1000
RateLimit-Remaining: 0
RateLimit-Reset: 12
Content-Type: application/json

{ "error": "rate_limited", "scope": "tenant", "retry_after_seconds": 12 }

Three things make this useful. Retry-After tells the client exactly when to come back, which converts a retry storm into a scheduled request. The limit and remaining headers let a well-behaved client slow down before being rejected, which is the difference between a client that gets throttled occasionally and one that lives permanently at the limit. And naming the scope tells the caller which limit they hit, so they know whether to slow down, upgrade, or spread their work across users.

On the client side, the rules are the ones from the reliability article: honour Retry-After when it is present, back off exponentially with jitter when it is not, keep a retry budget so that retries can never exceed a small fraction of traffic, and never retry a 429 immediately.

Failure, and the clock

The limiter is in front of everything, so its own failure modes are more important than its accuracy.

Fail open or fail closed? The answer is per rule rather than global. A plan-enforcement limit should fail open: if the counter store is unreachable, serving customers is better than rejecting them, and the revenue at risk exceeds the overage. An abuse limit should fail closed, because its whole purpose is to stop traffic that is already hostile. A capacity limit should fail to a conservative local fallback — each node enforcing a fixed share — because failing open there means the outage the limiter existed to prevent.

Clock skew shifts window boundaries between nodes. If each node uses its own clock, two nodes disagree about which window a request belongs to, and a client can exploit the seam. Taking the time from the counter store, in the same atomic call that does the check, removes the problem entirely.

Store outage is the case to rehearse. The limiter should degrade to a local, coarse, conservative limit rather than disappearing — and it should say so loudly in metrics, because a system running on fallback limits is one incident away from either an outage or a very large bill.

What breaks first

1. Round trips per request. Not the store's capacity but the number of calls: five rules evaluated as five sequential calls is 2.5 ms of added latency. Pipeline them into one, co-locating a tenant's keys with a hash tag so that is possible.
2. The hot key. The largest tenant's counter is touched on every one of their requests, and it lives on exactly one node. Sub-counters are the standard fix, at a small cost in accuracy.
3. Key cardinality. Per-IP limits on a large public surface can produce far more keys than expected. Short TTLs keep the set bounded, and the memory estimate should be made from distinct subjects per window rather than from total traffic.
4. The blast radius of the limiter itself. The most expensive failure in this article is not being slightly wrong about a limit, it is the limiter becoming a single point of failure in front of everything. Local fallbacks and per-rule failure modes are what bound it.

Recap