Log Replication

Once elected, a leader services client requests: it appends each command to its own log, then replicates the entry to the followers with AppendEntries RPCs — the same RPC that, sent with no entries, doubles as the heartbeat.

The key invariant is the Log Matching Property (§5.3):

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.

Raft maintains it with a consistency check: every AppendEntries request carries prevLogIndex and prevLogTerm, the coordinates of the entry immediately preceding the new ones. The follower accepts the entries only if its own log contains an entry at prevLogIndex with term prevLogTerm. If the check fails, the leader retries with a smaller prevLogIndex until the logs agree on a prefix — an induction step that repairs any divergence.

Figure 2, receiver implementation

You will implement these five steps literally:

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). prevLogIndex = 0 — the empty prefix — always matches.
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).

Steps 3 and 4 are where most buggy implementations die. Note what they do not say: they do not say "truncate the log to end at the last new entry". RPCs can be duplicated and can arrive containing entries the follower already has. If every incoming entry matches what is already in the log, the follower must change nothing — in particular it must not chop off entries after the matched prefix, because those entries may already be committed. Truncation happens only at an actual conflict: same index, different term.

Step 5's min also deserves a close read. "Index of last new entry" means prevLogIndex + len(entries) — the last index this particular RPC vouches for. A heartbeat that matched a prefix of your log at prevLogIndex = 2 only proves entries up to index 2 match the leader's log, so even if leaderCommit is 5 you may only advance commitIndex to 2 for now.

Finally, the term rules from lesson 1 still apply: a request with a higher term updates currentTerm (resetting VotedFor), and any valid AppendEntries — same term or higher — makes the receiver a follower. That is how a candidate that lost the race, or a deposed leader, gets back in line.