Consensus Algorithms · Phase 5

Classical Consensus — Paxos & Raft

Article 5.6 of 7

5.1 Paxos History 5.2 Single-Decree 5.3 Multi-Paxos 5.4 VR 5.5 Raft Election 5.6 Raft Safety 5.7 Zab

Jul 14, 2026 · devops · 23 min read · 4800 words advanced

Raft — log replication and safety.

devops distributed-systems raft series-consensus

With a leader elected (article 5.5), this article covers the remaining two-thirds of Raft's decomposition: how the leader actually replicates entries via AppendEntries RPCs, the elegant log-matching property that makes conflict detection cheap, and — the part that took Raft's own authors real care to get right — the one genuinely subtle safety rule about committing entries from a previous term. By the end, you'll have watched the complete safety proof assemble itself from mechanisms this entire series has built one phase at a time: majority overlap (3.3), log divergence and repair (3.2), safety vs. liveness (4.1), and the election guarantee from 5.5, all converging into one coherent, provably-correct algorithm.

AppendEntries: replication and heartbeats, unified

The leader replicates log entries (and, with zero new entries, serves as the heartbeat mechanism from article 5.5's FAQ) via a single RPC type, AppendEntries(term, leaderId, prevLogIndex, prevLogTerm, entries[], leaderCommit). The prevLogIndex/prevLogTerm pair is the crucial consistency-check mechanism: the leader is asserting "here's what should already be at the position right before these new entries — confirm you agree before I ask you to append after it."

A follower receiving AppendEntries rejects it (asking the leader to back up and try an earlier position) unless its own log actually has an entry at prevLogIndex with term exactly prevLogTerm. This single check is what enforces the log-matching property — a guarantee worth stating precisely because of how much work it does:

Log Matching Property: if two logs contain an entry with the same index and the same term, then (a) they store the identical command at that entry, and (b) every entry before that point in both logs is also identical. Property (a) follows directly from Raft's rule that a leader creates at most one entry per log index per term (no two different values can ever be proposed at the same index within the same term, since there's only ever one leader per term, per article 5.5's election guarantee). Property (b) — the more powerful, surprising half — follows by induction from the consistency check above: if AppendEntries's prevLogIndex/prevLogTerm check ever succeeds, everything before that point must already match, because the check itself is transitively chained back through every earlier AppendEntries call that successfully replicated the prior entries.

The payoff of this property: a follower and leader only ever need to compare one position (the most recent point they agree on) to know their entire logs match up to that point — exactly the cheap, incremental conflict-detection mechanism that makes article 3.2's "logs diverge, then get repaired" story efficient in practice rather than requiring a full log comparison on every append.

Log matching in action: one check confirms everything before it Leader's log 1,t1 2,t1 3,t2 4,t3 NEW Follower's log 1,t1 2,t1 3,t2 AppendEntries checks ONLY index 3, term t2 — matches, so append index 4. By the log-matching property, indices 1-2 are GUARANTEED to already match — no need to re-check them.

Fig 1 — One consistency check at the boundary is enough — the log-matching property makes the rest provably redundant to verify.

Commitment: the safety-critical rule about prior terms

Here's the one genuinely subtle piece of Raft's safety argument — subtle enough that Ongaro and Ousterhout's paper devotes specific, careful attention to it, and it's worth equal care here. The basic commitment rule, as you'd expect from article 3.2/3.3: an entry is committed once it's stored on a majority of servers. But there's a critical additional restriction: a leader can only conclude an entry is committed by counting replicas for an entry from its OWN current term. It is explicitly not safe to conclude an entry from a previous term is committed just because it's now been replicated to a majority — even though that sounds, at first glance, like it should be enough.

Here's the scenario that makes this restriction necessary, directly extending article 3.2's log-divergence-and-repair discussion: suppose an entry from term 2 gets replicated to a majority, but the leader that replicated it crashes before it's ever actually marked committed and exposed to clients. A new leader is elected for term 3, one that also happens to have that same term-2 entry (per article 5.5's election guarantee, it must). That new term-3 leader could, in principle, still overwrite that entry — because from article 3.2's repair rule, an uncommitted entry from a prior leader's term is fair game to be replaced. If a different new leader is later elected who lacks that entry, the "committed" (by the naive majority-count rule) term-2 entry could still be lost. The fix: a leader only trusts its own count of a majority for entries created during its own term; once such a current-term entry is confirmed committed, every entry before it in the log (including older-term entries) becomes committed too, transitively, by the log-matching property.

