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
Zone 1Zone 2Zone 3App server1App server 1App server2App server 2node Anode Bnode Cshared storageOrchestratorstateOrchestratorDatabaseDatabaseScheduler1 runnerSchedulerleaderfollowerfollowerleader · ticket 41 → Lucíaleader · ticket 41 → Mateofollowernetwork cutleader · term 21 of 3 · cannot commitfollowernetwork cutMajority (quorum)3 nodes2 must agree5 nodes3 must agreetwo majorities share a nodeonly one side can decidecandidate → leader · term 2voted for Bstill on term 1vote for me? · term 2Election · term 21B's timer runs out2B: term 1 → 2, votes for itself3B asks C for its vote4C agrees: 2 of 3, B leadsone vote per node per term1 2 3 · 4 Mateo1 2 3 · 4 Mateo1 2 3 · 4 Lucía uncommittedappend entry 4Commit rule1the leader appends the entry2sends it to every follower3a majority stores it→committed: answers “saved”follower · term 2 · caught upleader · term 2followerheartbeat · term 2leaderCluster size3 nodesmajority 2survives 14 nodesmajority 3survives 1, no gain5 nodesmajority 3survives 27 nodesmajority 4survives 3awake · thinks it leads term 2leader · term 3followerreport.csv · overwritten by Bstale writerefused · becomes followerleader · term 3followerhighest token seen: 3token 3token 2leader · waits for 1 ackfollowerfollower+1 round tripThe billevery write+1 round tripa single leaderone machine's ceilingno majorityno writesan electionpause ≈ 1 s (example)leader · term 3followerfollowerwhich one is primary?leader · term 3followerfollower
  • 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.

You will learn

  • Why naive failover leads to split brain
  • What a majority (quorum) is and why two always intersect
  • Terms, votes and elections in Raft
  • When a write counts as committed
  • How many nodes a cluster should have
  • Fencing tokens against leaders that froze