System designMedium35 min readruns in the simulator
Design a rate limiter that never becomes the outage
How a distributed rate limiter is designed: token buckets, local counters settled through Redis, per-endpoint limits and a failure policy, with a simulator that floods it and kills its store.
- api-gateway
- redis
- security
- resilience
- algorithms
- throughput
- 49,642 rps
- p99 latency
- 175 ms
- cost
- $5,176/mo
Requirements
Functional
- Allow each client 100 requests a second, with bursts of up to 100; refuse the rest with 429 Too Many Requests and a Retry-After header.noisy refused over quota ≥ 1800 rps
- A client over its quota never slows down or fails a client under it.honest error rate < 1%
- No endpoint takes more than its own limit, even from many clients that are each under quota.
- When an expensive endpoint slows down, no single client can hold all of its capacity.
Non-functional
- A refused request reaches no backend: the API sees only allowed traffic.api requests in < 50000 rps
- Limiting keeps working while the counter store is unreachable, and the API stays up.
- When the API is simply full, background work is dropped before any user-facing request.
- 10,000 clients and about 50,000 requests a second at peak, through one gateway tier.throughput ≥ 49000 rps
The requirements with a measurable target are checked live in the simulator: break something and watch them fail.
Back-of-the-envelope estimates
clients × pods → store calls and memory
| Quantity | Value |
|---|---|
| Clients input | 10,000 |
| Peak requests/s input | 50,000 |
| Gateway pods input | 10 |
| Sync interval (ms) input | 100 |
| Quota per client (requests/s) input | 100 |
| Store calls/s, local counters | 100 rps |
| Times fewer store calls than checking every request | 500 |
| Counter memory | 1 MB |
| Most one client gets while the store is down | 1,000 rps |
Every value is computed from the inputs. Change them in the simulator and the model re-sizes itself.
High-level architecture
Client Appsclient · web
Ten thousand apps calling the public API, each far under its quota.
Almost all traffic is honest. The limiter’s first promise is to these clients: whatever anyone else does, their requests are neither refused nor slowed down.
Noisy Clientclient
One client sending 2,000 requests a second against a quota of 100.
One misbehaving client is the everyday case: a retry loop with no delay, a script left running, a sync job that fetches everything at once. It is drawn on its own so you can watch its traffic being refused while everyone else carries on.
Botnetclient
Two thousand keys, each under quota, all aimed at the login endpoint. Quiet until the botnet story.
A distributed attack spreads its traffic over so many keys and addresses that each one looks honest. Only a limit on the thing being attacked, the endpoint, sees the total.
Load Balancerlb · nginx
Spreads requests over the gateway pods. It knows addresses, not clients.
A load balancer can limit by IP address, but an address is not a client: a whole office or mobile carrier can share one, and a botnet has thousands. So it applies only a coarse limit per address, far above what any office sends, which drops a flood from one address before the gateway does any work. The gateway, which knows the API key, does the real limiting.
API GatewayapiGateway
Checks every request against its client’s token bucket and its endpoint’s limit before any work is done. Refusals end here.
The decision belongs in front of the API, in one place: a refusal then costs one counter check in memory instead of a full request, and the policy lives in one tier instead of in every service. Each pod counts locally and settles with the store every 100 ms, so no request waits on a network call to decide.
Counter Storedb · redis
Holds every client’s settled count. Pods talk to it every 100 ms, never on a request.
Pods need to agree on what a client has spent, or a client spreading its requests over ten pods would get ten quotas. An in-memory store with atomic increments settles their counts, and because pods only sync every 100 ms the store sees about a hundred calls a second instead of one per request.
Protected APIserver · api
The service the limiter protects: 60 pods, 120,000 requests a second.
The API is sized for its honest peak with room to spare, not for every request anyone could send. The limiter is what makes that sizing safe.
Reporting Jobclient
One customer’s nightly job pulling usage reports: 300 requests a second at an expensive endpoint.
Some endpoints are expensive: a report scans a lot of data and takes a fifth of a second even on a good day. What hurts them is not how many requests a client sends but how many it has in progress at once, so they get a concurrency limit on top of the rate limit.
Report Serviceserver · api
Builds usage reports: slow and expensive, 50 in progress per pod at most.
The gateway routes report requests here instead of to the API: one entry point, several services behind it, which is what a gateway is for. Each pod can hold only 50 reports in progress, so when reports slow down, the service can take fewer a second.
Request paths
A client’s request
Load BalancerAPI GatewayProtected API
An allowed request
- The request arrives.
One of ten thousand client apps calls the API with its key. The load balancer hands the request to one of the 10 gateway pods; it does not know or care which client sent it.
- Check the bucket, in memory.
The pod looks up the client’s bucket in its own memory, tops it up for the time since the last request, and takes one token. This client sends about 5 requests a second against a quota of 100, so there is plenty. No network call: deciding costs microseconds.
- Forward to the API.
The request goes on to the API, and the response comes back with the rate limit headers: the quota, what is left, and when the bucket refills.
Background sync
Load BalancerAPI GatewayProtected API
A client’s report
Load BalancerAPI GatewayReport Service
The reporting job’s report
Load BalancerAPI GatewayReport Service
The noisy client’s request
Load BalancerAPI GatewayProtected API
A refused request
- 2,000 requests a second.
The noisy client sends 2,000 requests a second against a quota of 100. Its first 100 a second pass exactly like anyone else’s.
- An empty bucket means 429.
For the rest, the bucket is empty. The gateway answers at once with 429 Too Many Requests and a
Retry-Afterheader saying when a token will be back. About 1,900 requests a second end here. - The API never sees them.
A refusal cost the gateway a counter check and nothing else. The API serves the honest 49,500 requests a second plus the noisy client’s allowed 100, and nobody else notices the noisy client at all.
A login attempt from the botnet
Load BalancerAPI GatewayProtected API
How the design evolved
An API for 10,000 client apps
51,800 requests a second at peak. Each client may send 100 a second. One noisy client sends 2,000, and a slow reporting job shares the same front door.
Stage 1
Count in each API process
The first limiter lives in the API: each process keeps a counter per client in memory. It is simple and needs no new service, but each of 60 processes counts alone, so a client spread over all of them gets 60 quotas. And a refused request has already cost an API process its work.
breaks at 5,200 rpswhen noisy refused over quota > 50% stops holding$4,760/mo
Stage 2
A gateway with a counter in a shared store
The limit moves to a gateway in front of the API, and every request increments its client’s counter in a shared in-memory store, one fixed window per second. Counts are now exact and refusals cost no API work. But every request is a store call, so the store’s capacity is the ceiling of the whole API, and with the store down nothing can be counted at all.
breaks at 92,000 rpswhen counter-store utilization < 90% stops holding$5,176/mo
Stage 3
A sliding window, still in the store
A fixed window lets a burst across the reset through twice, so the counter becomes a sliding window. That closes the hole, but needs two store operations per request, which halves the store’s ceiling: it now breaks below today’s peak.
breaks at 45,000 rpswhen counter-store utilization < 90% stops holding$5,176/mo
Final design
Local token buckets, settled through the store
Each gateway pod keeps token buckets in memory and settles with the store every 100 ms, so the store leaves the request path and sees about a hundred calls a second. When the store is unreachable, pods keep limiting locally instead of failing. A cap on the login endpoint catches attacks spread over many keys, a coarse per-address limit at the load balancer drops floods for less, a concurrency limit guards the slow report endpoint, and priority shedding decides what gives when the API is simply full. This is the design on the board.
Key decisions
Where does each limit live?
Chosen
In three layers, each cheaper than the one behind it: a coarse limit per address at the load balancer, limits per API key and per endpoint at the gateway, and priority shedding as the last line of defense.
Why not
- Everything at the gateway. A flood from one address still costs gateway work that the load balancer could have saved.
- Everything per address at the load balancer. Addresses are not clients: shared addresses get punished, and an attack spread over many addresses passes.
- Inside each API process. Each process counts alone, so a client gets one quota per process. A refused request has already used a process.
Which algorithm?
Chosen
A token bucket: a smooth average with a bounded burst, from one number and one timestamp per client.
Why not
- Fixed window. A burst across the reset gets two quotas back to back.
- Sliding window. More state per client, and no gentler on bursts: a quiet client can still spend its whole quota at once.
Try the alternative in the simulator →
Source: Token bucket
Where do the counters live?
Chosen
In each gateway pod, settled through a shared store every 100 ms: at each sync the store gives every pod a share of each client's tokens, sized by the traffic that pod saw, and between syncs a pod spends only its share. The store leaves the request path, and a client never gets more than its quota; when its traffic moves between pods, a few requests can be refused early until the next sync.
Why not
- In the store, checked on every request. The store becomes the ceiling and a single point of failure. A flood of refusals becomes a flood on the store.
- In each pod, never shared. Pods never agree, so a client spread over every pod always gets pods × quota.
What happens when the store is unreachable?
Chosen
Pods keep limiting from their own buckets and an alert fires. Precision drops to at most pods × quota per client until the store returns.
Why not
- Fail closed. Every request fails: the limiter turns a store outage into an API outage.
- Fail open. The API stays up but is unprotected for the whole outage.
Limit per what?
Chosen
Per API key, plus a second limit per endpoint summed over every client, so many light senders aimed at one target are caught too.
Why not
- Per API key only. An attack spread over many keys, each under quota, passes untouched.
- Per IP address. Shared addresses get punished, and attackers have thousands of addresses.
Rate limit or concurrency limit?
Chosen
Both on expensive endpoints: the rate limit caps requests a second, the concurrency limit caps requests in progress, so a client’s allowance shrinks on its own when the endpoint slows.
Why not
- A rate limit only. When the endpoint slows, the same rate holds many more requests open, and the service runs out of room.
- A concurrency limit only. On a fast endpoint, a few requests in progress still allow thousands a second.
What gives when the API is simply full?
Chosen
Background sync first, then other normal traffic, user-facing requests last, by a priority on each flow. The gateway sheds just enough to hold the API at 85%.
Why not
- Nothing: serve everyone as well as possible. Past capacity every request queues and times out, so everyone fails together.
- Refuse at random. A user-facing request is as likely to fail as background work that could have waited.
What does a refusal look like?
Chosen
429 Too Many Requests with Retry-After and rate limit headers, decided before any backend call.
Why not
- 503 Service Unavailable. It blames the service, and many clients retry it at once; a 429 names the client as the cause.
- Queue the excess. The queue grows for as long as the client keeps sending, so the flood becomes a backlog and every request waits.
Sources: RFC 6585: Additional HTTP Status Codes (429 Too Many Requests), RFC 9110: HTTP Semantics, Retry-After
Refusing must be cheaper than serving
Why the limiter sits in front
A rate limiter earns its keep during floods, which is exactly when every unit of work counts. If refusing a request costs as much as serving it, a flood of refused requests still takes the service down. So the decision happens before any real work: in a gateway in front of the API, from a counter in memory, with no database call and no downstream request.
What a refusal says
A refused request gets 429 Too Many Requests, a status that means "you, specifically, are sending too much", and a Retry-After header with how long to wait. Rate limit headers on every response tell a client its quota and what it has left, so a well-written client slows down before it is ever refused. A 503 would blame the service, and many clients retry it at once; dropping the request silently would make them time out and retry; queueing it would only turn the flood into a backlog.
Three layers, cheapest first
Each layer catches what it can see
- **Load balancer, per address.** It knows nothing about clients, only addresses, so its limit is coarse and high: far above what a whole office sends, low enough to drop a flood from one address before anything else does work.
- **Gateway, per key and per endpoint.** It knows the API key and the endpoint, so this is where quotas live: a token bucket per client, a cap on the login endpoint for everyone together, and a limit on reports in progress.
- **Shedding, by priority.** When the API is full anyway, because everyone is honest and there are simply too many, the gateway drops background work first so user-facing requests keep working.
Requests a second, or requests in progress
A rate limit counts requests a second. An expensive endpoint is hurt by something else: how many requests are in progress at once. If a report suddenly takes seven times longer, the same rate holds seven times as many open. A concurrency limit caps those directly, so a client’s allowance shrinks on its own when the endpoint slows. The slow-endpoint story shows both.
Choosing an algorithm
Three ways to count
| Algorithm | How it counts | The catch |
|---|---|---|
| Fixed window | One counter per client per second, reset on the clock. | A burst across the reset gets two quotas back to back. |
| Sliding window | Counts what the client sent in the last second, whenever “now” is. | Never more than the quota in any window, but a quiet client can still send its whole quota at once. Exact only with a timestamp per request; the cheaper two-counter version weighs the previous second and is an approximation. |
| Token bucket | A bucket of tokens refills at the quota rate; each request takes one; an empty bucket refuses. | A burst up to the bucket size always passes, which is usually what you want. |
Why a token bucket
Real clients are bursty: an app opens and fires twenty requests at once, then goes quiet. A token bucket allows that burst, up to the bucket size, while holding the long-run average to the quota. It needs one number and one timestamp per client, and it refills lazily from the time since the last request, so no timer runs per client. The window-edge story shows the difference: the same burst gets 200 requests through a fixed window, 100 through a sliding window, and 120 through the bucket.
Where the counters live
Every pod must agree
The load balancer spreads each client over all the gateway pods. A client sending 1,000 requests a second through 10 pods sends 100 to each, and if each pod counted alone, every one of them would see a client within quota. The pods need a shared view of what each client has spent.
Two ways to share it
- **Ask the store on every request.** Exact, and simple: an atomic increment per request in an in-memory store. But every request, including every refusal, is now a store call. The store becomes the ceiling of the API and a single point of failure, and a flood of refusals is a flood on the store.
- **Count locally, settle on a timer.** Each pod keeps its own buckets and every 100 ms sends the store one pipelined call with what it has counted. The store answers with each client's share for that pod: the client's remaining tokens, split by where its traffic went. The store sees about a hundred calls a second whatever the traffic, and no request waits for it. The price is imprecision the other way: when a client's traffic shifts to another pod, that pod's share can run dry and refuse a few requests early, until the next sync rebalances.
Early refusals are the right trade
A quota is a business promise, not a safety interlock: refusing a client a few requests early, for a tenth of a second while its traffic moves between pods, harms nobody. A store that saturates under the very attack the limiter is meant to absorb harms everybody. The flood story lets you try both.
When the limiter itself breaks
Includes stated assumptions
Three policies
- **Fail closed:** refuse whatever cannot be counted. Quotas are never exceeded, and the API is down for everyone for as long as the store is.
- **Fail open:** allow everything. The API stays up, and is unprotected for exactly as long as the store is down.
- **Limit locally:** each pod keeps limiting from its own buckets. Every request still gets a decision; a client spread over every pod can get up to pods × quota until the store is back.
The rule
A limiter exists to protect the service, so it must never be the reason the service is down. Local limiting keeps protection and availability, and gives up only precision, for a bounded time, by a bounded amount you can compute in advance: here 10 pods × 100 = 1,000 requests a second for one client. An alert on the store makes sure that time stays short.
Limit per what?
Includes stated assumptions
Keys, addresses and endpoints
A limit per API key is fair: each customer gets what they pay for, whatever network they are on. A limit per IP address is what you fall back to for unauthenticated traffic, but it is blunt: one office or mobile carrier can put thousands of people behind one address, and an attacker can rent thousands of addresses.
The second limit
Neither catches an attack spread over many senders, each under its limit. A second limit on the endpoint, summed over every client, does: the login endpoint takes at most 5,000 requests a second whoever sends them. During an attack that limit can refuse some honest logins too, which is why it is set well above normal login traffic and paired with an alert, so someone can revoke the attacking keys.
What happens when it breaks
One client floods
A client goes from 2,000 to 20,000 requests a second. Nobody else notices.
| Reading | Healthy | During the failure |
|---|---|---|
| p99 latency | 175 ms | 170 ms |
| error rate | 0% | 0% |
| throughput | 49,642 rps | 49,642 rps |
| refused over quota | 2,158 rps | 20,158 rps |
- Allow each client 100 requests a second, with bursts of up to 100; refuse the rest with 429 Too Many Requests and a Retry-After header. (still holds)
- A client over its quota never slows down or fails a client under it. (still holds)
- A refused request reaches no backend: the API sees only allowed traffic. (still holds)
- 10,000 clients and about 50,000 requests a second at peak, through one gateway tier. (still holds)
Local counters can refuse a client a little early when its traffic shifts between pods. Do you switch to exact counting in the store?
- Keep local counters.
Nothing changes: the store takes about 100 calls a second, and the flood never reaches it.
- Check the store on every request.
Every request that reaches the gateway, refusals included, now calls the store: about 51,800 calls a second, half its capacity, and each request waits about 6 ms more at the gateway. A flood that gets past the load balancer, or a botnet, and the store is the bottleneck of the whole API.
Exactness has a price: with a check per request, a flood of refusals becomes a flood on the store. Local counters keep the store off the request path, and a few early refusals for one client are far cheaper than a store that fails under the very attack the limiter exists for.
Trade-offs
Algorithm
| Option | Gain | Cost |
|---|---|---|
| Token bucketdefault | A smooth average with a bounded burst, from one number and one timestamp per client. | Two settings to tune (rate and bucket size), and a burst up to the bucket size always passes. |
| Fixed window | The simplest possible counter: one increment per request, reset on the clock. | A burst straddling the boundary gets twice the quota. |
| Sliding window | No window of the chosen length holds more than the quota (exactly with a timestamp per request; the two-counter version is close). | More state per client (a count per slice, or a timestamp per request), and no extra allowance for a burst above the quota. |
When the store is down
| Option | Gain | Cost |
|---|---|---|
| Limit locallydefault | Every request still gets a decision, and the API stays protected. | A client can get up to pods × quota until the store is back. |
| Fail closed | Nobody ever exceeds a quota. | Nobody gets anything either: a store outage becomes an API outage. |
| Fail open | The limiter can never cause a failure. | No limits at all during the outage. |
Limit per
| Option | Gain | Cost |
|---|---|---|
| Client and endpointdefault | Catches one heavy client and many light ones aimed at one place. | Two limits to tune, and the endpoint limit can refuse honest users during an attack. |
| Client only | One limit, easy to explain to customers. | An attack spread over many keys passes untouched. |
Fixes and what they cost
| Fix | What it does | Trade-off |
|---|---|---|
| Check the store on every request | Exact counts: every pod asks the store before deciding, so no share runs dry early between syncs. | Every request, including every refusal, becomes a store call. The store is now the ceiling of the API and adds a round trip to each request. |
| Double the counter store | Twice the store capacity, sharded by client key. | Costs more, and only matters when the store is on the request path. |
| Double the API pods | More room behind the limiter. | Costs twice as much, and does nothing for a store or a gateway that is the real problem. |
| Settle every 500 ms | Five times fewer store calls. | Shares are rebalanced less often, so a client whose traffic shifts between pods can be refused early for longer. |
| Keep limiting locally when the store is down | Each pod limits from its own bucket until the store returns. | A client spread over every pod can get up to pods × quota during the outage. |
| Drop the concurrency limit on reports | Reports are held only by the per-client rate limit. | When reports slow down, a client can keep as many in progress as its rate allows, and the report service runs out of room. |
| Turn off load shedding | Every request competes equally for the API. | When the API is full, user-facing requests fail as often as background work that could have waited. |
| Allow everything when the store is down | No request fails because of the limiter. | No request is limited either, so the API is unprotected for as long as the outage lasts. |
Interview questions
What is the difference between rate limiting and load shedding?
Rate limiting refuses clients who send more than their share, whatever the load. Load shedding drops requests because the service is full, whoever sent them, lowest priority first. A rate limiter does nothing when every client is honest and there are simply too many; shedding is what keeps the service up then, until more capacity arrives.
Why put the rate limiter in an API gateway rather than in the service?
Because a refusal should cost as little as possible and the policy should live in one place. In the gateway, a refused request never reaches the service, and every service behind it gets the same limits without implementing them. Inside each service, every process counts on its own and a refusal still uses a full service process.
Token bucket or sliding window: which should I use?
A token bucket for most APIs: it allows the short bursts real clients make, holds the average to the quota, and needs one number and one timestamp per client. A sliding window when the limit must hold over every interval, such as a hard cap on paid operations, at the cost of more state per client. Avoid a plain fixed window: a burst across the reset gets two quotas.
Why not just use a Redis counter for every request?
It is exact and simple, and it puts the store on the path of every request, refusals included. The store then becomes the ceiling of the whole API and a single point of failure, and a flood of refused requests becomes a flood on the store. Counting locally in each gateway pod and settling every 100 ms keeps the store at about a hundred calls a second.
What should a rate limiter do if its store goes down?
Keep limiting from local counters in each instance, alert, and accept that a client may get up to instances × quota until the store returns. Failing closed turns a store outage into a full outage; failing open leaves the service unprotected exactly when something has already gone wrong.
Which status code should a rate limiter return?
429 Too Many Requests, with a Retry-After header telling the client when to try again. A 503 blames the service, and many clients retry it at once; a 429 names the client as the cause. Rate limit headers on every response let well-written clients slow down before they are refused at all.
Sources: RFC 6585: Additional HTTP Status Codes (429 Too Many Requests), RFC 9110: HTTP Semantics, Retry-After, RateLimit header fields for HTTP (Internet-Draft)
Does a rate limiter protect against DDoS attacks?
Against application-level abuse, yes: a per-endpoint limit caps what many senders together can push at one target, and per-client limits stop any single key from hogging the service. Against network floods that saturate links or the gateway itself, no: those need filtering at the network edge, before traffic reaches anything that has to look at a request.