Raft Consensus

The big picture#

Everything below expands on these points. Read the core sections top to bottom for the full mental model; the collapsible "Go deeper" boxes hold the advanced internals (membership changes, snapshots, lease reads, the exact safety argument) you can skip on a first pass and return to later.

Start here: why does a cluster need a leader?#

A single database server is a single point of failure — if it dies, every client request fails until it's replaced. The fix is to replicate the same data onto several machines. But replication immediately creates a new problem: if two clients write to two different replicas at the same time, which write wins, and in what order do all replicas end up agreeing to apply them?

The classic framing is the replicated state machine. If every node starts in the same state and applies the exact same sequence of commands in the exact same order, every node ends in the same state — deterministically. Replication then reduces to one thing: get all nodes to agree on a single ordered log of commands. That agreement, in the presence of crashes and an unreliable network, is consensus.

Raft's answer is to elect exactly one leader at a time. Every write goes through the leader, which appends it to its own log and then replicates that log, in order, to the other nodes (followers). As long as there's a single leader, there's a single order — the hard problem of 'what happened in what order' reduces to 'whatever order the leader appended things in.'

Terms: Raft's logical clock#

Raft divides time into terms, numbered consecutively. Each term has at most one leader. A node always carries a currentTerm number, and that number only ever goes up. Any message — a vote request, a replication request — carries the sender's term, and a node that sees a higher term immediately adopts it and demotes itself to follower.

This is the mechanism that prevents stale leaders from doing damage: a leader that's been cut off by a network partition keeps believing it's in charge, but the moment it's reconnected and hears about a higher term, it learns it's obsolete and steps down — even though, locally, nothing told it to stop being leader.

Leader election: from follower to candidate to leader#

Every follower runs an election timer. Each time it hears from the current leader (a heartbeat), it resets the timer. If the timer ever expires — meaning no leader has been heard from in a while — the follower assumes there's no functioning leader and starts an election: it becomes a candidate, increments its term, votes for itself, and sends RequestVote to every other node.

1. A follower's election timer expires with no heartbeat. It becomes a candidate for term T+1 and votes for itself.
2. It sends RequestVote(term=T+1) to every peer.
3. Each peer grants the vote if: the candidate's term is at least as new as its own, it hasn't already voted for someone else this term, AND the candidate's log is at least as up-to-date as its own (compared by last entry's term, then index).
4. If the candidate collects votes from a majority (including its own), it becomes leader for that term and immediately sends a heartbeat to assert its leadership before anyone else's timer expires.
5. If no candidate gets a majority (a split vote), every candidate's timer eventually expires again and they retry at an even higher term — staggered timeouts make this converge quickly in practice.

Log replication: AppendEntries and the consistency check#

Once elected, the leader accepts client commands by appending them to its own log first (uncommitted), then pushes them out via AppendEntries — the same RPC it uses as a heartbeat, just carrying entries instead of being empty. Each AppendEntries includes prevLogIndex/prevLogTerm: 'here is the entry I believe directly precedes what I'm sending you — confirm you have it.'

