Rate Limiting: Saying No Gracefully

Marlow Books is a four person online bookshop that exists only in this course, and on the first Saturday in June its founder finally did something about the robot.

Lesson 010 has the story it came from. A publisher page shipped at ten to five on a Friday in May, a search engine crawler found a link to it on every one of 1.2 million book pages, and by Monday morning twelve of box A's sixteen cores belonged to a machine that had not raised its rate by a single fetch. The index that fixed it went in at 23:10 that Monday.

What stayed with the founder was not the query. It was that there had been no lever. The shop could make the page cheaper, and did. It could not tell the robot to go away.

So on that Saturday in June they went into the managed balancer that lesson 006 put in front of both boxes in January, found the box marked requests per second per client, typed 10, saved it, and tested it by holding down F5 until the shop returned 429 Too Many Requests. It worked. They went to lunch.

The rule then did nothing at all for six and a half months.

On the Monday of Christmas week the founder was watching the balancer's dashboard, because it was the busiest morning of the year and that is what you do. Some time after ten the 429 line, flat at zero since June, lifted to roughly fifteen a minute and stayed there. They noticed it around eleven, and twenty minutes of clicking later they understood: every single one of those refusals was a customer, most of them from a handful of addresses belonging to mobile carriers, and every one had been told to go away on the shop's most profitable morning.

They turned the rule off at 11:20. Fifteen a minute across those eighty minutes is about twelve hundred people.

The crawler, over that same window, was refused zero times.

The only tool in the box that can say no

Twenty lessons of this course have been about making work cheaper or moving it somewhere else. Lesson 008 cached the book pages, lesson 010 indexed them, lesson 006 spread them over two boxes, lesson 017 put a queue behind the slow parts, and lesson 020 capped how much extra load a retry policy may offer a dependency.

Not one of them can refuse a request.

A rate limit is a rule that refuses a request because of who asked and how often they have asked, rather than because anything is wrong. That second clause is the whole character of it. The shop was not full on that Monday at eleven. Box A was fine. The limiter refused those twelve hundred requests because a counter said so, which is exactly what it was built to do.

Lesson 006 promised you this: once every request enters through the balancer, the balancer is the best place you have to count things and refuse them politely. Lesson 004 promised the other half, the 429 that means later rather than never, and lesson 020 built the client that listens. Today is the server that speaks.

The bucket, and the number everybody leaves alone

The mechanism worth knowing properly is the token bucket, and it is two variables.

capacity   b = 20 tokens
refill     r = 10 tokens a second, up to b
cost       1 token per request; no token, 429

A bucket holds up to b tokens and gains r of them a second. Every request spends one. Ask slowly and you find a full bucket and never notice the rule exists. Ask faster than r and you drain it, and from then on you get exactly r a second, because that is the rate the tokens arrive at.

The part that decides what your server actually feels is the emptying. A caller sending R a second, with R above r, drains the bucket at R minus r, so it empties after b divided by that difference:

The bottom row is the interesting one. A caller who is ten percent over the limit gets twenty seconds of being over it before anything happens to them, and if they back off for two seconds in the middle they get a fresh twenty. That is not a bug. It is the burst you asked for.

The rate decides what a caller gets in the long run; the burst decides your worst instant. A bucket of twenty at ten a second means somebody who has been quiet for two seconds can put twenty requests on your service inside a single millisecond, and your capacity plan had better hold twenty rather than ten.

Every team I have watched configure one of these spent the conversation on r and took whatever b the library shipped with. It is the wrong way round. r is a fairness decision you can change any afternoon; b is what lands on your boxes.

Windows, and why the boundary is not the real problem

Two other shapes are common enough to recognise.

A fixed window counts requests per clock minute and resets at the boundary: a counter and the minute it belongs to, which is about as cheap as state gets. Its famous flaw is that a caller who sends six hundred in the last moment of 10:00 and six hundred in the first moment of 10:01 has sent twelve hundred requests inside one second while never breaking the rule.

A sliding window counts over the trailing sixty seconds instead, so there is no boundary to straddle. Done exactly, that means keeping a timestamp per request per caller and dropping the ones older than a minute. The cheap approximation everybody actually ships keeps the current window's count plus a weighted share of the previous one, which gets close without storing anything per request.

Look down the third column, because the received wisdom about these three is slightly off. The boundary is not the fixed window's real weakness. Its real weakness is the sliding window's too: both let a caller spend the whole allowance in one instant and neither gives you a dial to say otherwise. Six hundred a minute reads like ten a second and permits six hundred at once. The boundary only lets you do it twice back to back.

The bucket is the only one of the three where the sustained rate and the worst instant are separate numbers you set on purpose. That is the reason to prefer it, and it has nothing to do with the boundary.

