Commit Rules, Figure 8, and Why a Leader Cannot Trust Its Log

A leader that has just been elected holds a log that a majority of nodes agree on, up to some point. The obvious rule is to commit everything in that log, since the majority already has it. The rule is wrong, and the counterexample that kills it is the most instructive failure case in the Raft paper. Getting the commit rule right requires understanding that a majority holding an entry does not mean the entry is safe, because a majority can hold an entry that a later leader is entitled to discard.

What a commit actually asserts

The commit index is the highest log index that the leader knows to be durably agreed. Every node maintains its own commit index, and a follower’s index can lag the leader’s, but the invariant is that a node never applies an entry to its state machine before that entry is committed.

The assertion behind a commit is stronger than “a majority has the bytes”. It is: no future leader will ever be able to discard this entry. That is the property that makes applying it safe, because the state machine history becomes monotonic: once applied, an entry cannot be retroactively removed. A commit rule that only establishes “a majority has it” is therefore insufficient, and the gap between the two statements is where the naive rule fails.

The gap exists because Raft permits a new leader to overwrite uncommitted entries from previous terms. A follower whose log diverges from the new leader’s has the divergent suffix discarded, by design, and this repair is what allows a lagging or corrupted follower to rejoin. The repair is bounded by the commit index: a leader will not overwrite anything it knows to be committed. But a leader only knows what it can prove, and the proof is the commit rule.

The Figure 8 scenario

The hazard needs an entry whose term is older than the term of the leader that finally replicates it to a majority, and a subsequent leader whose log is more recent than that entry.

A leader in term 2 appends an entry and gets it onto only a minority of the servers before crashing. A leader in term 3, elected without that entry, appends its own entry at the same index on a different set of servers and then also crashes. The term-2 leader restarts, wins a later term, and replicates its old term-2 entry until a majority of servers holds it. Nothing about that replication is unusual: the entry is now on a majority, and the leader that placed it there is legitimate.

Then a server whose log ends with a term-3 entry wins the next election. Its last entry is more recent than the term-2 entry, so every voter accepts it under the log-suffix rule, including the voters that hold the term-2 entry. The new leader replicates its own entry at that index, and the term-2 entry is overwritten on the servers that had it.

At the moment the term-2 entry sat on a majority, a commit rule based on majority possession alone would have declared it committed. A later, legitimately elected leader then removed it. If the state machine had applied it, the application would have executed an operation that no replica’s log still contains.

The entry’s problem is its age, not its replication. It was created in term 2, and no leader of a later term is obliged to preserve an entry from an earlier term. The servers that voted for the term-3-ending candidate did so correctly, and the servers that accepted the term-2 entry from its own leader did so correctly as well. The protocol is behaving as specified at every step, which is what makes the example a proof that majority possession is not the same claim as commit.

The term-boundary rule

Raft’s actual rule is: a leader may commit an entry at index i only if the entry at i was created in the leader’s current term. Entries from earlier terms are committed only indirectly, by being carried along when a later entry at a higher index is committed.

The reason a current-term entry is safe is the election rule. A future leader must be elected by a majority that intersects the current leader’s quorum, and each of those voters had to pass the log-suffix check against the candidate. A candidate whose log ended before the current leader’s term-T entry would fail that check, because the current leader’s term-T entry is more recent than anything such a candidate could offer. So no leader of a term greater than T can lack the entry, and the entry cannot be discarded.

Committing an entry from the current term at index i has the effect of committing everything below i, including old-term entries, because the log is a sequence: a committed prefix is committed. That is how the old entries become safe. They become safe not on their own evidence but as a consequence of a newer entry being provably undiscardable.

The cost is latency in the specific case of a leader that inherits a long tail of uncommitted old entries. It must append at least one entry of its own and have that entry committed before any of the inherited entries can be applied. A leader that has nothing new to append is stuck until a client request arrives or until it appends a no-op. Many implementations append a no-op on election for exactly this reason, which means every leadership change costs one extra round trip before the inherited backlog can be applied.

Repair and the truncation boundary

