Design a rate limiter

Ask for an OTP three times in a minute and the app says "try again in 30 seconds". That message comes from a rate limiter: a small piece of code that counts how many requests someone has made recently and turns the extra ones away. It protects your servers, and it keeps one noisy caller from hurting everyone else.

The noisy caller is usually not an attacker. It is a retry loop. Something times out, a client retries, the retry times out too because the first request is still holding a connection, and within a minute one integration is sending forty times its normal traffic. The customer does not know. Your pager knows. Watch one request go through the design this page builds.

Words this page uses a lot:

• A 429 is the HTTP status code for "Too Many Requests". It is how a server says "you, specifically, slow down".
• Retry-After is a response header that tells the client how many seconds to wait before trying again.
• The API gateway is the front door every request walks through before it reaches your services. The proxy vs reverse proxy vs API gateway article explains where it sits and what else it does.

Rate limiting has close cousins, throttling (slow down instead of refusing) and backpressure (let the slowdown travel back to the sender). Rate limiting vs throttling vs backpressure puts the three side by side. This page is about the first one.

Step 1: Understand the problem#

A rate limiter looks like one number in a config file, so people start drawing straight away. Ask these first. Two of the six answers decide the whole design.

What you are building#

Back of the envelope#

Three inputs. The point of the exercise is to find out whether the hard part is memory or speed. (New to this kind of estimate? The back of the envelope chapter walks through the method.)

Step 2: Propose the high level design#

The contract#

The response headers matter more than the list of endpoints. 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 counters live in Redis, an in-memory key value store that answers in well under a millisecond. Each counter is one key with a number in it, and every key has a TTL (time to live): Redis deletes the key by itself when the time runs out. The caching patterns chapter covers TTLs in more depth.

The whole system on one whiteboard#

Figure 1 is the same path as the picture at the top, with the metrics box added.

Walking Figure 1:

1. The request lands on any gateway host. A load balancer spreads requests across the hosts (the load balancing chapter shows how it picks one). The hosts 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-memory bucket first. For the great majority of users, who are nowhere near their ceiling, the answer is already known here and the request never leaves the machine.
4. Only users close to a limit cost a network call. That is one atomic INCR against Redis, and the value it returns is the decision. (Atomic and INCR get a full section in the deep dive.)
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 429s per route, and an alert when a gateway falls back to local-only counting. Otherwise nobody notices the day your limits quietly stopped being shared.

Two placement choices are worth defending out loud. The limiter runs in the gateway, not inside each service, so one counter covers every route and a rejected request never costs a service call. And it runs after cheap identification (reading the API key) but before expensive authentication (proving the key is real, often with a database lookup). Checking a token on a request you are about to reject is exactly the work you were trying to avoid. Authentication vs authorization explains the two checks that come after.

Step 3: Design deep dive#

How to count: three algorithms#

The counting rule is called the algorithm, and this is the part of the question with a right answer. The three below are the ones interviewers expect you to compare.

A worked example of the token bucket, with that limit of 10 a minute. At 0:00 a client fires 10 requests: the full bucket pays for all of them and is now empty. A request at 0:03 is rejected, because no token has come back yet. At 0:06 one token has refilled, so the next request is allowed. The client gets its burst, then a steady one request every six seconds.

Now see the three on the same traffic. It 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 why fixed window keeps losing this argument.

Token bucket is the default answer: constant memory per user, and a burst allowance that matches how real clients behave. Sliding window log is the right answer when the limit is small and must be exact, such as five login attempts in fifteen minutes.

Twenty hosts, one count#

Now the part that catches people. The algorithm is easy on one machine. With twenty gateway hosts, every host has to see the same count for the same user.

Here is the second rung going wrong. This bug has a name, the lost update, and the optimistic vs pessimistic locking article shows it in a database too.

Atomic means "happens as one step, with nothing able to sneak in halfway". The fix is not a lock. A lock around a counter that every request touches is a throughput disaster and a new way to fail. The fix is to stop reading and writing separately at all. With INCR, one round trip both counts the request and tells you where you stand. No read, no race, no lock.

When Redis goes down#

Redis is now a dependency of every request. Sooner or later it will be unreachable for a minute, and you have to decide in advance what the gateway does. (The availability chapter explains why every box in the request path drags your uptime down.)

Break it: the limiter becomes the bottleneck#

One Redis round trip per request means the counter store now carries your entire traffic. At 50,000 requests a second that is fine. Drag the dial and watch where it stops being fine.

Sharding means splitting the keys across several Redis machines, each owning a slice of the users (sharding covers it from the start). It works especially well here because counters never need each other.

The second change is worth stating as a principle. The exact shared count only matters for users close to their limit. Everyone else can be waved through on local knowledge, and that is almost everyone.

Trade-offs#

The level bar#

One moment from this round, answered three ways. Pick the one you think is staff level before the labels appear. (What changes at senior and staff explains the gap.)

Then run the question cold, with a 45 minute timer and no notes, and score the run on the five things this question is really testing.

Interview replay#

Checkpoint#