Pointer Walk

Split Brain and Quorum

The network splits and both halves elect a leader. Requiring a majority is what prevents two histories.

Distributed SystemsAdvanced10 min read

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".

No majority ruleInteractive
Aleader
Bfollower
Cfollower

x = 1

linked
Dfollower
Efollower

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.

A leader needs a majorityInteractive
Aleader
Bfollower
Cfollower

x = 1

linked
Dfollower
Efollower

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 serversWho can keep working
5 and 0Everyone
4 and 1The group of 4
3 and 2The group of 3
2, 2 and 1Nobody, 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.

No majority ruleInteractive
Rule
Aleader
Bfollower
Cfollower

x = 1

linked
Dfollower
Efollower

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.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    8 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress