The CAP Trade-off Without the Theorem

Marlow Books is a four person online bookshop that exists only in this course. On a Wednesday in June the network inside its data centre stopped carrying packets between two machines sitting in the same rack. The interruption lasted ninety seconds. The shop spent the next hour and fifty minutes quoting a price it would not honour and signing customers out, with every dashboard green.

The two machines were box A, which runs Postgres and half the application, and the streaming replica lesson 011 put beside it for five hundred dollars a month. Box A never noticed. It served book pages all afternoon at its usual couple of milliseconds.

The replica noticed, because twelve days earlier somebody had given it something to notice with.

Lesson 016 is why. On the last Saturday in November box A's 500 GB volume filled at ten to four in the morning, Postgres shut itself down rather than pretend a write had landed, and the shop was closed until twenty to nine. Four hours and fifty minutes, beside a complete, running copy of every byte that nobody touched, because lesson 011 had said what Marlow bought: a warm copy, no promotion, no rehearsal. So in the last week of May the founder wrote about fifty lines of Python. Ask box A for a connection every five seconds. If it has not answered for thirty seconds, promote the replica.

At 14:20:14 on the Wednesday, the packets stopped.

14:20:14  packets stop between box A and the replica
14:20:44  the watcher promotes the replica
14:21:44  packets resume, ninety seconds after they stopped
15:04     a customer asks why they keep getting signed out
16:10     the replica is taken out of rotation

Thirty seconds without an answer, and the watcher did precisely what it was written to do. Postgres on the replica ended recovery, gave itself a new timeline and became a primary. A minute later the network came back.

Nothing crashed. Nothing returned an error. Slow down here, because this is the whole lesson.

Box A had never stopped being the machine everything wrote to. Lesson 011 listed four things a failover needs, and repointing every client, pool and job is one; the fifty lines did none of it, so no write reached the new primary and there were no duelling orders to untangle. Two machines that both believe they are in charge is split brain, and Marlow got the cheap half.

What it got instead was a machine that had stopped being a copy, and could not replay another byte of box A's log, ever. Lesson 011's routing audit was still sending it four kinds of read: the full text search, the publisher page, the stock and price on every book page, and session lookup by id.

The loud failure was sign-in. Lesson 007 put session rows on box A and lesson 011 sent the reads by id to the replica, so a customer who signed in at half past two had their row on one machine and their next click answered by the other, which had never heard of them. The shop signed them out. Anybody already signed in was fine, which is why no email arrived until four minutes past three.

The quiet failure was May's bug again. The page fetches the price in the small second request lesson 023 pushed it into, lesson 011 routes that read to the copy, the checkout guard reads the row on the primary, and this time no ten minute expiry was going to end it.

At 16:10 the founder pointed everything at box A, which put the shop back where lesson 016 found it, one copy and a disk that is the end of the shop, until a fresh base backup of the 180 gigabyte data directory finished next morning. Then they deleted the fifty lines.

The watcher was not wrong. It could not have been right. From where it stood, a machine that will answer in a moment and a machine that is never going to answer again send exactly the same thing down the wire, which is nothing.

A partition is a Tuesday

A network partition is when some machines in your system cannot exchange messages with others, while all of them are running and each side can still be reached by somebody. Not a crash. Not a bug. A gap in the middle of a system that is otherwise entirely healthy.

It is a different word from lesson 013's partitioning, which was cutting a table into pieces on one machine. Same spelling, no relation.

It is also a different thing from a client being unable to reach you. Galewatch is a telemetry service in this course that collects a reading from each of nine hundred wind turbines every two seconds, and when one of its farms loses its radio link for four hours, which lesson 017 timed and sized, the turbines are clients rather than copies, and nobody on the far side holds a second opinion about the same fact. That is an availability problem with a buffer under it, and lesson 058 owns it. Today is about copies that cannot hear each other.

The causes are boring, which is the point. A switch. A security group rule applied to the wrong tag. A routing change somewhere you do not own. A link saturated enough that two percent of packets are lost, which TCP hides as latency for a while and then stops hiding. A process paused by garbage collection or a hypervisor long enough that its peers give up on it, which then comes back convinced it is still twenty past two.

Here is the part that makes this hard, and it is not the network. Stand inside one node. You send a message to a peer. Nothing comes back. That is the entire signal you will ever get, and it is the same signal whether the peer is dead, paused, overloaded, or perfectly fine behind a broken link. Lesson 019 put it as a rule about dependencies: a 503 is information, and a timeout is not. At the scale of one service calling another that cost Marlow a duplicate charge. At the scale of one machine deciding whether another is alive, it costs you the design.

