Catalog My learning Blog
Raft and Paxos Explained: Consensus, ZooKeeper and etcd · Phase 2 · Lesson 8 · 11 min read

Raft Log Replication and the Commit Index

On this page
  1. Learning Objective
  2. Concept Explanation
  3. Worked Example: Repairing a Divergent Follower and the Figure 8 Restriction
  4. Real-World Examples
  5. Review Questions & Answers

Learning Objective

Trace an entry from client request to committed and applied, explain the log matching property and the consistency check that enforces it, and state precisely why a leader may not commit an entry from a previous term merely because it is stored on a majority.

Concept Explanation

Once a leader is established, replication follows a single path. A client sends a command to the leader, the leader appends it to its own log as a new entry tagged with the current term, and it sends AppendEntries RPCs to all followers in parallel. When a majority of the cluster, counting the leader itself, has durably stored the entry, the leader advances its commit index, applies the entry to its state machine, and replies to the client. Followers learn about the new commit index from the leaderCommit field on the next AppendEntries and apply entries up to it against their own state machines. Note the ordering: the client is told the write succeeded once it is durable on a majority, not once every replica has it, which is what makes the system tolerate slow or dead followers without stalling.

The AppendEntries RPC carries more than the new entries. It also includes prevLogIndex and prevLogTerm, describing the entry immediately preceding the ones being sent, and a follower refuses the RPC unless its own log contains an entry at prevLogIndex with exactly that term. This consistency check is the enforcement mechanism for the log matching property, which has two halves: if two logs contain an entry with the same index and term, they store the same command at that index, and furthermore the two logs are identical in all preceding entries. The first half follows from a leader creating at most one entry per index per term. The second half follows inductively from the consistency check itself, because a follower only accepts an entry after confirming the previous one matches. The practical consequence is enormous: a single matching index and term is sufficient proof that two logs agree on their entire shared history, so reconciling a divergent follower needs only a search for the last matching point rather than an entry-by-entry comparison.

When a follower rejects an AppendEntries, the leader decrements its nextIndex for that follower and retries, walking backwards until it finds the last point where the logs agree, then overwriting everything after that point with its own entries. This unconditional overwrite is safe precisely because of the election restriction from the previous lesson: a leader is guaranteed to hold every committed entry, so anything it overwrites on a follower was necessarily uncommitted and was never acknowledged to a client. The naive backwards walk costs one round trip per entry of divergence, so real implementations including etcd send a hint back with the rejection - the term of the conflicting entry and the first index the follower holds for that term - allowing the leader to skip an entire term of divergence in a single step.

The leader tracks two arrays, one entry per follower. nextIndex is the leader's optimistic guess at the next entry to send, initialised to the leader's last index plus one and decremented on rejection. matchIndex is the highest index known to be replicated on that follower, which is conservative and only ever advances on a successful acknowledgement. The commit index is computed from matchIndex: the leader finds the highest index N such that a majority of matchIndex values are at least N, and commits up to N. This is the mechanism through which majority durability becomes commitment.

There is one additional restriction, and it is the subtlest rule in Raft. A leader may only advance the commit index to an entry from its own current term. An entry from a previous term that happens to be replicated on a majority is not thereby committed, and this is not an optimisation but a safety requirement, illustrated by Figure 8 of the Raft paper. The scenario is that a leader replicates an old-term entry to a majority without committing it, crashes, and a different sequence of elections allows a later leader with a different log to be elected and to overwrite that entry - meaning an entry that was on a majority was nonetheless not safe to call committed. Raft closes this by committing old entries only indirectly: a new leader commits an entry from its own term, typically a no-op appended immediately on election, and the log matching property then makes every preceding entry committed along with it. This is why etcd and similar systems append a no-op entry the moment a leader takes office, and why the first client write after a failover sometimes shows slightly elevated latency.

