Design a Rate Limiter: Algorithms, Trade-offs and the Distributed Version

"Design a rate limiter" is one of the most common system design questions because it's small enough to finish and deep enough to separate levels. A junior answer picks an algorithm. A senior answer explains what happens when the limiter runs on fifty servers and Redis is slow.

Clarify first

  • What is limited? Requests per user, per API key, per IP, or per endpoint.
  • Where does it run? In the API gateway, as a library in each service, or as a separate service.
  • Hard or soft limit? Must request 101 always be rejected, or is a small overshoot acceptable?
  • What does the client see? Usually HTTP 429 with a Retry-After header.
  • Scale: how many clients, and how many requests per second in total?

The five algorithms

AlgorithmHow it worksStrengthsWeaknesses
Token bucketA bucket holds up to N tokens and refills at R per second; each request takes oneAllows short bursts up to N, smooth average; two numbers of state per keyBurst size needs tuning
Leaky bucketRequests join a queue drained at a fixed ratePerfectly smooth outputAdds latency; bursts wait or get dropped
Fixed windowCount requests per key per calendar window (e.g. per minute)Simplest; one counter per keyUp to 2x the limit across a window boundary
Sliding window logStore a timestamp per request; count those in the last windowExactMemory grows with the limit
Sliding window counterWeight the previous window's count by how much of it overlaps the sliding windowClose to exact with two countersAn approximation

The fixed-window boundary problem, concretely: with a limit of 100 per minute, a client can send 100 requests at 12:00:59 and another 100 at 12:01:00, which is 200 requests in two seconds, and both windows say "allowed".

Sliding window counter, concretely: limit 100 per minute. The previous minute had 80 requests, the current minute so far has 30, and we're 25% into the current minute. The estimate is 30 + 80 × 0.75 = 90, which is under 100, so the request is allowed.

For most APIs, token bucket is the default answer: it allows reasonable bursts, keeps little state, and is easy to explain.

Token bucket in a few lines

Store two values per key: tokens and last_refill. On each request:

elapsed = now - last_refill
tokens = min(capacity, tokens + elapsed * rate)
last_refill = now
if tokens >= 1:
    tokens -= 1
    allow
else:
    reject with 429 and Retry-After = (1 - tokens) / rate seconds

Forgetting to update last_refill is a classic bug: the bucket then refills from the original timestamp on every call and never drains.

Making it distributed

With one server, state lives in memory. With many servers behind a load balancer, a client's requests land on different machines, so the counts have to be shared.

Centralised store (usually Redis):

  • Fixed window: INCR key and set an expiry on the first increment. Simple and atomic.
  • Token bucket or sliding window: the read-modify-write must be atomic, otherwise two servers read "1 token left" at the same time and both allow. Run the logic in a Lua script, which Redis executes atomically.
  • Key design: rl:{apiKey}:{endpoint}, with an expiry so idle keys disappear.

Costs and how to handle them:

  • Latency: every request now makes a network call. Keep the store close (same region) and the operation to a single round trip.
  • Hot keys: one huge customer hammers one Redis key. Shard by key and consider local pre-aggregation.
  • Store failure: decide between fail open (allow traffic, risk overload) and fail closed (reject traffic, risk an outage of your own making). Most public APIs fail open with a conservative local limit as a backstop.

Hybrid approach for very high scale: each server enforces a local limit of (global limit ÷ number of servers) in memory and syncs with the central store periodically. It's cheaper, slightly less exact, and a good trade-off to mention.

What to return to clients

  • 429 Too Many Requests when rejected.
  • Retry-After with the number of seconds to wait.
  • Optionally headers showing the limit and the remaining quota, so well-behaved clients can slow down before they hit it.

What interviewers push on

  1. "Two requests arrive at the same instant on different servers. What happens?" (Atomicity.)
  2. "Redis is down. What now?" (Fail open versus fail closed.)
  3. "Different limits for free and paid customers?" (Look up the rule per key; cache the rules.)
  4. "How do you limit by IP when many users share one NAT address?" (Prefer authenticated keys; treat IP limits as a coarse outer layer.)
  5. "How do you test it?" (Inject the clock, so time can be controlled in tests.)

Practise it both ways. Prepd has the rate limiter as a system design question (the distributed service) and as an LLD question (the classes and the algorithm), each broken into steps with written feedback.

Practise it