Lesson 29 · Consensus · Module 3
Raft: Log Replication
Lesson 28 elected a leader and stopped there — deliberately, because the leader it elected might be missing data. This lesson makes the logs identical, and then adds the two rules that make "committed" mean something.
The win in this lesson: you will be able to explain why a committed entry can never be lost, and why both the election restriction and the current-term commit rule are needed — neither one alone is enough.
1. What a leader alone does not fix
Electing one writer removes the duelling-proposer problem of lesson 27. It does not remove divergence. Leaders crash mid-broadcast, and the next leader inherits a set of logs that no longer agree with each other. The paper states the hazard plainly:
"[…] a follower might be unavailable while the leader commits several log entries, then it could be elected leader and overwrite these entries with new ones; as a result, different state machines might execute different command sequences."
In Search of an Understandable Consensus Algorithm (Extended Version), Ongaro & Ousterhout, §5.4
So the log is not a queue that happens to be replicated. It is the thing being agreed on, and two guarantees are wanted from it:
| Property (Figure 3) | What it says | Bought by |
|---|---|---|
| Log Matching | "if two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index" | The AppendEntries consistency check (§2 below) |
| Leader Completeness | "if a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-numbered terms" | The election restriction plus the commit rule (§5) |
| 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 log entry for the same index" | The two above, together |
The first is mechanism. The second and third are safety, and they are where the subtlety lives.
2. The consistency check, and the property it buys
Log Matching is really two claims:
"If two entries in different logs have the same index and term, then they store the same command. […] If two entries in different logs have the same index and term, then the logs are identical in all preceding entries."
Ongaro & Ousterhout, §5.3
The first is free: a leader creates at most one entry per index per term, and entries never move. The second is earned, by one field pair on every AppendEntries RPC.
"[…] the leader includes the index and term of the entry in its log that immediately precedes the new entries. If the follower does not find an entry in its log with the same index and term, then it refuses the new entries."
Ongaro & Ousterhout, §5.3
Those are prevLogIndex and prevLogTerm. Here is the whole receiver side, from
the condensed spec in Figure 2:
AppendEntries · Receiver implementation:
1. Reply false if term < currentTerm (§5.1)
2. Reply false if log doesn't contain an entry at prevLogIndex
whose term matches prevLogTerm (§5.3)
3. If an existing entry conflicts with a new one (same index but
different terms), delete the existing entry and all that follow it (§5.3)
4. Append any new entries not already in the log
5. If leaderCommit > commitIndex, set commitIndex =
min(leaderCommit, index of last new entry)Rule 2 turns a whole-log claim into a one-entry claim. The follower does not compare logs; it compares one index and one term. Because the check held on the previous append, and on the one before that, agreement at index n implies agreement at every index below it. The paper's word for this is exact: "The consistency check acts as an induction step".
"The consistency check acts as an induction step: the initial empty state of the logs satisfies the Log Matching Property, and the consistency check preserves the Log Matching Property whenever logs are extended. As a result, whenever AppendEntries returns successfully, the leader knows that the follower’s log is identical to its own log up through the new entries."
Ongaro & Ousterhout, §5.3
3. Committing: count replicas, then tell everyone
"A log entry is committed once the leader that created the entry has replicated it on a majority of the servers (e.g., entry 7 in Figure 6). This also commits all preceding entries in the leader’s log, including entries created by previous leaders."
Ongaro & Ousterhout, §5.3
Read "the leader that created the entry" carefully. It is the whole of §5.4.2, hiding in a subordinate clause. We come back to it.
Commitment is a leader-local decision that then propagates:
"The leader keeps track of the highest index it knows to be committed, and it includes that index in future AppendEntries RPCs (including heartbeats) so that the other servers eventually find out. Once a follower learns that a log entry is committed, it applies the entry to its local state machine (in log order)."
Ongaro & Ousterhout, §5.3
commitIndex: a majority stores the entry, and the entry's term
equals the leader's current term. Section 5 is about why the second one is not redundant.4. Repairing a follower that has diverged
After a crash, a follower's log can be short, long, or wrong. The paper enumerates it: a follower may "be missing entries that are present on the leader, it may have extra entries that are not present on the leader, or both."
"In Raft, the leader handles inconsistencies by forcing the followers’ logs to duplicate its own. This means that conflicting entries in follower logs will be overwritten with entries from the leader’s log."
Ongaro & Ousterhout, §5.3
The leader does not ask the follower what it has. It probes backwards until the consistency check passes:
"The leader maintains a nextIndex for each follower, which is the index of the next log entry the leader will send to that follower. When a leader first comes to power, it initializes all nextIndex values to the index just after the last one in its log (11 in Figure 7)."
Ongaro & Ousterhout, §5.3
"[…] the leader decrements nextIndex and retries the AppendEntries RPC. Eventually nextIndex will reach a point where the leader and follower logs match. When this happens, AppendEntries will succeed, which removes any conflicting entries in the follower’s log and appends entries from the leader’s log (if any)."
Ongaro & Ousterhout, §5.3
"With this mechanism, a leader does not need to take any special actions to restore log consistency when it comes to power. It just begins normal operation, and the logs automatically converge in response to failures of the AppendEntries consistency check."
Ongaro & Ousterhout, §5.3 — line-break hyphens in "auto-matically" and "Append-Entries" removed
There is no recovery mode, no catch-up protocol, no repair job. Repair is the steady state, run against every follower, all the time.
5. The two safety rules
Overwriting a follower is only acceptable if what you overwrite was never committed. Two rules together buy that, and this is the part of Raft people skip.
Rule one: the election restriction (§5.4.1)
"Raft uses the voting process to prevent a candidate from winning an election unless its log contains all committed entries. A candidate must contact a majority of the cluster in order to be elected, which means that every committed entry must be present in at least one of those servers."
Ongaro & Ousterhout, §5.4.1
"The RequestVote RPC implements this restriction: the RPC includes information about the candidate’s log, and the voter denies its vote if its own log is more up-to-date than that of the candidate. […] Raft determines which of two logs is more up-to-date by comparing the index and term of the last entries in the logs. If the logs have last entries with different terms, then the log with the later term is more up-to-date. If the logs end with the same term, then whichever log is longer is more up-to-date."
Ongaro & Ousterhout, §5.4.1
Note the comparison order: term first, length second. A long log full of stale-term entries loses to a short log with one newer entry. This is the promised addition to lesson 28's vote, and it is why a new leader never needs entries shipped to it — "log entries only flow in one direction, from leaders to followers, and leaders never overwrite existing entries in their logs" (§5.4.1, line-break hyphens in "di-rection" and "over-write" removed).
Rule two: commit only your own term (§5.4.2)
This is the rule that looks like an over-cautious detail and is actually load-bearing.
"A time sequence showing why a leader cannot determine commitment using log entries from older terms."
Ongaro & Ousterhout, Figure 8 caption — line-break hyphen in "de-termine" removed
"At this point, the log entry from term 2 has been replicated on a majority of the servers, but it is not committed. If S1 crashes as in (d), S5 could be elected leader (with votes from S2, S3, and S4) and overwrite the entry with its own entry from term 3. […] then this entry is committed (S5 cannot win an election). At this point all preceding entries in the log are committed as well."
Ongaro & Ousterhout, Figure 8 caption
"Raft never commits log entries from previous terms by counting replicas. Only log entries from the leader’s current term are committed by counting replicas; once an entry from the current term has been committed in this way, then all prior entries are committed indirectly because of the Log Matching Property."
Ongaro & Ousterhout, §5.4.2 — line-break hyphen in "count-ing" removed
So the commit condition in Figure 2 has three clauses, not two, and the third is the whole of §5.4.2:
Leaders (§5.3, §5.4):
If there exists an N such that N > commitIndex,
a majority of matchIndex[i] ≥ N,
and log[N].term == currentTerm:
set commitIndex = N6. What the two rules forbid
Here is the win. Suppose entry e is committed in term T, and ask how it could ever disappear. It would need a later leader U whose log lacks it. The paper's argument runs through one server:
"Thus, at least one server (“the voter”) both accepted the entry from leader T and voted for leader U, as shown in Figure 9. The voter is key to reaching a contradiction. […] The voter granted its vote to leader U, so leader U’s log must have been as up-to-date as the voter’s."
Ongaro & Ousterhout, §5.4.3
Two majorities always intersect — the same overlap that made lesson 28's election unique. The voter is in both, so it held e and it approved U. By the up-to-date test, U's log was at least as good, so U held e too. Contradiction.
| Remove this rule | The intersection argument breaks because… | Observable failure |
|---|---|---|
| Election restriction (§5.4.1) | The voter can grant its vote to a candidate whose log is missing e | A new leader forces its shorter log on everyone; a committed write vanishes |
| Current-term commit rule (§5.4.2) | e was never really committed — a majority storing it does not stop a later candidate from beating them all on last-log term | Figure 8 exactly: the client is told "committed", then index 2 is overwritten |
| Neither (Raft as written) | The voter both holds e and gates the election on log freshness | Leader Completeness, and from it State Machine Safety |
The election restriction protects a committed entry from the next leader. The current-term commit rule makes sure the word "committed" was earned in the first place. Drop the first and committed data is overwritten; drop the second and data was never committed, only counted. Both rules defend the same sentence — "if a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-numbered terms" — from opposite sides.
7. Crashes, and a log that cannot grow forever
Follower and candidate crashes need no machinery at all:
"Raft handles these failures by retrying indefinitely; if the crashed server restarts, then the RPC will complete successfully. If a server crashes after completing an RPC but before responding, then it will receive the same RPC again after it restarts. Raft RPCs are idempotent, so this causes no harm."
Ongaro & Ousterhout, §5.5
The log, though, does grow, and §7 discards its old prefix:
"Each server takes snapshots independently, covering just the committed entries in its log. […] Once a server completes writing a snapshot, it may delete all log entries up through the last included index, as well as any prior snapshot."
Ongaro & Ousterhout, §7
Two pieces of metadata survive the deletion, and the reason is section 2 of this lesson: the consistency check needs a previous index and term for the first surviving entry.
"[…] the last included index is the index of the last entry in the log that the snapshot replaces […] and the last included term is the term of this entry. These are preserved to support the AppendEntries consistency check for the first log entry following the snapshot, since that entry needs a previous log index and term."
Ongaro & Ousterhout, §7 — line-break hyphens in "sup-port" and "pre-vious" removed
Snapshots also break the walk-back of section 4. If nextIndex falls below what the leader
still stores, there is nothing to send:
"[…] the leader must occasionally send snapshots to followers that lag behind. This happens when the leader has already discarded the next log entry that it needs to send to a follower. […] The leader uses a new RPC called InstallSnapshot to send snapshots to followers that are too far behind; see Figure 13."
Ongaro & Ousterhout, §7
And on arrival the follower does the drastic thing: "the follower discards its entire log; it is all superseded by the snapshot and may possibly have uncommitted entries that conflict with the snapshot" (§7). Same principle as the overwrite in section 4, applied wholesale.
8. Residual risk
Acknowledged is not applied. A committed entry is guaranteed to survive and eventually be applied everywhere — "Raft guarantees that committed entries are durable and will eventually be executed by all of the available state machines" (§5.3) — but a follower learns of the commit only on a later AppendEntries. Read from a follower and you are reading the past. That is lesson 23's distinction, unchanged by consensus.
A new leader's first commit can be slow. Until it appends one entry in its own term, it may not commit anything, however well replicated the backlog is. On an idle cluster after an election, that is a real stall — hence the no-op append.
A single slow follower is cheap; a persistently slow one is not. Replication waits for a majority, so one laggard costs nothing. But a follower that falls behind the leader's retained log forces a whole-state snapshot transfer, and that is a bandwidth event, not an RPC.
The uncommitted tail is a trap for callers. Entries that are on disk on a majority may
still be erased, as Figure 8 shows. Anything that reads a Raft node's log directly, or watches replication
metrics and infers durability from them, has invented a guarantee the protocol does not offer. Only
commitIndex means committed.
9. Check yourself
10. Back to your world
Take any replication you own — a primary with read replicas, a change stream with consumers, a queue with a
durable offset — and ask what plays the part of prevLogIndex. When a replica reconnects, does it
present a position and an identity for what is at that position? A position alone cannot detect
divergence; it can only detect lag. Most homemade replication has the first and not the second, which is why
it resyncs by copying everything.
Then ask the harder one: what does your system call "durable", and is it a count or a decision? If an acknowledgement is issued because N replicas answered, name the scenario in which those N are outvoted later. If you cannot, you have not yet found your Figure 8 — you have only not looked.