Leader StateMeaningInitialised ToUpdated By
nextIndex[follower]Optimistic guess at the next entry to send this followerLeader last log index + 1Decremented on rejection, advanced on success
matchIndex[follower]Highest index known to be durably replicated on this follower0Set on a successful AppendEntries acknowledgement only
commitIndexHighest index known committed across the clusterLast value known at election timeHighest N with a majority of matchIndex >= N, and N from the current term
lastAppliedHighest index this node has fed to its state machineSnapshot index on restartAdvanced as entries up to commitIndex are applied in order

Worked Example: Repairing a Divergent Follower and the Figure 8 Restriction

Two behaviours are worth seeing together: how the consistency check finds the divergence point and overwrites safely, and why an entry sitting on a majority can still fail to be committed.

Code
# PART 1: repairing a follower whose log diverged under a previous leader.
# New leader L (term 7). Follower F crashed under an old leader.
#   L: [1:1, 2:1, 3:2, 4:5, 5:6, 6:7]        lastIndex=6
#   F: [1:1, 2:1, 3:2, 4:3, 5:3]             lastIndex=5
# Entries 4 and 5 on F came from a leader in term 3 and were NEVER
# committed - they never reached a majority.

nextIndex[F] = 7   # optimistic: L's lastIndex + 1

L -> F : AppendEntries(prevLogIndex=6, prevLogTerm=7, entries=[])
F      : I have nothing at index 6 -> REJECT
nextIndex[F] = 6

L -> F : AppendEntries(prevLogIndex=5, prevLogTerm=6, entries=[6:7])
F      : my index 5 has term 3, not 6 -> REJECT
         # optimised rejection hint: conflictTerm=3, firstIndexOfTerm=4
nextIndex[F] = 4      # L skips the whole divergent term in one step

L -> F : AppendEntries(prevLogIndex=3, prevLogTerm=2, entries=[4:5, 5:6, 6:7])
F      : my index 3 has term 2 -> MATCH. Accept.
         Truncate everything after index 3, append L's entries.
   F: [1:1, 2:1, 3:2, 4:5, 5:6, 6:7]   # identical to L
matchIndex[F] = 6

# The overwrite of F's entries 4 and 5 is safe because L was elected,
# which proves L holds every COMMITTED entry. Anything L overwrites was
# by definition uncommitted and was never acknowledged to a client.


# PART 2: why an entry on a majority is not automatically committed.
# 5 nodes: S1..S5.
S1 is leader in term 2 and appends entry (index=2, term=2).
S1 replicates index 2 to S2. Now 2 of 5 have it. NOT committed.
S1 crashes.

S5 is elected leader for term 3 (voted for by S3, S4, S5 - their logs
   are shorter but none has a HIGHER last term, so the up-to-date
   check passes). S5 appends its own entry at index 2 with term 3.
S5 crashes before replicating it.

S1 restarts, is elected leader for term 4, and resumes replicating its
   old index-2 entry (term 2) to S3.
   Now S1, S2, S3 all hold (index=2, term=2) -> a MAJORITY.

# Naive rule: "on a majority, therefore commit it." WRONG.
# If S1 crashed now, S5 could still be elected for term 5 (S5's last
# entry has term 3, which beats term 2 on the up-to-date check) and
# would overwrite index 2 on everyone. An entry called committed would
# have been destroyed.

# RAFT'S RULE: S1 may only commit an entry from its OWN current term.
# S1 appends a no-op at index 3 with term 4 and replicates that to a
# majority. Committing index 3 (term 4) commits index 2 INDIRECTLY via
# the log matching property. Now any future leader must hold index 3,
# and therefore must hold index 2 as well, so neither can be lost.
#
# Practical consequence: real implementations append a no-op entry the
# instant a leader takes office, which is why the first write after a
# failover can show slightly higher latency.
Raft log replication mechanics: the AppendEntries consistency check walking backwards to the last matching index and overwriting a divergent follower tail, alongside the commit-index rule showing why an entry from a previous term replicated on a majority is committed only indirectly, through an entry from the current term.
Raft log replication mechanics: the AppendEntries consistency check walking backwards to the last matching index and overwriting a divergent follower tail, alongside the commit-index rule showing why an entry from a previous term replicated on a majority is committed only indirectly, through an entry from the current term.

