Getting a group of unreliable machines to agree on a single value. It sounds abstract; it’s the foundation under every database primary, every distributed lock, and every configuration store you use.
Prerequisites: Leader Election, Failure Modes Time to read: ~24 minutes
Five nodes must agree on one thing — who is the leader, what the configuration is, what order these writes happened in. And they must agree despite:
🚨 And the agreement must be permanent. Once the group decides “X,” no future sequence of events may cause it to decide “Y.” Not after a partition heals, not after a crashed node returns with stale state, not ever.
That’s the consensus problem, and it’s the hardest fundamental problem in distributed systems.
Fischer, Lynch, and Paterson (1985) proved that in a fully asynchronous network — where messages can be delayed arbitrarily and you cannot distinguish a slow node from a dead one — no deterministic algorithm can guarantee consensus if even one node may fail.
🚨 That’s an impossibility proof, not an engineering gap.
So how does anything work? Because real algorithms relax one of the assumptions:
🎙️ The framing that shows understanding: “Consensus algorithms never sacrifice safety. They sacrifice liveness — under a sufficiently bad network they may simply not make progress, but they will never produce two conflicting decisions.”
Four properties:
| Property | Meaning |
|---|---|
| Agreement | No two nodes decide different values |
| Validity | The decided value was proposed by someone (not invented) |
| Integrity | Each node decides at most once |
| Termination | Every non-faulty node eventually decides (liveness — the one that’s conditional) |
Raft (2014) was explicitly designed to be understandable, after a decade of Paxos being notoriously hard to implement correctly. It’s what etcd, Consul, CockroachDB, TiKV, and modern Kafka (KRaft) use.
🚨 In an interview, explain Raft. Mention Paxos exists. Raft is what you’d actually deploy, and you can describe it coherently in two minutes.
Every node holds an identical, ordered log of commands. If all nodes apply the same commands in the same order to the same starting state, they end up in the same state.
Node A log: [set x=1] [set y=2] [del x] [set z=9]
Node B log: [set x=1] [set y=2] [del x] [set z=9]
Node C log: [set x=1] [set y=2] [del x] [set z=9]
↑ all identical, all in order
So the consensus problem reduces to: agree on the contents and order of the log.
Time is divided into terms, each with at most one leader. Every message carries a term number.
🚨 A node seeing a higher term immediately steps down and becomes a follower. This is Raft’s built-in fencing — an old leader returning after a partition sees a newer term and demotes itself automatically. It’s the same idea as fencing tokens, integrated into the protocol.
1. Followers expect a heartbeat from the leader.
2. No heartbeat within the election timeout (randomized, e.g. 150–300 ms)?
→ become a candidate, increment the term, vote for yourself, request votes.
3. A node grants its vote if:
- it hasn't already voted in this term, AND
- the candidate's log is at least as up to date as its own ← critical
4. Majority of votes → leader. Start sending heartbeats.
5. Split vote (nobody gets a majority)? Timeout, retry with new random timeouts.
🚨 Two details that matter and are worth mentioning:
Randomized timeouts prevent all followers from campaigning simultaneously, which would split the vote repeatedly. This randomization is how Raft sidesteps the FLP symmetry problem.
The log-completeness check guarantees the elected leader has every committed entry. A node with a stale log cannot win, because a majority of nodes have the committed entries and won’t vote for someone behind them. This is why Raft never loses committed data.
1. Client sends a command to the leader.
2. Leader appends it to its own log (uncommitted).
3. Leader sends AppendEntries to all followers.
4. Once a MAJORITY have written it to their logs → the entry is COMMITTED.
5. Leader applies it to its state machine and responds to the client.
6. Followers apply it once they learn the commit index (on the next heartbeat).
📐 Note step 4: a majority, not everyone. This is why the cluster tolerates minority failures and why write latency is bounded by the median follower, not the slowest one — a slow or dead node doesn’t block commits.
Safety under partition: a leader on the minority side cannot reach a majority, so it cannot commit anything. It accepts client requests and they simply never commit — the correct behaviour, though it means clients time out. Meanwhile the majority side elects a new leader and proceeds.
Log compaction / snapshots. The log can’t grow forever. Nodes periodically snapshot their state machine and discard the prefix. A far-behind follower receives a snapshot instead of replaying millions of entries.
Membership changes. Adding or removing nodes is genuinely subtle — a naive switch can briefly create two disjoint majorities. Raft uses joint consensus (a transitional configuration requiring majorities in both old and new sets) or single-node-at-a-time changes.
Read consistency. 🚨 A subtle trap: a leader might have been deposed without knowing yet, so serving a read from its local state can return stale data. Solutions: route reads through the log (correct, slow), confirm leadership with a heartbeat round before answering (ReadIndex — the common choice), or use leader leases with clock assumptions.
Paxos (Lamport, 1989) is the original and the theoretical foundation. It’s correct, it’s influential, and it’s notoriously difficult — the original paper was rejected, and Google engineers famously reported that turning Paxos into working code required solving many problems the paper doesn’t address.
Basic Paxos agrees on one value; Multi-Paxos extends it to a log and adds a stable leader, converging on something structurally similar to Raft. Used in Google Chubby and Spanner.
ZAB (ZooKeeper Atomic Broadcast) is ZooKeeper’s protocol. Similar to Raft, but designed specifically for primary-backup state machine replication with strong ordering guarantees.
🎙️ The honest framing: “They’re all solving the same problem with the same core mechanism — a stable leader plus majority quorums. Raft is the one designed to be implementable, which is why it’s what modern systems use.”
You need it for:
You don’t need it for:
📐 The performance reality:
Local write: ~1 ms
Consensus, same DC: ~2–10 ms (majority round trip)
Consensus, multi-region: ~100–300 ms (cross-region round trip)
Throughput: typically 1,000–10,000 writes/second for a whole cluster
🚨 That last number is the important one. A consensus cluster handles thousands of writes per second, not hundreds of thousands. This is why you store metadata in etcd, not application data.
🎙️ “I’d use etcd for cluster metadata and leader election, but application data goes in a store built for throughput. Consensus caps us at a few thousand writes per second because every write needs a majority round trip.”
Use 3 or 5 nodes. Never even numbers (why). Beyond 5, write latency grows with negligible availability gain.
Spread across failure domains. 5 nodes in one rack survives 2 node failures and zero rack failures. Spread across availability zones.
🚨 But mind the latency: cross-AZ adds ~1–2 ms per round trip; cross-region adds 50–200 ms. A consensus group spanning continents has terrible write latency. The usual answer is a consensus group per region, with asynchronous replication between them.
Never implement it yourself. Use etcd, ZooKeeper, Consul, or a proven library (hashicorp/raft, etcd/raft). Consensus implementations have subtle bugs that only appear under specific failure interleavings — this is exactly what Jepsen testing exists to find, and it has found bugs in most major implementations.
Plan for unavailability. A consensus cluster losing its majority stops accepting writes. Deliberately. Your application must handle “the config store is unavailable” by using cached last-known-good values rather than halting. → Coordination Services
| Decision | Gain | Cost |
|---|---|---|
| Consensus | Provable agreement; no split brain; linearizability | ~1k–10k writes/s ceiling; a round trip per write; unavailable without a majority |
| 3 nodes | Lower latency, cheaper | Tolerates only 1 failure |
| 5 nodes | Tolerates 2 failures | More nodes to convince; higher write latency |
| Cross-region consensus | Survives a region loss | 100–300 ms per write |
| Leader-based reads | Fast | Stale if the leader was deposed — needs ReadIndex or leases |
| Avoiding consensus | Far higher throughput | Eventual consistency; conflicts to resolve |
1. Watch Raft in your browser. The Raft visualization lets you kill nodes, partition the network, and watch elections and log replication happen. Ten minutes here is worth more than reading the paper, and it makes terms and log matching intuitive.
2. Run a real cluster. Three etcd nodes in Docker Compose:
etcdctl put /foo bar
etcdctl endpoint status --cluster -w table # see who's leader
docker pause etcd2 # still works — 2 of 3 is a majority
etcdctl put /foo baz # ✅
docker pause etcd3 # now only 1 of 3
etcdctl put /foo qux # ❌ no quorum — writes refused
That last failure is the CP choice made visible. Then unpause and watch it recover.
3. Force an election. Identify the leader, kill it, and time how long until a new one is elected. Then kill it repeatedly and watch terms increment.
4. Measure the throughput ceiling. Benchmark etcd writes (etcdctl check perf). Compare to
Postgres or Redis on the same hardware. The gap is the price of agreement, and knowing the number
makes the “metadata not application data” rule concrete.