Copies vs. Splits

Courtyard’s database is now both divided and copied. It has Chapter 4’s shards, and each shard has Chapter 3’s replicas, a primary and two copies. The two ideas are independent of one another: splitting is about how much one machine holds, and copying is about how many machines hold it. Combined, they give you capacity, write throughput, read throughput, and a machine to promote when a primary dies. It is the shape of almost every large database in the world.

Then a switch fails in the building, and for forty seconds the primary of shard 3 cannot reach either of its replicas. Nothing is dead. The primary is up and serving. The replicas are up and serving reads. They just cannot talk to each other. It is Part II Chapter 7’s convergence, inside your own datacentre. And while the switch is down, a write arrives at the primary: Mira sends a message to a conversation that lives on shard 3. The primary has to do something with it, and what it has run out of is the certainty it would need to know what.

You have two options, and you have to pick one now, in the forty seconds, without knowing how long they will last or whether the replicas are gone for good.

You could refuse the write. The primary cannot ship the change to its replicas, so it declines to accept it. Mira’s message fails to send and she gets an error, and so does everyone else writing to shard 3 for the next forty seconds. But the data stays consistent. Every copy that anyone can read agrees, because nothing changed on the primary that the replicas do not also have, and when the switch recovers there is nothing to reconcile.

Or you could accept the write. The primary stores Mira’s message, acknowledges it, and queues the change to ship later. Mira’s message sends, and Courtyard stays available; nobody sees an error. But now the primary has a message the replicas do not. A read from a replica shows the conversation without it. Theo, reading from a replica, replies to the message before Mira’s, because he cannot see hers. When the switch recovers the replica applies Mira’s message, and there is now a conversation in which Theo’s reply came after a message he provably had not seen. The copies diverged, and the divergence is baked into the data.

Do the exercise properly. Choose to refuse, and watch Courtyard show errors for forty seconds. Now choose to accept, and watch two copies drift apart and a conversation come out of order. Neither is good, and one of them is yours, because a write arrived and the primary had to do something.

Now let’s make it worse. Your monitoring notices that the primary of shard 3 has not reported to the replicas in thirty seconds, which is Part I Chapter 13’s heartbeat, missed three times. The automation concludes that the primary is dead and does what it was built to do, which is to promote a replica. The replica starts accepting writes, and the application is told the new primary’s address.

The old primary is not dead. It is on the other side of a failed switch, still up, still accepting writes from the application servers that can reach it. There are now two machines that each believe they are the primary for shard 3, each accepting writes for the same data, neither aware of the other. Mira’s message lands on one. Theo’s reply lands on the other. Priya’s edit to her profile lands on one, and her second edit, a moment later, is routed to the other. For forty seconds shard 3 is two shards with the same name, and every write is a coin flip.

Then the switch recovers, the two machines can see each other, and there is no automatic answer to the question of which one is right. Both have writes the other does not. Some of those writes conflict, as Priya’s two edits to the same field do. Someone has to decide, and whatever they decide, some acknowledged writes will be undone. Users were told that things happened which are about to un-happen.

This is a split-brain, and it is the worst failure a replicated system can have, because it does not lose data cleanly. It manufactures two incompatible histories and then forces you to destroy one. The heartbeat that triggered it was doing its job: it saw silence and declared death. It just could not tell death from a broken switch, which Part I Chapter 13 warned you it never can. Preventing this turns out to be surprisingly deep. You cannot even stop the old primary from believing it is still in charge, because a machine cut off from the others has no way to know it has been replaced, so the fix has to work at the storage rather than at the machine. It is hard enough that it gets a chapter of its own, the second to last. For now it is enough to see that the promotion you built to survive a dead primary is what turns an unreachable one into two.

Only now, having chosen both ways and been burned both ways, is it worth naming what you felt. When the copies of a piece of data cannot communicate, which the field calls a partition, a machine holding one copy that receives a write has two moves and no more. It can answer the write, and risk disagreeing with the copies it cannot reach, or it can refuse, and be unavailable until they are reachable again. It can be consistent or it can be available. It cannot be both during a partition, and this is not an engineering limitation to be clever about. It is arithmetic. A machine that cannot hear the others either speaks alone or stays silent.

The result is usually presented as a triangle, with consistency, availability and partition-tolerance at the corners and an instruction to pick two, and the triangle misleads in one important way. Partition-tolerance is not a choice. Partitions happen. Part II Chapter 7 showed you a cable on the seabed, and this chapter has shown you a switch in your own building. You do not get to pick “no partitions.” What you pick is what to do when one happens, and that is consistent or available, and the choice is made per operation, in advance, by how you configure the machines.

There is an everyday version of this that needs no partition at all. Even with every switch working, reading from a replica is a trade. The replica is faster, because it is closer or less loaded, and it is staler, by Chapter 3’s lag. Every single read from a copy chooses latency over freshness by some amount. The partition is only the moment at which the trade becomes stark. When things are healthy the trade is still there, in every read that does not go to the primary.

Refusing everything and accepting everything are the two ends of a scale, and there is a dial between them. It is worth deriving, because it is what real systems actually turn. Suppose each piece of data has N copies; say three. Instead of one primary that must reach all its replicas, let a write be accepted once W copies have stored it, and let a read consult R copies and take the freshest answer. Now pick W and R so that W plus R is greater than N. With three copies, write to two and read from two. Any two copies written overlap any two copies read in at least one place, so a read always touches at least one copy that has the latest write. You get consistency without every copy having to be reachable. One copy can be down or partitioned, and both writes and reads proceed, because two out of three is enough.

Turn the dial. With W equal to N and R equal to 1, every write must reach every copy, which is slow, and any one unreachable copy stops writes, but a read from any single copy is guaranteed current. With W equal to 1 and R equal to N, writes are instant and always succeed, but every read has to consult everything. With W and R both 2 out of 3 you have the balanced setting, surviving one failure for both reads and writes. Set them so that they do not overlap, W and R both 1, and you have chosen availability: fast, always up, and a read can miss the latest write.

The overlapping majority is called a quorum, and the sliders are the honest form of the consistent-or-available choice. It is not a philosophy but two numbers, chosen per kind of data, with a cost you can read off. Reads that consult two copies pay two network round trips’ worth of latency. Writes that wait for two copies pay the slower of the two. Nothing is free; the dial lets you pay in the currency that hurts least for each piece of data.

What can now fail, then, is divergence: two copies that both believe they are right, with no automatic way to reconcile, and acknowledged writes that may be undone. You will decide, per piece of data, which side of the choice it lands on. Chat messages will probably be available, since a message that arrives a little out of order is better than a message that fails to send. Account balances, if there ever are any, will be consistent, since an error is better than two truths about money.

And there is the split-brain, a promotion during a partition that creates two primaries. The heartbeat cannot prevent it, because the heartbeat cannot tell a dead machine from an unreachable one. Something stronger is needed to guarantee at most one, and that is Chapter 19. Revision five of the design document records the chapter: certainty ran out; you chose, per data type, whether a partitioned copy refuses or accepts writes, and tuned quorums; copies can diverge, acknowledged writes can be undone on reconciliation, and a false death can produce two primaries.