So you pick a threshold, and the threshold is where the trouble lives. Borrow the shape of the ingestion profile lesson 002 published for Galewatch, the most fully measured latency distribution in this course: a median of 12 milliseconds, a p99 of 400 and a p99.9 of 2,100. Lesson 020 multiplied that out against 450 readings a second and got 0.45 calls a second past 2.1 seconds. A healthy path crosses a 2.1 second cut-off about once every two seconds, and a threshold your system steps over that often is not a death certificate.

The usual answer is strikes, which is a bigger threshold in disguise, and lesson 006 has the bill for erring the other way. Stagefront is an event ticketing service that exists only in this course, and its health check ran every two seconds with a one second timeout and three strikes. Twenty of its application boxes at seventy five percent CPU lost five of their number in thirty seconds that way, with none of the five ever broken.

Every failure detector is a bet about the future dressed as a measurement of the past. Ask how long it has been quiet and you get a number. Ask whether it is going to answer and nothing on your side of the wire knows.

The two answers

A request arrives at a machine holding a copy. That machine cannot reach the other copy. There are two answers, and there is no third.

Answer it anyway. The reply might be missing a write that landed on the other side, or it might accept a write the other side will never hear about. You have stayed available and given up behaving like one copy, which is lesson 023's strong consistency.

Or refuse. Return an error, say why, and take the customer's disappointment. You have stayed correct and stopped being a service.

People reach for a third option, which is to wait for the partition to heal. That is refusing with worse manners. Lesson 020 priced it, since a timeout converts slow into failed, and lesson 004 named the sting: it is the one failure that carries no status code at all. You hold a connection open the whole time you produce it.

Marlow has a version of each answer in its own configuration. Replication is asynchronous, so box A commits, tells the customer yes, and ships the bytes when it ships them. That is answer one, chosen by accepting a default, and it is what made the ex-replica's freeze silent rather than loud. Lesson 011 described the switch that buys answer two: name the standby synchronous and a commit does not return until the standby has the bytes, so no acknowledged write can vanish. And if that standby goes down, commits stop. Lesson 011 called it a remarkable thing to have built in the name of staying up. One machine cannot be heard, so the other refuses to take money.

Now the three letters, once, because you will meet them. C is consistency, meaning lesson 023's strong, behaving as though there were one copy, not lesson 015's C in ACID. A is availability, every request getting an answer rather than an error or a hang. P is partition tolerance, continuing to work when messages between your machines are lost. There is a formal version with a proof, and the proof is not the useful part.

Read as a menu, pick any two, it misleads. Partition tolerance is not a feature you select; it is a hazard, handed to you the moment a fact lives on more than one machine, and you can buy a better network without ever buying one that cannot fail. "We will have C and A and simply not tolerate partitions" means "we will assume our machines can always hear each other", which is a thing to assume, not a thing to purchase.

There is one honest exception, and lesson 001 is about it. One machine holding the only copy cannot disagree with itself, so it has no partition to tolerate. It also has no second copy, which is why Marlow lost four hours and fifty minutes in November.

Which brings up what people do instead, and Stagefront does it on purpose. Its shows go on sale at exactly 10:00 with two hundred thousand people pressing the same button, and oversold seats are a lawsuit, so refusing is expensive and guessing is worse. Lesson 003 priced the window: forty on-sales a year at about ten minutes each, so four hundred minutes out of 525,600 carry the business, under a promise that at least 99.95 percent of purchase requests succeed in under two seconds inside it. Lesson 015 gave the mechanism, a hold committed in one short transaction on one database, and lesson 013 refused to shard those seats: cut by event and the on-sale minute is one machine at a hundred percent CPU with fifteen idle ones watching.

Stagefront keeps the thing that must be correct on a single machine so there is no second copy to have an opinion, and pays with a ceiling lesson 013 declined to remove. You can dodge the trade for one operation by refusing to distribute it. The bill arrives as capacity, and lesson 050 is where that bill stops being payable.

Forty three seconds, twenty four hours

On 21 October 2018 GitHub was replacing failing optical network equipment, and the work briefly cut the link between their US East Coast network hub and their primary US East Coast data centre. Connectivity came back in forty three seconds. In that window their automated failover, unable to reach the primary, promoted a database cluster on the US West Coast, and the East Coast primary had taken writes that never made it west. GitHub chose data integrity over availability and ran degraded for twenty four hours and eleven minutes.

Lesson 011 used that story to say a copy is not a failover. Today it says something else.

Divide the numbers. Twenty four hours and eleven minutes is 87,060 seconds against a partition of forty three, which is a ratio of about two thousand to one. The length of a partition tells you almost nothing about what it costs, because the recovery is not reconciling packets. It is reconciling decisions that two halves of a system made while each believed it was the one in charge, and decisions do not un-happen when the link comes back.

