Rate Limiter

What the interviewer is asking

"Design a rate limiter" usually means: your company runs a public API that customers call from their own code, each with an API key, and one customer's runaway script must not slow down everyone else. For every request, the limiter decides whether the client is still within its rate.

The algorithm is the easy part (the Rate Limiting lesson covers it). The interviewer listens for the system around it: where the counts live when the API runs on dozens of servers, how two servers avoid both letting the last request through, and what happens when the counts' store goes down. The walkthrough follows the 8 steps of the interview framework: scope, data, API, the busy path, numbers, services, scale and deep dives.

1. Scope: what version 1 must do

• Limit each API key to its plan's rate: say 100 requests a minute on the free plan and 1,000 on the paid one.
• Limit signed-out calls by IP address, or a script just leaves the key out. Keep it looser: one address can be a whole office.
• Refuse clearly: over the limit, answer 429 Too Many Requests with a Retry-After header that says when to come back.

Name the rest and park it: limits per endpoint (the same mechanism with more buckets), a dashboard of each key's usage, and billing by usage. Billing sounds close but isn't: it must record every call exactly, while a limiter only asks whether there is room right now.

2. Data: a token bucket per key

A token bucket fits most APIs. Each key's bucket holds up to 100 tokens and refills at 100 a minute; each request takes a token, and a request that finds none gets 429. If Acme's free key empties its bucket and comes back 30 seconds later with 80 requests at once, half a minute has earned it 50 tokens: 50 get through and 30 get 429. Short bursts pass, and the average holds at the refill rate.

what              per        changes
tokens left       API key    every request
last refill time  API key    every request
the plan's rule   plan       rarely
key → plan        API key    rarely

Rules change rarely, so every API server keeps a copy in memory and reloads it every minute. The two numbers per key change on every request, so they need the fastest store you have. (A fixed window would keep a count and the minute it started: also two numbers.)

3. The API: a check, not an endpoint

The rate limiter adds no calls of its own. It's middleware, code that runs before your API's own code in each server, or a step in an API gateway in front of them. Clients see it only in the replies:

GET /v1/orders
X-Api-Key: k_acme

HTTP/1.1 200 OK
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 99

(the 101st request of a burst)

HTTP/1.1 429 Too Many Requests
Retry-After: 1

Headers like X-RateLimit-Remaining are a common convention, not a standard, but they let a well-behaved client slow down in time. Retry-After gives the seconds to wait: at 100 a minute a token comes back every 0.6 seconds, so the reply rounds up to 1.

4. The busy path: every request

1. The client sends its call with its API key.
2. The load balancer passes it to one of the API servers.
3. The limiter tops up the key's bucket for the time since its last refill.
4. If a token is left, it takes one and the API's own code handles the call; if not, it answers 429.

Every request takes this path, refused or not, so the limiter sits on the busy path of the whole API. That sets its budget: about a millisecond at most.

5. The numbers

Numbers from the interviewer: 10 million API keys and 50,000 requests a second at busy hours.