This is precisely the kind of subtlety that makes hand-wavy liveness arguments acceptable (article 4.1) but demands rigor for safety. Getting this one rule wrong would reintroduce exactly the kind of silent, hard-to-detect data-loss bug this entire series has been building vocabulary to recognize and avoid — a "should be safe, but isn't quite" gap of the same character as 3PC's partition flaw (article 4.5), just far more subtle and far easier to miss without a rigorous proof. This is a genuine example of why the safety-proof half of these papers gets so much more scrutiny than the liveness half, exactly as article 4.1 predicted.

Assembling the full safety argument

With every piece now in place, here's how Raft's complete safety guarantee (formally: State Machine Safety — if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different entry for that same index) assembles from mechanisms this series built one phase at a time:

  1. Election Safety (5.5 + 3.3): at most one leader can be elected in a given term, because votes require a majority and a node votes at most once per term.
  2. Leader Append-Only: a leader never overwrites or deletes entries in its own log — it only appends (this is a simple, direct implementation rule, not a deep theorem).
  3. Log Matching (this article): the consistency-check property, guaranteeing identical entries at identical index+term imply identical history before that point.
  4. Leader Completeness (5.5's voting rule + 3.3's overlap): if an entry is committed in a given term, it will be present in the logs of every leader for every higher-numbered term — exactly the "any elected leader already has everything it needs" guarantee from article 5.5.
  5. State Machine Safety (this section's commitment rule, layered on top of 1-4): combining all of the above, once an entry is committed, every future leader's log is guaranteed to contain it (by Leader Completeness), so every server applies the identical sequence of committed entries to its state machine — restoring article 3.1's SMR guarantee at the top of the whole stack.
Every one of these five properties is something this series has already built the intuition for, well before reaching Raft's specific formalization of it. That's not a coincidence — it's the entire pedagogical bet this series made back in article 1.1: build the vocabulary (failure models, replication, quorums, safety/liveness, election) before the algorithms, so that by the time you reach the algorithm that actually ships in production systems, its safety proof reads as an assembly of familiar parts rather than a wall of new formalism to memorize.

FAQ

Why is it specifically unsafe to commit a previous-term entry by counting replicas, but safe once a current-term entry is committed?

Because a current-term entry being committed means the current leader — the one whose log is guaranteed complete by Leader Completeness — has confirmed a majority holds it, closing the loop this article's commitment-rule section describes. A previous-term entry's majority-count alone doesn't carry that same guarantee, because the leader that originally replicated it might never get the chance to also replicate a current-term entry, leaving open exactly the "different future leader lacks it" gap.

Does the log-matching property mean followers never need to delete any entries?

They do, in the log-divergence-and-repair scenario from article 3.2 — if AppendEntries's consistency check fails, the follower must delete its conflicting entry and everything after it before accepting the leader's version, exactly as article 3.2 described in the abstract. The log-matching property is what lets this repair happen via a single position check rather than a full log comparison.

How does Raft's safety proof compare in rigor to Paxos's?

Both are fully rigorous, formally-proven algorithms — Raft's authors provide a TLA+ formal specification and machine-checked proof alongside the paper, a level of rigor at least matching Paxos's own formal treatments. The genuine difference this whole phase has emphasized is presentation and pedagogical accessibility, not underlying mathematical rigor.

What's left to cover about Raft in the rest of this series?

This article and 5.5 cover Raft's three core sub-problems (election, replication, safety); cluster membership changes (safely adding/removing nodes from a live cluster) are previewed here but get full treatment in Phase 9.6, and Raft's real-world production usage (etcd specifically) is covered in Phase 8.1.

Takeaways

  • AppendEntries unifies replication and heartbeats; its prevLogIndex/prevLogTerm consistency check enforces the log-matching property — identical entries at identical positions guarantee identical history before them.
  • The subtle, critical commitment rule: a leader can only conclude an entry is committed by counting a majority for an entry from its own current term — never by directly counting replicas of a prior-term entry, which can reintroduce a genuine data-loss gap under a specific leader-succession sequence.
  • Raft's full State Machine Safety guarantee assembles from five properties — Election Safety, Leader Append-Only, Log Matching, Leader Completeness, and the commitment rule — each one built from mechanisms this series established well before reaching Raft itself.
  • This assembly is the direct payoff of the series' phase-by-phase structure: majority overlap (3.3), log divergence/repair (3.2), safety/liveness (4.1), and the election guarantee (5.5) combine into one coherent proof rather than requiring new formalism at the end.
  • Phase 5's classical algorithms are now essentially complete — one more article (5.7, Zab) rounds out the phase with ZooKeeper's closely related, independently-hardened protocol before Phase 6 turns to Byzantine failures.

References & further reading

← 5.5 Raft — Design and Leader Election next: 5.7 Zab — ZooKeeper Atomic Broadcast →
© cvam — written in plaintext, served warm