Raft 02: Log Replication

The Data Systems map of what a group can still promise. This stage builds the promise that a command, once acknowledged, stays acknowledged. Part of the Raft series, Build Your Own Raft.

Before you start. This series builds a small copy of Raft, the algorithm a group of machines uses to keep one shared list of commands. Raft 01: Leader Election built the first job, picking a single leader and replacing it when it goes quiet. This stage builds the second job: the leader copies its list of commands to the others, and the group decides when a command is safe. You need the terms and votes from that lesson.

The idea in 30 seconds

Each log entry has an index and the term it was written in. Raft’s log agreement invariant: same index and same term means the logs are identical up to that index.
A leader sends new entries with the index and term of the entry before them, and a follower accepts only if its own log has that same entry there.
If a follower disagrees, the leader steps back one entry and retries. If the follower holds conflicting entries that were never committed, it cuts them off and takes the leader’s.
An entry is committed when a majority holds it, but a leader may only count entries from its own term. Older entries commit by riding along.
A node refuses to vote for a candidate whose log is behind its own, so an elected leader already holds every committed entry.

Read the story · Skip to the numbers