Stagefront is this course's invented ticketing service, the one where a stadium show goes on sale at exactly 10:00 and two hundred thousand people press the same button inside the same minute. On Friday 30 October it kicked two thousand bot accounts off a sale, and about thirteen of them went on buying for the rest of the morning.
Nothing was down. Nobody got an error.
Lesson 029 built the thing that failed and priced it as a win, which it was. You cannot un-sign a token, so you keep a list of the ones you want refused, and the useful part is how small the list is: it only has to hold what is both revoked and unexpired. Kick two hundred accounts a minute against a five minute token and the list holds about a thousand entries, sixty four kilobytes at sixty four bytes an id, which fits in every process on every box with room to spare.
Sixty four kilobytes fits in one value, so that is where it went: one key, holding the whole list, read by every checking process and written by whoever did the kicking.
The kicking is done by the bot detector, and the detector runs on each of the twenty application boxes lesson 006 counted at Stagefront, because a detector needs the requests and the requests are on the boxes. Lesson 007 has a name for state shaped like that, derived by the box from the traffic it happened to see rather than handed to it by a customer, and the warning attached: losing it is invisible.
Twenty boxes, then, and one key. A kick is a read of the list, an addition, and a write of the whole list back.
Two hundred a minute is one kick every three hundred milliseconds. A read of sixty four kilobytes and a write of sixty four kilobytes is two round trips, a millisecond on lesson 002's ladder, and parsing a thousand entries and serialising them again is another; call the window in which another kick can slip in about two milliseconds, which is mine. So roughly one kick in a hundred and fifty has another kick start inside its window, and across the two thousand kicks that fit into the ten minutes of real intensity lesson 003 gives an on sale, that is about thirteen.
Thirteen accounts the detector kicked and did not kick. Each pair read the same list, each added its own id, each wrote the whole thing back, and the second write landed on top of the first. The store did exactly what it had promised to do, which was to keep the most recent value.
Lesson 023 settled why nobody saw it and lesson 029 is where the sentence is printed: a stale permission renders on no screen anywhere, it fails silently, and it fails in the direction of yes. The detector did notice, in the only way left to it, by kicking some of those accounts a second time later in the morning. An addition to a list that already holds the id is a no operation, and nobody has ever counted a no operation.
What found it was the chargeback file three weeks on. Four accounts on it that the detector's own log said had been removed from the sale.
You are designing the store they put the list in.
The brief, and the line that is not on it
An internal store, one per data centre, for small values that other teams own. Get, put and delete by exact key, and lesson 016's definition is the whole API: a dictionary you cannot ask questions of, where anything you did not put in the key you cannot ask.
Five hundred million keys at an average of four hundred bytes, so two hundred gigabytes of data. Four hundred thousand operations a second at the peak, nine in ten of them reads. Those are all mine and they set everything below.
Three customers, and they want different things.
Lesson 063's counter tier is the easy one and said so: a limiter's counters are the one piece of state in that design you may lose without a plan, because losing one costs a caller a window in which they start from full. It wants a hundred and twenty thousand decisions a second and no durability.
The revocation list from the hook wants the opposite. It is sixty four kilobytes that must not quietly drop a member, and the cost of dropping one is the whole of a ten minute event rather than the five minute revocation delay lesson 029 priced at half an event.
Then the ordinary middle: profile rows, preferences, the small per-customer facts that sit where lesson 007 put Marlow's sessions, out of the application tier and into a store every box can reach. A few thousand bytes, read constantly, written rarely, and nobody would notice a stale one for a second.
And then the line that is on no brief anywhere, which decides most of this design and all of the hook.
May a write be accepted by a node that cannot see the node that took the last one?
Say yes and you have a store that takes writes while a replica is unreachable, which is the property everybody wants. Say yes and you have also just manufactured two writers for every key you hold, in a building where nobody is offline and no phone is in a pocket, which is the property nobody puts on the page next to it.
Four lines on an envelope
Lesson 025's order, bytes first and money last.
Bytes. Two hundred gigabytes of data, three copies, so six hundred gigabytes to house. Lesson 005's box has sixty four gigabytes of memory, and lesson 062 called fifty of those available for holding data in memory, which is generous and is 062's figure rather than a new one. Six hundred over fifty is twelve nodes, of which four are holding your data and eight are holding the copies.
You could house the same bytes on three nodes and a lot of disk, and the usual objection to that is the wrong one. Lesson 002 puts a mainstream SSD random read at a hundred microseconds, a fifth of the half millisecond round trip, so disk is perfectly affordable per operation. What it is not is predictable, and the disk is where a slow reply comes from.
Two thirds of that fleet is copies, which is the first thing a reader of lesson 044 should object to, because object storage does not pay it: erasure coding with 044's k of 8 and m of 4 stores one and a half times your bytes against replication's three. Run it here and 044's own crossover answers. Four hundred bytes over eight fragments is fifty bytes a fragment, so a read becomes eight requests where replication makes three, and 044 put the crossover at four thousand bytes, under which the request costs more than the bytes. 044 priced that crossover in dollars, off somebody's price list; here it is the same shape in microseconds, and a read that needs all eight fragments waits for the slowest of the eight rather than the second fastest of three. Erasure coding is a bargain about bytes, and four hundred bytes is nothing to bargain with.
Operations. Four hundred thousand client operations a second, and here is the term that never makes the diagram. The node your client happens to reach is the coordinator for that request: it fans the request out to the replicas and answers once enough of them have come back. And a coordinator does not send two requests and wait for both; it sends three and takes the first two, which the latency line below turns into a bargain. So the fleet does 1.2 million node operations a second to be asked for four hundred thousand. Per node that is a hundred thousand, and lesson 047 priced dispatching a get at single digit microseconds, of which lesson 063 took five: half a second of work a second, half of one of lesson 005's sixteen cores.
On the wire, 047's instrument comes out clean for once. Rate times value size held against a card: 1.2 million times four hundred bytes is four hundred and eighty megabytes a second across the fleet, forty a node, three hundred and twenty megabits against the ten gigabit card 047 held Stagefront's seat map against. Three percent. The famous hot key problem of lesson 047 needs a megabyte to bite and we have four hundred bytes, which is lesson 063's inversion already published: a hot key is priced in bytes when the value is large and in operations when it is small.
Latency. Lesson 002 puts a round trip inside one data centre at half a millisecond, and that is what one replica costs. What a quorum costs is the second fastest of the three, which is lesson 033's sentence exactly, and 033 meant it as a warning.
Money. Twelve nodes at lesson 005's five hundred dollars is six thousand a month, double lesson 063's counter tier, of which four thousand is the copies.
Which answers the promise lesson 063 was given for nothing. Its counters may be lost without a plan, so they would have been happy at one copy, four nodes, two thousand dollars. They are on twelve because of the revocation list, and that is the whole bill of a shared store in one line: the replication factor is bought by the customer who cannot lose anything, and charged to everybody. Then lesson 056's afternoon, and this one is worse than most, because somebody has to own the answer to "which of these two values is the right one", and that question arrives at three in the morning from a team that did not know the store had versions in it.
The expensive term is not on the diagram again. It is the second customer's belief that a set they wrote to is a set.
The decision nobody writes down
Two branches, and the whole of the memorised answer is downstream of which one you take.
One owner per key. Every key belongs to a range, every range has an elected owner, and a write goes to the owner or it does not happen. Lesson 033 built all the machinery and you buy it unchanged: the write quorum and the vote quorum have to add up to more than the cluster, so the group can refuse to elect a machine that is behind. There is exactly one order for every key by construction, because one queue in one order is the definition of the thing, which is lesson 023's sentence about monotonic writes.
What it costs is the writes to one range while its owner is being elected. Seconds, not minutes, and lesson 024 has the shape of it: there are two answers and no third, and when you refuse you say so out loud rather than answering and hoping.
Any replica. A client talks to whichever node answers, that node accepts the write, and the write finds the others later. Writes survive a replica being unreachable, a node being restarted, a rack losing power. This is the design everybody can name.
Now the bill, and every line of it is famous as a feature.
Two writes to one key can now be accepted by nodes that never spoke, so you need a way to tell concurrent from ordered, which is lesson 034's vector clock: one counter per writer, incremented on your own write, merged by taking the larger of each position. You need a rule for what to do when it answers concurrent, and lesson 058 has already closed off the cheap one, because last write wins is the lost update with a better name and a network partition for an excuse. You need a read that notices two replicas disagree and repairs them on the way past. You need a sweep for the keys nobody reads, comparing whole ranges by hashing them into a tree, so that two nodes find their one disagreement in a few kilobytes rather than fifty gigabytes. And you need somewhere to park a write whose home node was down, for delivery when it comes back.
Five mechanisms. The words you will meet at work are not quite the ones I have used: read repair for the repairing read, anti-entropy for the sweep, a Merkle tree for the hashes it compares, and hinted handoff for the parked write. Every one of them is a line on the invoice for that yes, and a candidate who recites them without saying so has read the price list out as a brochure.
Then the one that is not on any list, which is my favourite thing about these stores.
A delete has to be a write. If a delete simply removed the row, a replica that was down for it would come back still holding the old value, and any read that asked it would see one node with a value and one with nothing, with that value the only version anybody has, so it wins and the store helpfully repairs it onto the others. A delete therefore writes a tombstone, a marker saying this key died at this version, which lesson 062 invented for an entirely different reason: there, the tombstone exists to stop a future version of you reusing a key. Here it exists to stop your own repair machinery running backwards.
Tombstones are swept eventually, because otherwise a store that deletes is a store that only grows. Whatever interval you pick for that sweep is now the longest a node may be away.
A node that has been down longer than your tombstone lifetime cannot be returned to the cluster; it has to be wiped and refilled, because everything it was holding when it left is a resurrection waiting to be repaired outward. I have never seen that sentence in a runbook, and the interval it depends on is a default in a configuration file three teams away from the person who reboots the machine.
For this brief I would take the first branch, and I will say why in the format lesson 061 asked for.
We give every key one owner, elected by lesson 033's rule.
Because no value on this brief is one the store could merge,
so the concurrent writes the other branch accepts have no
correct resolution waiting for them: the counters have one
writer per key, the profile rows have one, and a set is the
shape last write wins quietly eats a member of.
Costs the writes to one range during an election, which is
seconds, refused out loud rather than guessed at.
Does NOT fix the hook, which was two writers racing through
one owner, and needs the version check below instead.
Reverses the day a customer arrives whose writes commute and
whose refusals cost money, measured as writes refused per
election times what one refusal is worth.
The entry saying it does not fix the hook is the part a memorised answer cannot reach. The decision everybody argues about would not have saved Stagefront's morning. One owner serialises the two kicks perfectly, hands box 3's write and then box 7's write to the same key in a tidy order, and the entry is still gone, because both boxes read before either wrote. The famous decision is about writes arriving from two places, and the hook was two writers arriving at one place.
The famous design made its famous trade for a shopping basket at a shop where a refused add to basket is money on the floor. That is a real customer and it is not on this brief. Lesson 050 sorted this once and the sorting still holds: some data has no second writer, some conflicts are a merge, and some conflicts are a lawsuit. The first pile does not care which branch you took, the third forbids the second branch outright, and the middle pile is the entire reason the second branch exists.
One refusal gets no entry, because the measurement that would reverse it is the speed of light. Nothing here crosses a region: lesson 002 puts Mumbai to Virginia at two hundred milliseconds, four hundred times the local round trip, so a write waiting for two of three replicas spread across continents waits two hundred milliseconds whatever else you do. Lesson 050 owns that argument and ends in the same place: active-active is a lot of active-passive, cut finer.
What R plus W actually buys
The arithmetic everybody can recite. N copies, W of them must accept a write, R of them must answer a read, and if R plus W is greater than N then the two sets must overlap, so a read is guaranteed to touch a node that took the last write. Three copies, two and two, four is more than three, and you are told that this is how you get a consistent store out of an inconsistent one.
Hold it against lesson 033's version of the same inequality, because the difference is the whole section. 033's two quorums were a write set and a voting set, and the thing the overlap buys there is the right to refuse: a voter holding the newest entry can turn down a candidate that is missing it. There is no vote in R plus W. Nothing is ever refused. The overlap tells you a value is present somewhere in your read set, and that is a different sentence from the one you wanted.
R plus W greater than N makes a read find every write. It does not make the writes into a sequence, and the sequence is what you came for.
Three ways it leaks, and none of them is exotic.
Two writes that were concurrent have no last one, so the overlap hands you both and the inequality has nothing to say about which is the answer. A write that was told it failed is worse: W of two with one acknowledgement returns an error to the client and leaves the value on one node, where it is the newest version anybody holds, so the next read finds it, prefers it, and repairs it onto the other two. Your failed write becomes the value, and the store does the work for you. Then the one with the nickname: when a home replica is down, the write goes to a stand in outside the three, so the W of two is satisfied by one home node and one stranger. Only that single home node holds the value. The down node comes back empty, the parked write has not been replayed onto it yet, and a read asking two of the three home nodes satisfies R plus W greater than N on paper while missing the write one time in three, because one of the three pairs it can pick at random is the pair without it. That is a sloppy quorum, and the honest description is the arithmetic of R plus W greater than N with the arithmetic taken out.
So much for the promise. What a quorum genuinely buys you, every day, nobody sells, and it is not consistency.
A replica is occasionally slow. A compaction, a garbage collection pause, a disk deciding to think about its life. Take one request in a hundred at eighty milliseconds against the other ninety nine at half of one, both mine and both the first things I would measure. Now count what the coordinator does with three replicas.
| What the coordinator sends | Slow reads | Against one replica |
|---|---|---|
| Two of three, waits for both | 2.0 in 100 | twice as many |
| One replica | 1.0 in 100 | the baseline |
| Three of three, waits for two | 3 in 10,000 | a thirty third |
Spoken, since the audio skips tables: sending two and waiting for both gives twice the slow reads of asking one node, asking one node is the baseline, and sending three and taking the first two gives one thirty third of it.
That middle row is the surprise and the arithmetic is two lines. Send two and wait for both and you are slow if either is slow, which is one minus 0.99 squared, about two in a hundred. Send three and wait for two and you are slow only if two of the three are slow, which is three pairs at one in ten thousand each, three in ten thousand. Lesson 033 ran exactly that pair count on machines being down at one percent and got the same three in ten thousand, which is where I took the shape from; the only thing I have changed is what one percent means.
Between the top row and the bottom there is a factor of sixty seven, and R, W and N are identical in both. The letters describe what the store promises and the number of requests the coordinator actually sends describes what it feels like, and those two facts live in different documents. It is the only tail latency hedge in this course that is free, because you were going to send those bytes to those nodes anyway, and the envelope already counted them at three percent of a card.
Lesson 033's warning that a quorum's latency is set by its second fastest member turns out to be a promise when you point it at three replicas you do not have to wait for.
Who pays when two writes meet
The second decision, and it is made in the API before you have a single customer.
Can the store read the value?
If a value is opaque bytes, there is exactly one merge available, which is to pick one of them, and picking one is last write wins, settled by the clock lesson 034 spent a lesson discrediting: a median offset of four tenths of a second on machines with a job and a time daemon. Which is what ate the hook, with no clock skew and no partition anywhere near it.
Four answers.
Return both and let the client sort it out. This is the design that gets called eventually consistent and is really eventually your problem: every client that ever reads that key has to handle two answers, for ever, including the one somebody writes in four years who has never read this paragraph. It is the most honest of the four and the least used, because the first team to hit it writes a helper that takes the later timestamp and you are back to last write wins with extra steps.
Pick one, and say so on the price page. Last write wins is a legitimate choice for data whose conflicts cost nothing, which is most sessions and most caches. Say it in the API and in the sentence a new team reads on their first day, because the failure mode is silence.
Or let the value have a type the store understands. A counter whose merge is addition. A set whose merge is union. Lesson 058 named the shape, a conflict-free replicated data type, and proved its limit on Marlow Books, the four person online bookshop that exists only in this course: a commutative merge buys agreement by deleting the guard that was doing the work, so nine decrements against eight copies converge beautifully on minus one. A set of revoked token ids has no guard to delete. Union is simply correct there, and the hook's thirteen are thirteen because nobody ever told the store it was holding a set.
And the fourth answer, which costs one integer and is the one that would have saved the morning. Hand the client the version it read and refuse the write if the version has moved since. Box 3 reads the list at version 4,180, adds its id, offers the write against 4,180 and is told no, because box 7 got there first and the list is at 4,181; so box 3 reads again, adds its id to the newer list, and writes. That is lesson 015's conditional update with a version where the stock count used to be, and the shop was already shipping the shape: stock = stock - 1 WHERE stock > 0 rather than stock = 7, which lesson 058 named as the fix for the lost update. A store that cannot merge your value can still refuse to lose it, and the refusal costs one integer.
What it costs the caller is a retry loop, and under contention a queue, which is a refusal showing up as latency rather than as silence. I will take that trade every time, and the reason is the hook: the other option was thirteen.
Which gives lesson 016 a second half it could not have written. 016's rule is that anything you did not put in the key, you cannot ask. Anything you did not put in the type, the store cannot merge, and the second one is the expensive rule, because the first fails loudly at the query and the second fails silently at the write.
One node, and the arc it holds
The ordering under one node needs no deriving. Keys arrive hashed onto lesson 031's ring, so a node meets them in random order for ever, which lesson 062 has already priced: the worst order a B-tree can be handed, so you pay lesson 043's LSM price list minus the range scan, and the range scan was the expensive line. Galewatch, the telemetry company in this course that takes a reading every two seconds from each turbine on the wind farms it monitors, keeps its B-tree because its keys arrive in time order. We never will.
The ring's other bill is smaller than its reputation. Adding a thirteenth node moves one thirteenth of six hundred gigabytes, which is forty six gigabytes, and it arrives from twelve senders at once, so take the two hundred megabytes a second lesson 031 used for exactly this operation and lesson 043 pinned as a per machine rate with the rest of the fleet running: under four minutes. Lesson 031 priced seven hours and fourteen minutes for Galewatch's nineteenth machine on the by-turbine cut nobody chose, and twenty four minutes for the ring it took instead. Four minutes beats both, and the ring is not why: a node sized by memory holds fifty gigabytes where Galewatch's holds nearly three hundred.
What is expensive about the move is those minutes, and the quorum pays for them too. While the new node is filling, it must not count as one of the three for keys it has not finished receiving, or a read of two will find one empty node and one full one and repair the wrong way. The copy is cheap and the window is not, and the thing that protects the window is the same overlap you bought for durability.
Recap
The mechanisms a key-value store is famous for are the invoice for one question nobody asks out loud. May a write be accepted by a node that cannot see the node that took the last one? Say yes and you have bought writes that survive an unreachable replica, and you have manufactured two writers for every key in a building where nobody is offline. The vector clock, the merge rule, the repair past a disagreeing read, the hash tree sweep for the keys nobody reads and the parked write waiting for a dead node are five lines of that invoice, the tombstone is a sixth, and the memorised answer recites them as features. Saying yes would also not have saved the hook, which was two writers racing through one owner.
R plus W greater than N makes a read find every write, and does not make the writes into a sequence. Lesson 033's inequality had a vote in it, and a vote is a right to refuse; this one has none. It leaks on concurrent writes, which have no last one, on a write you were told had failed and which the next read will repair into place, and on a sloppy quorum, which satisfies the arithmetic by asking nodes that never held the data.
The letters are the promise and the fan-out is the experience. At one slow reply in a hundred, sending two and waiting for both gives two slow reads in a hundred, worse than asking one node; sending three and taking the first two gives three in ten thousand. Same R, same W, same N, a factor of sixty seven, and the only free tail hedge in this course, because the bytes were already going to those nodes.
Anything you did not put in the type, the store cannot merge. That is the second irreversible decision, taken in the API before there is a customer. Lesson 016 said you cannot ask for what you did not put in the key, and that one fails loudly at the query; this one fails silently at the write, because a value the store cannot read has exactly one merge available, which is to pick one, and picking one is lesson 058's lost update settled by lesson 034's discredited clock. A set is the shape it eats, and a revocation list is a set. A store that cannot merge your value can still refuse to lose it, and the refusal costs one integer, which is lesson 015's conditional update with a version where the stock count used to be.
A delete is a write, and its marker has an expiry that is really a limit on your operations. A removal that leaves nothing behind gets repaired back into existence by a replica that was away, so a delete writes a tombstone, and the sweep interval for tombstones is the longest a node may be absent before it has to be wiped rather than rejoined.
Check your understanding
A team wants to store a customer's list of saved payment methods in this store, as one JSON value per customer, and says their writes are rare enough that a conflict will not happen. Say what you would ask them about their writers, which of today's two decisions settles whether they are safe, and the one change you would require before saying yes.
Your store runs with N of 3, R of 2 and W of 2, and the coordinator sends exactly R and W requests to save bandwidth. The p99 of a read is worse than the p99 of the single replica it replaced, and a colleague concludes the quorum is overhead. Give them the arithmetic, say what you would change, and say what it costs.
A node is brought back after eleven days in a cupboard, on a cluster whose tombstones are swept after ten. Describe what happens over the following hour, which of your dashboards moves, and what you would have had the operator do instead.
Somebody proposes solving the hook by moving the revocation list from one key to one key per revoked id, with the checking processes reading all of them. Say what that fixes, what it breaks, and which number from lesson 029 you would put against it.
Lesson 063's counter tier and today's revocation list are both small values with high read rates, and today put them in the same store. Argue for splitting them into two stores, then argue against, then say which you would ship and what you would measure to find out you were wrong.
A write returns an error to your client after one of its two required acknowledgements. Your client is a payment service and its author asks what the row in the store now says. Answer honestly, say what you would have the client do next, and name the lesson whose key makes the next step safe.
Next lesson
065 Design a Chat System. Today's store answers for one key at a time and has no opinion about order; next lesson needs a million conversations whose whole product is that the messages arrive in the order they were sent.