STAGE 3 · THE REPLICATION BELT

The Replication Belt

The leader's only job is to make every other log identical to its own.

What you're wiring up

Clients hand commands to the leader, the leader appends them to its log and ships them out. What keeps logs from quietly diverging is the log matching check: every AppendEntries says these entries go immediately after index i, which had term t. A follower that does not have exactly that entry in exactly that slot refuses the batch.

On refusal the leader steps its guess back one entry and tries again, walking backwards until it finds the last index where the two logs agree, then overwrites everything after it. It is induction carried out on the wire — if two logs agree on one entry, they provably agree on every entry before it.

One thing is deliberately missing: any notion of when an entry is safe. Entries flow and logs converge, but nothing is committed and nothing is applied yet. Keeping replication and commitment as separate ideas is why both of them stay clear.

# leader holds 1..5, guesses the follower holds 1..3
AppendEntries{prevLogIndex: 3, prevLogTerm: 2, entries: [e4, e5]}
follower: my index 3 has term 1, not 2  →  {success: false}

# leader backs off one entry and retries
AppendEntries{prevLogIndex: 2, prevLogTerm: 1, entries: [e3, e4, e5]}
follower: match  →  {success: true}  →  nextIndex 6, matchIndex 5

Assembly steps

[ 01 ]

Add the log — a slice of {Term, Command} — plus the leader's per-peer nextIndex and matchIndex, initialized the moment you win an election.

hint

Use 1-based indexing with a sentinel entry at index 0. It deletes every "is the log empty?" special case from your prevLogIndex handling.

[ 02 ]

Implement Start(command) on the leader: append locally, return (index, term, isLeader) straight away. Followers return isLeader false.

hint

Never block in Start. Replication is asynchronous; the harness submits and then watches the logs converge on their own.

[ 03 ]

Teach the sender side of AppendEntries to carry real entries from nextIndex onward with matching prevLogIndex and prevLogTerm, advancing on success and backing off on refusal.

hint

Piggyback entries on the heartbeat ticker you already have rather than adding a second send path. One code path means far fewer interleavings to reason about.

[ 04 ]

Teach the receiver side: refuse on a prev-entry mismatch, and on a match truncate only genuinely conflicting entries before appending the rest.

hint

Truncate only when an incoming entry conflicts — same index, different term. Blind truncation lets one stale reordered RPC erase entries you already acknowledged.

[ 05 ]

Optional pace work: on refusal have the follower report its conflicting term and that term's first index, so the leader skips back a whole term at a time.

hint

Correctness passes without this. Only the 100-entry catch-up test's time budget cares.

Go deeper (after it passes)

The backtracking loop here is the same shape as any anti-entropy protocol you will meet later. Pair it with DDIA's replication module, and with the key-value store track if you built it — that store is the state machine this log is about to drive.