Raft: state, the safety properties, and the parts people skip

What it is

A consensus algorithm for replicating a log across a cluster such that all replicas apply the same operations in the same order, tolerating up to $f$ failures with $2f+1$ nodes.

Raft decomposes consensus into three subproblems, which is its actual contribution:

LEADER ELECTION      exactly one leader per term
LOG REPLICATION      the leader appends and pushes entries
SAFETY               constraints ensuring a committed entry is
                     never lost or reordered

Each server is in one of three states:

        ┌──────────┐  timeout, start election   ┌───────────┐
        │ FOLLOWER ├──────────────────────────►│ CANDIDATE │
        └────▲─────┘                            └─────┬─────┘
             │                                        │ wins majority
             │ discovers a higher term                ▼
             │                                  ┌───────────┐
             └──────────────────────────────────┤  LEADER   │
                                                └───────────┘

Commonly confused with a replication protocol. Raft replicates a log, not data. What the log contains and what applying an entry means are the application's business, which is why etcd, Consul, TiKV, CockroachDB and Kafka's KRaft all use Raft with entirely different state machines on top.

Also commonly confused with Paxos as a competitor. Raft solves the same problem with the same guarantees; its design goal was understandability, achieved mainly by imposing a strong leader and by forbidding the log holes that Multi-Paxos permits.

The problem it solves

Any system needing a single authoritative sequence of decisions across machines that can fail: cluster membership, leader election for something else, configuration, distributed locks, and the metadata layer of most databases.

The insight worth leading with is where consensus should not be. Raft is expensive: every write costs a round trip to a majority plus an fsync on each. So the systems that scale best keep consensus off the data path:

Cassandra    consensus for schema changes and (optionally)
             lightweight transactions. NOT for ordinary writes.
Dynamo / S3  no consensus on the data path at all.
Kafka        KRaft for metadata and leadership. Data replication
             is leader-follower with ISR, not Raft.
Spanner      Paxos per shard, so consensus is on the write path
             and that is why writes cost 10 to 100 ms.

"Do we need consensus here, or only for metadata?" is the staff-level question, and answering it correctly is worth more than reciting the protocol.

Mechanics

Terms, and why they matter

Time is divided into TERMS, numbered monotonically. Each term
begins with an election and has at most one leader.

term 1        term 2      term 3
[leader A][gap][leader B][leader C ...]
                ^ election failed, no leader that term

Every RPC carries a term. The rules:
  - A server seeing a HIGHER term immediately becomes a
    follower and updates its term.
  - A server seeing a LOWER term rejects the message.

Terms are a logical clock and they are what makes stale leaders harmless. A partitioned leader that rejoins discovers a higher term and steps down, which is why Raft does not need wall-clock synchronisation for safety.

Leader election

A follower that hears nothing for its election timeout
(randomised, typically 150-300 ms) becomes a candidate:

  1. increment currentTerm
  2. vote for itself
  3. send RequestVote to all peers
  4. become leader on a majority, step down on a higher term,
     or time out and start a new election

A voter grants its vote only if:
  - it has not voted in this term, AND
  - the candidate's log is AT LEAST AS UP TO DATE as its own

The randomised timeout is what prevents split votes from repeating. Without it, all followers time out together, all become candidates, all split the vote, and the cluster livelocks. Randomisation over a range roughly ten times the RPC round trip makes a repeat split vanishingly unlikely.

The up-to-date check is a safety property, not an optimisation:

"At least as up to date" compares (lastLogTerm, lastLogIndex)
lexicographically: a higher last term wins; on equal terms, a
longer log wins.

This guarantees that any elected leader holds every committed
entry, because a committed entry is on a majority, any majority
intersects the voting majority, and a voter with the entry
would refuse to vote for a candidate lacking it.

That intersection argument is the whole safety proof in one sentence and it is worth being able to state.

Log replication and the commit rule

The leader appends a command, then sends AppendEntries to all
followers. Each entry carries (term, index, command).

CONSISTENCY CHECK: AppendEntries includes prevLogIndex and
prevLogTerm. A follower rejects if it does not have a matching
entry there, and the leader decrements nextIndex for that
follower and retries, walking back until the logs agree.

This gives the Log Matching Property:
  if two logs have an entry with the same index and term, then
  the logs are IDENTICAL in all entries up to that index.

The commit rule contains the subtlety that trips people up:

An entry is committed once it is stored on a MAJORITY
*** and the leader's CURRENT term has an entry committed. ***

A leader may NOT commit an entry from a PREVIOUS term merely
because it is now on a majority.

Why that restriction exists (the Figure 8 scenario from the paper):

S1 leader, term 2: appends entry X at index 2, replicates to S2.
                   Not yet a majority. S1 crashes.
