Distributed Consensus: Raft & Paxos

The problem consensus actually solves#

Earlier pages in this track covered CAP/PACELC (the trade-offs consistency and availability force on you) and database replication (copying data from a primary to replicas). Neither actually answers a more basic question: when a set of independent machines can each crash, restart, and have their network connections to each other delayed or dropped at any moment, how do they agree on one thing — who the current leader is, what the next entry in a shared log is, who holds a distributed lock — without that agreement falling apart the moment something fails partway through?

A single vote round doesn't work. Suppose three nodes each try to "vote" once for a leader: a node can crash after receiving votes but before announcing a winner; a network partition can split the cluster into two groups that each believe they have enough votes; messages can be delayed long enough that a node acts on stale information. Consensus algorithms are protocols specifically designed to reach agreement correctly despite exactly these failure modes — not by preventing failures, but by tolerating a bounded number of them without ever agreeing on two different, conflicting answers.

The concept that makes this useful in practice is state machine replication: if every node applies the exact same sequence of commands, in the exact same order, starting from the same state, every node ends up in the same state. Consensus's actual job, then, is agreeing on that one ordered sequence — a replicated log — not on some abstract notion of truth.

Raft, conceptually#

Raft (2014) was explicitly designed to be an understandable consensus algorithm, decomposing the problem into two mostly-separate concerns: electing a leader, and replicating a log through that leader.

Roles and terms. Every node is a follower, a candidate, or the leader. Time is divided into terms — monotonically increasing numbers, each with at most one leader. If a follower stops hearing from a leader within a randomized timeout, it assumes the leader has failed, increments the term, becomes a candidate, and requests votes from the rest of the cluster.

Follower --[election timeout elapses,
             no heartbeat from a leader]--> Candidate
Candidate --[wins majority vote]-----------> Leader
Candidate --[another node wins first]------> Follower
Candidate --[election timeout, no winner]--> Candidate (new term, try again)

Leader election. A candidate votes for itself and requests votes from every other node. Each node votes for at most one candidate per term, on a first-come-first-served basis — a node that already voted this term rejects further requests. Whichever candidate collects votes from a majority of nodes becomes leader for that term and starts sending periodic heartbeats, which reset every follower's election timeout and prevent a new election from starting unnecessarily. Timeouts are randomized specifically so that two nodes rarely become candidates at exactly the same moment and split the vote repeatedly.

Log replication. Once elected, the leader is the only node that accepts new commands. For each command, it appends an entry to its own local log and sends that entry to every follower via AppendEntries. Once a majority of nodes (leader included) have durably stored the entry, the leader considers it committed, applies it to its own state machine, and tells followers to do the same on the next round. A command is never considered committed — and never applied — until a majority has it, which is exactly what guarantees it survives the failure of any minority of nodes.

Term 3, Leader = Node A

Node A (leader):  [1][2][3] --AppendEntries(3)--> Node B: [1][2][3]  (ack)
                                                -> Node C: [1][2][3]  (ack)

Majority (A, B) has entry 3 -> Node A commits it, applies to its state machine,
tells B and C to commit it too on the next heartbeat.

Safety. Raft adds one more rule specifically to prevent a subtle failure: a node whose log is behind (missing recently committed entries) must not be allowed to become leader and silently overwrite what the rest of the cluster already agreed on. During voting, a candidate includes information about how up-to-date its own log is, and other nodes refuse to vote for a candidate whose log is less complete than their own. Combined with the majority requirement for both voting and committing, this guarantees that any newly-elected leader already has every entry a previous leader committed.

Why a strict majority, not just "enough" nodes. Any two majorities of the same set of nodes must overlap by at least one node — that overlap is the entire mechanism that prevents two different leaders from being elected in the same term, or two conflicting entries from both being committed. A network partition can split a 5-node cluster into a group of 3 and a group of 2; only the group of 3 can reach a majority, so only it can elect a leader and commit new entries, while the group of 2 correctly refuses to do either until the partition heals. This is also why consensus clusters are typically sized as an odd number of nodes — a 5-node cluster tolerates 2 failures using the same majority-of-3 requirement that a 4-node cluster needs, while a 4-node cluster only tolerates 1 failure for the extra cost of running a 4th node.

