Consensus in Depth: Raft (and the Paxos Family)

The consensus protocol you will actually name

Raft powers etcd (and therefore Kubernetes), Consul, CockroachDB, TiKV, and countless control planes. Its selling point over Paxos is that it was designed to be understandable, by decomposing consensus into three separable problems: leader election, log replication, and safety.

Leader election

Raft time is divided into terms, each a monotonically increasing integer acting as a logical clock. At most one leader exists per term. Every node is follower, candidate, or leader. If a follower hears nothing from a leader within its election timeout, it becomes a candidate, increments the term, votes for itself, and requests votes. A candidate that collects votes from a majority wins. The clever bit that avoids endless split votes: each node's election timeout is randomized (say 150 to 300ms), so nodes rarely time out simultaneously; one usually starts first, gathers a majority, and shuts the others down. A node only grants its vote to a candidate whose log is at least as up to date as its own, which prevents a stale node from ever becoming leader and clobbering committed data.

Log replication

Clients send commands to the leader. The leader appends the entry and sends AppendEntries to followers. Once an entry is stored on a majority, the leader marks it committed and applies it. The commit rule is the heart: an entry is durable the instant a majority has it. Majority quorums work because any two majorities of N nodes must overlap in at least one node. That overlapping node carries committed entries forward into any future leader's election, so committed data is never lost.

  5-node cluster, leader crashes:
    term 4 leader (S1) dies
    S2..S5 election timeouts fire (randomized) -> S3 first
    S3 (up-to-date log) requests votes -> S2,S4 grant -> majority 3/5
    S3 becomes leader for term 5, resumes AppendEntries
    an uncommitted term-4 entry only on S1 is overwritten, never was committed

Safety

Raft guarantees: election safety (one leader per term), leader append-only, log matching (if two logs share an entry at an index/term, all prior entries match), and leader completeness (a new leader contains every committed entry from prior terms). Together: an entry, once committed, survives every future leader change. An entry replicated but not yet committed when the old leader crashed can be safely overwritten, and that is correct precisely because no client was ever told it committed.

A minority partition cannot make progress: a partitioned old leader with 2 of 5 nodes can append locally but never commits, and on heal it discovers a higher term and steps down, discarding its uncommitted tail. Membership changes use joint consensus (a transitional configuration requiring majorities of both old and new sets) so two disjoint majorities can never exist mid-reconfiguration.

Interview nuance on cluster size: always use an odd number. A 5-node cluster tolerates 2 failures (majority 3); a 4-node cluster also tolerates only 1 failure (majority still 3) while costing an extra machine and an extra vote to collect. The classic wrong turn is a 2-node cluster: majority is 2, so a single failure leaves no majority and a hung, unwritable system.

Paxos family. Basic Paxos solves single-value consensus; Multi-Paxos chains it for a log and underlies Chubby and Spanner. Paxos is more flexible but famously hard to implement correctly, which is why Raft constrains leadership to trade flexibility for a protocol engineers can get right. The FLP impossibility result says no deterministic consensus can guarantee termination in a fully asynchronous network with even one crash; real systems dodge it by assuming partial synchrony, which randomized timeouts operationalize.

Recap: Raft splits consensus into randomized-timeout leader election, majority-quorum log replication with commit-on-majority, and four safety properties that make committed entries immortal; minority partitions stall safely, membership changes use joint consensus, and clusters should be odd-sized.