Design a rate limiter

Limit requests per user/IP/route. Common warm-up design question and a foundation of every production API.

What "rate limiting" actually means

Rate limiting is the practice of restricting how many actions a single client may perform in a given time window. The "client" is whatever identity you decide to count by — a logged-in user, an API key, a source IP address, or a specific endpoint. The "action" is usually an HTTP request, but it could be anything: messages sent, emails dispatched, dollars spent. A rate limit is normally written as N per window, e.g. "100 requests per minute per API key."

A closely related word is throttling. People use the two loosely, but the useful distinction is: rate limiting typically means reject the excess (return an error and let the client retry later), while throttling often means slow down the excess (delay or queue it so it trickles through at the allowed pace). A rate limiter that drops over-limit traffic and a throttle that buffers it are two ends of the same idea — the leaky bucket below is the buffering kind.

When you reject, the standard signal is HTTP 429 "Too Many Requests". It tells the caller "you are healthy, the server is fine, but you have exceeded your share — back off." Polite servers add a Retry-After header saying how many seconds to wait, so a well-behaved client can pause exactly long enough instead of hammering blindly.

The four algorithms, in depth

Below is the same shortlist the interview answer uses, but with each algorithm explained from scratch: how it works, where it shines, and where it breaks. The collapsible summary further down keeps the original one-liners; this section is the long form.

1 · Fixed window

Chop time into fixed buckets — say every clock minute, 12:00:00–12:00:59, then 12:01:00–12:01:59. Keep one integer counter per client per bucket. On each request, increment the counter; if it exceeds the limit N, reject with 429. When the clock ticks into the next minute, the counter resets to zero.

Pros: trivially simple, one integer of memory per client, O(1) per request. Cons: the boundary burst. Because the counter snaps back to zero at the edge, a user can fire N requests in the last second of one window and N more in the first second of the next — 2N requests in a ~2-second span, double the intended rate. For loose limits that is fine; for tight ones it is a real leak.

2 · Sliding window log

Store the timestamp of every request in a list (the "log") per client. On each new request, drop all timestamps older than the window (e.g. older than 60 seconds ago), then count what remains; if that count is below N, accept and append the new timestamp, otherwise reject.

Pros: perfectly accurate — the window truly slides, so there is no boundary burst at all. Cons: memory grows with traffic. A client doing 1,000 req/min costs 1,000 stored timestamps, every minute, for every client. At scale that is expensive in both storage and the per-request work of pruning the log.

3 · Sliding window counter

A clever compromise that keeps fixed-window's tiny memory but smooths its boundary. Keep just two counters: the current window's count and the previous window's count. Then estimate the rolling count as a weighted blend — weight the previous window by how much of it still overlaps the rolling window. If you are 25% of the way into the current minute, the formula is roughly current + previous × 0.75. Compare that estimate to N.

Pros: O(1) memory (two numbers), no hard boundary burst, and the estimate is accurate enough for almost all real traffic. Cons: it is an approximation that assumes requests were spread evenly across the previous window; a pathological spike can be slightly mis-estimated. In practice this is the algorithm many production limiters (and CDNs) actually ship.

4 · Token bucket (the one to know)

Covered in full in the plain-English walkthrough above. To restate it precisely: a bucket holds at most B tokens (capacity = allowed burst). Tokens are added at R per second, capped at B. Each request consumes one token; if none are available, reject. Refills are computed lazily — on each request you add (now − last_refill_ts) × R tokens and cap at B, so no background timer is needed.

Pros: O(1) time and just two numbers of memory per client; naturally allows controlled bursts up to B while pinning the long-run average to R; the parameters R and B map cleanly onto product requirements. Cons: needs a careful atomic update (the read-modify-write race), and choosing B trades burst-friendliness against how much overshoot you tolerate.

A fully traced token-bucket run

The visual above shows the idea; here is the arithmetic spelled out request by request so you can see the lazy refill formula fire. Same parameters as the walkthrough — capacity B = 3, rate R = 1 token/sec — but now tracking the exact stored values tokens and last (the last-refill timestamp). The core line each time is tokens = min(tokens + (now − last) × R, B).

