Part 3 of 6 · 4 min read
How the algorithms work
An elected leader, numbered terms, and two rounds of voting with overlapping majorities.
Think of a committee. The chair proposes a motion, and it counts only if more than half of the members say yes. A new chair is chosen when the old one disappears. Because any two majorities share at least one member, the new chair always finds someone who knows what the old chair got passed.
The best-known fault-tolerant algorithms, per the DDIA book, are Viewstamped Replication, Paxos, Raft and Zab (used in ZooKeeper). They are similar but not the same. The book advises against writing your own, since it is hard and has a poor success record.
Most of them decide a sequence of values rather than one, which makes them total order broadcast algorithms: all nodes receive the same messages, exactly once, in the same order. That equals repeated rounds of consensus, one per message. Multi-Paxos is the name for this form of Paxos.
Total order broadcast
Total order broadcast delivers every message to all nodes exactly once and in the same order everywhere.
Example: three replicas receive "set x = 1", then "set x = 2" in that order. All three end with x = 2.
Why not just single-leader replication? If a human picks the leader, the system is a dictatorship and needs a person to recover. If the system elects its own leader, it needs agreement on who the leader is, and that is consensus again. The way out is the numbered term of module 5. The book calls it an epoch number: within an epoch there is only one leader. If two leaders clash, the higher epoch wins.
Two rounds of voting. The book explains it this way:
- A vote to choose a leader for a new epoch.
- For each decision, the leader sends the proposal and waits for a quorum to vote yes. A node votes yes only if it knows of no leader with a higher epoch.
The quorums of the two votes must overlap. So if a proposal wins, at least one voter also took part in the latest election, and would have revealed a higher epoch if there was one. The leader then knows it is still the leader.
The difference from two-phase commit (module 9): the leader is elected, not fixed; only a majority must say yes, not everyone; and there is a recovery procedure after a new leader is elected.
A Raft view of the log (from the Understanding Distributed Systems book). The leader keeps a log, an ordered list of entries. Each entry has an operation (such as "x = 3"), an index (its position) and the term in which it was created.
- The leader appends the new entry to its own log but does not apply it yet.
- It sends an AppendEntries request to every follower. This message is also sent regularly as a heartbeat.
- Each follower appends the entry and replies.
- When a majority has the entry, the leader treats it as committed, applies it, and tells followers the highest committed index in later messages.
- Followers apply an entry only after they learn it is committed.
With 2f + 1 nodes, the system tolerates f failures. A committed entry is durable and will eventually be run by all processes, not only the original majority.
Keeping committed entries safe. If the leader fails, the new leader must not lack committed entries. So a process refuses to vote for a candidate whose log is less up to date than its own. Comparing the last entries: if the last terms differ, the later term is more up to date; if equal, the longer log is. A winner needs a majority, and any committed entry exists on a majority, so the two majorities overlap and the winner contains every committed entry.
If a follower is down, the leader keeps retrying, which is safe because AppendEntries is idempotent. A follower returning is brought up to date because each message names the index and term of the entry just before the new one, and a follower that lacks it rejects the message until the gap is filled.
A worked example, 5 nodes. The leader L (term 3) has log entries 1 to 5. It sends entry 6 ("x = 9").
| Step | State |
|---|---|
| Leader appends entry 6 | Leader has 6 entries, committed index still 5 |
| Followers F1, F2 reply yes | 3 of 5 have entry 6 (L, F1, F2). Majority reached |
| Leader commits entry 6, applies x = 9 | Client gets "ok" |
| F3 and F4 are slow | Still have 5 entries. Will catch up on the next AppendEntries |
| L crashes | F3 (5 entries, term 3) asks F1 (6 entries, term 3) for a vote. F1 refuses: its log is longer, so more up to date |
| F1 asks F2 for a vote | F2 has the same log. Vote granted. F1 collects votes from F2, F3, F4 and itself and wins term 4 with entry 6 intact |
Check yourself:
- Why must the vote on a proposal use a quorum that overlaps with the election quorum?
- Why may a follower refuse to vote for a candidate?