Design a rate limiter
Most outages caused by a single customer are not attacks. They are a retry loop. Something times out, a client retries, the retry times out because the first request is still holding a connection, and within a minute one integration is sending forty times its normal traffic at you. The customer does not know. Your pager knows.
A rate limiter is the piece that turns that from an outage into a 429. It is a small system with a surprising amount of depth, which is why it shows up so often in interviews.
Before you scroll: you run 20 API hosts behind a load balancer and want to allow each user 100 requests a minute. Where do you keep the count, and what goes wrong with the obvious answer?
What you are building
- Limit requests per user, per API key and per endpoint. Different limits for different routes, since a search is not a login.
- Return 429 with a Retry-After header. A client that cannot tell when to come back will hammer you.
- Work correctly across every API host. This is the whole problem. One host counting alone is not a rate limiter.
- Adds under 5ms at p99 to a request.
- A limiter failure must not take down the API.
- 50,000 requests a second at peak across 20 hosts.
- Limits change at runtime without a deploy.
- DDoS protection. Volumetric attacks are absorbed at the edge before they ever reach an application limiter.
- Billing quotas. Similar counting, completely different consistency requirement, because money has to be exact and a rate limit does not.
- Per-tenant fair queueing. Worth mentioning as the next step up, out of scope for 45 minutes.
The numbers
1.4GB fits in memory on one machine, so this is a throughput problem rather than a capacity problem. That is what pushes the design toward a single round trip per request and nothing clever.
The contract
The response headers matter more than the endpoint list. A rate limiter that rejects without telling the client anything produces exactly the retry storm it exists to prevent.
{
"tier": "free",
"rules": [
{ "route": "POST /search", "limit": 20, "window": 60 },
{ "route": "*", "limit": 100, "window": 60 }
]
}Where the counters live
| key | string | PK | rl:{userId}:{route}:{windowStart} |
| value | integer | Request count in this window. Incremented, never read then written. | |
| ttl | seconds | IDX | Window length plus a small margin. Expiry is the whole cleanup story. |
The design
Two placement decisions are worth defending out loud. The limiter runs in the gateway rather than in each service, so one counter covers every route and a rejected request never costs a service call. And it runs after cheap identification but before expensive authentication, because verifying a token against a database on a request you are about to reject is exactly the work you were trying to avoid.
Deep dive one: the three algorithms, on the same traffic
This is the part of the question with a right answer, and the difference is invisible until you watch the same burst scored three ways. The traffic below is deliberately nasty: quiet, then ten requests packed against a window boundary, then a steady stream.
Switch between the three and watch the requests either side of the 2000ms line. Fixed window lets all of them through. The other two do not. That gap is the entire reason fixed window keeps losing this argument, and it is not theoretical: a client whose cron job happens to land on your boundary gets close to twice its limit, indefinitely, and nothing anywhere reports an error.
Token bucket is the default answer. Constant memory per user, a burst allowance that matches how clients really behave, and two integers to store. Sliding window log is the right answer when the limit is small and exactness matters, such as login attempts.
Deep dive two: the race that makes it a distributed systems problem
Now the part that catches people. Twenty gateway hosts share one counter. The obvious implementation reads the count, compares it against the limit, and writes the count back.
The fix is not a lock. A lock around a counter on the hot path of every request is a throughput disaster and a new failure mode. The fix is to stop reading and writing at all.
INCR in Redis is atomic and returns the new value, so one round trip both counts the
request and tells you where you stand. The check becomes: increment, and if the returned
value is above the limit, reject. No read, no race, no lock. When you need more than one
operation to stay atomic, such as an increment plus a conditional expiry, put both in a
Lua script, which Redis runs as a single atomic unit.
“What if Redis is down?” Decide this deliberately and say it out loud. Failing open lets traffic through unlimited, which risks the outage the limiter exists to prevent. Failing closed rejects everyone, which turns a limiter outage into a full outage. The usual answer is fail open with a local in-process limiter as a floor, so you degrade from precise global limits to approximate per host ones instead of to nothing.
Deep dive three: the limiter itself becomes the bottleneck
One Redis round trip per request means the counter store now takes your entire traffic. At 50,000 requests a second that is fine. Drag the dial and watch where it stops being fine.
That last step is worth stating as a principle. The exact global count only matters for users close to their limit. Everyone else can be waved through on approximate local knowledge, and that is almost everyone.
Trade-offs
| Choice | What you gain | What you pay | Pick it when |
|---|---|---|---|
| Token bucket | Two integers per user, allows a natural burst, then paces strictly. | A client can always burst up to the bucket size, so downstream has to survive that. | The default for API rate limiting. Pick this unless you have a specific reason not to. |
| Sliding window log | Exactly correct with no boundary to game. | Memory proportional to the limit for every active user, plus trimming work on each request. | Small limits where precision matters, like five login attempts in fifteen minutes. |
| Centralised counters in Redis | One true count across every host, and limits are exact. | A network round trip on every request and a shared dependency that can take your API with it. | Up to low hundreds of thousands of requests a second, which is most systems. |
| Local buckets with periodic sync | No round trip on the common path, and the limiter cannot take the API down. | Limits become approximate, and a user spread across hosts can exceed the global limit briefly. | Very high traffic, or when the limiter must never be in the critical path. |
Interview replay
Checkpoint
1. Why is read-count, compare, write-count wrong across twenty gateway hosts?
2. A client sends 10 requests at 0:59 and 10 more at 1:01 against a limit of 10 per minute. Which algorithm lets all 20 through?
3. The limiter is adding 4ms to every request and rejecting about 0.1% of them. What is the first change you would make?
I would put the limiter in the API gateway, before any expensive authentication work, so a rejected request costs almost nothing. Counters live in Redis keyed by user, route and window, with a TTL so there is no cleanup path to get wrong. Each gateway does a single atomic INCR rather than read-compare-write, because with twenty hosts the read-then-write version races and users drift over their limit. Algorithm is token bucket: constant memory per user, allows a natural burst, and no boundary to game the way fixed window has. If Redis is unavailable I fail open onto a local per host bucket, since a limiter outage should degrade limits rather than take the API down. And when the limiter itself becomes the bottleneck, the fix is to check locally for everyone who is nowhere near their limit, which is almost everyone.