• Bucket updates: one check per request, so about 50,000 a second. Dividing by 60 because limits are per minute (about 800) is a common slip. No job refills all 10 million buckets every second either: a bucket changes only when its key sends a request, and the refill is worked out at that check.
• Memory: about 100 bytes per bucket (the key, the two numbers and the store's bookkeeping), so 10 million × 100 bytes = about 1 GB. A record of every request for a day would take about 400 GB (50,000 × 86,400 seconds × 100 bytes).
• API servers: say one handles about 1,000 requests a second, so about 50 of them.

1 GB fits in one server's memory many times over; the hard number is the rate.

6. Services: where the buckets live

The limiter runs inside each API server. First idea: each server keeps its buckets in its own memory, with no trip at all. Run it with 4 servers, round robin, and a small bucket of 10 tokens. Acme sends a burst of 60 requests in one second:

requests   per server   let through   limit
1–4        1 each       4             10
5–12       3 each       12            10
all 60     15 each      40            10

Each server refuses only when its own bucket is empty, so each lets 10 through: 4 × 10 = 40, 4× the limit. With the 50 or so servers this API needs, a key could get 50× its limit.

So the buckets go into a shared in-memory store that every API server reads and updates, the counter store (Redis is a common example). One cache server answers about 100,000 operations a second, twice the 50,000 needed. The main database would need about 10 servers for this (at about 5,000 lookups a second each), and every request would wait on a database write. Sticky routing (all of a key's requests to one server) works until a server is added or fails: its keys move and their buckets start over full.

7. Scale: one millisecond, three shards

The counter store sits in the same data center as the API servers, where a round trip takes about 0.5 ms. A check that reads the bucket, then writes it back makes two trips: about 1 ms, the whole budget. Reading memory takes about 100 ns; the trips are what cost, and the deep dive below cuts them to one.

Then the interviewer adds: traffic will triple, to 150,000 checks a second. One cache server takes about 100,000, so split the buckets over 3 shards of about 50,000 a second each. Split them by API key, a hash of the key picking its shard (the Sharding lesson): each bucket lives whole on one shard, a check is still one trip, and 10 million keys spread evenly, about 330 MB per shard. Splitting by time would put every current check on one shard, all 150,000 a second; spreading a key's updates over all 3 gives it three buckets and 3× its limit.

8. Deep dive: the race between two servers

Acme's burst has used 9 of its 10 shared tokens, and requests 10 and 11 reach two servers at the same moment:

step   Server 1           Server 2           store (acme)
1      reads 1 token                         1
2                         reads 1 token      1
3      lets 10 through,                      0
       writes 0
4                         lets 11 through,   0
                          writes 0

Both servers read before either wrote, so 11 requests got through a bucket of 10, and the store says 0 as if nothing went wrong. Reading again before the write shortens the gap without closing it, and a bucket of 9 only hides the bug. The fix is one step inside the store:

def take_token(key):                   # runs inside the store, as one step
    now = store_time()                 # the store's clock, not each server's
    tokens, last = get(key) or (SIZE, now)
    tokens = min(SIZE, tokens + (now - last) * RATE)
    if tokens < 1:
        set(key, (tokens, now))
        return False
    set(key, (tokens - 1, now))
    return True

Redis, a common choice, runs such a script (written in Lua) as one step, with nothing in between. Whichever script runs first takes the last token and the second finds 0: exactly 10 get through, in either order. For a fixed window it's simpler still: an atomic increment that returns the new count (INCR in Redis), with the counter set to expire when its minute ends. Either way it's one trip instead of two, about 0.5 ms.

The script also settles clock skew: if each API server stamped the refill time with its own clock, a server whose clock runs ahead would top up buckets too much. Use the store's clock, one clock for every bucket.

9. Deep dive: when the counter store is down

Say shard 2 crashes. About a third of the keys live there, and every check for them waits on a shard that won't answer.

• Fail open: if the store doesn't answer within a few milliseconds, let the request through and raise an alert. For a public API's usage limits this is the common choice: a helper part shouldn't take the API down. The price: those keys aren't limited until the shard is back, so each server can apply a rough limit of its own meanwhile.
• Fail closed: answer 429 until the shard is back. About a third of your customers are refused for nothing they did, and the limiter becomes the outage. It's right where a limit guards something, such as sign-in attempts.
• Wait: never. At 50,000 requests a second, waiting calls pile up within seconds and every customer hangs, not just a third. The check needs a short timeout.

Give each shard a replica that takes over in seconds, and the fail-open window stays short.

What breaks first

• A hot key: one huge client lands all its checks on one shard, and one that keeps hammering after its 429s keeps the shard busy with refused requests. Once a key is over its limit, each API server can answer its 429s itself until Retry-After.
• Memory for idle keys: a full bucket needs no record, so let each bucket expire a minute after its key's last request, when it has refilled anyway. The store then holds only the keys active in the last minute.
• Distance: a store across an ocean, about 150 ms a round trip, would break the 1 ms budget more than a hundred times over. With several regions, a common approach is to count in each region separately.

Summary: the order to follow

1. Scope: limit each API key by its plan (IP when signed out), 429 with Retry-After; park per-endpoint limits, dashboards and billing.
2. Data: a token bucket per key, two numbers (tokens, last refill time); a rule per plan.
3. API: no new calls; a check on every request, rate-limit headers in each reply.
4. Busy path: every request, so the check adds about a millisecond at most.
5. Numbers: about 50,000 checks a second, about 1 GB of buckets.
6. Services: the limiter in each API server, the buckets in a shared in-memory counter store.
7. Scale: 3 shards, split by API key.
8. Deep dives: top up, check and take in one step inside the store; fail open when the store is down, with a rough local limit.

The same pattern, a shared counter updated in one step, comes back in view counters and flash-sale stock.