A second machine takes away three things you never knew you had
Across a network, messages take time, clocks disagree, and partial failure looks exactly like slowness.
A program on one machine has three quiet guarantees. Put a network in the middle and all three go at once. Messages take time. A call inside one machine takes nanoseconds. A round trip in the same rack is a tenth of a millisecond; to another region, up to a hundred and fifty. Clocks disagree. Even well synchronised machines are a few milliseconds apart, so a timestamp cannot tell you which of two events came first. And failure becomes partial. Machine A sends a request and hears nothing. Has B crashed? Is the network slow? Is a router somewhere dropping packets? From A’s side, these are identical. All it can do is wait, and guess.
What a second machine takes away · Going deeper · 1 of 2
From one machine to many
One machine has one clock, one memory and one failure mode. Two machines introduce time and partial failure; many machines make those the dominant problems. The hard part is that they overlap: a stale read might be an old value, a clock that ran backwards, a reordered message or a partition.
What a second machine takes away · Going deeper · 2 of 2
A partition: both sides keep going
When the link between two groups fails, each side believes the other is dead and keeps serving. When the partition heals, the two histories must be reconciled, and any write accepted on the losing side may be silently dropped.
Compounding failures and retries
Small failure rates multiply along a chain, and retries multiply them again
A remote call can be slow, fail halfway or arrive twice. Careless retries turn one slow service into an outage.
Most outages begin with code that treats a remote call like a local one. Take a request that passes through four services, each of them ninety nine percent reliable. Multiply those together and only ninety six percent of requests get through. One in twenty five fails, though every team can say their service is fine. Now one service slows down, and everyone above it does the obvious thing: try again. You retry three times. The service you called retries each of those three times, and so does the next. The struggling service now receives twenty seven times its normal traffic. The fix has three parts: wait longer after each failure, add randomness so the retries do not arrive together, and make a repeated request harmless.
Compounding failures and retries · Going deeper
The eight fallacies
Written down by Peter Deutsch in 1994, with an eighth added by James Gosling. Each is a real trade-off pretended away. “Topology doesn’t change” fails when an autoscaler replaces a machine and a cached DNS entry still points at the old address.
Logical clocks
Without a shared clock, order events by who could have known what
A vector clock counts events per machine, which reveals when two writes were truly concurrent.
Machines need to know which event came first, and their clocks cannot be trusted to say. So they count instead. Each machine keeps one counter per machine, written here as three slots. A writes x equals one, and bumps its own slot. A tells B. B takes the larger number in each slot, then bumps its own. Meanwhile C, having heard nothing from anyone, writes x equals ninety nine. Later B’s message reaches C, and C’s clock now covers everything. Compare the two writes. A’s is ahead in the first slot, C’s is ahead in the third. Neither contains the other. That is the signature of two writes made without knowledge of each other, and the system now has to resolve them.
Logical clocks · Going deeper · 1 of 3
Lamport clocks: one counter
The simplest logical clock is a single integer: bump it on every event, attach it to every message, and on receipt set it to the larger of yours and theirs, plus one. If A caused B then A’s stamp is smaller. It cannot tell concurrent events apart, which is what vectors add.
Logical clocks · Going deeper · 2 of 3
Vector clocks in detail
One vector happens-before another when every slot is less than or equal and at least one is strictly less. Otherwise they are concurrent. The cost is one counter per writer on every event. Hybrid logical clocks, used by CockroachDB and MongoDB, combine wall-clock time with a logical counter.
Logical clocks · Going deeper · 3 of 3
Spanner: buying better clocks
Google puts GPS receivers and atomic clocks in every data centre. Its clock API returns an interval, earliest to latest, instead of a point. A transaction commits at the latest time, then waits until that moment has certainly passed everywhere: a few milliseconds of delay in exchange for a true global order.
Check yourself
Two versions of a record carry these vector clocks. How are they related?
The left is ahead in the first slot and the right in the second, so neither contains the other. The system must merge them or pick one.
Consistency models
Consistency is a ladder, and every rung down buys speed or uptime
A consistency model is the contract for what a read may see. Stronger is easier to program; weaker is faster and survives failures.
When data lives on several machines, what is the current value stops being a simple question. The answer is a contract, and there is a ladder of them. At the top, linearizable: every read sees the latest finished write, whichever machine you ask. It behaves like one machine, and it is the most expensive to provide. Sequential: everyone agrees on a single order, though not one tied to real time. Causal: only cause and effect are kept in order. Your comment never appears before the post it replies to. Read your writes: you always see your own changes, even if other people do not yet. And at the bottom, eventual: if writes stop, the copies will end up the same. Nothing is promised about when, or about what you see meanwhile.
Consistency models · Going deeper
The hierarchy of models
Amazon S3 launched with eventual consistency for overwrites and deletes: for years, a fresh upload followed at once by a read could legitimately return “not found”. Strong read-after-write for all operations arrived only in December 2020.
CAP and partitions
When the network splits, choose: a correct answer, or an answer
The CAP theorem: during a partition a system keeps consistency or availability, never both.
Here is the choice every replicated system has to make. A write of x equals two has reached the first replica. Then the link between the replicas is cut, and a reader asks the second replica for x. It still holds the old value, and it cannot find out whether anything changed. It can refuse to answer. That keeps every answer correct, but this side of the system is down until the link heals. Or it can answer with what it has. That keeps the system up, but the answer may be stale, and when the link returns the two sides must be merged. There is no third option. And partitions do happen, so the only real decision is which of these to give up.
CAP and partitions · Going deeper
CAP, and PACELC for the rest of the time
CAP only describes a partition. PACELC adds the steady state: if Partitioned, choose Availability or Consistency; Else choose Latency or Consistency. Spanner is consistent in both cases and pays commit-wait latency. Cassandra favours availability and low latency, with consistency as a per-query knob.
Leader election
A leader is whoever a majority voted for, and a majority cannot be split
Consensus starts with electing one leader per term. Majorities overlap, so there can never be two.
To agree on anything, a group of machines first agrees on who is in charge. This is how Raft does it. In term five, A is the leader, and proves it is alive by sending a heartbeat every fifty milliseconds. Then A crashes. The heartbeats stop. B and C each have a timer set to a random length. B’s runs out first, after a hundred and eighty milliseconds of silence. B declares a new term, six, votes for itself, and asks C for its vote. C has not voted in term six, so it says yes. Two votes out of three is a majority. B is the leader of term six and starts sending heartbeats. Later A comes back, still believing it leads term five. The first reply it gets mentions term six. A higher term always wins, so A steps down.
Leader election · Going deeper
Follower, candidate, leader
A machine votes for at most one candidate per term, and only for one whose log is at least as up to date as its own. No deterministic algorithm can guarantee consensus on a fully asynchronous network with even one faulty machine (the FLP result), so every practical algorithm adds something: here, timeouts and randomness.
Consensus and commit
A write is real once a majority has stored it
The leader appends to a replicated log and commits each entry when a majority holds it. So 3 machines survive 1 failure and 5 survive 2.
Once there is a leader, agreement is a matter of copying a list. Every write goes to the leader, which appends it to its log, here y equals seven as entry four, and sends it to the followers. One follower stores it and confirms. Now two machines out of three hold the entry. That is a majority, so the entry is committed. Only at this point is the client told the write succeeded. The third machine is slow, and will catch up later. How many machines should there be? Three need two to agree, and survive one failure. Five need three, and survive two. Notice four and six: each needs a bigger majority than the odd number below it, and survives no more failures.
Consensus and commit · Going deeper · 1 of 3
Log replication in Raft
Only committed entries are applied. Followers learn the commit point from the leader’s next message. Raft is behind etcd, Consul, CockroachDB and TiKV; ZooKeeper and Spanner use relatives of Paxos. Different names, same shape: replicate a log, commit on majority, elect a leader when the current one goes silent.
Consensus and commit · Going deeper · 2 of 3
All or nothing across services: two-phase commit
A coordinator asks every participant to prepare, then tells them all to commit. If the coordinator dies in between, participants are stuck holding locks: they cannot abort and cannot commit. Production systems fix this by storing the coordinator’s decision with consensus.
Consensus and commit · Going deeper · 3 of 3
Sagas: undo instead of lock
A saga splits a long transaction into local steps, each with a compensating action. Intermediate states are visible: the customer is charged before the confirmation is sent. And compensations are not true inverses: a refund is not an un-charge.
Check yourself
A five-machine Raft cluster is cut into a group of 3 and a group of 2. What happens?
A write needs 3 of 5. The group of 3 can still reach that, electing a new leader if it must; the group of 2 never can, so it stops.
Replication
Three ways to keep copies, depending on who may accept a write
Replication keeps copies on several machines: one leader, a leader per region, or no leader at all.
One machine is one point of failure, so real systems keep copies. The layouts differ in who is allowed to take a write. One leader. Every write goes to it, and it streams the changes to followers. One place decides the order, which keeps things simple. But followers run a little behind, tens of milliseconds, sometimes seconds. A leader in every region. People write to the one nearest them, which is fast everywhere. But two leaders can accept conflicting changes to the same thing, and something has to merge them. No leader. A write is sent to every copy and counts once enough of them confirm. There is nothing to fail over, but the copies routinely disagree until they are repaired.
Replication · Going deeper · 1 of 4
The three topologies
With a single leader, synchronous replication waits for a follower before replying: one extra round trip, and no confirmed write is lost on failover. Asynchronous replication does not wait: faster, but the last few milliseconds of writes can vanish if the leader dies.
Replication · Going deeper · 2 of 4
Resolving conflicts: discard or merge
Last-write-wins keeps the newest timestamp and drops the other write; Cassandra and DynamoDB default to it. A CRDT is a data type whose merge gives the same result in any order: a counter with one slot per replica merges by taking the larger value in each slot, so concurrent increments both survive.
Replication · Going deeper · 3 of 4
Who is in the cluster: gossip
Each machine regularly picks a few random peers and swaps what it knows. Every round roughly doubles the number that know a fact, so news reaches everyone in about log N rounds; a 100-machine Cassandra cluster converges in seconds. The same channel carries failure suspicion.
Replication · Going deeper · 4 of 4
Across regions
Active-passive keeps a standby region and loses the most recent writes on failover. Active-active lets every region write, and every concurrent cross-region write is a conflict. Spanner and CockroachDB pay with consensus on every write; Cassandra pays with last-write-wins. There is no free, correct active-active.
Quorums
Overlapping groups: a read cannot miss the latest write
A quorum: write to W copies, read from R. When W + R exceeds the number of copies, every read sees the latest write.
With no leader, how can a reader be sure of seeing the latest write? By arithmetic. There are three copies. A write of x equals seven is sent to all of them and waits for two confirmations. Copy three is slow and still holds the old value. Now someone reads, asking any two copies. There are only three possible pairs. One and two: both new. One and three: one new, one old, and the newer wins. Two and three: the same. There is no way to pick two copies and miss both of the fresh ones. That is the rule. Two plus two is more than three, so the group that took the write and the group being read must share at least one machine.
Quorums · Going deeper
Quorums with five copies
Cassandra’s QUORUM level is a majority for both reads and writes; ONE and ALL are the two extremes. Divergence is repaired three ways: read repair on the hot path, background comparison with Merkle trees, and hinted handoff, which stores writes for a down replica and replays them when it returns.
Check yourself
Five copies. A write waits for 2 confirmations, and a read asks 2 copies. Can the read miss the latest write?
2 + 2 = 4 is not more than 5, so the two groups need not overlap. With five copies you need, for example, 3 and 3.
Partitioning
Splitting data by range keeps scans cheap; by hash keeps load even
Partitioning gives each machine a slice. Range or hash decides which queries are cheap, and a hash ring lets the cluster grow.
Copies give safety. To hold more data than one machine can, you split it, and how you split matters. By range: names A to H on one shard, I to P on the next. A question about neighbouring keys is answered by a single shard. But if one range is popular, that shard takes most of the traffic. By hash: scramble each key and let the result pick the shard. Load spreads evenly, but neighbours are now scattered, so the same range question must ask every shard. The hard part is growing. Arrange the hash values in a ring, and let each key belong to the next machine clockwise. When machine D joins, only the keys in one arc change owner: about one in N, instead of nearly all of them.
Partitioning · Going deeper · 1 of 2
Hash versus range
HBase, Bigtable and Spanner partition by range; Cassandra, DynamoDB and Riak by hash. A third option keeps an explicit directory from key to shard: fully flexible, but the directory becomes critical infrastructure. Moving data is slow: a 1 TB shard takes about 13 minutes at 10 Gbps flat out, and hours when throttled for live traffic.
Partitioning · Going deeper · 2 of 2
The consistent hashing ring
Each physical machine is placed at many positions on the ring (virtual nodes), so when one leaves its load spreads over many neighbours instead of landing on one. Hot keys remain hard: the usual answers are extra read copies, splitting one key into several with a suffix, or a cache in front.
Summary
Three facts, and everything else is a compromise with them
Time, clocks and partial failure explain every technique here. Next: systems design and cloud, where these parts become architectures.
Step back and the lesson has a simple shape. Three facts come with any network: messages take time, clocks disagree, and failure is partial. Each one forces a family of techniques. Because messages take time, copies lag, and you choose how much staleness to accept. Because clocks disagree, you order events by cause and effect. Because failure is partial, you decide by majority, with terms and leaders and a replicated log. And two moves build systems out of these: replication, more copies so a lost machine loses nothing; and partitioning, more slices so no machine holds everything. Real systems do both at once. Most of this field lives in research papers, not standards: Lamport’s clocks, Paxos and Raft, Dynamo and Spanner.
Lesson complete
You finished “Distributed Systems”
Answer the questions along the way to see your score here.