Your interviewer writes "design a rate limiter" and waits for you to start. Start with the algorithm. The wording of the limit tells you which one. If the limit is a sustained rate with a burst allowance, use a token bucket. If it is a count over a fixed window, like 100 requests per minute, use a sliding window counter. If the goal is to protect a slow downstream at a constant output rate, use a leaky bucket. State that choice in your first minute. The rest of the round follows from it, with two calls doing most of the work: where the limiter's state lives, and what you give up when the shared state goes slow.
Pick the algorithm from the wording of the limit
Each algorithm keeps different state and admits different bursts. The table is the decision rule you will say out loud, and the paragraphs below show the arithmetic for each algorithm.
| Algorithm | State per client | Burst behavior | Pick it when |
|---|---|---|---|
| Fixed window counter | One count per window | Hard stop at the window edge; up to twice the limit across a boundary | The limit is coarse and a boundary burst is acceptable |
| Sliding window log | A timestamp per request | Exact at every instant | You need per-request accuracy and the total volume is modest |
| Sliding window counter | Two counts, current and previous window | Smooths the boundary, approximately | The limit is stated as X per fixed window |
| Token bucket | Token count and last refill time | Admits a burst up to the bucket size | The limit is a sustained rate and a short burst should be legal |
| Leaky bucket | Queue length | Constant output; overflow is rejected | The downstream needs a smoothed, steady rate |
Token bucket. It is the default for an API limit. Keep a bucket of B tokens per client and refill it at R tokens per second. An allowed request takes one token, and a request that finds an empty bucket is rejected. Set R to the sustained rate and B to the burst you want to admit. For 5 requests per second with a burst of 10, R is 5 and B is 10. A client can fire all 10 requests in the first second and then hold 5 per second. The state is two numbers per client, and the check is one comparison, which is why it stays cheap at high volume.
Production rate limiters make the same choice. Amazon API Gateway throttles each account and route with the token bucket algorithm. The throttle rate is the requests per second at which tokens are added, the burst is the bucket capacity, and clients receive a 429 when the steady-state rate and the burst are both exceeded (Amazon API Gateway, HTTP API throttling). Microsoft's .NET rate limiting middleware ships the same three policies, a fixed window, a sliding window, and a token bucket, and partitions limits per tenant (ASP.NET Core rate limiting middleware).
Sliding window counter. It keeps two counts per client, the current window and the previous one, and weights the previous count by the fraction of it still inside the trailing window. With a limit of 7 per minute, 4 requests in the previous minute, 2 in the current, and 15 seconds elapsed in the current minute, the trailing one-minute window still covers 45 seconds of the previous minute, so the weight is 45/60, or 0.75. The estimate is 2 + (4 × 0.75) = 5. That is under 7, so the request is allowed. The catch is that it assumes requests spread evenly across the previous window, so it is an approximation. Bunching at the end of the previous window leaves the requests inside the trailing window, so the true count is higher than the estimate, an undercount. Bunching at the start leaves the requests outside it, so the true count is lower, an overcount. The undercount is the direction to watch when the limit is a ceiling, because the limiter sees a lower count and admits requests the true count would reject.
Sliding window log. It stores a timestamp for every request and, on each new request, drops the entries older than the window and counts what is left. With a limit of 3 per minute, a client with requests at 0:40, 1:10, and 1:11 is at the limit at 1:11, because the one-minute window ending at 1:11 holds all three. A fourth request at 1:12 sees four entries in its window and is rejected. A fixed window would allow that fourth request, because the 1:00-1:59 window alone holds only two so far. The cost is one timestamp per request. At 1,000,000 requests per second system-wide, that is a million new entries per second, so pick the log when the total volume is modest and exactness is the requirement.
Leaky bucket. It keeps a queue per client of length Q and drains it at a fixed rate D. Arrivals are enqueued up to Q, and anything beyond is rejected. The output is constant at D regardless of how bursty the input is, which is what a slow downstream, say a batch processor that takes 10 jobs per second, wants. The price is that a request waits whenever the queue is non-empty. If a client sends faster than the drain rate D, the queue builds and later requests wait longer, while light traffic passes with little wait. The queue is memory you pay for. A token bucket admits the burst and then throttles. A leaky bucket smooths the whole stream.
Fixed window. It divides time into windows, say per minute, keeps one count per client per window, rejects when the count hits the limit, and resets at the boundary. It is one integer per client, the cheapest state of the five. The failure mode is the boundary burst. With a limit of 100 per minute, a client can send 100 requests from 0:55 to 0:59 and another 100 from 1:00 to 1:04, for 200 requests in 10 seconds. Accept that when the limit is a soft protection, and move to a sliding window when it is a billing boundary.
Say the pick out loud, tied to the wording. "The limit is a sustained rate and clients batch, so a token bucket with a burst of 10." If the interviewer restates the limit as "100 requests per minute, and it must hold across the boundary," you switch to a sliding window counter and say why.
Where the limiter sits
Placement decides what context the limiter sees and how much latency it adds to every request.
At the edge (CDN, WAF, gateway). Every request is checked before it reaches your servers. The limiter sees only what is in the HTTP request, an IP, a path, headers, an API key. It is fast and it protects the whole fleet, but it cannot see plan tiers or account state. It also has a detection delay when it works by threshold. AWS WAF rate-based rules act on groups of requests that arrive at too high a rate, and the mitigation lag is typically 30-50 seconds, up to several minutes (AWS WAF, options for rate limiting). An edge rule stops sustained abuse. It does not enforce a per-request limit in time, so it complements a per-request check rather than replacing one.
As a dedicated service. An app server asks the limiter "allow user 123?" and gets a yes or no. The limiter has full context, plan tier, account state, business rules, and it keeps one global state. The price is a network round trip on every request. On a 5 ms check budget, a same-region store round trip of 1-5 ms (a planning number) leaves little for the rest of the path, which is the argument for keeping the check close to the edge.
In the app. The limiter runs inside each app instance and checks local in-memory counters. Zero network cost. Each instance sees only its own traffic, which is the distributed problem the next two sections handle.
A defensible answer puts each limit where its context lives. A coarse per-IP limit at the edge, the per-user limit at the gateway or in the app where the user identity is resolved, and shared state if the limit has to be exact. Say why each limit sits where it does, and what the tradeoff buys.
State the assumptions, then work the numbers
State the assumptions out loud, since the interviewer may push any of them. Assume 10 billion requests per day, 100 million active clients, a limit of 100 requests per minute per client, and a latency budget of 5 ms per check.
- Average rate. 10 billion / 86,400 is about 115,000 requests per second. Plan for a peak of 1,000,000 requests per second, roughly nine times the average.
- State size. 100 million clients at 100 bytes each (token count, last refill, window data) is 10^10 bytes, 10 GB. That fits in a small Redis cluster.
- Work per request. One check is a read of the state and a write back, 2 operations. At the peak, 2,000,000 operations per second. A single in-memory node cannot absorb that. Assume a node sustains 100,000 operations per second (a planning number, not a service guarantee), and the shard count is 2,000,000 / 100,000 = 20.
- Sharding. Partition by client ID with consistent hashing, so a client's state always lands on the same shard. Each shard runs one read-write primary and read-only replicas (Amazon ElastiCache, clusters). In a Multi-AZ cluster with replicas, the primary fails over to a read replica when the primary node fails (Amazon ElastiCache, high availability using replication groups).
- The check path. The gateway identifies the client, the user ID from the auth token, or the IP when the request is anonymous. It sends the client key to its shard, and a Redis Lua script does the whole decision. Refill the bucket from the elapsed time, compare tokens to zero, decrement, return allow or reject. The script runs as one atomic unit, so two concurrent requests for the same client cannot both read the same token count and both decrement (Amazon ElastiCache, Lua scripts).
- Why not read then write. If the read and the write are separate round trips, two requests can both read 1 token, both pass, and both decrement, and the limit is exceeded by one. Moving the read-modify-write into one atomic script closes that race.
- The 429 contract. Reject with a 429 Too Many Requests, and include a Retry-After header with the interval when you can compute it. Microsoft Graph's throttling guidance gives the client-side half of the contract. Wait the interval the Retry-After header gives, and fall back to exponential backoff when the header is absent (Microsoft Graph, throttling and throttling limits).
Here is the whole design at a glance, from the client to the shards.
And here is one request's path through the check.
Expect the interviewer to push on four points, in this order. Why not keep the counters in the app? The next section opens with the overcount that local counters cause. Why a token bucket? The limit is a sustained rate with a burst, and that wording points to it. What if a shard goes down? The next section ends with the failure mode. Where did the 20 shards come from? That is the arithmetic above.
Local state versus shared state
Pick between local counters and a shared store.
Option A, local counters. Each app instance keeps its own per-client counters in memory. The check is the fastest in this design, there is no dependency, and there is nothing to shard. The cost is accuracy. With N instances and a limit of L, a single client spread across the instances can send up to N × L in a window. Five instances, a limit of 100 per minute, a client round-robin across all five, and the ceiling is 500, not 100. Use local state when the limit is a soft, best-effort protection. AWS API Gateway says its throttles are best-effort targets, not guaranteed request ceilings (Amazon API Gateway, request throttling). A production system runs that way. If the limit is soft, say so out loud.
Option B, shared state. All instances read and write one store. The global limit holds exactly, and the price is a round trip per check and a shared dependency that is the bottleneck and the single point of failure. At 2,000,000 operations per second you shard (the 20 shards above). Each shard is a primary with replicas, so a lost primary fails over to a replica, but the shard still needs capacity headroom for the burst, and a full shard outage still costs you the check.
The tension, stated out loud. You have three properties. A strict global count (accuracy), a check under 5 ms (latency), and a limiter that keeps working when the store is slow (availability). You cannot hold all three at once in this tradeoff. The shared counter buys accuracy and spends latency and availability. Local state buys latency and availability and spends accuracy. Pick two, say which one you are giving up, and name the requirement that would flip the pick. A billing boundary flips to the shared counter. A consumer API that must stay up flips to local state with the overcount disclosed.
The failure mode. If the store is unreachable, either fail open, let the request through and stop enforcing until the store returns, or fail closed, reject everything and take the API down with the store. The requirement picks it. A billing or fraud boundary leans fail closed, because an unlimited window is worse than a short outage. Consumer availability leans fail open, because the limiter is not the only line of defense. State the pick and the condition that would flip it.
What a weak answer sounds like
- "Store the counters in Redis," with no reason why the state has to be shared, no atomic check, and no answer to "what happens when two requests for the same user arrive at the same time."
- A survey of the four algorithms ending in "it depends." The interviewer asked you to design one limiter. Pick from the wording of the limit and say what would change the pick.
- The 429 as an afterthought. No retry story. A limiter that rejects requests but tells the client nothing.
- Scale without arithmetic. "We would shard the database" with no client count and no operations per second behind the shard count means the sharding decision appeared from nowhere.
Next step
The pattern generalizes. The same three decisions, algorithm from the wording, placement from the context, state from the accuracy requirement, run through any rate-control prompt, from a per-user API limit to a per-region budget.
Practice this prompt against a timed structure. Take the free system design assessment, no credit card required. It returns a Readiness Report, your top decision gaps, and a targeted repair preview. The full path ($49.99 for 12 months) adds the Decision Drills, including the Specialized Systems drill that covers rate control, and the System Design Readiness Exam.