Paxos, briefly#

Paxos predates Raft by over a decade (Leslie Lamport, 1989, published 1998) and solves the same fundamental problem, but is notoriously difficult to fully understand and to implement correctly — a point Lamport's own later papers concede directly, and a large part of Raft's stated motivation for existing at all. Multi-Paxos (running repeated rounds of Paxos to agree on successive log entries) is the classic way to build a replicated log with it, conceptually similar to what Raft does with an explicit leader — but Paxos doesn't mandate a stable leader the way Raft does, which is a large part of what makes reasoning about it harder. In practice, most new systems reach for Raft specifically because it's easier to implement correctly and to reason about during an incident; Paxos and its variants (including Google's Chubby lock service, built on it) remain influential but are less commonly the starting point for new designs today.

Where this shows up in real systems#

• etcd implements Raft directly, and is itself the cluster state store behind Kubernetes — every kubectl apply ultimately becomes an entry in an etcd Raft log, replicated to a majority of etcd nodes before Kubernetes considers the change durable.
• ZooKeeper uses ZAB (ZooKeeper Atomic Broadcast), a leader-based protocol conceptually similar to Raft (leader election, then ordered broadcast of state changes to a majority) that predates it. ZooKeeper has historically been the default coordination service for distributed locks, leader election, and configuration in systems like older Kafka (broker/controller metadata) and HBase.
• Kafka's KRaft mode replaced that ZooKeeper dependency with a Raft-based controller quorum built directly into Kafka itself, removing an entire separate coordination cluster that used to be required just to run Kafka.
• Consul and CockroachDB both use Raft — Consul for its own service-discovery state, CockroachDB (and similarly TiDB) per data range/shard, running many independent Raft groups so each shard's replication is agreed on separately.

Common mistakes#

• Assuming any scheme where "enough nodes agree" is safe, without the log-comparison rule Raft's elections require — a node with a stale or incomplete log winning an election can silently discard already-committed entries.
• Running an even number of consensus nodes (e.g., 4) — it doesn't tolerate more simultaneous failures than the odd number just below it (3), since the majority-size requirement is the same either way, but it costs more to operate.
• Treating a consensus-backed store (etcd, ZooKeeper) as a general-purpose, high-throughput database — these systems are built for small amounts of strongly-consistent, coordination-oriented data (config, locks, leader pointers), not bulk application data or high write volume.
• Confusing consensus with ordinary primary-replica replication — plain replication (covered on the database-scaling page) copies data outward from a single primary but has no protocol for agreeing who the primary even is during a network partition, which is exactly the problem a quorum-based election solves.

Interview questions#

Q: Why does Raft require a strict majority (quorum) rather than simply "however many nodes happen to respond"? Because any two majorities of the same node set are mathematically guaranteed to overlap by at least one node — that overlap is what prevents two different leaders from being elected in the same term, or two conflicting log entries from both being committed, even during a network partition that splits the cluster into separate groups.

Q: What's the difference between Raft-style consensus and simple primary-replica database replication? Primary-replica replication copies data outward from one designated primary to replicas, but has no built-in protocol for the replicas to agree on who the primary is if it fails or becomes partitioned from them — that's usually left to an external mechanism or manual failover. Consensus protocols like Raft solve exactly that: nodes elect a leader through a majority vote and only commit new entries once a majority has them, so the system can safely continue (and knows it's safe to continue) even if a minority of nodes are unreachable.

Q: Why did Raft's designers build a new algorithm instead of using Paxos directly? Paxos is provably correct but widely regarded as difficult to fully understand and to implement correctly in practice, especially once extended (as Multi-Paxos) into a replicated log with no single stable leader. Raft was explicitly designed around understandability, decomposing the same problem into clearly separated leader election and log replication mechanisms so that engineers implementing and operating it could reason about its behavior with far more confidence.