TL;DR: Default to token bucket because it makes burst tolerance an explicit, tunable parameter; the failure that motivates the whole question is the fixed-window boundary burst that lets 2x your limit through. Make the check-and-decrement atomic in Redis so it can't race across servers.
How to approach it
Walk through the algorithms in order of sophistication, and for each one name the specific failure mode that motivates the next. This question is often the conceptual twin of a coding round (rate limiters are a live OpenAI/Anthropic coding prompt), so showing you understand the boundary behavior (not just the happy path) is what differentiates.
A strong answer
Fixed window counts requests per discrete interval ("100 per minute, resetting at :00"). One counter per key, trivially cheap. The break is the boundary burst. A client sends 100 requests at 11:59:59 and 100 more at 12:00:01: 200 requests in two seconds, all "legal." For any limit meant to protect downstream capacity, that's a 2x violation.
Sliding window log stores a timestamp per request and counts how many fall in the trailing window. Exact, with no boundary problem, but memory is O(requests) per key and painful at scale. The practical compromise is the sliding window counter: weight the previous fixed window's count by its overlap with the trailing window (e.g., 30s into the current minute, count = current + 0.5 × previous). Approximate, but smooth, and one or two counters per key.
Work the counter once so the approximation is concrete. Limit 100/minute; the previous minute saw 80 requests; we are 30 seconds into the current minute with 40 so far. The trailing 60-second window overlaps half of the previous minute, so the estimate is 40 + 0.5 x 80 = 80, under the limit, allow. The assumption doing the work is that the previous window's requests were evenly spread; a client that actually sent all 80 in the last second of the previous minute is under-counted for a while. That is the precision you gave up relative to the log, and it is usually a fine trade, but say it out loud in an interview: naming what an approximation assumes is worth more than the formula.
Token bucket is a bucket of capacity B that refills at R tokens/second; each request spends a token. This is usually the right default because it makes burst tolerance an explicit, tunable parameter: sustained rate R, burst up to B. It also degrades gracefully, because a client that's been idle can legitimately burst, which matches real traffic. (Leaky bucket is the same math enforcing smooth output instead.)
Choosing B and R is where this stops being a textbook question and becomes deployment work, and the two numbers come from different owners. R comes from the protected resource: if the downstream service holds up at 500 requests/second, the sum of all buckets' refill rates has to respect that, with headroom. B comes from observing legitimate clients: if the customer's dashboard fires 12 parallel calls on page load, a bucket smaller than 12 rate-limits their normal render and generates a support ticket that looks like an outage. So you set B from the p99 burst of well-behaved traffic and R from capacity math, and when the two collide (many clients, each wanting a large burst, small downstream), that collision is a capacity conversation with the customer, not a constant to tune quietly.
Production details that read senior: implement it in Redis with atomic ops or a Lua script so check-and-decrement can't race across app servers; return 429 with a Retry-After header and X-RateLimit-Remaining so clients can back off intelligently rather than thundering-herd you; and decide consciously what happens when Redis is down. Fail open (protect availability) or fail closed (protect the downstream) is a business decision, not a technical one.
The four algorithms side by side:
| Algorithm | Burst behavior | Memory/complexity | Best for |
|---|---|---|---|
| Fixed window | Boundary burst lets 2x through | One counter per key, trivially cheap | Cheap counts where the boundary burst is tolerable |
| Sliding window log | Exact, no boundary problem | O(requests) per key, painful at scale | Exactness when request volume per key is low |
| Sliding window counter | Approximate but smooth | One or two counters per key | Smooth limiting at scale |
| Token bucket | Tunable burst up to B, sustained rate R | Bucket state per key | Default; explicit burst tolerance, degrades gracefully |
What interviewers probe next
- "How do you rate limit across multiple API servers?" Centralized counter (Redis) for accuracy, or local counters with periodic sync if you can tolerate slop; name the tradeoff.
- "LLM APIs limit tokens per minute, not requests. Does your design survive?" Token bucket generalizes: spend N tokens per request instead of 1; estimate before the call, reconcile after.
- "What does the client experience and how do you make 429s debuggable?" Headers, documented retry semantics, and a dashboard the customer can see.
Common mistakes
Reciting all the algorithms but unable to say why anyone moved past fixed window: the boundary burst is the whole point of the question. Forgetting rate limiting is per-key (per API key, per user, per IP) and designing a single global counter. Ignoring the distributed problem entirely, as if one process serves all traffic. And describing the server side perfectly while having nothing to say about what the rate-limited client should do. As an FDE, you'll spend more time on the client side of someone else's 429s than on the server side of your own.
Key takeaways
- Token bucket is the default: sustained rate R with explicit burst capacity B.
- Fixed window's boundary burst lets 2x through; that failure is why the question exists.
- One atomic Redis Lua script for check-and-decrement, never GET-then-SET (it races).
- For LLM limits, spend N tokens per request, not 1, and reconcile actual usage after the call.