Consensus with Raft

A Kubernetes control plane stores everything it knows (every pod, every deployment, every secret) in etcd, usually on three machines. Lose one and nothing happens. Lose two and kubectl apply hangs, even though the last etcd node is healthy and holds a complete copy of the data.

A healthy machine with all the data, refusing to accept a write. That is not a bug. It is the rule that stops a cluster from ever disagreeing with itself, and this chapter is about why the rule is right.

What consensus is for#

Replication with one primary and some replicas works well until the primary dies. Then someone has to pick a new primary, and the dangerous moment is when the old one comes back still believing it is in charge: two primaries, two histories, split brain. Doing that failover safely, automatically, is the job of consensus.

The shape is always the same. A group of machines (almost always 3 or 5) keeps a replicated log: an ordered list of commands like "set x = 2". Every machine applies the same commands in the same order, so every machine ends up in the same state. Consensus guarantees that once an entry is committed at a position in the log, no machine will ever have a different entry at that position, whatever crashes or splits happen.

You rarely write this yourself. You use a system that does it, and put your critical, small, must-agree data in it: which node leads, which shard lives where, the cluster's configuration.

Why a majority#

A write counts as committed once a majority of the group has it: 2 of 3, 3 of 5. The reason is one fact about majorities: any two majorities of the same group share at least one machine. Whatever happens next, any future majority, for an election or for another write, includes at least one machine that saw this write. It cannot be forgotten.

That also tells you how many failures a group survives:

Four machines tolerate exactly as many failures as three, and write more slowly, because every write now waits for three acknowledgements instead of two. So consensus groups are odd sized. And now the cold open makes sense: one etcd node out of three is not a majority. If it accepted writes on its own, the other two might be alive on the far side of a network split, accepting different writes. Refusing is the only safe choice.

Terms: a counter for leadership#

Raft has a single leader that takes all writes, and followers that copy it. Time is divided into terms, numbered 1, 2, 3 and up. Each term starts with an election and has at most one leader.

The term number works like the Lamport clock from the clocks chapter, for leadership. Every message carries the sender's term. Any node that sees a higher term than its own immediately adopts it, and if it was a leader, it steps down on the spot. A leader that was cut off and missed an election finds out the moment it hears from anyone in the newer term.

Electing a leader#

The leader sends a heartbeat to every follower many times a second. A follower that hears nothing for its election timeout assumes the leader is gone and stands for election itself. The original paper suggests a timeout chosen at random between 150 and 300 ms, and the randomness matters: it makes one follower almost always time out first and win before anyone else starts.

The second rule on the vote is where safety comes from. A node only votes for a candidate whose log is at least as up to date as its own: a later last term, or the same last term and at least as long. Every committed entry is on a majority, the winner needs votes from a majority, and those two majorities overlap. So the winner always holds every committed entry, because any voter that had one more would have refused.

Replicating the log#

Once there is a leader, a write works like this:

One round trip to the nearest majority, plus a disk write on each. That is the cost of every committed write, and it is the number to remember when someone proposes putting consensus on a hot path.

Break it#

Here is a five node group you can damage. Start by splitting the network so the leader ends up on the small side, then write through both sides, then reconnect. After that, stop two nodes, then a third, and try writing.

Three things to take from it.

The old leader never stops believing. Cut off with only one follower, A still thinks it leads and still accepts writes. It just cannot commit any of them, because it cannot reach three nodes. The clients writing to it wait and time out.

The majority side moves on. C, D and E elect a new leader in a higher term and keep serving writes. Two leaders exist at once, but only one of them can commit, so there is no split brain in the data.

Healing throws away only what was never promised. When the network comes back, A sees term 2, steps down, and its uncommitted entries are overwritten. No client was ever told those writes succeeded, so nothing anyone relied on is lost. Those clients still need to retry, which is why every write to a consensus system should carry an idempotency key.

Reading from a Raft group#

Writes are safe. Reads have a subtle problem: the leader you ask might have been replaced a moment ago without knowing yet, exactly like A in the widget. If it answers from its own state, it might return a value that a newer leader has already overwritten.

Three ways to read, in order of cost:

Read from any follower. Fast and spreads the load, and possibly stale. etcd calls this a serializable read (--consistency=s).

Read from the leader, after it confirms it is still the leader. The leader notes its commit point, exchanges one heartbeat round with a majority, and then answers. This is called ReadIndex. It is etcd's default, which it calls a linearizable read: one extra round trip, no disk write.

Read from the leader under a lease. The leader assumes nobody else can be elected for a little while after a successful heartbeat, and answers without a round trip. This is fast, and it quietly depends on clocks running at roughly the same rate, which the clocks chapter gave you reasons to doubt.

Raft and Paxos#

Paxos is the older answer to the same problem. Leslie Lamport described it around 1989 and published it in 1998, and its reputation is that almost nobody understands it on the first read. The basic algorithm agrees on one value. Building a full replicated log out of it (Multi-Paxos) was left largely to implementers, who each filled the gaps differently.

Raft was published by Diego Ongaro and John Ousterhout in 2014, with understandability as the explicit goal. It has a strong leader, says exactly how elections, log repair and membership changes work, and gives the same guarantees: a group of 2f + 1 machines survives f failures and never commits two different entries at the same position.

In practice they are equivalent for an interview. Google's Chubby and Spanner use Paxos; etcd, Consul, CockroachDB, TiKV and Kafka's KRaft use Raft. If asked "how do the replicas agree?", "a consensus protocol such as Raft or Multi-Paxos, with a majority quorum" is the complete answer, and the mechanism above is the follow up.

What consensus costs#

Latency. Every commit waits for a majority round trip and a disk flush on each. Inside one region that is a few milliseconds. Put the replicas in Mumbai, Singapore and Frankfurt and every write pays the round trip to the nearer of the other two.

Throughput does not grow with machines. All writes go through one leader, and more followers only add work for it. A bigger group is more fault tolerant and slower. Systems that need throughput run many small groups side by side, one per shard, which is what CockroachDB and TiKV do.

Size. etcd keeps its whole data set in memory-mapped files and limits it to 2 GB by default. Consensus stores are for metadata measured in megabytes: who leads, what lives where, configuration and locks. Your orders table belongs somewhere else.

Interview replay#

Checkpoint#