Raft from scratch, part 2: log replication, commit & safety under partition

Last week’s cluster could agree on who’s in charge. This week I gave it something worth being in
charge of: a replicated log. This is where an election turns into a database — the leader takes
commands, copies them to a majority, and every peer ends up with a byte-identical log, even across
crashes and partitions.

What I built

A leader that accepts client commands, replicates them to followers, and commits them once a majority
have a copy — with the follower-side consistency check that keeps a partitioned-and-rejoined peer’s
stale log from silently corrupting anyone else’s.

client ──Start(cmd)──► Leader (term T)
                          │ append {T, cmd} to own log at index N
                          ▼
              AppendEntries(prevIdx, prevTerm, [cmd], leaderCommit) ──► each follower
                          │
              follower: does my log agree with leader at prevIdx?
                 yes ──► append/overwrite, ack success
                 no  ──► reject; leader backs up and retries with an earlier prefix
                          │
              majority ack'd index N  ──►  commitIndex = N  ──►  applyCh (every peer, same order)

The concepts that made it work

• Commit means “a majority have it,” not “everyone has it.” The leader tracks a matchIndex per
  follower — a proven high-water mark — and advances commitIndex the moment a majority’s matchIndex
  reaches some index. Slow or disconnected followers just catch up later; they never block progress.
• The Log Matching Property turns “probably fine” into “provably fine.” Every AppendEntries call
  makes the follower check its entry at PrevLogIndex against PrevLogTerm before accepting anything
  new. Reject on mismatch. This one check is enough to guarantee that if two logs ever agree at one
  index, they agree on everything before it — so a leader can safely reason about a follower’s log
  from a single point of comparison instead of diffing the whole thing.
• nextIndex is a guess; matchIndex is a proof. The leader optimistically assumes a follower is
  caught up and corrects downward one entry at a time on rejection, but only trusts matchIndex upward
  once a follower actually confirms it. Keeping those two concepts separate is what makes the retry
  logic simple instead of tangled.
• The current-term commit rule is the subtle one. You can’t commit an old-term entry just because a
  majority happen to hold it — it could still be silently overwritten by a future leader before anything
  from this term commits on top of it. Only count majority-replication toward commit for entries from
  your own current term. Skip this guard and every easy test still passes; it only bites you under a
  specific multi-crash sequence, which is exactly why it’s the thing every Raft explainer calls out.

The thing that bit me

I got the append logic right on the first pass — new entries appended, conflicting entries truncated —
except I truncated on every overlapping entry, including ones that already matched. That’s fine until
a delayed, duplicate AppendEntries shows up (normal under any lossy network): it carries an old prefix
of entries the follower already has, and a truncate-then-append that doesn’t check “is this identical
already?” first chops off everything after it — including entries that were already committed and
applied. The fix is a one-line guard (else if term differs: truncate; if it matches, touch nothing),
but the reason it matters took a while to click: in Raft, “already have this” and “conflicting” are
different outcomes of the same comparison, and treating them the same silently deletes data.

Tradeoffs & the road not taken

• No persistence yet. currentTerm, votedFor, and the whole log live in memory. A crash right now
  doesn’t just risk a double vote (last week’s gap) — it can lose committed entries outright. That’s the
  very next thing to fix, and Week 1’s storage engine was built exactly for this job.
• nextIndex backs off one entry at a time. Correct, but slow to recover a follower that’s fallen
  far behind after a long partition — a real implementation has the follower report back a conflicting
  term so the leader can skip back a whole term per round trip instead of one entry. I left this as a
  stretch goal rather than building it up front; getting the safety rules right mattered more than
  making recovery fast.

Where this sits in the system

Last week: an election with nothing at stake. This week: a leader whose commands survive a majority of
crashes and a leadership change, in a provably consistent order. Next: persistence — so a restarted
peer doesn’t forget its term, its vote, or its log — and then putting a key-value store on top of this
log, turning “everyone agrees on the order of commands” into “clients see a consistent, fault-tolerant
database.”

Part of a series building a distributed database from scratch.