Design Interviews · lesson 2 of 15 · about 28 min
A rate limiter for a whole fleet, end to end: what it stores, why the obvious counter update is wrong, how to trade accuracy for speed, what the 429 should tell clients, how to weigh expensive calls, and what happens when the limiter itself goes down. Tap any for a plain-language card.
A limiter is a service too
Two numbers size it: the checks per second (one per request, so the same as your traffic) and the number of counters (callers × rules). Counters are tiny but numerous; checks are many but simple. Sharding the store by caller key spreads both. Estimate yours.
10 million active users with 3 rules each is 30 million counters, about 3 GB at 100 bytes each; 100,000 checks a second at 50,000 operations per shard needs at least 2 shards.
10 million callers with 3 rules each is 30M counters, about 3.0 GB; 100,000 checks a second need at least 2 shards. Memory is easy; the throughput and the latency of each check are the real constraints.
Arithmetic. Counters are keys with a time-to-live so idle callers disappear; keep the working set, not every caller ever seen. The shard throughput is an assumption: measure your store.
Two requests, one counter
The fix is to make check-and-update a single indivisible operation inside the store: an INCR followed by a comparison, or a small server-side Lua script in Redis, or a compare-and-set. Simulated below: one key, Poisson arrivals, a fixed window. Compare both modes and widen the round trip.
Limit 100 per minute, 20 requests a second, 10 ms between read and write: the naive code lets 133 through. At 50 ms it lets 207 through. The atomic version allows exactly 100.
With GET-then-SET and 10 ms between read and write, 133 requests passed a limit of 100: 33 too many (33% over), because concurrent requests read the same count and overwrote each other's increments.
Seeded simulation: Poisson arrivals over one 60-second window; the naive path reads the counter, then writes the value it read plus one after the chosen delay.
Accuracy costs a round trip
The usual compromise is local counting with periodic synchronisation: nodes count locally and exchange (or batch-send) their counts every T milliseconds. Between syncs each node is blind to the others, so the limit can be exceeded by about traffic × T. Lengthen T and you save store traffic and latency but accept a bigger overshoot. Choose T by how much overshoot is tolerable.
800 req/s offered against a global 1,000/s limit over 10 nodes with Zipf skew 1.0: a static 100/s split wrongly rejects 26% of legitimate traffic. Syncing every 100 ms overshoots by up to 80 requests (8%).
With 10 nodes, skew 1.0 and a 1,000/s limit, a static 100/s split wrongly rejects 26% of a legitimate 800/s caller. Syncing every 100 ms lets the limit be exceeded by up to 80 requests (8%).
Static split: rejection = Σ max(0, node share × load − limit ÷ nodes) ÷ load. Sync overshoot ≈ offered load × sync interval (the worst case, when all traffic arrives within one interval).
What the 429 should say
Spread the retries: tell each client a slightly different Retry-After (add random jitter to the value you send), and make client libraries add and exponential of their own. Fixed windows make this worse because every caller's window resets on the same clock tick; sliding windows or per-caller start times avoid the shared edge. Try a spread.
100,000 blocked clients retrying at the same reset instant send 100,000 requests in one second. Spread over 30 seconds the peak is about 3,400 a second.
100,000 clients told to come back at one instant create a spike of 100,000 requests in a second. Spreading the Retry-After over 30 s cuts the peak to 3,423 a second, 29.2× lower.
Seeded simulation: each client picks a uniform random moment within the spread; the number is the busiest one-second bucket.
Not every request weighs the same
The same idea gives you tiers (free: 600 tokens a minute, paid: 6,000), per-endpoint rules in addition to a global one, and rules by dimension (per user, per IP, per organisation, whichever trips first). Set the cost from measurement of CPU or database time, and publish the costs so clients can plan.
With 20% of requests costing 20 tokens the average cost is 4.8, so a 600-token budget allows 125 requests a minute, instead of 600 that could load the backend with 2,880 token-equivalents.
If 20% of requests cost 20 tokens the average is 4.8, so a 600-token budget allows 125 requests a minute. A flat limit of 600 requests would let that caller put 2,880 units of load on the backend, 4.8× what the budget intends.
Arithmetic: average cost = (1 − p) × 1 + p × cost; requests allowed = tokens ÷ average cost. A flat limit equal to the token budget lets through tokens × average cost units of load.
Pick the mechanism
Each situation has one mechanism that fits best. Each answer is worth 20 XP.
Match the symptom: lost updates, round-trip cost, uneven request cost, or a dead store?
Two app servers both read a count of 99 and both allow the request.
Tip: press 1 to 4 to answer, Enter for the next one.
Who lives by this
Published write-ups of rate limiting at scale.
Scaling your API with rate limiters
Stripe's engineering write-up describes a token-bucket request-rate limiter plus a concurrent-requests limiter and two load shedders that protect the fleet, with the stated aim of keeping a few misbehaving clients from affecting everyone else.
sliding-window counters
Cloudflare described a rate limiter that uses an approximate sliding-window counter per client and per rule, chosen because it needs very little memory and is accurate enough, then synchronised across its edge locations.
X-RateLimit headers
The GitHub API returns limit, remaining and reset values in response headers so that clients can pace themselves before they are rejected, a convention many APIs now copy.
RateLimit header fields draft
An IETF working group has been drafting standard RateLimit header fields, so that clients and libraries can understand quota information the same way across services.
Interview angle
Six questions, each worth 20 XP. Good answers cover accuracy, latency and failure behaviour.
State where it runs, how it counts, how it degrades.
Why is GET-then-SET wrong for a shared counter?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
A better design degrades gracefully: each limiter node falls back to local in-memory counters with per-caller limits, less accurate than the shared store but still separating a flood from ordinary users. Add a short timeout on the store call (a slow limiter is as bad as a dead one), a so you stop calling a failing store, and an alert. And test the failure on purpose.
Backend capacity 5,000 req/s, 3,000 legitimate plus 12,000 abusive: fail open puts 15,000 on the backend (3× overload, only a third of users served); fail closed serves nobody; a local fallback that lets 10% of abuse through puts 4,200 on it and serves everyone.
With fail-open the backend receives 15,000 requests a second against a capacity of 5,000 (300%). 33% of legitimate users are served; 1.2M legitimate requests are lost in 10 minutes.
Arithmetic: overload is shared proportionally across all requests, so legitimate service falls with the overload factor. In reality, overloaded systems often collapse faster than this.
Where to go next