TT Lab
Get started
Learn Learning paths Courses

There Were Two Leaders

It is committed only when a majority has it

Continue in TT Lab

Goal

You write as rules how a value the leader received spreads to the three nodes and at what moment it becomes "final." When you finish, you will have experienced by hand log matching, overwriting, the commit condition, and how a lagging node catches up.

Why it matters

Replication is not "sending a value to several places." It is about distinguishing what was sent from what was finalized. The fact that the leader received a value and wrote it to its own log guarantees nothing: if that leader dies the next moment, the value can become as if it never happened. Only when a majority holds the same entry at the same position does "no future leader can change this position" hold, and only then can you tell the client it succeeded.

The commit condition comes with one more caveat that people almost always forget: the leader raises the commit index only when an entry from its own term has reached a majority. If it commits because an entry from an earlier term reached a majority, another leader elected afterward can overwrite the same position, and a value that was already declared final can disappear.

Steps

  1. Put node.py and rules-for-replication.py in place, elect a leader, and write it to /root/raft/leader.json.
  2. In raftrules.py, add up_to_date and make on_request_vote check that condition too.
  3. In /root/raft/raftlog.py, write append_entry(log, term, value).
  4. Add log_ok(log, prev_index, prev_term) to the same file.
  5. Add apply_entries(log, prev_index, entries) to the same file.
  6. Add commit_index(counts, total, log, term) to the same file.
  7. Write three values, watch all three nodes commit, and record it in /root/raft/replicated.json.
  8. Kill and revive one follower, watch it catch up, and record it in /root/raft/catchup.json.

Notes

Set up the result of the previous lab again

Place /opt/lab/raft/node.py and /opt/lab/raft/rules-for-replication.py as /root/raft/node.py and /root/raft/raftrules.py, start three nodes, and write the elected leader to /root/raft/leader.json.

Each lab starts in a fresh Pod, so nothing you built in the previous lab remains. The election rules are provided as the answer from the previous lab. In leader.json, write the two keys leader and term.

Do not vote for a lagging candidate

In raftrules.py, add up_to_date(log, last_index, last_term), and change on_request_vote so that it also checks that condition before granting a vote.

Once a log exists, the election gets one more condition: you grant a vote only if the candidate's log is at least as up to date as yours. The comparison does not start with length. Look at the term of the last entry first, and only when those are equal decide by length. Without this condition, a lagging node could become leader and overwrite entries that are already committed.

A client value is appended to the log

In /root/raft/raftlog.py, write append_entry(log, term, value). Return a new list with an entry holding term and value appended at the end.

An entry carries not only the value but also the term at that time. That term later becomes the only basis for comparing two logs. Do not modify the list you were handed in place; build and return a new list, because the wiring keeps the original separately.

Log matching

In raftlog.py, add log_ok(log, prev_index, prev_term). It decides whether the term at position prev_index equals prev_term.

Raft does not compare the whole log. If a single position matches, it treats everything before it as identical; this property is called Log Matching. prev_index is a position number counted from 1, and 0 means "there is no preceding position." If your log is shorter than prev_index, there is nothing to compare in the first place.

Cut off from the position where entries diverge

In raftlog.py, add apply_entries(log, prev_index, entries). When it meets a position that diverges, it cuts off from that position and returns the list with the new entries appended.

The key is "when not to cut." If it is only the same entry of the same term arriving again, you must not touch what follows. If you cut every time in an environment with frequent retransmission, the follower's log keeps getting shorter and longer. The same goes for a heartbeat that has no entries at all.

The commit condition

In raftlog.py, add commit_index(counts, total, log, term). counts is the number of entries each server holds; return the highest number that a majority holds and whose position is an entry of the current term.

"Commit if a majority replicated it" alone is not enough. If you commit because an entry from an earlier term reached a majority, a leader elected afterward can overwrite that position with a different entry. That is the incident in Figure 8 of the paper. So the leader raises the commit index only when an entry of its own term reaches a majority, and the earlier ones come along with it at that point.

Write values to the three nodes

Start three nodes, write three values to the leader, confirm that commit is 3 on all three nodes, and then write values, commit, and log_len in /root/raft/replicated.json.

Write values only to the leader: curl -s -XPOST -d '{"value":"x"}' 127.0.0.1:5001/client. If you send to a follower, it rejects and tells you who the leader is. Right after writing, it is normal for commit not to have risen yet; it is reflected only after the followers' responses come back and the next heartbeat goes out.

The revived node catches up

Kill and revive one follower, confirm that it catches up three positions from an empty log, and write node, log_len, and commit in /root/raft/catchup.json.

This toy implementation does not persist the log to disk. So the revived node comes back knowing nothing, and the leader steps the position number it sends back one at a time to find the matching point and fills in from there. To kill one, specify the number too, as in pkill -f 'node.py --id 2 '. After reviving it, watch log_len go up.