Distributed systems
Part 4 of 5 · Raft consensusLog Replication & Commit Index — Matching, Conflict Resolution & Safety
AppendEntries + prevLog match; nextIndex backoff; truncate divergent suffixes; commitIndex on majority current-term matchIndex (Figure 8); safety sketch.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
How replicas agree on a log
Prefer
Raft leader push + matching + Figure 8 commit
Leader appends. Followers reject mismatches. nextIndex backs up. commitIndex only moves on a current-term majority.
- Total order is the leader's log.
- Conflict = truncate uncommitted suffix, then append.
- Snapshots compact applied prefix for slow followers.
- Safety is a handful of named invariants, not vibes.
Alternative
Primary-backup, gossip, or slot-by-slot Paxos
Same RSM goal, different conflict stories. Gossip/CRDTs are not this product.
- Primary-backup without terms has a sloppy uncommitted-suffix rule.
- Multi-Paxos chooses per slot with ballots — see the comparison page.
- CRDT merge is AP data, not SM consensus.
- Apply out of order destroys determinism.
Overview
Raft keeps a single replicated log as the source of truth for the state machine. The leader pushes entries with AppendEntries, followers reject mismatches, and the leader backs up nextIndex until logs align. commitIndex advances only with majority replication (plus the current-term commit rule).
This lesson covers the matching property, conflict resolution, commit vs apply, and a concise safety proof sketch interviewers expect.
Replication styles
| Style | Ordering | Conflict handling | Typical use |
|---|---|---|---|
| Raft leader push | Total order via leader log | Truncate divergent suffix on followers | etcd, Consul |
| Multi-Paxos | Chosen values per slot | Ballot / promise rules | Custom systems |
| Primary-backup chain | Primary seq | Failover + catch-up | Some databases |
| Gossip / CRDT | Concurrent merges | Application merge | AP data, not SM consensus |
What fails if you choose wrong
- Truncate a committed prefix on a follower → irreversible state divergence.
- Advance
commitIndexfor a prior-term entry without a current-term commit (Figure 8) → a "committed" entry can be lost after leadership change. - Apply out of order → state machine no longer deterministic.
Log matching property
If two logs have an entry with the same index and term, they are identical in all preceding entries. Maintained by:
- Leader never changes its own log index contents once written (only appends).
AppendEntriesconsistency check: follower must haveprevLogIndex/prevLogTermmatch.
Sequence
- 1
Leader
Step 1 leader sends AppendEntries
- 2
Leader → Follower
prevLogIndex prevLogTerm entries
- 3
Follower → Leader
success append entries
- 4
Follower → Leader
reject
- 5
Leader
Step 4 decrement nextIndex retry
Lesson map
Log Replication & Commit Index — Matching, Conflict Resolution & Safety
AppendEntries + prevLog match; nextIndex backoff; truncate divergent suffixes; commitIndex on majority current-term matchIndex (Figure 8); safety sketch.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB l["Leader append"] f["Follower persist"] l -->|prevLogIndex| f f -->|success append| l f -->|reject| l
nextIndex vs matchIndex: nextIndex is the speculative send pointer; matchIndex is the highest confirmed identical index.
Conflict resolution
When a follower's log diverges (uncommitted entries from an old leader):
- Leader finds the first conflicting index (optimizations: term-based backup in the paper §5.3).
- Follower deletes the conflict and all following entries.
- Leader sends its entries from that point.
Never delete entries at or before a known commit on a node that participated correctly — safety relies on not committing until majority durable.
commitIndex rules
- Leader tracks which indices are stored on each follower (
matchIndex). commitIndex= highest N such that a majority hasmatchIndex ≥ Nandlog[N].term == currentTerm(simplified statement of the restriction).- Followers learn
commitIndexfrom leaders (including heartbeats) and apply entries withlastApplied < commitIndex.
Architecture
Step 1 — Replicate
- 1
Client write
- nextLeader append
- 2
Leader append
- nextFollower persist
- nextFollower persist
- 3
Follower persist
- 4
Follower persist
Step 2 — Majority
- 5
matchIndex quorum
- nextReplicas at index N
- 6
Replicas at index N
- nextEntry term is currentTerm
Step 3 — Commit
- 7
Entry term is currentTerm
- nextcommitIndex advances
- 8
commitIndex advances
- nextState machine
Step 4 — Apply
- 9
State machine
- nextApply in index order
- 10
Apply in index order
Safety proof sketch (interview form)
Goal: If a log entry is committed, any future leader's log contains that entry at that index (State Machine Safety).
- Election Safety: ≤1 leader per term.
- Leader Append-Only: leaders only append; never overwrite their own indices.
- Log Matching: same index+term ⇒ identical prefixes.
- Leader Completeness: if an entry committed in term T, leaders of terms > T have that entry — because a majority stored it, and winning an election requires votes from a majority whose up-to-date check forces the winner's log to include all committed entries.
- Figure 8 guard: do not mark prior-term entries committed until an entry from the current term is committed via majority — closes the classic hole where an uncommitted majority copy could still be overwritten.
Sandbox: conflict truncate (Python)
Follower has a divergent term-2 suffix. Leader sends a term-3 entry after a matching prefix.
Press Run. Snippets must be self-contained — no network, files, or native modules.
commitIndex from matchIndex (TypeScript)
Majority commit for current-term entries only.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Interview Q&A
What does the AppendEntries consistency check prevent?
Answer
Holes and mismatched histories — the follower refuses if prev index/term do not match. The leader then decrements nextIndex and retries.
Who truncates the log?
Answer
Followers truncate divergent suffixes when accepting a leader's conflicting entries. Committed prefixes must not disappear from the cluster.
Why is commit ≠ majority alone for old-term entries?
Answer
Figure 8: an entry replicated to a majority in an old term might still be overwritten unless a current-term entry commits. This is the paper's most famous trap.
matchIndex vs nextIndex?
Answer
nextIndex is the speculative send pointer. matchIndex is the highest confirmed identical index. Commit uses matchIndex, not nextIndex.
Can followers reorder applies?
Answer
No — apply in index order up to commitIndex for deterministic state machines.
What if the leader crashes before responding to the client?
Answer
The client may retry; a committed command will still apply once. Need idempotent client requests / session ids — see at-least-once vs exactly-once and outbox/inbox.
What are snapshots for?
Answer
Compact the prefix of the applied log. InstallSnapshot RPC brings slow followers forward so the log does not grow without bound.
How does this differ from primary-backup without terms?
Answer
Terms + voting completeness give a precise rule for which uncommitted suffixes die. Without terms, failover often hand-waves that rule.
Pitfalls
Leader log: indices 1..5 terms 1,1,1,4,4. Follower: 1,1,2,2. Draw nextIndex backoff until prevLog matches, then the truncated follower log. Mark which indices could be committed in term 4.