Distributed systems
Majority quorums
A decision counts only when more than half the nodes accept it. Because any two majorities overlap, two conflicting decisions can never both win. This is why consensus clusters have 3 or 5 nodes.
A cluster of machines must sometimes make one decision, such as "who is the leader?". If two groups of nodes each decide alone, you get split brain. A majority quorum prevents that. A decision needs more than half of the nodes to accept it.
Concept
Before you start. A crash is a node that stops responding. A partition is a network split that cuts nodes off from each other. A quorum is the minimum number of nodes whose agreement counts. See failure models for more on crashes and pauses.
The big idea
Think of a committee of five. A motion passes with three votes. Two different motions cannot both get three votes out of five, because the two groups of three must share at least one member. That shared member cannot vote for both.
This overlap is the whole trick. Any two majorities of the same set share at least one node. The protocol forbids that node from accepting two conflicting values.
Walking through it
With n nodes, a majority is more than half. Write n = 2f + 1. Then the majority is f + 1, and the cluster keeps working while up to f nodes are down.
| Cluster size | Majority | Failures tolerated |
|---|---|---|
| 1 | 1 | 0 |
| 2 | 2 | 0 |
| 3 | 2 | 1 |
| 4 | 3 | 1 |
| 5 | 3 | 2 |
| 7 | 4 | 3 |
Look at the 3 and 4 rows. Four nodes tolerate exactly one failure, the same as three. The fourth node adds cost and one more machine to write to, and gives no extra safety. That is why clusters are almost always 3 or 5 nodes.
During a partition, the side with a majority keeps going. The minority side cannot commit anything. That is consensus choosing consistency over availability.
Common mistakes
- Using an even number of nodes for extra safety. Four nodes tolerate the same single failure as three.
- Thinking a majority means all nodes. Only
f + 1of2f + 1need to agree. - Spreading nodes unevenly across zones. Two nodes in one zone and one in another means losing the first zone loses the quorum.
Check yourself
- How many failures does a 7-node cluster tolerate? Three. A majority is four, so three nodes can be down.
- Why can't two conflicting values both get a majority in a 5-node cluster? Each majority has at least three nodes out of five, so the two groups overlap. The shared node cannot accept both values.
Key takeaways
- A decision needs more than half the nodes to agree.
- Any two majorities overlap, so conflicting decisions cannot both win.
2f + 1nodes tolerateffailures.- Use 3 or 5 nodes. Even sizes add cost without extra safety.
Further learning
Next, see how Raft uses this rule to choose a leader in Raft leader election.
The Raft site has an animated visualization of majorities and elections.
Raft Consensus AlgorithmRaft is a consensus algorithm that is designed to be easy to understand.raft.github.ioRelated
Consensus and Raft
How a cluster agrees on one value or one log despite crashes and partitions, how Raft works, and where etcd, ZooKeeper and consensus-backed databases fit.
What goes wrong in distributed systems
Partial failure, unreliable networks, paused processes and timeouts, and the fencing tokens and failure detectors that let you build correct systems on top of them.
Quorum reads and writes
With N replicas, a write succeeds after W of them acknowledge, and a read waits for R. When R + W is greater than N, every read overlaps every successful write in at least one replica.