S5 elected leader, term 3 (votes from S3, S4, S5, whose logs
                   lack X because X was never on a majority).
S1 recovers, elected leader, term 4. Replicates X to S3.
                   *** X is now on a MAJORITY (S1, S2, S3). ***
                   If S1 committed it here, then crashed:
S5 could be elected again in term 5 and OVERWRITE index 2.

A committed entry would have been lost.

The fix: a leader commits an old-term entry only indirectly, by committing a new entry from its own term at a higher index, which carries the earlier entries with it. Most Raft implementations do this by having a new leader immediately append a no-op entry.

Being able to state that restriction and why is the strongest single signal on this topic, because it is the part of Raft that is genuinely subtle and the part most summaries omit.

The five safety properties

ELECTION SAFETY       at most one leader per term
LEADER APPEND-ONLY    a leader never overwrites or deletes its
                      own log entries
LOG MATCHING          identical (index, term) implies identical
                      prefixes
LEADER COMPLETENESS   a committed entry is present in every
                      future leader's log
STATE MACHINE SAFETY  if a server has applied an entry at index
                      i, no other server ever applies a different
                      entry at i

Leader Completeness is the load-bearing one, and it is enforced by the up-to-date vote check plus the commit restriction above. The other four follow more directly.

Pre-vote: the fix for the disruptive rejoin

A production necessity that is not in the original paper's core algorithm.

PROBLEM: a node partitioned away keeps timing out and
incrementing its term. It rejoins at term 847 while the cluster
is at term 12. Its higher term forces the healthy leader to
step down, triggering an unnecessary election, and the rejoining
node cannot win (its log is behind) so the cluster loses its
leader for nothing.

PRE-VOTE: before incrementing its term, a candidate asks peers
"would you vote for me?" without changing any state. Only if a
majority says yes does it increment the term and start a real
election.

Without pre-vote, any flapping node repeatedly disrupts a healthy cluster. etcd, Consul and TiKV all implement it, and its absence is a common source of "the cluster keeps re-electing for no reason".

Membership change: joint consensus

Naively adding or removing nodes can produce two disjoint majorities.

Cluster {A, B, C}, changing to {A, B, C, D, E}.
If A and B adopt the new config while C, D, E still hold the old:
  old config majority = 2 of 3 = {C, ...}
  new config majority = 3 of 5
  Two leaders can be elected simultaneously. SPLIT BRAIN.

Two solutions, both used in practice:

