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.

What you are building#

Back of the envelope#

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#

The whole system on one whiteboard#

Walking Figure 1:

1. The request lands on any gateway host. They are interchangeable, which is exactly why the count cannot live inside one of them.
2. 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.
3. 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.
4. Only users close to a limit cost a network call. That is one atomic INCR against Redis, sharded by user id, and the returned value is the decision.
5. 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.
6. 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.

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.

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#

Interview replay#

Checkpoint#