Commit, and the Figure 8 trap

An entry is only safe to apply once the CURRENT leader has gotten one of its OWN-term entries onto a majority — counting copies on entries inherited from older leaders looks correct but isn't, because a future leader can still overwrite them; this is the bug Raft's Figure 8 scenario demonstrates and the current-term commit rule prevents.

Previously

Last scene you learned how a leader copies its log onto followers and how the consistency check keeps every follower's prefix matching the leader's. Once an entry is on a majority of servers, the obvious next question is: when is it safe for the application to ACT on that entry — to charge the credit card, print the order, advance the bank balance?

Scene 05

Commit, and the Figure 8 trap

Watch
Try it
Predict
Capture

index-2 sits on S1 and S2 only — a minority →

What to watch for

Here's a sneaky failure that almost made Raft incorrect. Watch what happens when we use a naive 'replicated to a majority = safe' rule. The story plays out across three panels you'll see appear one after another. Panel (a): S1 is the leader for term 2. It writes a new entry at log index 2 and manages to copy it to S2 before anything bad happens. Two servers out of five have the entry. That is a minority — not enough to call the entry safe yet. Panel (b): S1 crashes. S5 wakes up and runs an election for term 3. S3, S4, and S5 all have only the term-1 prefix in their logs, so from each other's point of view they're equally up-to-date — S5 wins with votes from S3, S4, and itself. S5 is now leader. It writes its OWN entry at index 2 (a different one, for term 3) — into its own log. Then S5 crashes too, before telling anyone. Panel (c): S1 comes back to life. It runs an election for term 4 and wins — S1 still has the term-2 entry at index 2, which is more up-to-date than what S3 has, so S1 gets votes from itself, S2, and S3. As leader, S1 continues the work it never finished and copies its term-2 entry out to S3. Now three servers out of five — S1, S2, S3 — hold that index-2 entry. A majority. With a naive rule of 'on a majority = safe,' S1 would now mark this entry committed and tell the application to act on it. In the next phase you'll see why that would be a disaster.

Implementation

Highlighted lines are the ones running in the diagram right now.

Leader.tryAdvanceCommit (naive — BUGGY)

the version that Figure 8 breaks

1def tryAdvanceCommit():
2    # for every index N > commitIndex, count replicas
3    for N in range(commitIndex + 1, log.lastIndex() + 1):
4        replicas = 1  # leader itself
5        for f in followers:
6            if matchIndex[f] >= N:
7                replicas += 1
8        if replicas > len(cluster) / 2:
9            commitIndex = N  # advances on ANY entry

Follower.handleAppendEntries (truncation step)

the mechanism panel (d1) uses to overwrite idx=2

1def handleAppendEntries(req):
2    # … term and consistency checks elided …
3    # step (3): if an existing entry conflicts with a new
4    # one (same index, different term), delete it AND
5    # everything after it, then append the new entries
6    for i, e in enumerate(req.entries):
7        idx = req.prevLogIndex + 1 + i
8        if idx <= log.lastIndex() and log[idx].term != e.term:
9            log.truncateFrom(idx)  # this is how (d1) wipes idx=2
10        if idx > log.lastIndex():
11            log.append(e)

Sources

Where this sits in Build Raft — consensus you can defend

Scene 05 of 12. An entry is committed when stored on a majority AND at least one entry from the leader's CURRENT term is replicated to a majority. The second clause is the one that prevents Figure 8 — without it, a 'committed' entry can be overwritten by a future leader.

Up next. With the commit rule in place, the next scene zooms out: the rule you just learned, plus the election restriction from scene 3, together prove the five named safety properties Raft promises — Election Safety, Leader Append-Only, Log Matching, Leader Completeness, and State Machine Safety.

All 12 scenes in Build Raft — consensus you can defend · Every curriculum

Built with Arqly

Every scene in Build Raft — consensus you can defend builds on the one before it.All 12 Build Raft — consensus you can defend scenes