Lesson browser Distributed consensus, replication, and fault tolerance lessons Previous: Raft elections and persistent terms Next: Paxos and preserving an earlier decision

Distributed systems · Lesson 9

Raft log repair and commitment

Explain prefix matching, leader completeness, and the current-term commitment rule.

By the end: Distinguish entries that may be overwritten from the prefix future leaders must preserve.

Match a prefix before extending it

AppendEntries carries the leader’s term, a previous log index and term, new entries, and information about the committed prefix. A follower first checks that it has the expected entry at the previous index with the expected term. If that check fails, it rejects the request. The leader retries with an earlier matching point or a snapshot when necessary.

Once the preceding entry matches, a conflicting entry and its following suffix can be replaced by the leader’s entries. A follower does not delete extra entries merely because a heartbeat contains no new entries. Actual conflicts drive truncation. With Raft’s rules, an entry with the same index and term has the same preceding history. This log-matching property makes agreement about a later point imply agreement about its prefix.

Repair a conflicting suffix from a verified matching point

Treat each log entry as a position, an entry term, and a command. The election term in an AppendEntries request describes the sender's authority attempt. The entry terms describe when particular entries were first created. A leader in term 8 can legitimately send entries created in terms 5 and 6 while bringing a follower up to date. Copying those entries does not change their terms to 8. Confusing these two uses of term would break both freshness comparisons and the commitment test.

In a separate paper repair case, suppose leader A has entries at indexes 1 through 5 with terms 1, 1, 3, 4, 4. Follower B has terms 1, 1, 2, 2 through index 4. The commands at the first two positions match. A request that claims the previous entry is index 4, term 4 fails at B because B's entry there has term 2. Rejecting protects the assumption that new entries extend the same preceding history.

A can try an earlier point. A request whose previous entry is index 2, term 1 passes. It carries A's entries beginning at index 3. B compares the supplied index-3 entry with its own and finds different entry terms, so it deletes its conflicting suffix beginning there. B then stores A's entries for indexes 3 through 5. The repaired sequence is 1, 1, 3, 4, 4. The request established a matching prefix before replacing the divergent suffix.

The rejected request did not require A to copy all of B's entries or decide which commands looked more reasonable. Raft repairs according to log identity and leader authority, not application preference. If B's term-2 command reserved a seat, the application must not have treated it as final merely because B stored it. A safe implementation applies only committed entries. That boundary is what lets an uncommitted suffix be replaced without retracting a promised committed application result.

Successful repair must become durable before B sends an acknowledgment that the leader may count as durable replication. A reply based only on memory would let A rely on copies that disappear during a covered crash. The receiver must also respect the sender's request term. An obsolete leader cannot repair a follower that has already advanced to a higher term by presenting an attractive matching prefix. Authority checks and prefix checks answer different questions, and both matter.

Log matching is stronger than seeing equal lengths or equal final commands. Under Raft's creation and append rules, equal entry term and index identify the same entry and therefore the same prefix. Two arbitrary files containing a term label do not gain that property by naming it. The reasoning assumes legitimate Raft histories, one elected leader per term, and persistent protocol state. The bounded replication lab from lesson 5 fixes one term and cannot demonstrate this repair process or validate those assumptions across elections.

Why counting old-term copies is unsafe

A leader advances commitment by counting a majority for an entry from its current term. Earlier entries become committed indirectly as part of that prefix. It must not declare an earlier-term entry committed solely because it now appears on a majority. Figure 8 of the Raft paper gives the critical counterexample.

In a five-server example, A and B receive x at index 2 in term 2. Later E alone stores y at index 2 in term 3, after winning an election with servers whose logs were sufficiently old. A then wins term 4 using A,B,C and copies x to C. Now x is on A,B,C, but E can still win a later election with C,D,E because E’s last entry is from term 3 while C’s is from term 2. Without a committed term-4 entry, x can still be overwritten. Majority presence of this old-term entry was not enough.

Follow the old-term counterexample through legal elections

Expand the five-server case as a paper timeline. All servers initially share an entry at index 1 from term 1. A wins term 2 and creates x at index 2. Only A and B receive x before communication changes, so no majority has stored it. A valid command can exist without being committed. The later terms in this example concern leadership attempts; x keeps entry term 2 throughout every later copy.

E then wins term 3 using voters C, D, and E, whose logs still end at index 1 in term 1. E's own log is at least as fresh as theirs, so this election need not violate the voting restriction. E appends y at index 2 in term 3 but does not replicate it to a majority. At this stage A and B hold x, E holds y, and C and D have neither index-2 entry.

