Start practising

SYSTEM DESIGN · CONCEPTS · DISTRIBUTED SYSTEMS · EPISODE 34

Consensus: Raft and Paxos in Plain Words

What consensus means, why a replicated log needs it, how Raft elects a leader with terms and majority votes, how it replicates and commits log entries, what happens in a network split, why clusters have 3 or 5 nodes, where Paxos fits, and which systems use consensus (etcd, ZooKeeper, Kafka KRaft, Spanner).

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
1 / 10

Press play to hear the narration, or step through at your own pace. Every picture here is the same one used in the YouTube video.

Notes

The goal

Consensus means a group of machines agreeing on a value, and in practice on an ordered log of commands: set x to five, the lock belongs to server three. If every node applies the same log in the same order, they all end up in the same state. That's a replicated state machine, and it must keep working while some nodes crash.

Consensus
  • agree on one value, or one
  • ordered log of commands:
  • 1. set x = 5
  • 2. lock owner = server-3
  • 3. leader = B
  • even if some nodes crash
  • and messages are delayed
  • every node applies the same
  • log → same state

Majority

The key trick is majorities. With five nodes, a decision needs three. Any two groups of three overlap in at least one node, so two conflicting decisions can never both win. Five nodes tolerate two failures, three nodes tolerate one, and four nodes still tolerate only one, which is why clusters use odd numbers.

Why a majority
  • 5 nodes → majority is 3
  • any two majorities overlap in
  • at least one node
  • so two different decisions
  • can never both win
  • 5 nodes survive 2 failures
  • 3 nodes survive 1 failure
  • 4 nodes: still only 1 (no gain)

Leader election

Raft, the most popular consensus algorithm, starts by electing a leader. The leader sends regular heartbeats. If a follower hears nothing for a random timeout, it becomes a candidate, increases the term number and asks for votes. Each node votes once per term, and a candidate with a majority becomes leader. Random timeouts keep candidates from colliding.

Raft election
  • leader sends heartbeats
  • follower times out (random
  • 150–300 ms) → becomes candidate
  • increments the term, asks votes
  • each node votes once per term
  • majority → new leader
  • random timeouts avoid
  • split votes

Replication

All writes go to the leader. It appends the command to its log as entry seven and sends it to the followers. Once a majority, counting itself, has stored it, the entry is committed: it's applied and the client gets success. A slow or crashed follower simply catches up later.

Log replication
  • all writes go to the leader
  • leader appends entry #7 and
  • sends it to followers
  • majority stored it →
  • COMMITTED, apply, reply
  • slow or dead follower?
  • it catches up later

Split brain

Now a network split cuts node A off. A can't reach a majority, so it can't commit anything, even if it thinks it's a leader from an old term. The other three still form a majority and carry on. When A rejoins, it sees a higher term, steps down and copies the current leader's log. Two leaders can never both commit.

Network partition
  • A is cut off (1 of 5)
  • A cannot get a majority
  • → cannot commit anything
  • B, C, D (3 of 5) carry on
  • when A rejoins it sees a
  • higher term, steps down and
  • copies the leader's log
  • no split brain, by design

Paxos

Paxos is the original consensus algorithm, proven correct and famously hard to understand. Raft was designed later to give the same guarantees in a way engineers can follow. ZooKeeper uses its own protocol, Zab. They all share the same core: majority quorums, numbered terms or ballots, and a single leader at a time.

Paxos and friends
  • Paxos: the original (1990s),
  • proven, famously hard to
  • understand; Multi-Paxos for logs
  • Raft (2014): same guarantees,
  • designed to be understandable
  • Zab: ZooKeeper's protocol
  • all: majority quorums +
  • terms/ballots + one leader

In practice

You'll meet consensus inside etcd, which stores all of Kubernetes' state, in ZooKeeper and Kafka's controllers, in Consul, and in databases like CockroachDB and Spanner, which run a consensus group per shard. You almost never implement it yourself; you use one of these for leaders, locks and configuration.

Where you meet it
  • etcd (Kubernetes state)
  • ZooKeeper (Hadoop, older Kafka)
  • Kafka KRaft controllers
  • Consul
  • CockroachDB, TiDB, Spanner
  • (per-shard Raft/Paxos groups)
  • you rarely implement it:
  • you use one of these for
  • locks, leaders, config

Say it like this

In an interview, if you need a leader, a lock or cluster membership: use etcd or ZooKeeper, which run Raft or Zab on three or five nodes with majority quorums. Pair leadership with leases and fencing tokens. Keep consensus off the hot path; every write waits for a majority, so store only small, critical metadata there.

In the interview
  • "How do you elect a leader?"
  • use etcd / ZooKeeper (Raft/Zab)
  • 3 or 5 nodes, majority quorum
  • leader lease + fencing token
  • (episode 31)
  • writes slower: majority round
  • trip; keep it off the hot path
  • store small, critical metadata

Interview questions

What problem does consensus solve?

Getting a group of machines to agree on a value or an ordered log of operations even when some machines crash and messages are delayed, so all replicas apply the same commands and stay identical.

Why do consensus clusters use 3 or 5 nodes?

Decisions need a majority. Three nodes tolerate one failure and five tolerate two. Even numbers add cost without adding fault tolerance (four still tolerates only one failure).

How does Raft elect a leader?

Followers expect heartbeats; one that times out (randomised timeout) becomes a candidate, increments the term and requests votes. Each node votes at most once per term, and a candidate with a majority becomes leader.

When is a Raft log entry committed?

When the leader has replicated it to a majority of nodes (including itself) in its current term. Only then is it applied to the state machine and acknowledged to the client.

What happens during a network partition in Raft?

Only the side with a majority can elect a leader and commit entries. The minority side cannot make progress; when it rejoins, nodes see a higher term, step down and catch up from the leader's log.

What is the difference between Raft and Paxos?

Both provide the same safety guarantees using majority quorums. Paxos came first and is notoriously hard to understand and implement; Raft was designed for understandability with a strong leader and clear log replication rules.

Which real systems use consensus?

etcd (Kubernetes), ZooKeeper, Consul, Kafka's KRaft controllers, and distributed SQL databases such as CockroachDB, TiDB and Spanner that run a consensus group per data range.

Why not store all application data in etcd or ZooKeeper?

Every write needs a majority round trip through a single leader, so throughput is limited. They are designed for small, critical metadata like configuration, leader election and locks.