Real-World Examples

  • The Raft paper's Figure 8 scenario is not a theoretical curiosity: etcd's Raft implementation appends an empty entry immediately upon a leader taking office specifically to satisfy this restriction, so that entries carried over from previous terms become committed indirectly. The behaviour is directly observable as a brief spike in commit latency on the first write after a leadership change in a Kubernetes control plane.
  • The optimised AppendEntries rejection, in which a follower returns the conflicting term and the first index it holds for that term so the leader can skip an entire term of divergence per round trip, appears in essentially every production Raft implementation including etcd's raft library and HashiCorp's raft library used by Consul and Nomad. The naive one-index-per-round-trip walk described in the paper would take thousands of round trips to repair a follower that had been partitioned for an extended period, which is exactly the situation where fast recovery matters most.
Common PitfallA follower that rejects AppendEntries is not failing - it is telling the leader where the logs diverge, and the backwards walk is the repair protocol. The subtle rule to remember is that replication to a majority is necessary but not sufficient for commitment: a leader may only advance the commit index to an entry from its own term, committing older entries indirectly through the log matching property, which is why implementations append a no-op the moment a leader takes office.

Review Questions & Answers

It has two parts: if two logs contain an entry at the same index with the same term, they hold the same command there, and the two logs are identical in every preceding entry. The first part holds because a leader creates at most one entry per index per term and never changes an entry once written. The second holds inductively from the AppendEntries consistency check, since a follower accepts an entry only after confirming that its entry at prevLogIndex has the matching prevLogTerm, so each accepted entry inherits the guarantee about everything before it. That induction is why one matching point certifies the whole shared prefix, which in turn is why reconciling a divergent follower is a search for the last matching index rather than an entry-by-entry comparison.

Because the election restriction guarantees the leader holds every committed entry. A candidate can only win with votes from a majority, every voter refuses candidates whose logs are less up to date than its own, and any majority intersects the majority that committed the latest entry. Therefore anything present on a follower but absent from the leader was never replicated to a majority, was never committed, and was never acknowledged to any client as durable. Discarding it loses nothing that was ever promised, which is what lets Raft resolve conflicts by unconditional truncation rather than by merging.

Because a node whose log ends with a higher-term entry may still be electable, and if it wins it will overwrite that index on every follower, destroying an entry that had been declared committed. Majority storage alone therefore does not make an old-term entry safe. Raft's rule is that a leader may only advance the commit index to an entry from its own current term; once it commits an entry from term 4, the log matching property makes every preceding entry, including the term 2 entry, committed along with it, because any future leader must hold the term 4 entry and therefore its whole prefix. Implementations force this quickly by appending a no-op entry as soon as a leader takes office.

nextIndex is an optimistic guess at what to send next, initialised high and decremented on rejection, so it can easily be wrong. matchIndex is a conservative fact, advanced only when a follower has actually acknowledged storing entries up to that point, so it is never an overestimate. The commit index derives from matchIndex because commitment is a claim about durability that must never be wrong: the leader finds the highest index at which a majority of matchIndex values are at least that high. Deriving it from nextIndex would let an unconfirmed guess be reported to clients as a durable commit.

The paper's approach decrements nextIndex by one per rejected round trip, so repairing a follower that diverges by K entries costs K round trips. A follower that was partitioned for an extended period can diverge by thousands or millions of entries, turning recovery into an unacceptably long sequence of round trips exactly when the cluster most needs the node back. The optimisation has the follower return the term of its conflicting entry and the first index it holds for that term, letting the leader skip an entire term of divergence per round trip and typically converge in a handful of exchanges instead. This matters most after long partitions and after restoring a node from an old backup.