# State: tokens (float), last (timestamp of last update). Start full.
# B = 3, R = 1 token/sec

# t=0.0  new user            tokens=3.0  last=0.0
# req @ t=0.0  refill: min(3.0 + (0.0-0.0)*1, 3) = 3.0  >=1 -> ALLOW, spend 1 -> tokens=2.0
# req @ t=0.0  refill: min(2.0 + 0*1, 3)        = 2.0  >=1 -> ALLOW, spend 1 -> tokens=1.0
# req @ t=0.0  refill: min(1.0 + 0*1, 3)        = 1.0  >=1 -> ALLOW, spend 1 -> tokens=0.0 (burst of B=3 used)
# req @ t=0.0  refill: min(0.0 + 0*1, 3)        = 0.0  <1  -> REJECT 429, state unchanged
# req @ t=2.0  refill: min(0.0 + (2.0-0.0)*1, 3)= 2.0  >=1 -> ALLOW, spend 1 -> tokens=1.0, last=2.0
# req @ t=10.0 refill: min(1.0 + (10.0-2.0)*1,3)= 3.0  >=1 -> ALLOW, spend 1 -> tokens=2.0  (capped at B, the long gap did NOT bank 9 tokens)

Two things to notice. First, the min(..., B) cap is what stops a client who went quiet for an hour from accumulating thousands of tokens and then unleashing them all at once — the bucket can never hold more than B. Second, every step is pure arithmetic on two stored numbers; there is no list to scan and no background process. That is why token bucket is O(1) in both time and memory per client.

# Per user/IP, stored in Redis as a hash
key = f"rl:{user_id}"
# Redis fields: tokens (float), last_refill_ts (float)
def allow(user_id, now):
    tokens, last = redis.hmget(key, "tokens", "ts")
    tokens = (tokens or CAPACITY) + (now - last) * RATE
    tokens = min(tokens, CAPACITY)
    if tokens >= 1:
        tokens -= 1
        redis.hmset(key, {"tokens": tokens, "ts": now})
        return True
    return False

Where to enforce it: gateway vs service

Independent of the algorithm, you must decide where in the request path the check runs. The two common homes:

The usual real-world answer is both: a coarse global limit at the gateway to absorb floods cheaply, plus targeted limits inside services for sensitive actions. In the interview, name the gateway as the default and mention service-level limits for business rules.

Distributed rate limiting

A single server can keep its counters in local memory. But real systems run many app servers behind a load balancer, and a user's requests may land on any of them. If each server kept its own private counter, a "100/min" limit across 10 servers would effectively become 1,000/min — the limit leaks by the fan-out factor. The fix is distributed rate limiting: every server reads and writes the same counter in a shared store, so they all see one consistent view.

That shared store is almost always Redis — an in-memory key-value database fast enough to sit in the hot path (sub-millisecond reads/writes) and equipped with two features rate limiters need: per-key TTL (time-to-live, so stale counters expire automatically) and atomic scripting via Lua. Each app server, on every request, calls Redis to do the token-bucket check against the shared key.

Pitfalls to name

• Clock skew. The lazy refill relies on timestamps. If different servers' clocks disagree, (now − last) can go negative or balloon, granting or denying tokens wrongly. Fix: compute time using the shared store's clock (e.g. Redis's TIME) rather than each app server's local clock.
• Burst at window edges. The fixed-window boundary burst — 2N requests across two adjacent windows. If a strict cap matters, prefer sliding-window-counter or token bucket, which do not snap to zero at a boundary.
• Distributed consistency. Replicated counters lag, so a hard "never exceed N" guarantee is hard to keep under failover. Decide up front whether your limit is a safety guard (loose is fine) or a correctness invariant (needs strict serialization).
• Fail-open vs fail-closed. If Redis is unreachable, do you allow all requests (fail-open: stay available, lose protection) or block them (fail-closed: stay protected, risk an outage)? Most public APIs fail-open for resilience; pick deliberately and say so.
• Choosing the limit key. Per-IP buckets punish whole offices/NATs sharing one address; per-user needs auth and can be gamed by creating accounts. State your key and its trade-off.