Design a distributed rate limiter
What interviewers are testing
Rate limiting looks like a simple counter until it becomes distributed. Interviewers probe the algorithmic trade-offs — fixed versus sliding windows, token versus leaky buckets — and then the correctness trap: two servers reading the same token before either writes. Candidates who reach for an atomic shared operation, and who design a clean 429 contract, stand out from those who only sketch an in-memory counter.
Mental model
At its core a limiter answers one atomic question: does this key have budget left? The token bucket is the usual choice because it allows bursts up to capacity while enforcing the refill rate on average. In a distributed system the bucket lives in a shared store, and the read-refill-decrement happens in one atomic step so concurrent servers cannot double-spend.
Step-by-step solution
Step 1 of 5
Compare four rate limiters
Four standard algorithms fit different goals. Fixed window counts requests per interval: trivial and memory-light, but bursts at a window boundary can pass twice the limit because the counter resets. Sliding window counter interpolates the previous window count, smoothing boundaries at almost no extra memory, while a full sliding-window log is exact but stores every timestamp. Token bucket holds up to C tokens and refills at R tokens per second; each request costs one token, so steady traffic is limited to R while short bursts up to C are allowed — the best fit for public APIs. Leaky bucket is the mirror image: requests enter a queue and drain at a constant rate, which smooths output but adds queueing latency. Watch the animation compare their shapes: the fixed window boundary spike, the smoothed sliding edge, the bucket burst then cap, and the leaky bucket steady drip. Choose based on whether you are protecting a backend or shaping traffic.
Animation — Compare four rate limiters
count / interval
blended count
C tokens, refill R
drain at fixed rate
A request arrives and needs a limiting policy.
Edge cases & traps
- Distributed races double the effective limit: make check-and-decrement atomic with a Redis Lua script or a single atomic operation, never a GET followed by a SET.
- Fixed windows allow twice the limit at boundaries: use a sliding window counter or a token bucket that enforces a sustained refill rate.
- A limiter outage must not take down the API: fail open by default or fail closed on security-sensitive routes, and fall back to a local in-memory limiter meanwhile.
- Per-IP limiting punishes users behind a shared NAT: prefer API keys or user ids when available and treat IP as a fallback dimension only.
- Clients retrying immediately after 429 create a thundering herd: return Retry-After and require jittered exponential backoff.