What about memory? At Marlow's scale, nothing separates them. A sixty second sliding window over Christmas week's 400 requests a second is 24,000 timestamps for the entire shop. The memory argument belongs to systems two orders of magnitude larger, and to lesson 063.

The cost that does bite at a bookshop is a different one. Marlow has two boxes. If the limiter runs inside the application, each box has its own counter and every caller gets twice the limit. Twenty boxes make it twenty times. A limiter that counts per caller needs one counter that every box can see, which is lesson 007's relocation problem arriving in a new outfit, and it is the reason limiters live at the balancer or the edge rather than in your handler.

Per what

Everything above is arithmetic. This is the part that decides whether the arithmetic is aimed at anything.

The founder's rule counted per client address, which is the default in every balancer and the first thing anybody reaches for. Work out what that rule was actually saying at Marlow.

Lesson 010 established that the crawler holds about a dozen fetches open at once and gets forty a second out of them. Say those dozen come from a dozen different addresses, which is how the large crawlers work and which nobody at the shop ever checked. Then each address was asking for 3.3 pages a second, against a limit of ten. The rule could not see the robot. To catch it you would have to set the limit below 3.3 a second per address, and at lesson 007's one request per person every 133 seconds, 3.3 a second is four hundred and forty people reading at once.

So the threshold has to go on the wrong side of one of them. A crawler looks like a small office and an office looks like a big crawler, and a counter keyed on an address cannot tell you which one it has.

That explains why the rule never fired on the robot. It does not explain the twelve hundred customers. Four hundred people behind one carrier address average three requests a second, and the balancer's ten a second is a bucket of ten refilling at ten, which three a second never empties.

Averages are not what a bucket sees. Four hundred strangers do not take turns. They arrive in clumps, the way lesson 015's ninety flash sale buyers did, and a bucket of ten is a bet that eleven of them will never press a link in the same instant. Nobody had measured how clumped the arrivals were, and on the busiest morning of the year the bet came in. A per-address limit's real threshold is not a rate, it is a coincidence count.

Then it fed itself. A customer who gets a 429 sees a bare error page. Lesson 020 named what that customer does next: somebody who has watched a broken page for thirty seconds hits reload. That reload spends a token the address does not have, which refuses them again. The limiter and the human retry layer had built a small, perfectly stable loop that punished the innocent, while the robot, which honours nothing and reloads nothing, sailed straight through the middle of it.

The unit is a guess about what a request costs

The June rule had a second problem, independent of the first.

Requests are not the same size. Lesson 010 priced a cached book page at two milliseconds and the unindexed publisher page at 290, a factor of a hundred and forty five, and lesson 006 put a full text search over 1.2 million descriptions at about sixty milliseconds. A limit denominated in requests a second charges all three the same, so it is at once far too generous on the expensive path and far too mean on the cheap one.

Two ways out. Limit per endpoint, so the search gets its own tighter number, which is easy and underused. Or charge different requests different numbers of tokens, so a search costs thirty and a book page costs one, which is more honest and means your limit is denominated in something closer to work. I have shipped the first far more often than the second, mostly because per endpoint limits are a configuration line and weights are a conversation about what a millisecond is worth.

Which leaves the case where there is nothing else to count

By now per-address limiting looks indefensible, and I have been unfair to it. One set of paths has nothing else to count.

Sign in. Password reset. Sign up. A guest checkout. On every one of those the caller has no account yet, or is in the middle of proving they have one, so there is no customer to count and no API key to count. These are also the paths you most want limited, because somebody working through a list of leaked passwords is doing exactly that: many attempts, no identity. The requests you most want to limit are the ones you cannot attribute, which is why per-address limiting survives despite everything above.

What changes is the threshold, and what sets it is not the cost of the request. It is the cost of being wrong. Five sign in attempts a minute from one address will occasionally catch a genuine cluster of people behind a shared connection, and those people are asked to wait thirty seconds on a form they were already concentrating on. A book page refused looks like a broken shop. Same mechanism, same false refusal rate, completely different bill.

Marlow's rule, written down properly in February, is a deletion, two limits and a line in a text file. The site-wide limit goes. A tight per-address limit on sign in and password reset, where there is nothing else to count and a wait is survivable. A per-address limit on full text search, the one expensive public path left after May's index. And a robots.txt entry disallowing the publisher page's sort and paging parameters, which takes lesson 010's hundred and twenty thousand URLs out of the crawl frontier for free, and works only because that particular robot is well behaved, which is the entire reason limiters exist for the ones that are not.

Three things were wrong with the June rule, and each of them is the normal way this gets built. It was aimed at a threat an index had already removed in May, denominated in a unit that could not see that threat, and set against a coincidence rate nobody had measured.

