Consensus and leader election
- Lesson 17 of 40
- 14 min
- Advanced
- 12 steps
Copying data between servers is easy while everything works. The hard part starts when the leader goes quiet and nobody knows whether it died or is just cut off. Here you will see how a cluster decides without getting it wrong.
- Leaders
- 1
- Term
- 3
- Conflicts
- 0
- Failures tolerated
- 1
- request
- response
- health check
- waiting in queue
Step 1 of 12
Concept
One leader, two followers
You saw it in Replication: one leader node takes every write from the app server and copies it to its followers. If the leader fails, a follower is promoted and the service carries on.
That sentence hides the hard question: who decides that the leader has failed? And what happens when they get it wrong?
Step 2 of 12
Problem
Two leaders at once
A network fault isolates A from B and C. A is still alive and serving app server 1, but B stops hearing from it, decides the leader is dead and promotes itself.
Now two leaders accept writes. A sells ticket 41 to Lucía; B sells that same ticket to Mateo. Those are two histories you cannot merge without throwing one away: that is split brain.
What changed
- The network between A and the others is cut
- B makes itself leader
- Two leaders, two different histories
Step 3 of 12
Solution
Nothing counts without a majority
The fix is a single rule: a leader is only elected, and a write only confirmed, when more than half of the nodes accept it. With three nodes, that means two.
Cut off, A can only count itself: 1 of 3. It cannot confirm anything, so app server 1's writes wait until they time out. B and C make 2 of 3: they can elect a leader and carry on. Two majorities of the same group always share at least one node, so two leaders can never win the same term.
What changed
- Rule: every decision needs 2 of 3
- A on its own: cannot confirm writes
- B + C: a valid majority
Step 4 of 12
Technique
How a leader is elected
This is how the Raft algorithm does it. The leader sends heartbeats at short intervals. Every follower runs a timer of random length; if it runs out with no heartbeat, that follower becomes a candidate.
B's timer runs out first. B opens term 2, votes for itself and asks the others for their vote. Each node gives one vote per term, and only to a candidate whose log is at least as up to date as its own. C agrees: 2 of 3, and B leads term 2.
What changed
- B: no heartbeats, stands for term 2
- C votes for B
- B wins with 2 of 3 and starts sending heartbeats
Step 5 of 12
Technique
A majority commits the write
Writes follow the same rule. App server 2 asks the leader for ticket 41 → Mateo. B appends it to its log as entry 4 and sends it to the followers.
As soon as a majority has it stored (B and C), the entry is committed. Only then does B apply it and answer “saved”. A committed entry survives any failure that leaves a majority standing.
What changed
- B appends entry 4 to its log
- C stores it: 2 of 3
- Committed: app server 2 hears “saved”
Step 6 of 12
Solution
The old leader steps aside
The network recovers. A, still believing it leads term 1, gets a heartbeat from B stamped with term 2. A higher term always wins: A becomes a follower at once.
A's log holds one entry that never reached a majority: the sale to Lucía, which app server 1 never saw confirmed. A drops it and copies B's log. The three nodes are identical again and nothing that was committed has been lost.
What changed
- Network recovered
- A sees term 2 and becomes a follower
- A's uncommitted entry is dropped
- A copies B's log
Step 7 of 12
Concept
How many nodes?
A cluster of N nodes needs a majority of half plus one (N/2 rounded down, plus 1). With 3 nodes the majority is 2 and it survives 1 failure; with 5, the majority is 3 and it survives 2.
A fourth node is a trap: the majority rises to 3 and you still survive only one failure, with one more machine that can break. Use odd sizes and put each node in a different zone, so a single outage cannot take the majority with it.
What changed
- Each node in its own availability zone
Step 8 of 12
Problem
The leader that froze
Leader B freezes for a long while, say 20 seconds: a long garbage-collection pause, or its virtual machine being moved to another host. A and C stop getting heartbeats, elect C for term 3 and move on.
Then B wakes up. As far as it knows no time has passed, and it is still the leader. Before any message can correct it, it finishes what it was in the middle of: it writes a file to shared storage, right over the new leader's work.
What changed
- B freezes for about 20 s
- A and C elect C: term 3
- B wakes up and writes as if it still led
Step 9 of 12
Solution
Fencing tokens
The fix does not rely on B noticing anything. Every request from a leader carries its term number as a fencing token, and the storage remembers the highest token it has seen.
C has already written with token 3. When B's write arrives with token 2, the storage refuses it: the resource itself keeps the stale leader out. Shortly after, B gets a heartbeat from term 3 and becomes a follower.
What changed
- Every write carries the leader's term
- Storage refuses tokens lower than the highest it has seen
- B's write refused: 2 < 3
Step 10 of 12
Trade-off
What consensus costs
Every write waits for a round trip to a majority. Within one data center that is a millisecond or two; with nodes in different regions, around 50 to 150 ms on every write (example values).
All writes go through a single leader, so throughput is capped by one machine. And when no majority can be reached, the cluster accepts no writes, on purpose.
What changed
- Each write: +1 round trip to the majority
- An election pauses writes (≈ 1 s in this example)
Step 11 of 12
Concept
You use it far more than you build it
Hardly anyone implements Raft or Paxos themselves. You run a small coordination cluster of 3 or 5 nodes and keep only the critical facts in it: who the leader is, the configuration and who holds each lock.
Everything else leans on it: a container orchestrator keeps its cluster state there, a replicated database uses it to decide which replica is the primary, and a scheduler makes sure each job runs on exactly one machine. Many distributed databases also run consensus inside every partition.
What changed
- Three systems that depend on the cluster
Step 12 of 12
Summary
Recap
A timeout cannot tell a dead node from an unreachable one: naive failover ends in split brain.
Majority rule: elections and writes need more than half of the nodes, and two majorities always intersect.
Terms order the leaders: the higher term wins and a stale leader steps aside.
A write is committed once a majority has stored it, never before.
Run 3 or 5 nodes across zones, and use fencing tokens for anything outside the log.
← → step · R replay · Space pause
You will learn
- Why naive failover leads to split brain (covered)
- What a majority (quorum) is and why two always intersect (covered)
- Terms, votes and elections in Raft (covered)
- When a write counts as committed (covered)
- How many nodes a cluster should have (covered)
- Fencing tokens against leaders that froze (covered)