JOINT CONSENSUS (the paper's approach)
  Transition through C_old,new, where a decision requires
  majorities in BOTH the old and new configurations. No moment
  exists where two disjoint majorities are possible.

SINGLE-SERVER CHANGES (the dissertation's simplification)
  Add or remove ONE server at a time. Old and new majorities
  always overlap by at least one node, so split brain is
  impossible. Simpler, and it is what etcd and most
  implementations do.

Single-server-at-a-time is the practical answer and it means a three-to-five expansion is two separate operations, not one.

The cost, which decides where to use it

Write path per committed entry:
  1. leader appends to its log        + fsync
  2. AppendEntries to followers        network RTT
  3. followers append                  + fsync
  4. majority acknowledges
  5. leader commits and applies

Latency = local fsync + RTT to the quorum + follower fsync

Same-AZ:    ~1-2 ms   (fsync dominates on non-PLP SSDs)
Cross-AZ:   ~2-5 ms
Cross-region: 60-200 ms

Which is why etcd publishes wal_fsync_duration_seconds as a primary health metric and recommends p99 under 10 ms: a slow disk caps cluster write throughput regardless of network speed, and it also causes spurious leader elections when heartbeats are delayed behind fsync.

A worked example: sizing and failure

5-node etcd cluster, one per AZ across 3 AZs (2+2+1).

FAULT TOLERANCE
  5 nodes tolerate f = 2 failures (majority = 3).
  Losing the 2-node AZ leaves 3, which is still a majority: OK.
  Losing a 2-node AZ AND one more node leaves 2: NO QUORUM,
  the cluster is unavailable for writes.

WHY NOT 4 NODES?
  4 nodes have majority 3, so they tolerate f = 1, the SAME as
  3 nodes, while costing more and making elections slower.
  *** Even cluster sizes are strictly worse. Always odd. ***

WHY NOT 7?
  7 tolerates f = 3, and every write waits for 4 acknowledgements
  instead of 3, so tail latency rises. Beyond 5, the marginal
  availability rarely justifies it.

CROSS-REGION?
  A 3-region cluster means every write waits for a second region,
  so 60-200 ms per write. Almost always the wrong shape: keep
  the Raft group within a region and replicate across regions
  by another mechanism.

Production evidence

Ongaro and Ousterhout, "In Search of an Understandable Consensus Algorithm" (USENIX ATC 2014) is the paper, and Ongaro's dissertation (2014) adds single-server membership changes, pre-vote, and the leadership-transfer extension, none of which are in the conference version.

etcd is the reference implementation and backs Kubernetes; its documented hardware recommendations (low fsync latency, p99 under 10 ms) and its exposure of wal_fsync_duration_seconds as a health metric are the clearest evidence that disk latency rather than network is the usual bottleneck.

Kafka's KRaft replaced ZooKeeper with a Raft-based metadata quorum, and the design deliberately keeps data replication on the existing ISR mechanism rather than Raft, which is a production instance of keeping consensus off the data path.

CockroachDB and TiKV run one Raft group per data range (thousands of groups per cluster), which is the sharded-consensus pattern, and both implement pre-vote and single-server membership changes.

Jepsen's analyses of etcd and Consul found the implementations largely upheld their claims, which is unusual, and the issues found were in the surrounding API semantics rather than the consensus core.

HashiCorp's Consul documentation on autopilot and its handling of non-voting members is a good practical reference for how membership changes are staged in production.

The debate

The case for Raft over Paxos: understandability is a real engineering property. Multi-Paxos is under-specified in the literature, every implementation differs, and the log holes it permits complicate the state machine. Raft's strong leader and no-holes log make correct implementation reachable, which is why almost every consensus system built since 2014 uses it.

The case for Paxos: it is more general, permits out-of-order commits which can give better throughput under loss, and Spanner and Chubby demonstrate that it works at enormous scale. Raft's strong leader is a throughput bottleneck that Paxos variants (EPaxos, Flexible Paxos) avoid.

The case for avoiding consensus: it costs a quorum round trip plus fsync per write, so any data path that includes it has a hard floor. Dynamo-style systems reach scales that consensus-based ones do not, precisely by not coordinating.

My position: use Raft for metadata, leadership and configuration, and keep it off the data path unless the data genuinely needs a total order.

That is the decision the protocol knowledge is actually for. Cassandra, Dynamo, S3 and Kafka all reach very large scale by confining consensus to a small, low-throughput set of decisions, and Spanner's 10 to 100 ms writes are the visible price of the alternative. The question "does this need consensus, or only its metadata need consensus" is worth more than being able to recite the state machine.

When Raft is the answer, three implementation details I would treat as mandatory rather than refinements. Pre-vote, because without it any flapping node repeatedly deposes a healthy leader by arriving with an inflated term, and the symptom is unexplained re-elections. Single-server membership changes rather than joint consensus, because the overlap argument is trivially checkable and joint consensus is a well-known source of implementation bugs. And treating fsync latency as the primary health metric, because a slow disk both caps throughput and causes spurious elections by delaying heartbeats behind log writes.

The sizing rule I would state flatly: five nodes, odd, within one region. Even sizes are strictly worse, since four tolerates the same single failure as three while making every write wait for one more acknowledgement. And a cross-region Raft group puts a 60 to 200 millisecond floor on every write, which is almost never what anyone intended when they asked for multi-region.

The part of the protocol I would make sure to know cold is the commit restriction: a leader may not commit an entry from a previous term just because it now sits on a majority, because Figure 8 in the paper shows that entry can still be overwritten. It is the one genuinely subtle rule, it is what most summaries omit, and it is where an interviewer probing depth will go.

Follow-up Q&A

"Walk me through Raft." Three subproblems. Leader election: a follower that hears nothing for a randomised timeout becomes a candidate, increments its term and requests votes, and wins on a majority. Log replication: the leader appends entries and pushes them with a consistency check on the previous index and term, which gives the Log Matching Property. Safety: five properties, of which Leader Completeness is load-bearing, enforced by requiring voters to refuse candidates whose logs are less up to date than their own.

"Why is the up-to-date vote check a safety property?" Because it is what guarantees any new leader holds every committed entry. A committed entry is on a majority; any two majorities intersect; so at least one voter has it, and that voter refuses to vote for a candidate whose log is behind. That intersection argument is the whole safety proof in one sentence, and it is why the check compares last log term first and then length.

"What's the commit restriction and why does it exist?" A leader may not commit an entry from a previous term merely because it is now stored on a majority. Figure 8 in the paper shows why: an entry from an old term can reach a majority and still be overwritten by a later leader whose log did not contain it, so committing it would lose a committed entry. The fix is that a leader commits old entries only indirectly, by committing an entry from its own term at a higher index, which is why implementations append a no-op immediately on election.

"What is pre-vote and why does production need it?" A node partitioned away keeps timing out and incrementing its term, so it rejoins at term 847 while the cluster is at 12. Its higher term forces the healthy leader to step down, and the rejoining node cannot win because its log is behind, so the cluster loses its leader for nothing. Pre-vote makes a candidate ask "would you vote for me" without changing state, and only increment its term if a majority would. Without it, any flapping node repeatedly disrupts a healthy cluster.

"How do membership changes avoid split brain?" Naively, they do not: if some nodes adopt the new configuration and others hold the old, two disjoint majorities can each elect a leader. The paper's answer is joint consensus, transitioning through a combined configuration where decisions need majorities in both. The dissertation's simplification, and what etcd and most implementations do, is to change one server at a time, because old and new majorities then always overlap by at least one node. So expanding three to five is two operations, not one.

"How many nodes, and where?" Five, odd, within one region. Odd because even sizes are strictly worse: four nodes have a majority of three, so they tolerate the same single failure as three nodes while making every write wait for an extra acknowledgement. Five rather than seven because seven waits for four acknowledgements and the marginal availability rarely pays. Within one region because a cross-region group puts a 60 to 200 millisecond floor on every write, which is almost never what someone asking for multi-region intended.

"What is the actual bottleneck?" Disk, usually, not network. Every committed entry requires an fsync on the leader and on each acknowledging follower, so a 10 millisecond fsync caps cluster write throughput regardless of how fast the network is. It also causes spurious leader elections, because heartbeats queue behind log writes and followers time out. That is why etcd publishes wal_fsync_duration_seconds as a primary health metric and recommends a p99 under 10 milliseconds, and why running it on shared or network storage causes elections under load.

"When would you not use consensus at all?" Whenever the data does not need a total order, which is most data. Cassandra uses consensus for schema changes and optionally for lightweight transactions, not for ordinary writes. Dynamo and S3 have none on the data path. Kafka's KRaft is metadata and leadership only, with data replication still on ISR. Spanner does put Paxos on the write path and its 10 to 100 millisecond writes are the visible price. So the question I would ask first is whether this needs consensus or whether only its metadata does.

"Raft or Paxos?" Raft, for anything I am implementing or operating, because understandability is a real engineering property: Multi-Paxos is under-specified, every implementation differs, and the log holes it permits complicate the state machine. Paxos variants like EPaxos avoid Raft's strong-leader throughput bottleneck and are genuinely better under some conditions, and the operational cost of a subtly wrong consensus implementation is high enough that I would take the simpler protocol.

Common misconceptions

"Raft replicates data." It replicates a log of commands. What applying an entry means is the application's business, which is why the same protocol backs a key-value store, a scheduler and a metadata quorum.

"More nodes is more available." Even sizes are strictly worse than the odd size below them, and beyond five the extra acknowledgement latency usually outweighs the marginal fault tolerance.

"A committed entry just needs a majority." Not if it is from a previous term. That is the Figure 8 restriction and it is the subtle part of the protocol.

"Raft needs synchronised clocks." Terms are a logical clock. Timeouts affect liveness and performance, never safety.

"Consensus is how you replicate." It is how you agree on an order. Most systems that scale keep it off the data path.

Interview delivery note

Structure it as the three subproblems, because that is the paper's own decomposition and it keeps the answer to ninety seconds: "Raft splits consensus into leader election, log replication and safety. Election is a randomised timeout, a term increment, and a majority vote. Replication is the leader pushing entries with a consistency check on the previous index and term. Safety is five properties, and the load-bearing one is Leader Completeness."

Then give the intersection argument, because it is the proof in one sentence: "The reason a new leader always has every committed entry is that a committed entry is on a majority, any two majorities intersect, and voters refuse candidates whose logs are less up to date than their own. So at least one voter holds the entry and blocks the election."

Volunteer the commit restriction, because that is where a depth probe goes: "The subtle part is that a leader can't commit an entry from a previous term just because it's now on a majority. Figure 8 in the paper shows that entry can still be overwritten by a later leader, so committing it would lose a committed entry. Leaders commit old entries indirectly, by committing one from their own term at a higher index, which is why implementations append a no-op on election."

Then move to the operational layer, which is what the question is usually testing: "In production I'd treat pre-vote and single-server membership changes as mandatory. Without pre-vote, a flapping node rejoins with an inflated term and deposes a healthy leader for nothing. And I'd watch fsync latency as the primary health metric, because a slow disk caps write throughput regardless of network speed and causes spurious elections by delaying heartbeats."

Close with the judgement, because it is worth more than the protocol: "and five nodes, odd, within one region. But the question I'd ask before any of this is whether the data path needs consensus or whether only the metadata does. Cassandra, Dynamo, S3 and Kafka all reach very large scale by keeping it off the data path, and Spanner's ten-to-a-hundred-millisecond writes are the price of the alternative."

The Staff & Team Lead Interview Reference