In this article
Before you start
This page is one step of the system design learning path.
Why interviewers ask this
A limiter that works on one server and breaks on ten is the usual way this answer fails, and that is the gap the question probes. Interviewers use "design a rate limiter" in the system design round of an interview loop because it looks small and hides four separate decisions: which algorithm, where the counters live, how the update stays correct when many servers write at the same moment, and what happens when the counter store is down.
A weak answer names the token bucket and stops. A strong answer says where the state lives, makes the update atomic, and states what the client sees on a rejection. The topic is reported in interviews at AI labs and large tech companies, and it also arrives as "design a frequency capping system" for advertising. The same mechanics sit behind the representational state transfer (REST) API questions about throttling.
Rate limiter from first principles
- Rate limiter
- A rate limiter is a component that counts the requests each client sends and rejects those above an agreed rate, so that one client cannot use more than its share of a service.
- Token bucket
- A token bucket is a counter that refills with tokens at a steady rate up to a fixed capacity, where each request must take one token and is rejected when the bucket is empty.
- Atomic update
- An atomic update is a read-and-write on shared data that runs as one indivisible step, so no other process can see or change the data halfway through.
In plain words
Picture a jar of tokens next to a cashier. Every request must take one token to be served. A helper drops new tokens in the jar at a steady pace, and the jar holds only so many. If the jar is empty, the request waits outside or is turned away. The analogy breaks in one place: a real gateway fleet has many cashiers, and they all must share one jar, which is where the difficulty lives.
In one precise sentence: a distributed rate limiter stores each client's counter, here a token bucket, in one shared place and lets every gateway change it through one atomic operation.
Step 1: Pick the key and the limits
A rate limiter needs a key, the identity it counts per, and a rule, the rate and burst allowed for that key. A burst is a short run of requests above the steady rate that the limiter still accepts. Typical keys are an API key, a user id or an address. Stripe's engineering team (2017) describes running four kinds of limiters in production, two rate limiters and two load shedders, and advises starting with the request rate limiter, which caps each user at a set number of requests per second.
The gateway is the natural place to check, because every request passes it before reaching a backend. Amazon API Gateway shows the layering: per-client limits from usage plans keyed by API key, per-method limits, then account-level limits per Region, applied in that order (as of October 2026). Input: a request. Output: a key and a rule. What you now know: the limiter is a counter per key; the next step is what shape the counter takes.
Step 2: Hold a token bucket per key
A token bucket stores two numbers per key: how many tokens are left and the time of the last update. The bucket needs no timer. When a request arrives, the limiter adds the tokens earned since the last update, capped at the capacity, and then tries to take one.
Amazon's documentation defines both settings the same way: the throttling rate is the rate, in requests per second, at which tokens are added to the bucket, and the burst is the capacity of the bucket. Stripe describes the same structure, a centralised bucket host where each request takes a token. The function below is the one run in the simulation: rate is tokens per second and cap is the burst.1
def take(state, now, rate, cap):
tokens, last = state
tokens = min(cap, tokens + (now - last) * rate) # refill for elapsed time
allowed = tokens >= 1
if allowed:
tokens -= 1 # spend one token
state[0], state[1] = tokens, now # write both back together
return allowedInput: the stored pair and the clock. Output: a yes or no and a new pair. The cost is two numbers per key, which is why the algorithm scales to many clients. Both numbers are written together, and that matters in Step 4.
Step 3: Share the state across gateways
A fleet of gateways needs one count per client, not one count per server. If each of N gateways keeps its own bucket, the limit is either N times too loose or split into N slices. Splitting is unfair: when requests land at random, a client sending exactly its limit still has some rejected, because one gateway's slice fills first. In the simulation with a limit of 100, splitting over 2, 4 and 10 gateways wrongly rejected 3.97%, 6.91% and 11.9% of requests that were within the limit.1
The fix is a shared store that every gateway reads and writes. Stripe says it implements its rate limiters with Redis, an in-memory data store with atomic commands. The store can be sharded by client key, as in designing a distributed cache with consistent hashing. Envoy, an open-source proxy, takes the layered view: a global limit through an external service, which its reference implementation backs with Redis, plus a local token bucket that absorbs bursts and reduces load on the global service (Envoy documentation, as of October 2026).
Step 4: Make the check and the update atomic
Two gateways can read the same count, both decide there is room, and both write. The check and update must be one atomic update. In a worst-case model where gateways always read the count together, a read-then-write check admitted 100 of 1,000 requests with one gateway, 200 with two, 400 with four and 800 with eight, against a limit of 100; an atomic increment admitted 100.1 Real overlap is partial, so the overshoot is smaller.
The Redis documentation for the increment command (INCR) shows the same care. Its basic limiter increments a per-address, per-second counter and sets its expiry in one transaction. Its single-counter variant has, in its own words, a race condition: if the client increments but never sets the expiry, the key leaks. The fix is a Lua script run on the server, so both happen as one step. A token bucket reads and writes two values, so the whole take function must run inside one script on the store.
Step-by-step description
- Choose who is limited: an API key, a user or an address.
- The bucket refills at the rate and allows a burst.
- One store means every gateway sees the same count.
- One script reads, decides and writes with no gap.
- Reply 429 and say when to retry.
- A rate limiter needs a key, the identity it counts per, and a rule.
- A token bucket stores two numbers per key: how many tokens are left and the time of the last update.
- A shared store gives every gateway one count per client.
- The check and the update must happen as one atomic update.
- A rejection should use 429 Too Many Requests and may include a Retry-After header.
Input: a key and the time. Output: an answer computed with no gap between read and write.
Step 5: Answer clearly when the bucket is empty
A rejection should use the status code built for it. Request for Comments (RFC) 6585, section 4 (April 2012) defines 429 Too Many Requests as meaning the user has sent too many requests in a given amount of time, and says the response may include a Retry-After header saying how long to wait. Amazon's documentation says clients may receive 429 responses and should resubmit failed requests in a way that is itself rate limited.
Tell the client the limit, what remains and when to retry, so a well-behaved caller backs off instead of hammering. Rejections should be cheap: the check runs before any real work. What you now know: key, bucket, shared store, atomic script, clear reply. That is the whole design; the rest is choosing numbers and failure behaviour.
Knowing it is half the job. Saying it is the other half.
Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.
Start Free Trial →Worked example
The simulation sets a limit of 100 requests per 60 seconds. All traffic is synthetic and the results are illustrative; the scripts and their saved outputs are in the data folder.1
| Test | Offered | Fixed window | Sliding log | Sliding counter | Token bucket |
|---|---|---|---|---|---|
| 100 requests in the last second of a window, then 100 in the first second of the next | 200 | 200 | 100 | 102 | 103 |
The fixed window counts per calendar minute, so two bursts on either side of the boundary each see an empty counter. A sliding log stores the time of every accepted request and counts those in the last 60 seconds, which is exact but costs one stored time per request.
The sliding window counter is Cloudflare's approximation (2017): rate equals the previous window's count times the share of that window still in view, plus the current count. Cloudflare's own example is 42 requests in the previous minute and 18 in the current one, 15 seconds in: 42 times 0.75 plus 18 is 49.5 against a limit of 50. On 400 million requests from 270,000 sources, Cloudflare reports that 0.003% were wrongly allowed or limited.
Text description of the diagram
- With a limit of 100 a minute, 100 requests in the last second of one window and 100 in the first second of the next were all allowed by a fixed window.
- A sliding log allowed 100, a sliding window counter 102 and a token bucket 103.
The boundary test lasts two seconds, which flatters the token bucket. Over a full minute, a bucket with capacity 100 that refills 100 tokens a minute admits its capacity plus a minute of refill: 199 requests in one 60-second span when a burst of 100 is followed by one request every tenth of a second.1 A token bucket bounds the burst, not the count per window. If the contract is 100 in any minute, use a sliding log or sliding window counter, or set the capacity to the burst you accept.
The second test is the race of Step 4, 1,000 offered requests against a limit of 100.1
| Gateways acting at the same moment | Read then write | Atomic increment |
|---|---|---|
| 1 | 100 | 100 |
| 2 | 200 | 100 |
| 4 | 400 | 100 |
| 8 | 800 | 100 |
Text description of the diagram
- With a limit of 100 and 1,000 offered requests, an atomic increment admitted 100.
- A read-then-write check admitted 100, 200, 400 and 800 with 1, 2, 4 and 8 gateways acting at the same moment.
Finally, capacity arithmetic, with assumed inputs. Take 10,000,000 requests per second at the gateways and an assumed 100,000 operations per second per store shard. One store call per request needs 100 shards. If each gateway leases 100 tokens at a time and every lease is spent, the store sees 100,000 calls per second, one shard.1
That holds only for busy keys: the saving per key is the number of tokens a gateway actually spends per lease, so a lease must be a small share of the key's limit, and a key sending a few requests a minute gains almost nothing. The assumed inputs are illustrative; measure your own store. The price of leasing is accuracy: tokens parked on one gateway are refused to the same client on another, and leases spent late can bunch requests above the steady rate, so leases carry a short expiry.
Trade-offs and edge cases
The algorithm is a choice between accuracy, memory and burst behaviour.
| Algorithm | State per key | Bytes per key at a limit of 100 | Over any 60 seconds | Bursts |
|---|---|---|---|---|
| Fixed window | One counter | 8 | Up to twice the limit | Within a window |
| Sliding log | One time per request | 800 | Exact | Never above the limit |
| Sliding window counter | Two counters | 16 | Close | Mostly smoothed |
| Token bucket | Tokens and a time | 16 | Up to capacity plus refill | Allowed by design |
The sizing assumes 8 bytes per value and ignores store overhead.1
Failure of the store. When the shared store does not respond, the gateway must pick a default. Failing open keeps the API up but drops protection; failing closed protects the backend but rejects good traffic. Stripe's engineering team (2017) chose to fail open: a bug in the limiter or a Redis outage should not affect requests. An abuse-sensitive endpoint, such as a login, can justify the opposite choice. A local token bucket in each gateway keeps a coarse limit while the store is down; Envoy uses the same local bucket to absorb bursts in front of its global service.
Hot keys. One client with a huge share of traffic makes one store shard hot. Local buckets absorb part of it, and leasing tokens reduces calls.
Not every limit is a rate. Stripe also limits concurrent requests per user, which protects expensive endpoints, and sheds load by priority when the fleet is busy. A rate limiter is one of several guards.
Multiple regions. A single global counter adds a round trip across regions for each request, so many designs keep per-region limits and accept that the global total is approximate. Which is right depends on how strict the contract is.
How to answer it in an interview
How would you design a distributed rate limiter for an API gateway?
I would key limits by API key and use a token bucket, because it allows bursts and stores only two numbers per client. The gateways share one Redis store, and each check runs as a single Lua script so the read and the write are atomic. Otherwise two gateways can both see room and overshoot. On rejection I return 429 with a retry-after hint. If Redis is unreachable I fail open for normal traffic, with a local bucket as a backstop. The trade-off is one extra network call per request, which I reduce by leasing tokens in batches.
The spoken structure: name the key and the bucket, say where the state lives, say why the update is atomic, then give the failure behaviour and the cost.
Common mistakes
- "Each gateway keeps its own counter." (wrong) The limit becomes N times looser, or split slices reject honest traffic: 6.91% with four gateways in the simulation. (right) "State lives in one shared store."
- "I read the count, compare, then write it back." (wrong) In the worst-case model, eight overlapping gateways admitted 800 of 1,000 against a limit of 100. (right) "The check and update are one atomic script."
- "A fixed one-minute window is exact." (wrong) It allowed 200 requests across a boundary against a limit of 100. (right) "For a count per window use a sliding log, or a sliding window counter for a close count; a token bucket bounds bursts, not the count per minute."
- "Return an error and say nothing else." (wrong) Clients retry immediately and add load. (right) "Return 429 with a retry-after value."
Follow-up questions
How would you design a frequency capping system?
Frequency capping limits how often one user sees one advertisement, so it is a rate limiter keyed by user and campaign with long windows. The same shared store and atomic update apply; the counters count impressions, not API calls.
How would you support limits like five impressions per day or ten in two weeks?
Keep two limits on the same key and check both in one script, admitting only if both allow it. Keep one counter per calendar day and let each expire after fifteen days: today's counter enforces five a day, and the sum of the last fourteen enforces ten in two weeks, rolling one day at a time. A single counter with a fourteen-day expiry is a fixed window, so at its boundary it can let 20 through in four days.
What granularity would you cap at?
Cap at the finest identity that matters for fairness and abuse: per user and campaign for advertising, per API key for an API. Finer keys use more memory, coarser keys let one noisy client hide inside a group.
What happens when a server does not respond?
If a gateway dies, the requests it was handling fail; a client or load balancer that retries sends them to another gateway, and the shared state is unaffected. If the store does not respond, the gateway applies its fail-open or fail-closed default, as in the trade-offs above. Use a short timeout so the limiter never becomes the slowest part of the request.
Should the limiter fail open or fail closed?
It depends on the cost of each error. Failing open risks overload during a store outage; failing closed turns the outage into a customer-visible failure. Many designs split by endpoint. A related pattern for delivering events safely is covered in webhook design, where retries and idempotency matter.
- A distributed limiter needs one shared count per client and an atomic update.
- The token bucket stores two numbers per key and allows bursts up to its capacity.
- A fixed window let 200 requests through in two seconds against a limit of 100; a token bucket sized to the limit can admit 199 over a full minute.
- A read-then-write check can admit the limit once for every gateway that overlaps; one atomic script per check holds the limit.
- Reply 429 with a retry hint, and decide on purpose whether the limiter fails open or closed.
Sources
- Scaling your API with rate limiters — Stripe Engineering Blog (Paul Tarjan), 30 Mar 2017
- How we built rate limiting capable of scaling to millions of domains (Counting things, a lot of different things) — Cloudflare Blog, 7 Jun 2017
- RFC 6585: Additional HTTP Status Codes, section 4 (429 Too Many Requests) — IETF (Nottingham and Fielding), 1 Apr 2012
- INCR, pattern: rate limiter — Redis documentation (date = read date), 24 Oct 2026
- Throttle requests to your REST APIs for better throughput in API Gateway — Amazon Web Services documentation (date = read date), 24 Oct 2026
- Global rate limiting — Envoy documentation (date = read date), 24 Oct 2026