A policy and a reaction are not the same rule

A rate limit is a policy. You decide in advance what a caller is entitled to, and you enforce it whether you are idle or on fire. Its trigger is a counter, and the counter knows nothing about how your service is feeling.

Load shedding is a reaction. You notice you are in trouble and start refusing whatever you can, on the grounds that serving nobody slowly is worse than serving most people quickly. Its trigger is a measurement of yourself: requests in flight, queue depth, how far your latency has drifted from normal.

The confusion runs both ways. Marlow's Monday was the first in its purest form: a quota used as protection refuses people while the machine it is protecting is bored. The second is worse and less obvious. Protection used as a quota is fair to nobody, because a shedder sheds whoever happens to arrive during the bad second, so the caller sending a thousand a second and the customer sending one lose the same fraction, and the customer is the one who notices.

You want both, wired to different things.

A rate limit protects your callers from each other. Load shedding protects you from all of them. A limiter cannot save a saturated service, because the whole point of it is that it does not know the service is saturated. A shedder cannot deliver fairness, because at the moment it fires it has no time to work out who deserves what.

If you are going to pick a signal to shed against, lesson 002 already gave you the right one. Requests in flight beats CPU, because Little's law ties concurrency to latency, so a climbing number tells you the queue is growing before the CPU graph gets interesting, and lesson 001's hockey stick is why you fire well before the obvious threshold. Lesson 041 owns backpressure and lesson 042 the circuit breaker, so I will stop there.

One piece of caution, and lesson 006 got there first. Its panic threshold exists because a balancer that believes its own health checks will remove an entire healthy fleet the moment the checks break. A shedder is the same shape and wants the same escape hatch: never let it refuse everything, because the likeliest explanation for a signal saying refuse everything is that the signal is broken.

The callers you own

Galewatch, which collects a reading from each of nine hundred wind turbines every two seconds, is where this topic stops.

Rate limit that ingest path and you have protected nothing. Lesson 007 established that a turbine's flash memory holds the only copy of a reading while the farm's link is down, so a 429 to a turbine either gets resent, which is the load arriving anyway a minute later, or gets dropped, which loses the product. Lesson 017 priced a four hour outage at Tarrow Ridge, a farm of sixty turbines: 432,000 buffered readings against a path that stores five thousand a second.

A limiter is for callers you do not control. When you own both ends the honest answer is a queue and backpressure, lesson 017 and lesson 041, and the reason is not politeness. There is nowhere for the refused work to go.

What a good no looks like

Lesson 020 built a client that honours Retry-After and handed this side of the header to today.

The code is 429, which lesson 004 already filed as the 4xx that will succeed later: nothing was wrong with the request, only with when it arrived. A 503 says something different, that the service cannot serve anybody right now. The distinction matters to the caller, because a 429 is information about themselves that they can act on and a 503 is not.

Retry-After takes either a number of seconds or a date, and a limiter is in the unusual position of knowing the answer exactly. It has a bucket. It can compute when the next token lands. Sending that number costs nothing and it is the difference between a caller who comes back once at the right time and one who comes back immediately, which is the default.

Beyond the header there is a convention, spelled slightly differently by everybody who has implemented it, of returning the limit, how much is left and when it resets. Send those on every response, not only the refusals. A caller who can see their remaining quota slows down before they are refused; one who only finds out by being refused can only probe you.

Then the thing that costs nothing and gets left out. Say which limit was hit, and if the caller is a person say it in a sentence rather than an empty page. The founder's 429 returned the balancer's default error body, which is why twelve hundred customers concluded the shop was broken and none of them emailed to say so. Lesson 010 is blunt about that: customers do not email you when a site is slow, they leave.

And the worst option of all is the one that looks like the cheapest.

Drop the connection. Reset the socket. Stop answering. Lesson 004 called that the failure with no status code, and lesson 019 called it the unanswerable question, and lesson 020 explained what a client does with one: it cannot tell a refusal from a hang, so it waits out its full timeout and then retries, and the retry is a fresh connection. The most expensive way to refuse a request is to refuse it silently. A 429 with a number in it is a rescheduling. A dropped packet is an invitation.

Sized by what you refuse

Stagefront is a ticketing service that exists only in this course, where a stadium show goes on sale at exactly 10:00 and two hundred thousand people press the same button in the same minute. Lesson 017 did the arithmetic: 3,333 requests a second arriving, a purchase path converting five hundred a second, forty thousand seats, so the sale is over in eighty seconds and a hundred and sixty thousand people were never getting a ticket.

