When the network splits
Servers in a cluster talk to each other over a network, and networks fail in an awkward way. Sometimes a link breaks so that the servers are all still running, but they fall into two groups that cannot reach each other. This is a network partition.
From the inside, a partition looks exactly like a crash. If server D stops hearing from server A, it has no way to tell which happened:
- A is dead, or
- A is fine and the cable between them is not.
D has to act without knowing. That uncertainty is the root of the problem.
Two leaders
Suppose the rule is the obvious one: "if you cannot reach the leader, choose a new one".
x = 1
x = 1
Start. Five servers keep copies of the same data. A is the leader: all writes go through it and are copied to the others.
- Leaders
- 1
- Network
- connected
Each side did something reasonable. The left side kept its leader. The right side, hearing nothing, elected its own. Both accepted writes. Both told their clients "saved".
When the network heals, the cluster has two leaders and two different versions of the truth. This is split brain. One of the two confirmed writes has to be discarded, and the client that made it was told it succeeded.
For a shopping cart that is annoying. For a bank balance or a lock, it is a disaster.
The fix: require a majority
Add one rule: nothing counts unless more than half of all the servers agree to it. Not half of the servers you can see. Half of the total.
That number is called a quorum. With 5 servers it is 3.
x = 1
x = 1
Start. Five servers keep copies of the same data. A is the leader: all writes go through it and are copied to the others.
- Leaders
- 1
- Network
- connected
The left side has 3 of 5. It has a quorum, keeps working, and accepts writes. The right side has 2 of 5. It cannot elect a leader and it refuses writes.
When the link returns, the right side discovers it is behind and copies what it missed. There was never a second history to reconcile.
Why it always works
The argument fits in two lines.
Example
Two majorities must overlap
A majority of 5 is at least 3 servers. Two separate groups of 3 would need 6 servers. There are only 5.
So two groups cannot both have a majority at the same time. However the network splits, at most one side can act.
It does not matter where the cut falls: 3 and 2, 4 and 1, or 2 and 2 and 1. At most one piece holds a majority. Sometimes none does, and then the whole cluster pauses until enough servers can talk again. Pausing is safe. Disagreeing is not.
| Split of 5 servers | Who can keep working |
|---|---|
| 5 and 0 | Everyone |
| 4 and 1 | The group of 4 |
| 3 and 2 | The group of 3 |
| 2, 2 and 1 | Nobody, until the network recovers |
The price
Look again at the right-hand side in the second animation. Two healthy servers, a client that wants to write, and the answer is "no".
That is the trade. During a partition a system must choose:
- Stay consistent: the minority side refuses requests. Some users get errors, and nobody ever sees wrong data.
- Stay available: every side keeps answering. Nobody gets an error, and the sides may disagree until the conflict is sorted out later.
You cannot have both while the network is split. This is the heart of the CAP theorem. Quorum-based systems choose consistency. That is the right choice for money, locks and configuration. A shopping cart or a "like" counter might reasonably choose availability and merge afterwards.
x = 1
x = 1
Start. Five servers keep copies of the same data. A is the leader: all writes go through it and are copied to the others.
- Leaders
- 1
- Network
- connected
Quorums for reading and writing
The same overlap argument works for ordinary reads and writes, not only for elections.
With N copies of the data, require a write to be confirmed by W servers and a read to ask R servers. If W + R is greater than N, every read is guaranteed to include at least one server that has the latest write.
Example
Five copies
N = 5, W = 3, R = 3. A write lands on 3 servers. A read asks 3 servers. Since 3 + 3 is more than 5, the two groups share at least one server, and the read sees the new value.
Lower W for faster writes and raise R to compensate, or the other way round.
Key takeaways
- A network partition splits a cluster into groups that cannot reach each other. From inside, it looks like a crash.
- If each group elects its own leader, both accept writes and the data diverges: split brain.
- Requiring a majority of all servers (a quorum) means at most one group can act.
- Two majorities always share at least one server, so they cannot both exist.
- The cost is that the minority side must refuse requests until the network heals.