Consensus and Leader Election

The problem: a leader that only looks dead

The usual failover promotes a follower when the leader goes quiet. Say a shop's database runs on two servers: A leads, and B takes over if it hears nothing from A for 10 seconds. There's 1 ticket left for tonight's show.

Now the network splits in two: A and App server 1 on one side, B and App server 2 on the other. A is fine, but after 10 seconds of silence B decides A has crashed and promotes itself. Both servers now act as leader:

event                        Database A    Database B
start                        1 left        1 left
network splits               1 left        1 left
B promotes itself            1 left        1 left
Ana buys via App server 1    sold to Ana   1 left
Ben buys via App server 2    sold to Ana   sold to Ben
network heals                sold to Ana   sold to Ben

Both buyers were promised the ticket. Two servers acting as leader at once is split brain: each takes writes the other never sees, and their data conflicts.

A better timeout can't fix it. To B, a crashed A, a frozen A (stuck in a long garbage-collection pause) and a cut-off A all look the same: silence. A broken network or a pause can outlast any wait, and asking A "are you alive?" crosses the same broken network. You need a rule that makes two leaders impossible.

Majorities: why two leaders can't both win

Add a third server and one rule: a server may lead only with votes from a majority of all the servers, its own included, and each server votes once. With 3 servers a majority is 2, and two candidates can't both get 2 of 3 votes: any two majorities share a server. If the network splits A | B, C, only B and C's side can elect a leader. A, alone with 1 vote, can't lead, so its side stops taking writes until the network heals.

The majority counts every server, including those that are down; otherwise each side of a split could call itself one. So a cluster survives as many failures as it has servers beyond a majority:

servers   majority   can be down
2         2          0
3         2          1
4         3          1
5         3          2
6         4          2
7         4          3

An even count adds a machine but no safety, and a 2 | 2 split of 4 servers leaves neither half a majority. With 2 servers a majority is both of them, which is why the two-server failover had to guess. Clusters run 3 or 5 servers, sometimes 7: every write waits for a majority, so more servers means more to wait for.

How a Raft election works

Raft, a widely used consensus algorithm, numbers its elections: each term starts with one and has at most one leader.

1. The leader sends each follower a heartbeat, say every 50 ms, which restarts its election timer.
2. Each follower picks a random timeout, say between 150 and 300 ms. If its timer runs out with no heartbeat, it starts the next term, votes for itself and asks the others.
3. Each server votes once per term, for the first candidate that asks, if the candidate's log is at least as up to date as its own.
4. A candidate with votes from a majority leads that term. Its heartbeats keep the others' timers from running out.

A run with 5 servers: A leads term 1 and freezes in a long pause at t = 0, right after a heartbeat. The followers' timeouts are B 220 ms, C 160 ms, D 290 ms and E 250 ms.

time       event                                   terms A B C D E
0 ms       A's last heartbeat, then A freezes      1 1 1 1 1
160 ms     C's timer runs out: term 2, asks        1 1 2 1 1
160 ms     B, D and E vote for C; A hears nothing  1 2 2 2 2
160 ms     C has 4 of 5 votes: leader of term 2    1 2 2 2 2
1,000 ms   A wakes, sends a term-1 heartbeat       1 2 2 2 2
1,000 ms   refused; A steps down into term 2       2 2 2 2 2

Random timeouts make it likely that one server asks well before the others. If two ask at once and split the votes, nobody leads that term; they retry after new random waits.

Terms: how an old leader is stopped

When A wakes up, it still believes it leads term 1. Every other server, now in term 2, refuses its term-1 heartbeat and answers with its own term. Two rules do this: a message from an older term is refused, and a server that sees a newer term adopts it and becomes a follower. So A steps down, and until it does, nobody accepts anything from it.

The term works like a fencing token: a number that only grows, checked by whoever receives the request. Use it outside the cluster too: stamp the leader's writes to a job store with its term, and have the store refuse terms older than the newest it has seen.

Committing a write on a majority

The leader adds each write to its log, stamped with its term, and sends it to every follower. It tells the client "saved" only once a majority, 3 of 5 counting itself, has stored it: the write is then committed. Saying "saved" on the leader alone loses the write if the leader crashes first; waiting for all 5 lets one crashed server stop every write.

A committed write survives any 2 servers failing: a copy remains. And the next leader always has it: it needs 3 votes, at least one from a server that stored the write, which won't vote for a candidate missing it.

You rarely build this yourself

Real consensus has many more corner cases, and subtle bugs lose data. Most designs use a coordination service such as ZooKeeper, etcd or Consul. It runs on its own 3 or 5 servers; your servers ask it who leads, take locks from it and read shared settings. etcd and Consul use Raft; ZooKeeper uses a similar protocol, Zab. It's for small data that must be right, not your app's data: each of its servers keeps all of it, and every write waits for a majority. Some databases, such as CockroachDB, run Raft inside for their own failover.

Where it shows up in system design interviews

Whenever a design has one of something: one leader, one scheduler, one lock holder. The interviewer asks what happens when it dies and what stops two. A strong answer: two or more instances elect the leader through a coordination service such as etcd or ZooKeeper, so only a majority can elect one; each leader gets a new term; and the systems it writes to refuse old terms. "A standby takes over after a timeout", alone, is the split-brain answer.

Common interview questions

What is split brain, and how do you prevent it?

Two servers acting as leader, after a network split or a long pause made a live leader look dead. Elect leaders by majority vote, so only one side of a split can, and fence off old leaders with terms.

Why do consensus clusters have an odd number of servers?

A majority of 4 is 3, so 4 servers survive 1 failure, the same as 3, and a 2 | 2 split stops both halves. 5 servers survive 2 failures, and 6 still survive only 2.

What happens when an old leader comes back?

Its messages carry its old term, so the others refuse them and reply with the newer one, and it steps down. Systems it writes to should check the term too, like a fencing token.

Summary

• Split brain: a cut-off leader looks dead, and two leaders take conflicting writes.
• Majority: lead only with votes from more than half the servers; a minority side stops.
• Odd sizes: 3 servers survive 1 failure, 5 survive 2; even counts add no safety.
• Terms: the first timer to run out starts a new term; the newest term wins, and an old leader steps down.
• Commits: a write is saved once a majority has stored it.
• In practice: a coordination service such as ZooKeeper, etcd or Consul.