Put a global limiter in front at five hundred a second. It admits five hundred a second, which is correct, and refuses 2,833 a second, which is also correct. Now add lesson 020's phone app, which tries three times, and the person behind it, who tries until they believe the answer. A hundred and sixty thousand disappointed people at three attempts each, over eighty seconds, is six thousand refusals a second.

The limiter is now the busiest component in the building, and every one of those six thousand refusals has to cost nearly nothing. A limiter is sized by the traffic it refuses, not the traffic it admits, which is the most consistently missed thing about them and the reason they belong as far out as you can push them. On a reused connection a 429 is a handful of bytes. On a fresh one it is the four round trips lesson 004 priced before you get to say no, and there is a rate above which you cannot refuse fast enough to survive. Lesson 022 moves that boundary outward and lesson 057 owns what lives beyond it.

Which brings back the room lesson 017 argued for and never built. A waiting room and a limiter run the same arithmetic and differ in one respect: the limiter says no and the room says wait, with a position and a closing time. Six thousand refusals a second is what the first one turns a hundred and sixty thousand people into. A limiter is the right answer when the caller is a program. A waiting room is the right answer when the caller is a person. Stagefront has built neither. After the March incident in lesson 020 it changed one number in a payment client, and the on-sale minute is still a hundred and sixty thousand people finding out one refusal at a time.

Where the number comes from

Nowhere, usually. Ten a second came off the same shelf as lesson 019's ten second timeout, and lesson 020 already made the general point: a limit nobody chose is a limit you inherited.

The number in a limiter is a capacity number wearing a fairness costume, and lesson 055 owns capacity. The cheapest first step is the one nobody takes: run the limiter in a mode that counts and logs and refuses nothing, for a week. Then look at the spread of per-caller rates you actually have, set the limit above the busiest legitimate one, and choose the burst on purpose rather than inheriting it from a library.

A week of counting in June would have shown the founder two things. The busiest sustained callers were the crawler's own addresses, at 3.3 a second. The addresses that occasionally spiked past ten were carrier pools full of customers. Both facts sat in the same graph, and either one of them kills the rule.

Recap

A limiter is the only thing in your architecture that can say no. Caches, indexes, replicas, balancers and retry budgets make work cheaper or move it. A rate limit refuses a request because of who asked and how often, not because anything is wrong, which is why it can fire on a perfectly healthy morning.

The rate decides what a caller gets; the burst decides your worst instant. Everybody tunes the rate and inherits the burst, and the burst is what lands on your boxes. Both window shapes permit their whole allowance in one instant with no dial to say otherwise; the bucket is the one that gives you the dial.

A limiter per address is a limiter per office, and its real threshold is a coincidence count rather than a rate. A crawler looks like a small office and an office looks like a big crawler. Keep per-address limits for the paths with no identity to count, and set them by what a false refusal costs rather than by what the request costs.

A rate limit is a policy and load shedding is a reaction. One is a counter that ignores how you feel; the other is a measurement of yourself that ignores who is calling. Neither will do the other's job.

A limiter is sized by the traffic it refuses. Stagefront's five hundred admissions a second come with six thousand refusals once you count the retries, so the refusal path has to be the cheapest, simplest code you own, as far out towards the client as you can get it.

The most expensive way to refuse a request is to refuse it silently. A 429 with a Retry-After, the remaining quota on every response and a sentence saying which limit was hit produces a caller who comes back once, at the right time. A dropped connection produces one who waits out a full timeout and then opens a new connection to try again.

Check your understanding

1. A service sets a token bucket at 100 requests a second with a burst of 1,000 for each customer, and has forty customers. Work out the worst instant the service must survive, then say what you would change and what you would need to measure before changing it.

2. Marlow's founder proposes putting the site-wide per-address limit back, at 50 a second instead of 10, on the grounds that the Christmas refusals were just a threshold that was too low. Say what that change fixes, what it does not fix, and what you would build instead.

3. Your API returns 429 with Retry-After: 60 to a caller who is over quota, and the caller's client retries immediately anyway, every time. Describe two changes you could make on your side, one that reduces the damage and one that reduces the load, and say which you would ship first.

4. A colleague wants to shed load when CPU goes over 80% and rate limit each customer to a share of capacity, both computed from the same capacity number. Say where those two rules will disagree with each other, and which of them you would let win during an incident.

5. Galewatch's nine hundred turbines are joined by three hundred belonging to a customer who runs their own hardware and their own firmware, which Galewatch cannot change. Say whether those three hundred should be rate limited, what the limit would have to do about a reading it refuses, and which earlier lesson owns the alternative.

Next lesson

022 CDNs and Edge Caching: Moving Bytes Closer. Today ended on a refusal that has to be cheap and as far out towards the caller as possible; next lesson moves the successful responses to the same place, and finds that the hard part is not the moving.