Notice also who chose. Nobody at GitHub made a decision at the moment of the partition. A machine did, in forty three seconds, following a policy somebody had written down earlier. The humans made the interesting choice afterwards, once there were two sets of writes on the table and somebody had to say which mattered more, the data or the site. Lesson 018 found the same shape in a retry schedule: the sum of the sleeps is your policy, and nobody chose it. The partition choice is always made in advance, usually by a default, and called in at the worst possible moment.

Marlow's version of that sentence is fifty lines of Python with a thirty second constant in it, which promoted a database twelve days later while every graph stayed green.

The partition nobody draws

Every picture of this has two boxes and a lightning bolt between them. Real systems are not shaped like that.

Lessons 013 and 014 sharded Galewatch across eighteen machines, keyed on the farm and then the turbine: thirteen sites on a machine each, three pairs of small sites doubled up, and Ardnave Point's two hundred turbines split across two, so twenty farms over eighteen machines.

Take one machine off the network. Not the cluster. One.

Tarrow Ridge panel   its own machine, answers in 10 ms
Kilmore Sands panel  that machine, answers never
fleet roll-up        needs all eighteen, answers never

Kilmore Sands, 140 turbines, is the largest farm that still fits on one machine, and that machine is the one that went. Its engineers get nothing. The other nineteen farms are perfect, answering in the under ten milliseconds lesson 013 preserved by cutting this way. And the fleet roll-up, the one screen showing every farm at once, is a scatter-gather across all eighteen, so it returns when the last machine does and one machine is never returning. Seventeen eighteenths of the product is fine and the view everybody looks at is dead.

Ask whether Galewatch is available and there is no answer, because the question has the wrong shape. It is available for nineteen farms and unavailable for one, in the same instant, and it has lost a screen that no single shard could have broken.

The roll-up now has to make today's choice on its own account. It can refuse, which is correct and useless. Or it can draw nineteen farms and say plainly that the twentieth is unknown. Lesson 023 said that when you cannot be fresh you put the number's age on the glass. Widen it: an answer that does not say what it is missing is not a partial answer, it is a lie with a chart on it.

Lesson 027 owns partial outages. What today needs is that the ragged version is the normal one, and that a system no more has a single answer to today's question than it has a single latency.

How much of your work can wait

While that machine is unreachable, Kilmore Sands does not stop generating readings. A hundred and forty turbines at one reading every two seconds is seventy a second, so an hour of partition is 252,000 readings and, at the 200 bytes lesson 002 sized them at, about 50 megabytes. It waits on the flash inside the turbines, which lesson 007 called the only copy of those readings in the world while it is there. Then it arrives, and lesson 017 has been through what that arrival costs and who it starves.

Nothing was lost. The partition was survivable because the work could wait.

Now the other side of Galewatch. An engineer in a site office at half past three wants to know what a turbine is doing at half past three. No flash memory anywhere can hold that request until the network comes back, because by then it is a different question.

That asymmetry is worth more than the letters are. A write can usually be made to wait. A person looking at a screen cannot.

Which means most of what this course has taught about queues was secretly about today. Lesson 017's buffer with a memory, lesson 018's retry to a deadline, lesson 007's flash at the edge, lesson 020's budgeted retries: each buys the right to be unreachable for a while without losing anything. They make you neither consistent nor available. They convert an outage into a delay, and a delay is the one failure a customer sometimes forgives.

So the real question in front of a design is rarely C or A. It is how much of this work can wait, for how long, and who is standing there while it does. Marlow's confirmation emails can wait four and a quarter hours, which lesson 018 measured by adding up a backoff schedule nobody chose. Marlow's sign-in cannot wait four seconds.

The partition you scheduled

Go back to May, three weeks before the Wednesday. Nine edge caches served a price box A had retired, for ten minutes, and lesson 023 spent a lesson on it without once calling it a partition. Look at the shape though. Nine copies of a fact, and for ten minutes not one could hear the machine where the fact had changed. No cable was cut. The delete message went to the shared cache and was never addressed to the edges at all.

Functionally that is the Wednesday, arrived at by design rather than by accident. Lesson 022 called an edge cache replication lag you chose. The sharper version is that a TTL is a partition with a timer on it. You decided in advance how long some of your copies would be unable to hear the truth, and the timer is the only reason it ended.

Which is also why the trade cannot be a badge a database wears. During those ten minutes in May, Marlow was available and wrong at nine edges, and at the same moment as consistent as a shop can be at the checkout, because lesson 015's conditional update decides and writes on box A in one statement. Same shop. Same second. Both answers, on different requests.

Lesson 023 put it as buying strong consistency per read rather than per system. Today is that sentence with the network broken: the trade is made per operation and per moment. A database's documentation tells you what one of your copies does by default, and your system is that database plus every copy you have put in front of it, which at Marlow is a replica, a shared cache and nine edges.

