If you get "design a rate limiter" in a system design interview, the interviewer is testing one thing above all: do you understand the tradeoffs between the standard algorithms, and can you reason about where each one breaks under real traffic. There are five algorithms worth knowing (token bucket, leaky bucket, fixed window counter, sliding window log, sliding window counter), and the strongest answers spend most of their time on failure modes and the distributed setup, not on drawing a bucket. We run these mocks all day, and the candidates who stall are almost always the ones who memorized one algorithm and can't pivot when the follow-up hits.
Here is how to cover the whole space in a way that survives probing.
The five algorithms you must know
Start by clarifying requirements out loud: what's the limit (requests per user, per IP, per API key), what's the time granularity, do you need to allow bursts, and is this single-node or distributed. Then walk the options. A quick map before the details:
| Algorithm | Allows bursts | Memory per key | Accuracy | Common use |
|---|---|---|---|---|
| Token bucket | Yes (up to bucket size) | O(1) | Good | API quotas (Stripe) |
| Leaky bucket | No (smooths output) | O(1) + queue | Good | Traffic shaping (Shopify) |
| Fixed window counter | Yes (at edges) | O(1) | Poor at boundaries | Simple quotas |
| Sliding window log | Yes | O(requests) | Exact | Low-volume, high-precision |
| Sliding window counter | Partial | O(1) | Approximate | High volume (Cloudflare-style) |
Token bucket
A bucket holds up to N tokens and refills at a fixed rate (say 10 tokens per second). Each request removes one token; if the bucket is empty, the request is rejected or queued. This is the default answer for most API rate limiting because it allows short bursts (up to the bucket capacity) while enforcing a steady average rate. It's cheap: you store two numbers per key, the current token count and the last refill timestamp, and compute the refill lazily on each request.
Leaky bucket
Requests enter a FIFO queue and drain at a constant rate, like water leaking from a bucket with a hole. If the queue is full, new requests spill over and get dropped. The key difference from token bucket: leaky bucket enforces a smooth, constant outflow and does not allow bursts to pass through to the backend. That makes it great for protecting a downstream service that hates spikes, but it adds latency because requests wait in the queue, and it needs somewhere to hold that queue.
Fixed window counter
Divide time into fixed windows (for example, per minute) and keep a counter per key per window. Increment on each request, reject when the counter exceeds the limit, reset when the window rolls over. It's trivial to implement with a single Redis INCR plus a TTL. The problem is the boundary, which we cover below.
Sliding window log
Store a timestamp for every request in a sorted structure. On each new request, drop timestamps older than the window and count what remains. This is exact: no boundary artifacts, no approximation. The cost is memory and write volume, because you store one entry per request and prune constantly. It falls apart at high request rates where a single hot key can accumulate millions of timestamps.
Sliding window counter
A hybrid that fixes the fixed-window boundary problem without storing every timestamp. You keep counters for the current and previous window, then estimate the rate using a weighted blend based on how far into the current window you are. For example, 30 seconds into the current minute, you count all of the current window plus roughly 50 percent of the previous window's count. It's O(1) memory and close enough for production traffic, which is why it's popular at scale.
Where each one fails (the part interviewers probe)
This is where interviews are won or lost. Naming the algorithm is table stakes; predicting the failure is the signal.
Fixed window boundary burst. This is the classic gotcha, and a good interviewer will draw it out. With a limit of 100 per minute, a client can send 100 requests in the last second of one window and 100 in the first second of the next. That's 200 requests in a two-second span while never violating the per-window count. If you propose fixed window, volunteer this failure before you're asked, then offer sliding window counter as the fix.
Leaky bucket adds latency and drops under sustained load. Because it drains at a constant rate, a legitimate burst gets queued rather than served immediately, which hurts tail latency. And if input consistently exceeds the drain rate, the queue fills and you drop requests that a token bucket would have absorbed. It also raises the question of where the queue lives and what happens when that store fails.
Sliding window log does not scale. Storing every request timestamp is fine for a low-volume, high-value endpoint (think login or password reset), but for a hot API key doing thousands of requests per second, the memory and the prune operations become the bottleneck. Say this explicitly rather than proposing it as a general-purpose default.
Token bucket burst can overwhelm a fragile backend. The same burst tolerance that makes token bucket pleasant for clients can let a full bucket dump N requests at once onto a service that can't take it. If protecting the downstream is the goal, leaky bucket or a smaller bucket is the better call. The right answer depends on whether you're protecting the server or being fair to clients, and strong candidates ask which.
Sliding window counter is an approximation. The weighted estimate assumes requests were spread evenly across the previous window, which isn't always true. It can allow slightly more or fewer requests than the exact limit. For most systems that error is acceptable, but if you're billing customers per request or enforcing a hard contractual cap, name the tradeoff.
Making it distributed (the real interview)
A single-node limiter with a local hash map is easy. The interesting version runs across many API servers, and the follow-up is always some version of "now you have 50 app servers, how do they share state?"
The standard answer is a centralized store, usually Redis, holding the counters or tokens. That immediately creates a race condition: if two servers do GET, then compute, then SET, they can both read the same count and both allow a request that should have been rejected. The fixes worth naming:
- Atomic operations.
INCRwith anEXPIREhandles fixed window cleanly because the increment is atomic. - Lua scripts. For token bucket or sliding window, wrap the read-modify-write in a Lua script so Redis executes it atomically as one round trip.
- Sorted sets for sliding window log. Use
ZADDto record timestamps andZREMRANGEBYSCOREto prune, thenZCARDto count.
Then raise the failure modes yourself: Redis latency now sits in the request path, so decide whether the limiter fails open (allow on Redis outage, favor availability) or fails closed (reject, favor protection). Discuss reducing chattiness with local token batching, where each node checks out a block of tokens at once to cut Redis calls, at the cost of slightly looser global accuracy. Stripe's well-known writeup on scaling their API with rate limiters is a good reference point here: they run a token bucket in Redis and layer multiple limiter types (request rate, concurrent requests, and load shedders) rather than relying on one.
How to structure your answer in the interview
Spend your first two minutes on requirements and units, then propose token bucket as a sane default and explain why. Move quickly to the boundary failure of fixed window and the memory failure of sliding window log to show range. Reserve the back half for the distributed store, the race condition, and the fail-open versus fail-closed decision. That arc demonstrates exactly the judgment interviewers score.
Rate limiter design also pairs naturally with a stateful coding round, and the reasoning transfers. Firms like SIG mix system design discussion with implementation problems such as "Design Memory Allocator," which tests the same skill of maintaining correct state under a stream of operations. You can drill both the design reasoning and the implementation muscle on our practice questions, and browse related building blocks like hash tables and simulation problems that show up in these rounds.
FAQ
Which rate limiting algorithm should I recommend by default?
Token bucket for most API rate limiting, because it enforces an average rate while tolerating short bursts and costs O(1) memory per key. Switch to leaky bucket when the priority is protecting a fragile downstream with smooth output, and to sliding window counter when you need to eliminate fixed-window boundary bursts at high volume.
What is the fixed window boundary problem?
With a per-minute counter, a client can send a full limit's worth of requests at the end of one window and another full limit at the start of the next, doubling the effective rate over the two-second boundary. Sliding window log or sliding window counter fixes it by considering a rolling time range instead of discrete resets.
How do you make a rate limiter work across many servers?
Move the state to a shared store like Redis and use atomic operations so concurrent servers can't both read a stale count and over-admit. Use INCR with EXPIRE for fixed window, or wrap token bucket and sliding window logic in a Lua script to make the read-modify-write atomic in a single round trip.
Should a distributed rate limiter fail open or fail closed?
It depends on what you value more. Fail open (allow requests when the store is down) preserves availability but removes protection, while fail closed (reject) protects the backend but can cause an outage if Redis blips. State the choice explicitly in the interview and tie it to the system's priorities.