Module 19 / Algorithms behind big systems

Module 19 · lesson 14 of 22 · Read 9 min

Raft: log replication

How a majority commits an entry.

The last lesson got Raft a leader. That's only half the job. The point of a leader is to put every change into one agreed order, and get that order onto enough machines that losing a few of them loses nothing.

Raft does this with a replicated log. Every change is an entry in a numbered list. The leader decides what goes at each position, copies the list to the followers, and declares an entry committed once a majority have it. Every node then applies committed entries, in order, to its own copy of the data. Same starting state, same entries, same order: same result everywhere.

Back to Tiffin's 5-node etcd cluster. An operations engineer sets the Bengaluru surge multiplier to 1.5 at 8:02pm. Let's follow that one write.

The log

Each log entry has three parts: its index (position in the log), the term in which a leader created it, and the command itself.

Index Term Command
1 1 open city Pune
2 1 surge.blr = 1.2
3 2 flag new-checkout = on
4 2 surge.blr = 1.5

Once the leader that wrote an entry knows a majority of nodes hold it, that entry is committed. A committed entry will never be lost or changed, and every node will eventually apply it at the same index.