A can next win term 4 with A, B, and C. A and B end in entry term 2; C ends in entry term 1. Those voters can pass A's freshness test, assuming no prior vote prevents it. A copies x to C. Three servers now durably hold x, and A can receive acknowledgments for those copies. However, the counted entry still belongs to term 2. It is not a newly created term-4 entry merely because term-4 messages carried it.

Now suppose A fails before establishing a current-term committed entry. E seeks election in term 5 using C, D, and E. E's last entry is y from term 3, while C's last entry is x from term 2 and D still ends in term 1. E passes the term-first freshness check at both voters. It can win with those three votes and then replace the conflicting x entries with y. Counting x's three copies as direct commitment in term 4 would therefore have made an unsafe promise.

Compare the alternative continuation in which A first creates z at index 3 in term 4 and durably replicates the matching prefix through z to A, B, and C. A may directly commit through z because the counted entry belongs to its current term. That commitment includes x before it. In the attempted E election, C now ends in term 4 and refuses E's term-3 final entry. E cannot obtain C's vote in this attempted quorum.

Blocking that one election illustrates the rule but is not the entire proof over future terms. A later candidate might itself have an entry with a still higher term. The full leader-completeness argument reasons about the first supposed leader missing a committed entry and shows that the earlier election and append rules make that leader impossible. Do not replace this induction over legitimate histories with a claim that any locally higher number automatically proves possession of every earlier committed command.

Work through the model

Compare the two log prefixes

Each cell is one log position, not an elapsed-time interval. The shared prefix through index 1 is omitted. The entry label t2 means entry term 2, even while A leads term 4. On the left, E can still win a later election using its term-3 entry. On the right, committing z from the current term protects x as part of the same prefix under the Raft rules. These are alternative continuations, not two simultaneous configurations.

Stage	A	B	C	D	E
Term 2	x@2	x@2	empty	empty	empty
Term 3	x@2	x@2	empty	empty	y@3
Term 4, old entry copied	x@2	x@2	x@2	empty	y@3
Alternative: term 4 prefix committed	x@2,z@4	x@2,z@4	x@2,z@4	empty	y@3

Only index 2 onward is shown; @ marks the entry term, not its index. The last row is an alternative continuation. A current-term majority commits its preceding prefix.

Read copies, commitment, and alternatives separately in the table

The table begins at index 2 rather than drawing the common index-1 prefix. Its notation x@2 means command x whose entry term is 2. It does not mean an arbitrary command located at index 2 solely because of the symbol after the at sign. Both x and y compete for index 2 in the constructed history. The additional z in the alternative final row follows x at index 3 and has entry term 4.

Read the first three rows as one continuation. The term-2 row has only two x copies. The term-3 row adds a conflicting y at E without erasing x at A and B. The term-4 row adds x at C. At that point the observer can count three x copies. The missing justification is direct commitment under A's term-4 leadership, since none of those x entries was created in term 4. The table intentionally separates a visible count from a safe protocol conclusion.

Read the last row as an alternative to stopping at that third stage. A has appended and replicated z from its own term after x. Prefix matching makes the three z copies evidence of agreement on the preceding x as well. The rule can now protect the prefix through index 3. The table is a static comparison; it does not offer message delivery, election, or log editing controls. The paper elections above explain one legal way to reach the illustrated states.

For a separate paper delivery case, let a leader send an empty request matching index 5, followed by a request that appends index 6 after that same matching point. The network delivers the second request first. The follower stores index 6 and acknowledges it. When the earlier empty request finally arrives, the follower still matches index 5. Deleting index 6 now would discard an entry the leader just supplied, despite no conflicting replacement. Message reordering explains why an empty request must not imply truncation.

Continue that paper case by delaying the index-6 acknowledgment until after the empty request's response. The empty response establishes agreement through its matching point; it does not justify reducing a previously confirmed replication boundary or counting a different later entry. The eventual index-6 acknowledgment concerns the request that actually carried that entry. Reasoning about message contents, rather than arrival order alone, separates a follower's valid prefix check from the leader's evidence about durable replication progress.

Finally, attach local knowledge to each table row on paper. After A commits through z, C can still lack a message announcing that committed boundary. Its stored entries are protected globally even before C knows that fact. C must not guess its application boundary from the number of entries it holds. The figure shows a global history comparison, whereas a server acts on its local protocol state and received evidence. Neither table color nor an observer's knowledge constitutes a message delivered to C.

Connect the rules into a safety argument

If A instead appends a term-4 entry after x and stores that prefix on A,B,C, a future candidate lacking a sufficiently fresh compatible history cannot obtain the needed votes. The election restriction, one vote per term, and prefix matching together support leader completeness: every later leader contains every committed entry. This is the essential argument; a full proof must handle every possible first violating leader, not just this example.

