Raft log replication

Once a leader is elected, clients send it commands. The leader writes each command into its log, sends it to the followers, and waits for a majority. Only then is the entry committed, and only then is it applied and acknowledged. The leader's log is the source of truth. Followers are made to match it.

The big idea

Think of a shared ledger. A line only counts once most copies of the ledger have it. If the leader crashes, every line that counted is still in the ledger that the next leader holds.

The analogy hides one subtle rule. A leader may not count old-term entries toward a majority on its own. Those commit only indirectly, through a new entry from the current term.

Walking through it

Five nodes. The leader has entry 7 and sends it to everyone. S2 and S3 acknowledge. S4 is slow and S5 is down.

S1 (leader):  log 1..7
S2:           log 1..7   ack
S3:           log 1..7   ack
S4:           log 1..6   slow
S5:           down
S1 + S2 + S3 = 3 of 5, entry 7 is committed

The leader does not wait for S4 or S5. A majority is enough.

The commit index is the highest index that a majority has stored. The leader tracks matchIndex for each node, then picks the value at the majority position:

package main

import (
	"fmt"
	"sort"
)

// commitIndex returns the highest log index stored on a majority.
func commitIndex(matchIndex []int) int {
	sorted := append([]int(nil), matchIndex...)
	sort.Sort(sort.Reverse(sort.IntSlice(sorted)))
	return sorted[len(matchIndex)/2] // 5 nodes: the third-highest value
}

func main() {
	fmt.Println(commitIndex([]int{7, 7, 7, 6, 3}))
	fmt.Println(commitIndex([]int{7, 7, 6, 4, 2}))
}

Output:

7
6

Followers that fall behind are repaired by the leader. Each AppendEntries message carries prevLogIndex and prevLogTerm. A follower rejects the message unless its log matches at that point. The leader then steps back one entry and retries, until the logs match. After that, the follower's extra entries are overwritten.

Common mistakes

• Treating "sent" as "committed". Only entries stored on a majority are committed.
• Writing to a follower directly. Only the leader decides. Followers are repaired from the leader.
• Retrying a command without an idempotency key. A client whose write timed out does not know if it committed. Retries must be idempotent.

Check yourself

1. With matchIndex [7, 7, 6, 4, 2] on five nodes, what is the commit index? 6. Three nodes have stored at least index 6, which is a majority.
2. Why does a new leader append a no-op entry in its own term? Entries from earlier terms commit only when a current-term entry after them commits. The no-op lets older entries commit quickly.

Key takeaways

• An entry commits when a majority of nodes store it.
• The commit index is the median-style value of the nodes' match indexes.
• The consistency check makes followers copy the leader's log, overwriting stale entries.
• Committed entries survive leader changes because a new leader must already hold them to win a vote.

Further learning

Next, see what consensus costs in time and throughput in what consensus costs.

Martin Kleppmann's lecture walks through Raft as pseudocode, line by line.