Design rate limiter
Four algorithms, one interface — and the interviewer wants to know which you'd pick.
standard · 45 minutes · 7 classes
Requirements
- Decide whether a request from a given key may proceed, right now.
- Limits configured per key — per user, per IP, per API token.
- Support more than one algorithm behind a single interface.
- Thread-safe: many requests for one key arrive concurrently.
- Tell a rejected caller when to retry.
Say these are out of scope
- Distributed coordination across nodes — call it out, then design single-node first.
- Persisting counters across restarts.
- Billing or quota accounting.
A shape that works
One reasonable decomposition, not the only one. What matters in the round is that you can defend the boundaries you drew.
What they'll push on
Fixed window, sliding log, or token bucket?
Fixed window is cheapest and wrong at the edges — 100/minute allows 200 across a window boundary. Sliding log is exact and costs memory proportional to the requests in the window. Token bucket allows controlled bursts and is O(1) in memory, which is why it's the usual production answer. Name the boundary-burst flaw in fixed window unprompted; it's the thing being checked.
Why inject a Clock?
Because otherwise the tests have to sleep. Every one of these algorithms is a function of time, so a fake clock turns a flaky ten-second test into a deterministic one. It's also the cheapest possible demonstration that you design for testability.
Now run it on twenty servers.
Per-node counters mean the real limit is twenty times what you configured. The options are a shared store (Redis with an atomic increment or a Lua script for the token bucket), which costs a network hop per request, or a per-node budget of 1/N, which is simple but wastes headroom when traffic is uneven. Say which you'd pick and why — there's no free answer.