If the follower's log doesn't have a matching entry at that position (it's missing entries, or has different ones from a previous, now-abandoned leader), it rejects the request. The leader responds by decrementing nextIndex for that follower and retrying one position earlier next round, until it finds a point both logs agree on — then it overwrites the follower's divergent suffix with its own. Entries are only ever appended or overwritten in bulk from a known-good point; they're never reordered.

The commit rule: majority replication, with one subtlety#

An entry is committed once it's been replicated to a majority of nodes — at that point it's durable even if the leader immediately crashes, because any future leader (also elected by majority) is guaranteed to overlap with at least one node that has it. The leader tracks matchIndex per follower (the highest index it has confirmed that follower holds) and advances its own commitIndex to the highest index a majority agrees on.

Failure modes: partitions, split votes, and split brain#

If the leader is cut off from a majority of the cluster, two things happen in parallel: the isolated leader keeps accepting client writes into its own log (since nothing has told it otherwise) but can never replicate them to a majority, so they can never commit — those writes are effectively stuck. Meanwhile, the majority side notices it's heard nothing from the leader, times out, and elects a new leader among themselves (since they still have enough nodes for a majority).

When the partition heals, the old leader receives a message from the new leader carrying a higher term, recognizes it's stale, and steps down to follower — then catches its log up to the new leader's via the ordinary AppendEntries consistency check. Its uncommitted, never-replicated writes are simply discarded by being overwritten.

• Split vote — two candidates start elections at the same term and each grabs part of the cluster, so neither reaches a majority. Raft fixes this with randomized election timeouts (e.g. 150–300 ms): the node that times out first usually wins outright before others even start, so split votes are rare and self-correct on the next, re-randomized timeout.
• Leader crash — followers stop hearing heartbeats, an election timer fires, and a new leader is elected, typically within an election timeout. Committed entries survive because any new leader already holds them (election restriction).
• Network partition / split brain — the cluster splits into groups. Because a leader must reach a majority to commit, at most one group can make progress; the minority side cannot elect a leader or commit anything. This is the structural guarantee against two leaders committing conflicting data.
• Stale leader still serving reads — a partitioned-off old leader may not yet know it was deposed and could answer a read with stale data. Preventing this needs an explicit read protocol (see Variants → read-only optimizations); replication alone does not make reads linearizable.

Quorums, fault tolerance, and message cost#

Raft's safety rests on a counting argument: any two majorities of the same set must overlap in at least one member. So if an entry is on a majority, and a future leader was elected by a majority, those two majorities share a node — and that node, by the election restriction, forced the new leader to already hold the entry. Overlap is the whole reason a majority quorum is safe.

• Fault tolerance: a cluster of N = 2f+1 nodes tolerates f crash failures and still has a majority (f+1) available. 3 nodes tolerate 1 failure; 5 tolerate 2; 7 tolerate 3.
• Why odd sizes: 4 nodes need a majority of 3 — same fault tolerance as 3 nodes (1 failure) but more nodes to coordinate and slower quorums. Even sizes buy you nothing and cost latency, so clusters are almost always 3, 5, or 7.
• Commit latency: one client write needs a single round-trip from the leader to the fastest majority of followers — roughly one network RTT plus a disk fsync on each. The slowest node in the majority does not gate you; the (f+1)-th fastest does.
• Message cost: each AppendEntries round is O(N) messages (leader to each follower) and an election is O(N) RequestVotes plus O(N) replies — both linear in cluster size, which is why Raft clusters stay small (3–7) and scale reads, not the consensus group, horizontally.

Beyond the core: membership changes, snapshots, fast reads#

The election-plus-replication core is the exam answer, but production Raft needs three more pieces to actually run for years. Each is bundled into the paper or Ongaro's thesis.

• Cluster membership changes — you can't just swap the node set atomically, because nodes apply the change at different moments and could briefly form two disjoint majorities (two leaders). The paper's solution is joint consensus: a transitional configuration C(old,new) in which decisions require majorities of BOTH the old and the new sets, so overlap is preserved throughout the switch. The thesis later simplified this to single-server changes: add or remove one node at a time, where old and new majorities always overlap automatically — this is what most implementations use.
• Log compaction / snapshots — the log can't grow forever. Each node periodically writes a snapshot of its state machine and discards the log prefix the snapshot covers. A leader that has already discarded entries a lagging follower needs sends an InstallSnapshot RPC instead of replaying ancient AppendEntries.
• Read-only optimizations — a naive read goes through the log like a write (correct but slow). To serve linearizable reads cheaply, a leader confirms it is still leader (exchange heartbeats with a majority) before answering, and records the commit index at read time. Leader leases go further: a leader holding a time-bounded lease can serve reads locally without a round-trip, trading a clock-bound assumption for latency.
• Pre-vote — a partitioned node keeps timing out and bumping its term; when it rejoins, its inflated term forces an unnecessary leader step-down (a 'disruptive server'). The pre-vote extension makes a node first ask 'would you vote for me?' WITHOUT incrementing its term, and only starts a real election if a majority says yes — preventing needless disruption.

Trade-offs: what consensus costs you#

Raft buys you a single, linearizable, durable log — and you pay for it in latency, throughput ceiling, and availability under partition. It is firmly a CP system in CAP terms: when a partition prevents a majority, the minority side sacrifices availability (it refuses writes) to preserve consistency.

• Availability vs consistency — under a partition, only a majority side stays writable; a cluster with no majority side is fully unavailable for writes. Raft never sacrifices consistency for availability, by design.
• Latency — every committed write pays a majority round-trip plus per-node fsync. You cannot beat one network RTT to your quorum, which dominates in geo-distributed deployments.
• Leader bottleneck — all writes (and, for strong reads, the read confirmation) funnel through one node. The leader's CPU, disk, and uplink cap write throughput; the cluster does not scale writes by adding voters. Followers can offload only stale or lease-bounded reads.
• Small clusters only — because every round is O(N) and quorums get slower with more members, Raft groups stay at 3–7 nodes. Scaling data past that means sharding into many independent Raft groups (the CockroachDB / TiKV model), not growing one group.

Raft vs Multi-Paxos vs ZAB#

The headline: Raft and Multi-Paxos are equivalent in power and efficiency — Raft is essentially Multi-Paxos with a strong-leader discipline and a no-holes log bolted on to make it teachable and buildable. ZAB is close to Raft in spirit (single leader, ordered broadcast) because both were built for real primary-backup systems; the differences are mostly in how leadership/epochs and recovery are framed.

Where Raft runs in the wild#

Raft became the default consensus layer for new infrastructure after 2014, largely because it is realistic to implement correctly from the paper. Most uses follow one of two patterns: a single Raft group holding cluster metadata, or many Raft groups (one per data shard) for horizontal scale.

• etcd — the canonical Raft library and the key-value store behind Kubernetes; the entire cluster state of Kubernetes lives in a single etcd Raft group.
• HashiCorp Consul / Nomad — service discovery and scheduling; use the same battle-tested hashicorp/raft library for their server quorum.
• CockroachDB — shards ("ranges") of the keyspace are each their own Raft group, with thousands of groups per cluster, giving SQL-level horizontal scale on top of per-range consensus.
• TiKV / TiDB — the same per-region multi-Raft model; TiKV's Raft implementation is a direct port of etcd's Raft to Rust.
• Kafka KRaft — Kafka's replacement for its ZooKeeper dependency: the controller quorum now runs a Raft-based metadata log internally, removing the separate ZAB-based ZooKeeper ensemble.

Common misconceptions & gotchas#

In an interview#

Lead with the shape of the problem: replicate a log, not arbitrary state, by funneling all writes through a single elected leader per term. That single decision is what turns 'how do N machines agree' into 'how do we safely elect and replace a leader' — a much smaller problem.

Know the two RPCs by name (RequestVote, AppendEntries) and the two safety rules that make them correct: the log-recency check during voting (so an out-of-date node can't get elected even with a higher term), and the current-term-only commit rule (so a majority count alone never resurrects an uncommitted entry from a dead leader's term). Be ready to explain what happens during a network partition — an isolated leader keeps accepting writes that can never commit, while the majority side elects a new leader and keeps going.

Then try it in the simulator: TICK until a leader is elected, CLIENT_APPEND a couple of commands and TICK until they commit on every node, then PARTITION the leader and watch the majority side re-elect — followed by HEAL to watch the old leader discover the higher term, step down, and catch its log up.

References & further reading#