Apply only committed commands, in increasing index order. A follower can possess an entry without yet knowing it is committed; the leader advertises the commit boundary. A new leader may contain all committed entries without initially knowing the precise boundary, which matters for reads. Storage, commit knowledge, application progress, and client replies remain distinct. A command that was never committed can survive an election, but it can also disappear; a timeout does not settle which outcome will occur.

Move the committed boundary into application state without skipping entries

A committed log prefix and an applied state machine can advance at different times. Suppose A knows the log is committed through index 12, but its application has executed only through index 10. Applying index 12 first would skip the state produced by index 11. Even deterministic commands can then produce the wrong result because the starting state differs. The server must execute the committed commands in index order and track which prefix its application has actually completed.

Use a separate paper example with a balance initially 20. Index 11 debits 5 and index 12 conditionally debits 18 only if sufficient funds remain. Correct application leaves 15 after index 11, then rejects index 12. Executing index 12 against the old balance 20 would approve it, changing the outcome. Consensus about the command sequence gives replicas enough information to agree; the application still has to consume that sequence faithfully and retain deterministic results.

Clients need a success contract tied to these boundaries. A system may know a command is committed before it has computed the application result. For an operation such as a conditional debit, reporting success requires the actual result of application, not merely a log index. A lost reply after application leaves the outcome unknown to the client while the state remains decided. Repeating the same logical operation safely later requires a durable identity and result record committed atomically with the effect.

A new leader can possess all committed entries while initially lacking proof of the previous committed boundary. A current-term no-op can establish a committed prefix without changing business state. It still occupies a log position and must pass the same durable replication rules. Committing it does not itself show that application has caught up. Before serving a linearizable read, the server also needs appropriate evidence of current authority for that read and an application state through the safe read boundary.

Crashes do not turn an uncommitted suffix into committed history, nor do they necessarily erase it. Such entries may survive recovery and later become part of a protected prefix, or a legitimate new leader may overwrite them. This explains why a client timeout cannot classify an entry by durability or finality. To diagnose a disputed operation, locate its identity, stored position, entry term, commitment evidence, application result, and reply history rather than assuming that one missing response proves absence from the log.

These arguments require durable terms, votes, and entries under the promised crash model. They assume nonmalicious participants follow the append and voting rules, fixed membership for the examples, and no silent loss of acknowledged storage. They do not certify arbitrary log files, dynamic membership changes, or dishonest replicas. The coming Paxos lesson uses a different mechanism to preserve an earlier chosen value. Keep its ballot and adoption rules distinct from Raft's current-term commitment test, even though both rely on remembered obligations and intersecting quorums.

Exercises

What can repair erase?

A follower has an extra uncommitted entry at index 8. A heartbeat matches index 7 but carries no new entries. Must it delete index 8 immediately?

Hint

Raft truncates when a supplied entry conflicts at the same index.

Worked answer

Message	Existing suffix	Action
Match #7, no new entries	#8 uncommitted	Do not truncate merely for being extra
Match #7, conflicting #8	#8 uncommitted	Replace conflicting suffix

Prefix validation and conflict truncation are separate checks.

No. A matching heartbeat by itself is not a conflicting replacement entry. A later AppendEntries containing a different entry at index 8 can cause the conflicting suffix to be removed. Committed history must remain protected by the election and commitment invariants.

A majority of an old-term entry

A term-9 leader has copied a term-7 entry onto three of five servers. May it advance commitment solely on that count?

Hint

Which term must the counted entry belong to?

Worked answer

Counted entry	Copies	Can directly advance commit?
Term 7 under term-9 leader	3 of 5	No, not solely by this count
Term 9 after that prefix	3 of 5	Yes, with normal Raft rules

A no-op occupies a real log position even though it leaves application state unchanged.

No. It can replicate and commit an entry from term 9 after it, which commits the preceding prefix. The term-7 copies alone do not satisfy Raft’s direct commitment rule. A current-term no-op is often used to establish a safe boundary without changing application data.

Sources and further reading

The explanations and worked answers above stand alone. These references provide the original algorithms, assumptions, and deeper proofs; they are not required downloads.

Ongaro and Ousterhout: In Search of an Understandable Consensus Algorithm, extended version
Raft protocol, Figure 2, safety and Figure 8, membership, snapshots, and client interaction. Primary protocol reference.

Lesson browser Distributed consensus, replication, and fault tolerance lessons Previous: Raft elections and persistent terms Next: Paxos and preserving an earlier decision