Across Many Machines
Clocks that order messages without a wall clock, copies of a record and the reads they serve, a ring that places keys and shards that split a table, then committing across machines, electing a leader that keeps a log, and the choice a partition forces.
System Design
Before you start
Some lessons here build on lessons from other arcs: The Actor Model, WAL: Crash Recovery, Hash Functions: Avalanche and Integrity, B-Trees: How Indexes Work, Transactions & ACID.
- 1
Logical Clocks: Ordering Without Timein review
Systems · Coordination · ~20 minMachines have no shared clock, so order comes from the messages: a counter that ticks and travels puts every cause before its effect, and a vector tells when neither came first.
- 2
Replication: One Write, Many Copiesin review
Systems · State at Scale · ~25 minA leader ships every write to its followers. What a client is promised depends on how many copies a write waits for and how many a read asks, and a lag or a partition shows the difference.
- 3
Consistent Hashing: Keys on a Ringin review
Systems · State at Scale · ~25 minHash the nodes onto a ring too, walk each key clockwise to the first node point, and a node joining or leaving moves only its neighbours' keys instead of nearly all of them.
- 4
Sharding: One Table, Many Machinesin review
Systems · State at Scale · ~25 minCut one table over many machines by range, hash, or directory; route each request to its shard, watch a hot spot form, and split it at the median key.
- 5
Two-Phase Commit: All or None, Across Machinesin review
Systems · Coordination · ~25 minA coordinator asks every machine to prepare, commits only on a unanimous yes, and logs each step so a crash on either side still ends with every account changed or none.
- 6
Raft: Electing a Leader, Replicating a Login review
Systems · Coordination · ~30 minRandomized timeouts pick a leader by majority vote, the leader replicates a log, a majority commits an entry, and a higher term ends any stale leader: one log on many machines.
- 7
CAP: What a Partition Forces You to Choosein review
Systems · State at Scale · ~25 minTwo sites, one link that drops: a request on the far side can be answered and risk being wrong, or refused and be unavailable, and the theorem says there is no third way.