Design a rate limiter

Why did three accounts get most of the coupons?

It is festival morning. At nine o’clock the kitchen announced a coupon: the first 300 orders of the day get a free box of sweets. Two servers had been added in the spring, so the order API could take about 800 requests a second.

By 9:02 it was taking 900. A student ordering from his hostel watched the spinner turn and then saw “Something went wrong”. He tried four times. So did hundreds of others.

The kitchen screen filled with tiny orders: one chapati each, to the same three addresses. Nobody eats one chapati for lunch. A script was sending about 400 requests a second to the coupon endpoint from three accounts. By 9:05 the coupons were gone.

That afternoon the accountant went through the orders. 214 of the 300 coupons went to those three accounts. Real customers paid for the slow site and got nothing.

The first suggestion is the cloud firewall: switch it on in front, and it blocks bots. A firewall does not know what a coupon is. Nothing in the system limited how many requests one person may send, so every request was treated the same and the fastest client won.

That is the job of a rate limiter: decide how many requests each client may send in a period of time, and turn away the rest cheaply, before they cost the kitchen anything.

It sounds like one counter. Before reading on, guess what a limit of 100 a minute becomes on four servers behind a load balancer, when each server keeps its own count. On a fleet of servers the counter raises three harder questions: where the shared count lives, how it stays right when requests arrive at the same moment, and what to do when the counter itself breaks.

Pause and predict Which rule stops the script from taking the coupons and still lets the student order?

What must never go wrong?

The System Context diagram shows the API and everyone who calls it, including the client we would rather not serve.

The requirement that matters most to the people running the kitchen: the limiter must never be the reason a paying customer cannot order.

Core entities, in two minutes

A Rule (route, what to count by, limit, window, what to do if the counter store fails), an Override (one client’s different limit), and a Counter (one per client per rule, short-lived).

The estimate that changes the design

Every request now costs one extra trip to a shared counter. Is one counter store enough?

For the kitchen: 50,000 clients x 3 counters x about 100 bytes is 15 MB, and 900 checks a second is under 1% of what one Redis node can do. One node with a replica is enough, with no sharding. A public API with 10 million active clients and 500,000 requests a second needs 4 GB of counters and about 10 nodes, sharded by client key. The design is the same; only the number of machines changes.

The obvious version, and how it breaks

The first fix takes an hour. Each API server keeps a dictionary in memory: client id to a count of that client’s requests this minute. If a client’s count goes over 100, the server refuses the request.

It works on a laptop. In production there are four servers behind a round-robin load balancer, and each one counts only the requests it sees.

Pause and predict The limit is 100 requests a minute, and four servers take turns. How many requests a minute can one client get through?

Three things go wrong:

• The limit multiplies. With four servers taking turns, a client gets 4 x 100 = 400 requests a minute, not 100. Adding servers to survive the festival also loosens every limit.
• Counts vanish. A deploy or a crash wipes a server’s dictionary, and every client on it starts again from zero.
• Sticky routing does not save it. Sending each client to one server fixes the count until that server dies, and it puts a heavy client’s whole load on one machine (lesson 1.1).

The servers are stateless on purpose: any server can handle any request, because none of them keeps data that outlives a request. A client’s count must outlive many requests, so it has to live somewhere every server can reach.

A mental model

Token bucket

Each client has a bucket that holds up to B tokens and refills at r tokens a second. A request takes a token; with no token, it is refused.

For example: B = 10 and r = 2 a second: a quiet client can send 10 at once (a burst), then about 2 a second after that.

When the counter store is down, open or closed?

Every rate limiter must answer this in advance, and two goals pull against each other: orders that keep flowing, and coupon stock that cannot be taken back.

The answer is to decide per route, based on what each route’s limit protects, instead of once for the whole API. The limit on orders protects capacity. A short limiter outage puts that capacity at a small risk, while refusing orders loses sales for certain, so order routes fail open. The limit on coupons protects a scarce stock that cannot be taken back once it is given away, so coupon routes fail closed.

What to remember

1. A rate limiter decides, per client and per route, how many requests to allow in a window, and refuses the rest early and cheaply.
2. On a fleet, the count is shared state: counters in each server’s memory multiply the limit by the number of servers.
3. The token bucket allows short bursts and holds the long-run rate. Check and update it in one atomic step (a Lua script in Redis).
4. Refuse with 429 and Retry-After. When the server is the problem, answer 503.
5. Decide in advance how each route fails when the counter store fails: fail open on routes that protect capacity, and closed on routes that protect something scarce.

Refuse before the request costs anything, and keep the count where every server can see it.

In the real world

Production limiters add layers our toy leaves out: concurrency limits (how many requests a client may have in flight at once, as well as per second), load shedding that drops low-priority traffic when the whole fleet is hot, separate limits per tier of customer, and abuse detection that looks at behaviour rather than counts. Stripe describes running several of these together.

The token bucket reappears later in this course: notification providers limit you (Part 4), an LLM service gives each tenant a quota (Part 7), and retries need their own budget (Part 7). An LLM agent’s token budget is this limiter with tokens or rupees as the unit instead of requests.