Log replication — AppendEntries and Log Matching — Build Raft

Build Raft — consensus you can defend (12 scenes)

Scene 04 · Log replication — AppendEntries and Log Matching

AppendEntries with prevLogIndex/prevLogTerm consistency check + nextIndex backoff inductively maintains the Log Matching Property: if two logs share an entry at (index, term), they share every preceding entry.

Previously

The last two scenes were all about getting a leader: scene 3 picked one with majority votes; scene 3a installed Pre-Vote and CheckQuorum so a stranded server cannot disrupt a healthy one and a half-deaf leader cannot wedge the cluster. So we now reliably have a leader. The natural next question is what does that leader actually DO? Its whole job is to take new client commands, write them into its own log, and copy that log onto every follower so that all five servers eventually run the same commands in the same order. This scene is about the single message that does the copying — its name is **AppendEntries** — and the tiny rule the follower runs on each one that keeps every log honest.

Scene 04

Log replication — AppendEntries and Log Matching

Watch

Diagram

Three Raft servers (S1..S3) sitting in a row. Each cell shows the server's id, its role badge (follower / candidate / leader), its currentTerm, who it voted for, and a horizontal strip of its log. Each cell in the log strip is one **log entry** (a single client command), and entries are colored by the **term** (from scene 2 — the logical clock that ticks on every election attempt) in which they were created. Two little markers sit under each strip: commitIndex (▲) is the highest log index known to be safely replicated, and lastApplied (▽) is the highest index this server has actually fed into its state machine. Arrows between cells are **AppendEntries RPCs** — the leader's replication messages. Each arrow carries a payload (prevLogIndex, prevLogTerm, entries, leaderCommit) shown on the arrow itself; a ✓ means the follower accepted it, a ✕ means it rejected; on a rejection, the follower's hint back to the leader (conflictTerm, conflictFirstIndex) is printed on the arrow too.

Sources

leader writes new entry into its own log at index 3 →

Watch one clean replication round. Plain English first: a client just sent the leader a new command, the leader wrote it down in its own log, and now it has to copy that one new entry onto each follower. The single message the leader sends to do that is called an **AppendEntries RPC** (a network message — short for Remote Procedure Call — that says 'please append these entries to your log'). Think of it as a chat message that carries (a) the leader's term so the follower knows who is calling, (b) the new entry or entries to append, and (c) a one-line proof that the leader's log lines up with the follower's log just before the new entry. That last piece — `prevLogIndex` and `prevLogTerm` — is the load-bearing trick: 'I am about to send you the entry at index 3; before you accept it, please confirm the entry you already have at index 2 was created in term 1.' The follower runs the **prevLogIndex / prevLogTerm consistency check**: it looks up its own entry at `prevLogIndex` and accepts only if its term matches `prevLogTerm`; otherwise it rejects. In this show, both followers already have term-1 at index 2, so both accept. The leader keeps two pieces of per-follower bookkeeping it updates whenever an AppendEntries succeeds: **matchIndex** (the highest log index it knows is safely on that follower) bumps to 3, and **nextIndex** (the next index the leader plans to send to that follower) bumps to 4.

Implementation

Leader.replicate

per-tick, per-follower replication loop

1# Leader-side: per follower, sustain replication.
2on tick (leader) for each follower p:
3    prevIdx  = nextIndex[p] - 1
4    prevTerm = log[prevIdx].term  # 0 if prevIdx == 0
5    entries  = log[nextIndex[p] .. log.lastIndex]
6    send AppendEntries {
7        term:         currentTerm,
8        leaderId:     self,
9        prevLogIndex: prevIdx,
10        prevLogTerm:  prevTerm,
11        entries:      entries,
12        leaderCommit: commitIndex,
13    } -> p

Follower.onAppendEntries

consistency check + conditional truncate (sec 5.3)

1on receive AppendEntries(req):
2    # (universal step-down already at handler top)
3    if req.term < currentTerm:
4        reply { term: currentTerm, success: false }
5        return
6    reset election_timeout            # we have a leader at currentTerm
7 
8    # Consistency check (sec 5.3): log[prevLogIndex].term == prevLogTerm.
9    if log.length <= req.prevLogIndex
10       OR log[req.prevLogIndex].term != req.prevLogTerm:
11        reply { term: currentTerm, success: false,
12                conflictTerm:       log[req.prevLogIndex]?.term ?? null,
13                conflictFirstIndex: firstIndexOfTerm(...) }
14        return
15 
16    # CONDITIONAL TRUNCATION — naive 'always truncate, then append' is a bug.
17    # AppendEntries can arrive OUT OF ORDER; truncating a committed suffix
18    # we already have is silent corruption.
19    for i, e in entries:
20        idx = req.prevLogIndex + 1 + i
21        if log.length > idx AND log[idx].term != e.term:
22            log = log[0..idx]         # truncate ONLY on conflict
23        if log.length == idx:
24            log.append(e)
25 
26    if req.leaderCommit > commitIndex:
27        commitIndex = min(req.leaderCommit, log.lastIndex)
28    reply { term: currentTerm, success: true }

Leader.onAppendEntriesReply

naive backoff vs. sec 5.3 conflict-term jump

1on receive AppendEntriesReply(reply, from p):
2    if reply.success:
3        matchIndex[p] = req.prevLogIndex + req.entries.length
4        nextIndex[p]  = matchIndex[p] + 1
5    else if reply.conflictTerm != null
6            AND log.containsTerm(reply.conflictTerm):
7        # Jump nextIndex past our last entry of conflictTerm in O(1).
8        nextIndex[p] = lastIndexOfTerm(reply.conflictTerm) + 1
9    else:
10        nextIndex[p] = reply.conflictFirstIndex
11        # or decrement by 1 if the follower has no hint to give

PreviousPre-Vote and CheckQuorum — fixing the disruptive server NextCommit, and the Figure 8 trap