Marlow Books, the four person online bookshop that exists only in this course, has bought its stock through one distributor since its first year, and the arrangement is a file. At six every morning a CSV lands with about two hundred and fifty new titles and stock corrections on roughly eight thousand rows. Lesson 009 told the story of the April morning when that file said twelve and the shop's cache still said sixty.
In October the distributor shipped an API. One call, one ISBN, the stock figure as of now. Marlow's plan allowed ten requests a second, which the founder thought was generous, because what he had wanted since April was a way to check a number before a customer bought against it.
He wrote the job in an evening and started it at ten on the Monday night, 5 October. It walked the catalogue oldest figure first, one ISBN at a time, six requests a second.
Five out of every six came back 429 Too Many Requests.
He killed it at twenty to midnight. It had re-checked about six thousand titles out of 1.2 million, which is what one request a second buys you in a hundred minutes.
His email was reasonable and so was the reply, which came on Wednesday 14 October: their logs put Marlow's busiest second that week at about one request, a tenth of its limit of ten. Both sentences were true.
What he did next was guess. He split the job into twelve workers, each opening its own connection, on a feeling that the limit might be counted per connection. The refusals stopped, the job settled at about twelve requests a second, took a day and a bit, and he thought no more about it.
On Sunday 25 October he wanted the whole catalogue re-checked before the Christmas orders went in, so he set the worker count to a hundred and twenty and started it at ten at night. It ran at forty four requests a second, four and a bit times his plan, and nothing refused it once. It finished at 05:34 on the Monday, twenty six minutes before the morning file landed.
Nobody at the distributor noticed, and their own dashboard is why. The API runs on forty eight copies. The limiter inside each copy divides a caller's plan by the number of copies and then applies a floor of one request a second, because ten divided by forty eight rounds to nothing and a plan that rounds to nothing refuses everybody. So every copy gave Marlow one a second. One connection reached one copy. Twelve reached close to twelve. A hundred and twenty covered all but about four of them, which is where the missing four a second went, and forty four a second is what a ten a second plan is really worth over there.
Two lines of code, both of them sensible, producing the two opposite failures of a distributed limiter at once: refusing a caller a long way inside the limit, and admitting one at over four times it. The floor that stops the division refusing everybody is the thing that sets the real ceiling, and the real ceiling is a number nobody at the distributor has ever written down.
The founder is the only reason anybody knows. He asked, in an email, whether the all night run had been all right.
You are designing the limiter they should have had.
The brief, and the two lines nobody puts on it
An API with twenty thousand paying callers, each holding a key. Peak load a hundred and twenty thousand requests a second at the edge. Nearly every caller is on the standard plan, a hundred requests a second with a burst of two hundred, and four of them are on a plan of twenty thousand a second with a burst of forty thousand. The decision has to be made on every request, before anything expensive happens.
The fleet is sixty of lesson 005's sixteen core boxes, four processes to a box, which is the shape lesson 001 gave Marlow. Two thousand requests a second a box at the peak is my figure and the only thing that sets the sixty. The number that matters is the other product: two hundred and forty copies of the limiter are running. Lesson 049 is blunt about which number that is, because a limiter inside the application gives every caller one full allowance per copy, and 049 corrected lesson 021's arithmetic to say Marlow's real multiplier is eight processes rather than two boxes. Count processes.
One thing this is not for. Galewatch, the telemetry company in this course that takes a reading every two seconds from each wind turbine on the farms it monitors, must never have a limiter on its ingest path, and lesson 041 gave the reason: a limiter is for callers you do not control and backpressure is for the ones you do, because only one of them has somewhere to put the work. Lesson 017 priced what a refusal there would have to put somewhere: 432,000 readings buffered in one farm's flash over four hours. Everything here assumes a caller who survives a refusal.
Then two requirements that appear on no brief and between them decide most of this design.
The limiter answers on the path of every request, so its availability multiplies into the API's. Lesson 003 prices a tier at 99.95 percent at 4.4 hours a year, and when every number is near one the product is near one minus the sum of the gaps, which is 003's own shortcut. Add a counter tier to the request chain and you have bought 4.4 hours a year of whatever that tier's failure does to you. The decision is not whether to accept it. It is what those hours look like.
You have sold far more requests a second than you own. Nineteen thousand nine hundred and ninety six callers at a hundred a second plus four at twenty thousand is 2.08 million a second of quota, against a fleet that peaks at a hundred and twenty thousand. Seventeen times. That is not alarming, because selling a ceiling is not selling a reservation and the callers are never all busy at once. It does mean the thing you are building cannot protect you, and no amount of accuracy changes that.
Four lines on an envelope
Lesson 025's order, bytes first and money last.
Bytes. A token bucket per caller is a count and a timestamp, sixteen bytes of content, call it sixty four once the store has taken its own overhead. That sixty four is mine. Twenty thousand callers is 1.3 megabytes, which is not a line item, it is a rounding error on one.
Lesson 021 left the other shape here on purpose. An exact sliding window keeps a timestamp per request per caller and drops the ones older than the window, and 021 measured the whole of Marlow at 24,000 timestamps for a sixty second window at its Christmas peak of four hundred a second, then said the memory argument belongs to systems two orders of magnitude larger and to this one. So: a hundred and twenty thousand requests a second over sixty seconds is 7.2 million timestamps, three hundred times Marlow's, which at sixty four bytes is 461 megabytes.
That is affordable. The reason to refuse it anyway is that the structure's size is set by your traffic rather than by your customer list, and the customer list is the quantity you control. Your plans are a table you own; your traffic is other people. Every other piece of state here is twenty thousand rows whatever happens.
Operations. The number the design turns on, and lesson 047 published the input. Dispatching one GET costs Redis single digit microseconds, which 047 priced at under two percent of its single command loop for the 3,333 requests a second at Stagefront, the ticketing service in this course where two hundred thousand people press the same button at ten in the morning. Take five microseconds and one loop serves about two hundred thousand commands a second. A token bucket is a read, an arithmetic step and a write, run as one script so the three cannot be split: call it fifteen microseconds and sixty six thousand a second. That fifteen is mine and the first figure I would measure.
A hundred and twenty thousand decisions a second does not fit on one of those. It fits on two, with a third for the failure. Counters shard beautifully, which is the one easy thing here: lesson 014 says a shard key is a promise about what stays together, and a caller's counter stays with nothing at all, so lesson 031's ring takes it and never argues.
Latency. Lesson 002 puts a round trip inside one data centre at half a millisecond. Against an API request of forty milliseconds, which is my figure, asking a counter on every request is a 1.25 percent tax, and the fleet wide cost is 002's busy room run forwards: a hundred and twenty thousand a second times half a millisecond is sixty requests in flight doing nothing but waiting. Sixty. The famous objection to the exact design is latency, and the latency is nothing.
Money. Three counter nodes and three replicas at lesson 005's $500 is $3,000 a month against the gateway tier's $30,000. A tenth, for the component the product's whole fairness story rests on. Then lesson 056's afternoon: somebody owns the plan table and answers the caller wanting an exemption for one Tuesday. That line never gets approved and never goes away.
The envelope has done its job and the expensive term is not on the diagram. It is the twenty thousandth caller's belief about what their hundred a second means.
The one thing sharding cannot fix is your biggest customer
Four callers are on twenty thousand requests a second. Each of them is one key, and lesson 047 owns what happens next: sharding spreads keys and a hot key is one key, because the key is the input to the division. No ring divides it.
Twenty thousand scripts a second at fifteen microseconds is 0.3 seconds of work a second, thirty percent of one command loop, for one caller. Put two of the four on the same node by bad luck in the hash and that node is at sixty percent before any of the twenty thousand standard callers arrive.
Now check it 047's way, because 047's rule is that a hot key is priced in bytes, not in operations. Twenty thousand requests a second at a couple of hundred bytes of request and reply is four megabytes a second, thirty two megabits, which is a third of one percent of the ten gigabit card 047 held Stagefront's seat map against. The bytes say the key is asleep and the operations say it is a third of a machine.
That is the exact inverse of 047's finding, and the reason sits inside 047's own arithmetic rather than against it. Its seat map is a megabyte and a token bucket is sixteen bytes, a factor of 65,536, which moves the bill off the card and onto the command loop. 047 told you to multiply rate by value size and hold the product against a card; do that here and the product is small, which answers 047's question and not yours. A hot key is priced in bytes when the value is large and in operations when the value is small, and a limiter has the smallest value in the building.
Wrong about the rate, or wrong about the burst
Four ways to run one counter across two hundred and forty copies, and the useful way to sort them is not by cleverness. Lesson 021's sentence is that the rate decides what a caller gets in the long run and the burst decides your worst instant. Hold each candidate against that pair. One letter carries the table: k is the number of copies that one caller's own traffic actually reaches, and it is not the two hundred and forty.
| Design | Wrong about the rate | Wrong about the burst |
|---|---|---|
| Full plan in each copy | up to k times | up to k times the burst |
| Plan divided by the copies | refuses inside the limit | nothing |
| Ask the owner per request | nothing | nothing |
| Grant, then spend locally | nothing | up to k times the grant |
Spoken, since the audio skips tables: the full plan in every copy multiplies a caller's rate by k, the divided plan refuses callers who are inside their limit, asking the owner per request is exact on both, and grants are exact on the rate and generous on the burst by k grants.
Lesson 002's busy room gives the floor under k. A standard caller at a hundred a second against a forty millisecond API has four requests in flight, so four connections at the very least, so at least four copies. The largest caller has eight hundred in flight and is long past the two hundred and forty. The floor is the part you can derive, and above it the caller decides: a client library with a pool of fifty holds fifty connections to send the same hundred a second, and nothing in the design can tell the difference.
Read the first row with that in hand. A standard caller gets four hundred a second instead of a hundred, tolerable until they open more connections. The error in a copy-local limiter is chosen by the caller, because lesson 004's connection reuse means a caller with one connection talks to one copy for as long as they keep it, and one multiplexing everything down a single connection reaches one copy however fast they send. Marlow's founder found that lever by accident on 25 October and had no idea what he had found.
The second row is the distributor's without its floor, and in that pure form it never over-admits a single request. The floor they bolted on to stop a plan of ten rounding to nothing is the whole of 25 October: one a second times forty eight copies is a ceiling of forty eight, for any plan at all. So the row is honest and the patch on it is not.
It is still the worse design in either form, because its mistake is invisible to the people running it. A limiter's dashboard counts admissions, and an admission count cannot show you a refusal that should never have happened. Lesson 062 found the same asymmetry pointed at somebody walking a key space and called the refusal rate the sensor nobody builds. Here it is the only evidence there is, and the distributor has had a month of it.
And that row's divisor belongs to somebody else. The copy count is set by lesson 055's autoscaler, which already earned the line that an autoscaling group is a deploy that fires when it feels like it. Here it is a contract change too: take the fleet from sixty boxes to ninety and every customer's enforced rate falls by a third, with no release, no ticket and nobody from the commercial side in the room.
The third row is the memorised answer, a bucket in Redis behind a Lua script, and the arithmetic above says it is affordable: three nodes, sixty requests in flight, 1.25 percent of a request's latency, a tenth of the gateway tier's bill. I would not argue with it on cost. I would argue with the two numbers it leaves standing, which are thirty percent of a command loop for one caller's single key, and 4.4 hours a year in which the limiter cannot count.
A grant is a lease you are allowed to trust
The fourth row is one idea. A copy does not ask about a request, it asks for an allowance: give me fifty of this caller's tokens. It spends them locally and asks again. The owning node debits the caller's bucket when it issues the grant, so it is still the only place the rate is enforced.
What that buys is one division, and lesson 047 wrote the formula already in another costume. 047's local caches come out as fetches a second equals caches divided by the local TTL; here grant requests a second equals offered load divided by the grant size. Size the grants per plan, which the next paragraph argues for, and the sum is small: the four large callers at plan are eighty thousand a second on grants of a hundred and sixty seven, which is 479 asks a second, and the other forty thousand a second on grants of fifty is 800. Under thirteen hundred asks a second, two percent of one command loop, for a tier the memorised answer builds a cluster for. That total assumes the big four are at their plan, and the mix needs no defending, because the worst one is the whole peak arriving through standard grants of fifty: 2,400 asks a second, under four percent. The largest caller's own key falls from thirty percent of a loop to under a fifth of one percent.
The grant size is not a tuning knob, and this is the part I have never seen written down. The burst it costs you is k grants outstanding at once, so the grant you may safely issue is the burst you already sold divided by k. The standard plan sold two hundred against four copies, which is fifty. The largest sold forty thousand against two hundred and forty copies, which is a hundred and sixty seven. The burst in a plan, which lesson 021 said everybody inherits from a library rather than choosing, turns out to be the number that sizes your entire counter tier. Tighten the burst and you pay in round trips: the cost is offered load times k over the burst, and nothing else is in the formula.
Which leaves k, and k is countable rather than derivable, which is the one piece of luck in this design. The owning node sees every grant request, so the distinct copies asking for one caller's tokens inside a window are that caller's k, counted, with no cooperation from the caller at all. Somebody who widens their pool to thirty connections shows up as a k of thirty and a grant of six, and the asks rise on their own: forty thousand a second times a k of thirty over a burst of two hundred is six thousand asks a second rather than eight hundred, nine percent of a command loop rather than one. The tier takes that. The busy room's four is the floor you design against until you have the count.
Then the half of this that reads like a violation of lesson 035.
A grant has an expiry, so a grant is a lease, and lesson 035 spent a whole lesson on why you cannot trust one. A lease is a promise to stop, kept by the machine losing it, reading its own clock, which a paused or swapping process does not have. From Kleppmann's case 035 takes the point that survives everything else: without a fencing token no lock of any kind is safe for correctness.
All of that is true here and none of it matters, for a reason 035 supplied itself. 035 says sort the resource before you choose the lock, and the resource here is a count. A holder spending a hundred milliseconds past its expiry admits at most its grant's worth of extra requests, which is fifty, inside the burst you sold. A lease failure on a mutex is two writers and a corrupted row. Here it is a slightly longer queue. You may trust a lease when the resource is divisible and the failure is additive, and the fence 035 asks for would guard a number you have already agreed to.
Settlement needs one more field and lesson 019 minted it long ago. A copy returns what it did not spend, keyed by the grant's id, which is 019's idempotency key doing exactly its published job: a unique string naming an action the caller intends to perform, not a hash of the request. A duplicate settlement writes the same answer. A lost one costs the caller those tokens until the grant expires and the owner credits them back anyway. Lesson 036's at-least-once delivery plus one unique constraint is the whole mechanism, which is 036's own sentence. What it must not be is a delta. Report a total or a settlement, never an increment, because an increment delivered twice is wrong and no key fixes it afterwards.
The clock is shorter work than you would expect. No two machines here have to agree about when a second ended: the only clock consulted is the owning node's, and lesson 034's rule puts the refill on a monotonic duration rather than a wall clock boundary. Lesson 021's two window shapes both want a shared instant and a bucket does not, which is a second reason to prefer it; 021 gave the first.
One thing follows that would be indefensible anywhere else in this course. None of this state has to survive anything. Lose a counter node and the buckets on it go too, and the cost is one window in which those callers start from full; lesson 031's ring moving an arc does the same thing on purpose. A limiter's counters are the one piece of state in this design you may lose without a plan, which is why it belongs in a cache with no durability, and why lesson 033's machinery is the wrong shopping list for it.
What it does when it cannot count
Lesson 048's rule is fail static: when the control plane cannot be reached, keep using the last answer you had. Its sharp edge is that fail static buys you the fleet you have and nothing you are about to start.
That sentence arrives at a grant with nothing changed. A copy holding a grant keeps spending it. A copy holding none, or one for the wrong caller, has nothing to be static about, and the 4.4 hours are entirely about those.
Three answers, and the two obvious ones want pricing before the one I would ship.
Fail closed and the counter tier's 4.4 hours a year become 4.4 hours of a dead API, which is 003's whole table thrown away to protect a fairness property. Fail open and the same hours permit 2.08 million requests a second of sold quota against a fleet that holds a hundred and twenty thousand. Lesson 021 said a limiter cannot save a saturated service because it does not know the service is saturated; fail open is the version that cannot even count.
The third answer is to fall back to the table's first row, a full local bucket in every copy, and here the design's one split bites a last time. For a standard caller whose counted k is four, copy-local gives them four hundred a second instead of a hundred: wrong, bounded, survivable for an hour. For the largest caller k is two hundred and forty, so it gives them 4.8 million a second, forty times the fleet's peak and more than every customer's quota added together.
So the fallback is not one rule. Small plans degrade to the full plan in every copy and take the over-admission. Large plans degrade to the divided plan and take the refusals, which is the table's second row chosen deliberately, for an hour, for the four callers who have somebody to ring.
In degraded mode you choose which error to take, and the right choice runs in opposite directions for your biggest and your smallest callers.
Underneath all of it goes the layer the brief never asked for. Every copy also holds a plain cap on its own admissions, with no identity in it, nothing shared and no clock: the fleet's ceiling over the copy count. Call the ceiling a hundred and sixty thousand a second, which is this design's peak read at the seventy five percent CPU lesson 006 measured on Stagefront's boxes, borrowed as a shape and not as a number. Over two hundred and forty copies that is about 666 each, and the busy room converts that into the form with no clock in it at all: 666 a second at forty milliseconds is twenty seven requests in flight, which is a semaphore and a number. It tightens on its own when the box slows down, which a rate never does, and it needs nothing it cannot reach.
That cap is lesson 021's load shedding and lesson 042's graceful degradation, and it is the only thing here still protecting you on purpose once the counter tier is gone. The limiter is the fairness. The cap is the protection. Build the limiter they asked for and the cap they did not, then write down which is which, because the next engineer will delete the one with no ticket attached.
Which gives the design its entry in lesson 061's format.
We do not ask the owning node on every request.
Because a grant divides the asking by its own size, taking
the counter tier from two machines at full stretch to two
percent of one, and the largest caller's key from thirty
percent of a command loop to under a fifth of one percent.
Costs a burst of up to k grants, which is the burst each
plan already sold: 200 standard, 40,000 for the largest.
Reverses if a plan is ever sold with a burst smaller than
the copies a caller reaches, because then the grant is
less than one token and we are asking every time anyway.
One refusal gets no entry. Nothing here crosses a region: lesson 002 puts Mumbai to Virginia at two hundred milliseconds, four hundred times the local round trip, so a standard caller's grant of fifty would leave one request in fifty waiting a fifth of a second. The honest answer is to split each plan per region and live with the split being wrong, which is the hook's failure with a continent inside it, and lesson 050 owns that argument.
Recap
A distributed limiter cannot be wrong about a caller's rate, only about their burst, once every counter has one owner. Sort the candidates by which of lesson 021's two numbers they break: the full plan in each copy multiplies the rate, the divided plan refuses callers who are inside it, and a grant spent locally is exact on the rate and generous on the burst by k grants.
k is the number of copies a caller reaches, and the caller picks it. Lesson 002's busy room gives it as rate times latency: a hundred a second at forty milliseconds is four copies, and twenty thousand a second is all two hundred and forty. Lesson 004's connection reuse is the lever in both directions, and a customer who opens more connections to stop being refused walks past their plan without noticing, which is what Marlow's founder did on 25 October.
The burst you already sold is what sizes the counter tier. The grant you may issue is that burst over k, and grant requests a second are the offered load over the grant, which is lesson 047's local cache formula in new clothes. Grants sized per plan take a hundred and twenty thousand decisions a second down to under thirteen hundred asks, two percent of one command loop.
A hot key is priced in bytes when the value is large and in operations when it is small. Lesson 047's seat map is a megabyte and a bucket is sixteen bytes, a factor of 65,536, which moves the bill onto the single command loop: thirty percent of it for one caller at twenty thousand a second, and nothing any ring can divide.
You may trust a lease when the resource is divisible and the failure is additive. Lesson 035 is right that a lease is kept by the machine losing it, and a holder spending past its expiry costs you one grant, inside the burst you sold. Settle by the grant's id, which is lesson 019's key, and report totals rather than increments, because an increment delivered twice has no key that can save it.
Fail static buys you the grant you are holding and nothing else. Fail closed turns a counter outage into an outage and fail open permits every token you ever sold. Degrade small plans to copy-local and large plans to the divided plan, because one fallback is survivable for the first and forty times your peak for the second. Then keep a per-copy admission cap that needs no counter at all, because the quota you sold is seventeen times the fleet you own, and a limiter was never what protected you.
Check your understanding
Your largest caller moves from four hundred connections to twelve hundred with no change in their request rate. Say what changes in this design and what does not, and which number in your monitoring moves first.
A product manager wants to sell a plan at five thousand requests a second with a burst of five thousand, on the grounds that a burst equal to the rate is the tidiest thing to put on a price page. Work out what that does to the counter tier, then give the smallest change to the plan that you would accept instead.
The counter tier is up, but one of its three nodes is answering in eighty milliseconds rather than half of one. Say what each copy of the limiter should do, what happens to the callers whose counters live on that node, and whether you would rather this looked like a failure or like slowness.
Somebody proposes dropping grants and asking the owning node on every request, on the argument that it is simpler, exact, and that the latency arithmetic above says it is affordable. Give the strongest version of that argument, the two numbers you would put against it, and what you would ship if the team disagreed with you.
Marlow's founder writes to the distributor again, asking this time for a plan of a hundred requests a second. Say what the distributor should change before selling it to him, what their support team should be able to tell him and currently cannot, and which of the two would have prevented 25 October.
Your autoscaler takes the gateway tier from sixty boxes to ninety during a campaign. Say what happens to a standard caller's enforced rate under each of the four designs in the table above, and which of the four you would want somebody from the commercial side to have signed off.
Next lesson
064 Design a Key-Value Store. Today's counters sat in a store this lesson treated as given, one that shards by key, loses state without ceremony and answers in half a millisecond; next lesson builds it and finds what each of those promises costs.