The commit rule interacts with the log-repair procedure. A leader that receives an AppendEntries rejection from a follower because the follower’s log does not match backs up one index at a time, or jumps back using a hint, until it finds an index where the logs agree, then sends the follower everything from there.

A follower that has fallen behind the leader’s compacted log boundary cannot be repaired with entries at all, and must be sent a snapshot instead.

The truncation boundary must respect the follower’s commit index. A follower must never truncate below its own commit index, because it may have applied those entries to its state machine, and removing them would make the state machine’s history non-monotonic. In a correct implementation this cannot happen, since the leader will not have an entry below the follower’s commit index that conflicts with the follower’s log: the commit index only advances when the entry is agreed, and agreement means no conflicting entry exists. The invariant is worth stating anyway, because implementations that get it wrong corrupt state machines rather than logs, and log corruption is easier to detect.

The reverse direction matters too: a leader that is behind on the commit index must not apply entries on its own authority. The commit index is advanced only by counting acknowledgements, and a leader that has just been elected has an empty acknowledgement set regardless of how complete its log is.

What the commit index does to reads

A read served from a follower’s state machine reflects entries up to that follower’s commit index, not the leader’s. A client that reads from a follower after a write has been committed on the leader can therefore see the old value for as long as the follower’s commit index lags, which is typically one heartbeat interval. This is a real staleness window and it is why follower reads are only offered when the application can tolerate it, or when the read is accompanied by a commit index and the client checks it.

Reads served by the leader have the opposite problem. The leader’s commit index is current, but the leader’s state machine may not have applied the entry yet: the log is written, the commit index is advanced, and the application of the entry to the state machine happens afterwards, possibly asynchronously. A read that consults the state machine before applying the committed entries sees stale data even though the commit index says otherwise. The fix is to apply entries synchronously with the commit advance, or to have the read wait for the apply to catch up, and this is the reason many implementations process committed entries in a single-threaded apply loop.

There is also the question of whether the leader is still the leader at the moment of the read. A leader that has been partitioned from its followers can believe it is leader, hold a current commit index, and answer reads from a state machine that the rest of the cluster has moved past. The commit index does not by itself establish leadership; that requires either a quorum round trip per read or a lease with a bounded validity.

The connection to the abstract problem

The Figure 8 scenario is the same shape as the Paxos adoption rule’s necessity. In Paxos, a proposer must adopt the highest-numbered value it learns during phase one, because otherwise it can overwrite a value that a majority accepted. In Raft, a leader must not commit an inherited old-term entry on the strength of its majority, because a future leader can legally overwrite it. Both are statements that “a majority accepted this” is weaker than “this is decided”, and both are resolved by requiring evidence tied to the current epoch: the current proposal number in Paxos, the current term in Raft.

The difference is that Raft’s rule is a restriction on when a commit can be declared, whereas Paxos’s rule is a restriction on what value can be proposed. Raft’s log is a sequence, so a commit is always a prefix and the problem is to know when the prefix is safe. Paxos’s register has no sequence, so every proposal is independent and the problem is to know which value is the safe one. The log structure is what makes Raft’s version simpler to reason about, and it is also why Raft needs an explicit commit index where Paxos needs only the acceptor’s accepted value.

Failure modes in the commit path

Three failure modes recur in implementations.

The first is advancing the commit index on a quorum of sent acknowledgements rather than received ones. A leader that optimistically commits when it has dispatched messages to a majority has not established anything; the messages may be lost or the nodes may reject them.

The second is committing entries out of order relative to the log. The commit index is a single integer precisely because the log is a sequence; an implementation that tracks per-entry commit flags can end up applying entry 5 while entry 4 is uncommitted, which breaks the prefix property and with it every argument about state-machine consistency.

The third is treating the commit index as durable state that must be replicated. It is not. A node that restarts with a log but no commit index re-derives the index from the leader. What must be durable is the log itself and the term and vote record; the commit index is a derived fact about what the cluster has agreed, not an independent piece of state that could disagree with the log.

The commit rule is one sentence long and its justification is a three-node scenario with two leader changes. Both are worth keeping in mind when reading an implementation, because the naive rule is the one an implementer writes first, and the test suite that passes with the naive rule is the one that has not yet run Figure 8.