Who Decides?

Almost everything in this part has worked by avoiding the need for machines to agree. The stateless servers of Chapter 2 do not coordinate, since any of them can handle anything. The sharding of Chapter 4 divides the data so that machines do not contend for it. Caching, fan-out, and queues were all built to let machines work independently, because independence scales and coordination does not. That was deliberate, and it has carried you a very long way.

But a few things do require agreement, and you have been assuming them all along without building them. Take the shard of Chapter 4. Exactly one machine must be the primary for shard 3, because Chapter 5 showed that two primaries is split-brain, the worst failure there is. Take the scheduled job of Chapter 17. If there is a nightly job that deletes expired data, exactly one worker must run it; with two, you might delete twice or race. Take the promotion of Chapter 3. When a primary dies, exactly one replica must be promoted, or again you have two primaries. A leader, an owner, a runner: over and over the system needs exactly one of something, chosen from among many candidates, and needs it to stay exactly one even as machines fail and networks partition. The resource that has run out is agreement itself.

This is the hardest problem in the book, and like Part I Chapter 21 this is a chapter in which you derive the want precisely and are then shown the machinery rather than asked to build it. Nobody reinvents consensus in a workshop, and the value lies in understanding what it guarantees and what it costs.

To make exactly one machine own shard 3, the natural idea is a lock: a shared record, in some store that every candidate can reach, saying that machine 7 owns shard 3. Before acting as owner a machine must hold the lock, and only one machine can hold it at a time. Machine 7 takes it and becomes the owner, and everyone else, seeing the lock held, stands down. There is exactly one owner, and it seems that you are done.

You are not, because machine 7 can die while holding the lock, and then the lock is held for ever by a dead machine and shard 3 has no owner at all. So the lock must expire. Machine 7 holds it for thirty seconds at a time and must keep renewing it; if machine 7 dies it stops renewing, the lock expires, and another machine can take it. A lock that expires is a lease, and it is the heartbeat of Part I Chapter 13 turned into ownership. You keep proving that you are alive in order to keep the lease, and if you fall silent you lose it.

And now the trap, which is the whole of this chapter. Machine 7 holds the lease on shard 3, and it pauses. A garbage-collection pause, or the operating system descheduling it, or a slow disk, any of the slow things from Part I Chapter 15 arriving at the worst moment, and for forty seconds machine 7 is frozen, doing nothing and renewing nothing. The lease expires. The system, quite correctly by its own rules, grants the lease to machine 8, which becomes owner of shard 3 and starts writing to it. Then machine 7 wakes up. It has no idea that it was paused. As far as machine 7 knows no time has passed, it still holds the lease, and it is still the owner, so it writes to shard 3 too. Two machines both believe they own shard 3 and both are writing. This is the split-brain of Chapter 5, produced by the very lease that was meant to prevent it, because a paused machine cannot know that its lease expired.

You cannot fix this by having machine 7 check the lease before each write, because it can check the lease, which is still valid as far as it knows, then pause, then have the lease expire, then write. The pause can always land between the check and the action. No amount of checking closes the gap, because the gap is time itself, and a paused machine has no way of knowing that time passed. The heartbeat of Part I Chapter 13, once again, and this is the truth that recurs most deeply in the book, cannot distinguish a machine that is alive from one that was dead and came back.

The fix does not try to stop the stale machine from believing it is the owner. It stops the stale machine’s writes from landing, by involving the resource itself.

Every time the lease is granted, you attach a number that only ever goes up. Machine 7 gets the lease with token 51. Machine 7 pauses, the lease expires, and machine 8 gets it with token 52. Now the resource, shard 3’s storage, remembers the highest token it has seen and rejects any write that carries a lower one. Machine 8 writes with token 52; the storage accepts the write and remembers 52. Machine 7 wakes and writes with token 51; the storage sees that 51 is less than 52 and rejects it. Machine 7’s stale write bounces off the resource, not because machine 7 knew it was stale, since it did not, but because the resource knew. This number is a fencing token, and what it does is move the check from the confused holder, who cannot be trusted to know the time, to the resource, which has one simple and reliable rule, never to go backwards.

