Agree or Die: Consensus from Scratch
You cannot tell a crashed machine from a slow one — every consensus algorithm ever written is a workaround for that one fact.
The idea
Two of your servers both think they are the leader. Both accept writes. Which one survives? If your instinct is "the newer timestamp wins", you have just discovered you need a clock — and clocks on different machines disagree by more than the milliseconds a leader election takes to decide. Physical time cannot order events across machines.
Lamport clocks fix half of that. Every node keeps a counter, bumps it on each event, and piggybacks it on every message it sends. If A caused B, A's number is smaller. But the reverse does not hold: a smaller number might just mean the two events never knew about each other. You get an order, not the order anyone actually witnessed.
So we can order events. Who decides which order is official? That is agreement, and it is hard for exactly one reason: over a network, a crashed node and a slow node look identical. Raft's answer is to elect one node as dictator for a term and let it sequence every write. Two rules keep that safe — a leader needs votes from a majority, and any two majorities share at least one voter, so a new leader always overlaps the old one; and you cannot win an election if your log is behind.
Put a state machine behind that replicated log and every replica applies the same commands in the same order. That is a linearizable database: no matter how many copies exist, it behaves as if there were only one.
The bench — 4 exercises
Whose Write Wins?
Run two processes that each keep a Lamport clock and log events to a shared SQLite table, with one process's wall clock deliberately skewed. Then work out from the data alone which events are causally ordered and which are merely concurrent.
- Create a SQLite table events(node, lamport_ts, wall_ts, payload) and two small processes that append to it and exchange messages over a socket or a file.
- Implement Lamport rules: increment on every local event, and on receive set counter = max(local, received) + 1.
- Start one process with a fake clock offset of +2 seconds (an env var your code reads when stamping wall_ts).
- Fire interleaved bursts from both processes, then classify every pair of events as ordered or concurrent using only lamport_ts and the message links.
- Write one sentence explaining a specific pair that wall_ts ranks backwards.
hint
Concurrency is not the same as equal timestamps — you need the send/receive edges, so record which message caused which event.
hint
Keep bursts small (10-20 events) so you can check your answers by hand against the message log.
DONE WHEN
· Every causally-linked pair has a strictly increasing Lamport timestamp
· At least one pair is ordered by causality but reversed by wall_ts
· Your classification of ordered vs concurrent pairs matches the recorded message edges
Elect a Dictator
Implement Raft leader election only — no log yet — across three local processes, and prove that no two nodes can ever be leader in the same term.
- Run three processes on localhost speaking a small RPC over TCP or HTTP, each holding currentTerm, votedFor, and a role.
- Implement randomized election timeouts: on timeout become candidate, bump the term, vote for yourself, and send RequestVote to the others.
- Grant a vote only if you have not voted in that term, and step down immediately whenever you see a higher term.
- Add heartbeats from the leader so followers stop timing out, then kill the leader and watch a new one appear.
- Cut the old leader off from the others (drop its traffic) for ten seconds, heal it, and check what it does when it reconnects.
hint
Randomize timeouts over a wide range (say 150-300ms) or all three nodes will keep splitting the vote forever.
hint
Dump each node's (term, role) to a file every 100ms — that log is how you check the safety property afterwards.
DONE WHEN
· Three fresh nodes settle on exactly one leader within five seconds
· Killing the leader produces a new leader within two election timeouts
· Across all state dumps, no term ever has two leaders
Log Replication Under Chaos
Add AppendEntries with the consistency check, majority commit, and follower log repair — then break it on purpose with a seeded scheduler that drops, delays, duplicates and reorders RPCs while restarting nodes mid-append.
- Implement AppendEntries with prevLogIndex/prevLogTerm; a follower rejects if it does not match, and the leader backs up until it does.
- Advance the commit index when an entry from the current term is stored on a majority, then apply committed entries in order.
- Make followers truncate and overwrite any conflicting suffix rather than merging.
- Write a seeded chaos wrapper around your RPC layer that drops, delays, duplicates and reorders messages, and randomly crash-restarts a node.
- Run at least fifty seeds and assert the two safety invariants after each run, printing the seed on failure so you can replay it.
hint
Persist currentTerm, votedFor and the log before replying to any RPC, or crash-restart will lose elections you already promised.
hint
Duplicated and reordered RPCs are the killer: make every handler idempotent and always ignore replies from an older term.
DONE WHEN
· Entries with the same index and term are byte-identical on every node
· No two nodes ever apply different commands at the same log index
· A failing seed replays deterministically and reproduces the same failure
Your KV Store, Replicated
Mount your key-value store from the storage-engine module as the state machine behind the Raft log, so SET/GET/DEL survive leaders dying — a linearizable replicated database.
- Route client SET/DEL to the leader, append them as log entries, and apply them to the KV store only on commit.
- Serve reads through the log too — append a no-op read entry and answer after it commits (slow but honestly linearizable).
- Have clients retry against another node when they hit a follower, and return the current leader hint.
- Run several concurrent clients while you kill and restart the leader twice, recording every operation's invoke and response time.
- Check the recorded history by hand or with a small checker: every read must be explainable by some serial order consistent with the real-time ordering.
hint
Keep the operation window small (a few dozen ops on a handful of keys) or checking linearizability by hand becomes impossible.
hint
Only acknowledge a write after it is committed and applied — acknowledging on append is exactly how you lose data.
DONE WHEN
· Zero acknowledged writes are lost across two leader kills
· No client ever reads a value older than one it previously read
· The recorded history has at least one valid serial order respecting real-time ordering
Go deeper (after the bench)
Read DDIA Chapter 9, "Consistency and Consensus", now rather than before — the linearizability formalism lands very differently once you have watched your own history checker reject a run; skim the clocks section of Chapter 8 alongside Exercise 1. For free follow-up, read the Raft paper, "In Search of an Understandable Consensus Algorithm" by Ongaro and Ousterhout; section 5.4 is precisely the safety argument your chaos runs were testing.