The Wednesday showed the other half of why this is hard. Lesson 011 sent session lookups to the replica, and lesson 012 measured what that exposure costs: a median lag of 6 milliseconds against a 45 millisecond gap to the customer's next read, which lost about three review posts in a hundred. The same exposure has always sat on a freshly written session row, at a rate low enough that a customer who signs in twice blames their own typing. Freeze the copy and the three percent becomes everybody.

A partition does not invent new failures. It takes the small numbers out of the ones you already had.

What to write down before Wednesday

Decide per operation, in advance, and write it next to the operation rather than in an architecture document. The question is never whether the shop is consistent. It is what this request should do when this machine cannot hear that one.

Four rows, and the shop has never written any of them down. Search and the book page may answer from a stale copy, which they already do at three radiuses on an ordinary Tuesday. The bound in the first row is what is worth adding: a copy allowed to be stale should know how stale it is and refuse past some number, because an unbounded stale answer is exactly what the Wednesday served for an hour and fifty minutes. Sign-in and the stock guard refuse, the first because a session that half exists costs a customer their basket, the second because lesson 023 settled it. A read that decides is the first half of a write.

When you refuse, say so out loud. Lesson 021's line was that the most expensive way to refuse a request is to refuse it silently, and a partition is where that bill arrives. A 503 with a sentence in it is information the customer and your logs can both use. A stale 200 is a decision you made on their behalf without telling them.

And do not build a failure detector you have not costed. Lesson 011's four things are a death certificate, a promotion, a repoint and a fence; Marlow's script had the promotion, and a promotion with no repoint and no fence is not a failover, it is a second opinion. The same question with a lock in it is lesson 035.

I have no clean answer to the detector problem and nor does anybody. What the industry buys instead is a shared opinion about who is alive, which is what lessons 032 and 033 are for, and a shared opinion still is not a correct one, only one you can reason about.

Then practise the switch. Lesson 011 noted the founder never had.

Recap

A partition is a Tuesday, not a thought experiment. Some machines cannot hear others while everything is running: a switch, a rule, a saturated link, a paused process. It is not lesson 013's table partitioning, and it is not a client that cannot reach you.

Every failure detector is a bet about the future dressed as a measurement of the past. Silence from a peer is identical whether it is dead, paused or fine behind a broken link, and on Galewatch's own latency profile a healthy path crosses a 2.1 second threshold about once every two seconds.

There are two answers and no third. Answer and give up behaving like one copy, or refuse and stop being a service; waiting is refusing with worse manners. Marlow chose the first by leaving replication asynchronous, and lesson 011 published the switch that chooses the second, where one dead standby stops every commit. Partition tolerance was never on the menu: the second copy hands it to you. One machine escapes it at lesson 001's price, Stagefront escapes it for one operation by keeping the seats on one machine and paying in capacity.

The cost of a partition is not its length. Forty three seconds at GitHub in October 2018 became twenty four hours and eleven minutes of degraded service, about two thousand to one, because recovery reconciles decisions rather than packets. A machine made that call from a policy written months earlier; the humans made the real one afterwards.

The ragged partition is the normal one. One machine of Galewatch's eighteen goes quiet, nineteen farms stay perfect, and the screen everybody watches is dead, because a scatter-gather finishes when its slowest leg does. An answer that does not say what it is missing is a lie with a chart on it.

Ask how much of the work can wait. Queues, buffers and deadlines make you neither consistent nor available; they convert an outage into a delay, which is the one failure people forgive. A write waits on a turbine's flash. A person watching a dashboard cannot.

A TTL is a partition with a timer on it, which is why the trade is per operation and per moment rather than a badge. And a partition invents no new failures: it takes the small numbers out of the ones you already had, which is how three lost review posts in a hundred became all of them, and every sign-in with them.

Check your understanding

1. Marlow's founder wants to rewrite the watcher rather than delete it. Pick the number that replaces thirty seconds and defend it with something other than taste. Then say what the script must do after promoting for the promotion to be worth anything.

2. Take lesson 011's four routed reads one at a time. For each, say whether it should answer from a frozen copy or refuse, and how you would set the bound past which it stops answering.

3. One of Galewatch's eighteen machines is unreachable for forty minutes, and it is the one holding Kilmore Sands. Say what the fleet roll-up should put on the screen, and roughly how much data is waiting at the turbines when it comes back.

4. A colleague says the database they have chosen is "AP, so it stays up during network trouble". Name two operations in a service you have worked on where that is the wrong answer, and say what you would change instead of the database.

5. A partition at 10:02 cuts Stagefront's ticket database off from half its application tier, inside the window where lesson 003 promised at least 99.95 percent of purchase requests succeeding in under two seconds. Say which half should keep taking money, and what would have to be true to let the other half sell.

Next lesson

025 Back-of-the-Envelope Estimation. Every choice today assumed somebody already knew how many machines, copies and requests were involved; next lesson works those numbers out in your head, before anyone has built anything to measure.