Distributed Systems Core · lesson 3 of 11 · about 35 min
How a group of unreliable machines agrees on one order of events: why a majority is the magic number, a live Raft cluster where you kill leaders and cut networks, how elections and log commits work, what a committed write costs, and why the correct answer to losing the majority is to stop. Tap any for a plain-language card.
The problem
Why a majority? Because any two majorities of the same group must share at least one member. That shared member will not vote for two different leaders in one term and remembers what it accepted, so two leaders can never both gather a majority in the same term. The page checks this by brute force for your cluster size. The price: a cluster of N tolerates only ⌊(N−1)/2⌋ failures, and an even size buys nothing over the odd size below it.
Compare 3 and 4 nodes, and 5 and 6: the even size tolerates no more failures than the one below it.
5 servers need a majority of 3 and tolerate 2 failures. The two smallest possible majorities share at least 1 server, found by checking every pair of 3-server subsets. With each server down 5% of the time, the cluster is available 99.884% of the time.
Brute-force check over every pair of majority-sized subsets; availability is an exact binomial tail assuming independent failures.
Leader election
The cluster below is live. It is a working simplified Raft: 5 servers, 10-20 ms message delays, heartbeats every 50 ms. Kill the leader and watch the followers time out, one becoming a candidate in a higher term and winning. The experiment underneath repeats the failover 60 times for your timeout range: if the range is too narrow, two followers time out together, split the vote and must try again (a ).
Kill the leader twice in a row. Then set the spread to 5 ms and watch the experiment's split votes rise.
Timeouts of 150 to 300 ms: a failure is repaired in about 184 ms on average (worst 390 ms), and 8% of the 60 runs needed an extra term because of a split vote. Shorter timeouts mean faster failover but more false alarms on a slow network; a wider spread makes split votes rarer.
Real simulated Raft (terms, RequestVote, AppendEntries heartbeats, randomised timeouts). One tick is 10 ms. Failover time includes the timeout and one round of voting.
Log replication
Cards show each server's log: solid squares are committed, hatched ones are written but not yet committed (a dot is a leader's no-op). Send commands and watch the commit index advance a round trip later. Then take followers down: with 3 of 5 still alive the cluster keeps committing; with fewer, entries pile up uncommitted.
Send four commands, kill two followers and send more: still committed. Kill a third and they stay hatched.
5 of 5 servers are up, so every command reaches a majority (3) and is committed within about a round trip: 1 committed, 0 still in flight.
Working Raft log replication with the AppendEntries consistency check, majority commit and a leader no-op on election.
Safety
When the network heals, the old leader hears a message with a higher term and steps down. Its uncommitted entries conflict with the new leader's log, so they are deleted and replaced. Nothing that was committed is ever lost, and a client that was told “committed” can rely on it. A client that sent a command to the old leader gets no commit and must retry: that is the price of safety. Press the buttons in order.
Press “Split”, then “Send to the new leader”, then “Heal” and watch the hatched entry disappear.
The cluster is healthy with one leader. Split it to see what the minority side can and cannot do.
The same simplified Raft as before, with a partition applied to message delivery. “Entries deleted” counts log entries a follower removed because they conflicted with the leader's.
What it costs
Messages are the other cost: in steady state each entry costs one append and one acknowledgement per follower, 2 × (N − 1) messages, and every added node raises the work the leader does. More nodes buy fault tolerance, not speed. Multi-Paxos with a stable leader has the same steady-state cost; Raft was designed to be easier to understand and implement, not faster.
Set 5 nodes with 2 near (1 ms) and 2 far (80 ms): the write takes about 3 ms. Then set only 1 near.
With 5 servers, a commit needs the leader plus 2 followers. 2 near followers are enough, so the far ones never hold the write up: about 3.1 ms (p99 3.7 ms). At 5K commits a second the leader exchanges 40K messages a second.
4,000 seeded commits: latency = fsync + the k-th smallest follower round trip (log-normal jitter). Messages: one append plus one acknowledgement per follower.
Does it need consensus?
Consensus is powerful and expensive. Use it only when the problem truly demands agreement. Each answer is worth 20 XP.
Ask: must exactly one answer win? and is a wrong or duplicate answer a real problem?
Choosing exactly one leader for a database cluster, even when messages are delayed or lost.
Tip: press 1 to 3 to answer, Enter for the next one.
Who lives by this
Four real systems that run consensus, and what they have published.
paper 2014 · "In Search of an Understandable Consensus Algorithm"
Diego Ongaro and John Ousterhout designed Raft explicitly to be easier to understand than Paxos, splitting consensus into leader election, log replication and safety. Their USENIX ATC 2014 paper reports a user study in which students answered questions about Raft more accurately than about Paxos, and there are many open-source implementations.
kube-apiserver → etcd (Raft) → desired state
etcd is a distributed key-value store using Raft, and Kubernetes keeps all cluster state in it. Its documentation recommends clusters of 3, 5 or 7 members: more members add no speed and tolerate more failures only at odd sizes, and each write needs a majority to be committed.
lock service → Paxos groups
Google's Chubby lock service (2006) uses Paxos to replicate a small, highly consistent store used for leader election and configuration, and the paper "Paxos Made Live" describes the engineering effort of building it. Spanner uses Paxos groups to replicate each shard of data across zones.
controller quorum → Raft metadata log
Kafka used ZooKeeper to store cluster metadata, then built KRaft, its own Raft-based metadata quorum, so the cluster manages itself. KRaft became production-ready in Kafka 3.3 and ZooKeeper mode was removed in Kafka 4.0: consensus moved from a separate service into the system.
Interview angle
Six questions, each worth 20 XP. “Explain Raft” or “why do we use an odd number of nodes?” are common senior-level questions.
Name the three parts (election, replication, safety), say what a majority guarantees, and say what happens when it is lost.
Why does a Raft cluster need a majority to elect a leader or commit an entry?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
Kill servers one by one and try to send a command after each. When the majority returns, the cluster recovers by itself: a leader is elected and everything that was committed is still there. Notice also what cannot happen: the two surviving servers never decide on their own, so there is no split brain and no divergence to repair afterwards.
Kill three servers and press “Send a command”: it is not accepted. Then revive all.
5 servers up and S5 leads with a majority: the cluster accepts and commits commands (1 committed so far).
The cluster is a working simplified Raft. “Leader with a majority” means a leader that a majority of live servers currently follow.
Where to go next