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.
Step 1: Understand the problem
A rate limiter looks like one number in a config file, so people start drawing immediately. Ask these first. Two of the six answers below decide the entire design.
| You ask | They say | What it settles |
|---|---|---|
| What are we limiting: users, API keys, IPs, endpoints? | Per user and per API key, with a different limit on expensive routes. | The shape of the counter key, rl:{user}:{route}:{window}. One user calling two routes needs two counters, which is what makes the key count large. |
| How many API hosts share one limit? | Twenty, behind a load balancer. | The whole problem. One host counting on its own is not a rate limiter, so the counter has to live outside the process and every host has to agree on it. |
| How exact does the limit have to be? | Close enough. Nobody is billed for it. | Your escape hatch later. Approximate counting is what lets you take the network off the hot path when the limiter itself becomes the bottleneck. If the answer had been "exact", as it is for login attempts, the design gets slower and more careful. |
| What does a rejected client see? | A 429, and enough information to back off sensibly. | Retry-After plus the X-RateLimit headers, with jitter. A limiter that rejects silently causes the retry storm it exists to prevent. |
| Can limits change without a deploy? | Yes, during an incident, in seconds. | Rules live in watched config and the gateway hot reloads them. It also means a bad config change is now a way to take yourself down, so the config path needs validation. |
| If the counter store dies, does the API stay up? | The API stays up. Always. | Fail open, with a local bucket as the floor. Settling this in minute three is much better than being asked it as a gotcha in minute forty. |
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.
Back of the envelope
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.
Step 2: Propose the high level design
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 whole system on one whiteboard
Walking Figure 1:
- The request lands on any gateway host. They are interchangeable, which is exactly why the count cannot live inside one of them.
- The gateway looks up the rule for this user and route. Rules come from watched config, so tightening a limit during an incident is a config push and not a deploy.
- It checks its own in-process bucket first. For the overwhelming majority of users, who are nowhere near their ceiling, the answer is already known here and the request never leaves the box.
- Only users close to a limit cost a network call. That is one atomic
INCRagainst Redis, sharded by user id, and the returned value is the decision. - Allowed requests go on to authentication, then to the service. Rejected ones turn
round here with a 429 and a jittered
Retry-After, having cost you a hash lookup. - Every decision is counted. You want a dashboard of 429 rate per route and an alert on the gateway running in local-only fallback, because otherwise nobody notices the day your limits quietly stopped being global.
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.
Twenty gateway hosts share one limit of 100 requests a minute. What goes wrong if each host reads the counter, compares it to the limit, and writes the new value back?
Step 3: Design deep dive
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, forever, 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.
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.
Break it: the limiter 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?
- 50,000 requests a second, one INCR each. Every check sits on the hot path.
- 5 million users x 3 rules is 15 million keys, about 1.4GB. Memory is never the problem here, throughput is.
- A single Redis primary runs out of one core somewhere past 100,000 ops a second. Not memory, not network.
- 99.9% of requests are allowed. That is how much of the round trip bought you nothing.
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.