That is the shape of making “exactly one” hold in fact: not a lock that the holder trusts, but a lease with a monotonic token that the resource enforces. It requires the resource to take part, since the storage has to check tokens, which is why fencing is neither free nor automatic, and why “just use a lock” is a subtly broken instinct that this chapter exists to correct.

There is a deeper question hiding inside the phrase “grant the lease”. The machines that grant and track the lease must themselves agree on who holds it, and they are a distributed system, subject to everything else in this part. If the lease-granting store is one machine, it is a single point of failure, and the whole scheme dies with it. If it is several machines, then they have to agree among themselves on the state of the lease, despite failures and partitions, which is the same “exactly one” problem, one level down.

This is consensus: getting a group of unreliable machines to agree on a value, such as who holds the lease and what the token is, in such a way that they never disagree, even as some of them fail and the network partitions. It is provably hard, and there are famous impossibility results about doing it with perfect guarantees under all conditions. The working algorithms, whose names you will be given rather than asked to derive, achieve it by requiring a majority to agree on every decision: a value is decided only when more than half the machines have durably accepted it. The majority requirement is the quorum of Chapter 5, W + R > N with the machines voting, and it is what prevents split-brain at this level. Two different majorities of the same group must overlap in at least one machine, and that machine will not vote for two conflicting things, so two conflicting decisions cannot both get a majority. A partition that splits the group leaves at most one side with a majority, so at most one side can decide anything, and the minority side stops. This is Chapter 5’s consistent-but-not-available choice: during a partition, the side that cannot form a majority refuses to act rather than risk disagreeing.

There is a practical instruction that matters more than the algorithm, and it is why this chapter ends on restraint rather than on machinery.

Consensus is expensive. Every decision requires a majority of machines to durably agree, which means several network round trips, at the latencies of Part II Chapter 6, and it cannot be sharded or cached away, because the whole point is a single agreed truth. A system that runs every operation through consensus is a system that is slow and does not scale, and you would have thrown away everything the rest of this part built. So the rule is to use consensus for the smallest possible set of facts, and to build everything else so that it does not need it.

You do not reach consensus on every write to shard 3. You reach consensus once, on the fact that machine 7 owns shard 3 with token 51, a small fact that rarely changes, and then you let machine 7 handle all the shard’s writes on its own authority, fenced by the token, at full speed, with no consensus per write. Consensus decides the ownership, and the owner does the work. The expensive agreement happens rarely, over tiny facts, such as who leads, who owns, and what the configuration is; the cheap independent work happens constantly, over all the real data. Every well-built large system uses consensus as a small and precious coordination kernel, often a dedicated cluster whose only job is to hold these few critical facts, and keeps the vast majority of its operations far away from it. You buy consensus as a product, and you do not build it, because the impossibility results and the decades of subtle bugs are a warning. You run it for leader election and configuration and the granting of locks, and you architect everything else, all of Chapters 2 through 18, so that it does not need to ask.

The consensus system is now the ultimate critical dependency, the small kernel that decides who is in charge of everything, so if it is unavailable there are no leadership changes, no failovers, and no lease grants, and the system cannot heal itself even though the data machines are fine. It has to be extremely reliable, and it is kept small partly for that reason. Fencing tokens have to be threaded through to every resource that needs protecting, and a resource that does not check them is a split-brain waiting to happen, the uninstrumented-hop problem of Chapter 18 with worse consequences. And the whole scheme rests on getting subtle things right, clock assumptions, the monotonicity of the token, the size of a majority, which is why the instruction is to use a proven system rather than build one, and to need it as rarely as you can. So the nineteenth revision of Courtyard uses a proven consensus system to hold a minimal set of critical facts, the leaders, owners, and leases, enforced at each resource by monotonic fencing tokens, and architects everything else to avoid needing consensus at all. The consensus kernel is the ultimate critical dependency, and it is kept as small as it can be.