knaxuslearn · build · ship

Roadmaps / Distributed Systems / Phase 2

Phase 2 of 4 · Study weeks 5-8

Replication and consensus

This phase makes the second checkpoint possible: a replicated log that elects a leader and never loses an acknowledged write. It is four weeks because consensus is hard to get right.

Topics every week

  1. Week 58 h
    • Replication styles: leader-based, multi-leader and leaderless
    • Quorums
    • The Raft paper: terms, roles and the log

    Hand inA one-page summary of the safety rules in your own words

  2. Week 68 h
    • Leader election
    • Randomised timeouts
    • Voting rules and the up-to-date check
    • Split votes

    Hand inLeader election working in the workbench, with the election table started

  3. Week 78 h
    • Log replication
    • The commit rule
    • Log matching and repair after a crash
    • Client requests and duplicates

    Hand inA replicated log and the seeded early-acknowledge bug caught by the checker

  4. Week 88 h
    • Linearizability and how a checker tests it
    • Partitions and the minority side
    • Reads in a consensus system
    • Predicted against measured

    Hand inCheckpoint 2: the election table, the checker report and the failing history

Practice projects

  • Practice 1, the safety rules (Week 5): write the five Raft safety properties and, for each, the rule that gives it. Done when: a peer or mentor agrees each property maps to a rule, or you cite where it does not.
  • Practice 2, the election table (Week 6): kill the leader 20 times with three timeout ranges. Done when: a table shows time to new leader and split votes for each range.
  • Practice 3, the early acknowledge (Week 7): acknowledge a write before a majority stores it. Done when: the checker finds a lost write under a partition and saves the failing history, and the fix passes.
  • Optional, the library version: replace your log layer with a consensus library. Done when: the same checker run passes and a table compares lines of code and election time.

GitHub repos to study

Existence and last commit were checked on 22 Nov 2026 by shallow clone. Every repository below had a commit in the last 12 months.

RepoWhat to readWeek
etcd-io/raftThe library's state machine and its tests6
hashicorp/raftA second implementation, to compare the API and the design6
apache/ratisA Java Raft library you can embed7
pingcap/talent-planThe TinyKV course: a Raft-based key-value store, step by step7

Milestone checkpoint

Build Checkpoint 2. Write the 20-kill script and the checker run first. Build or integrate election and replication, run the kills with three timeout ranges and the 10-minute partition run. Seed the early acknowledge and keep the failing history. Hand in the election table, the checker reports, ADR-3 (the timeout range and its reasons) and ADR-4 (the commit and acknowledgement rule).

Check yourself

Answer each question in your head first, then open it to check.

  1. Why does a Raft leader need a majority to commit a write?
    Any two majorities overlap in at least one node, so a later leader must have seen every committed entry.
  2. What stops two leaders in the same term?
    Each node votes once per term, and a candidate needs a majority of votes, so two candidates cannot both win the same term.
  3. What happens to a minority side during a partition?
    It cannot commit writes because it has no majority, so it refuses them. A leader there may keep serving reads unless reads also check with a majority.
  4. What is linearizability, in one sentence, and why is it hard to test?
    Every operation appears to take effect at one instant between its call and its reply, in an order all clients agree on. A checker must search the possible orderings of a concurrent history, which grows quickly.
  5. Why can a deposed leader still serve a stale read?
    It does not yet know a newer term exists, so it believes it is leader. Reads must go through the log, or use a lease with a bound on clock skew.