What a second machine takes away

A second machine takes away three things you never knew you had

on one machineacross a network (round trip)Messages take timeevery decision pays for the tripa call takesnanosecondssame rack0.1 msnext zone1 msanother region30 – 150 mssatellite600 msClocks disagreetimestamps cannot order eventsone clock,one order12:00:00.00012:00:00.004synced: a few ms apartunsynced: seconds a dayFailure is partialone side down, the other alivecrashed meansnothing runsAB has crashedB is alive, but the network is slowB is alive, but a router is dropping packetsFrom A’s side, all three look exactly the same: no reply.Every idea in this lesson is a workaround for one of these three facts.A timeout is the only detector there is, and any value is wrong somewhere: too short fails healthy machines, too long blocks everyone.

Across a network, messages take time, clocks disagree, and partial failure looks exactly like slowness.

What a second machine takes away · Going deeper · 1 of 2

From one machine to many — each step adds a new failure mode single machine two machines many machines one process · one clock a wire between a cluster behind a network A A B failures are total crash = nothing runs message latency > 0 peer crash, you cannot tell partitions, partial failure consensus, sharding, replication consequences cascade → message ordering · clock skew · split brain · stale reads consensus to agree on a single value · quorums to mask failures replication for durability · partitioning for capacity · rebalancing

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 network partition — both sides keep serving, neither knows about the other N1 N2 N3 N4 N5 N6 partition no traffic crosses left half: serves clients elects own leader accepts writes right half: serves clients elects own leader accepts writes split brain

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

You99% okA99% okB99% okC99% okD96%of requests get throughFour calls in a row, each one 99% reliable: 0.99 × 0.99 × 0.99 × 0.99. One request in 25 now fails.Then C slows down, and every layer above it retries 3 timesnormal traffic1×you retry3×A retries each of those9×B retries each of those27×load arriving at C, which was already strugglingThe fixwait longer after each failure (backoff)add randomness so retries do notarrive together (jitter)make a repeated request harmless(idempotency keys)A remote call is not a function call: it can be slow, fail halfway, or arrive twice.The classic false assumptions: the network is reliable, instant, unlimited, secure, unchanging, free, uniform, and run by one team.

A remote call can be slow, fail halfway or arrive twice. Careless retries turn one slow service into an outage.

Compounding failures and retries · Going deeper

The eight fallacies of distributed computing 1 · Network is reliable 2 · Latency is zero 3 · Bandwidth is infinite 4 · Network is secure 5 · Topology is stable 6 · One administrator 7 · Transport cost is zero 8 · Network is uniform retries pile up, duplicate writes, silent drops sync RPC chains blow past p99 SLO cross-region elephant flows starve neighbours, egress bills explode MITM, replay, trust the wire → get owned DNS flips, autoscaling churn, cached IPs go stale policies diverge at AWS / Azure / on-prem boundary serialization, TLS handshakes, cross-AZ data fees MTU, IPv4/v6, protocol versions, hardware quirks the network looks reliable in development; production is what production is

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

ABC[1,0,0]writes x = 1[1,1,0]B hears about it[0,0,1]writes x = 99having heard nothing[1,1,2]has now seen bothWhich write came first?[1,0,0]vs[0,0,1]A’s write is ahead in slot A.C’s write is ahead in slot C.Neither contains the other, soneither knew of the other:they are concurrent.The system must merge them, pickone, or hand both to the application.With no shared clock, “before” can only mean “could have known about”.Each machine counts its own events in its own slot [A,B,C], and on every message keeps the larger number in each slot.Timestamps cannot settle it: the two clocks may differ by more than the gap between the writes.

A vector clock counts events per machine, which reveals when two writes were truly concurrent.

Logical clocks · Going deeper · 1 of 3

Lamport logical clocks — counters bumped on every event, exchanged on every message node A node B node C 1 2 5 7 1 3 6 1 4 5

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 — each node tracks a counter per peer, revealing concurrent events A B C [1,0,0] [2,0,0] [3,2,1] [0,1,0] [2,2,0] [0,0,1] [2,2,2]

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 TrueTime — bounded clock uncertainty TT.now() returns an interval, not a point [earliest ··· latest] ε ≈ 1–7 ms Commit protocol: 1. assign commit timestamp s = TT.now().latest 2. wait until TT.now().earliest > s (commit-wait ≈ 2ε) 3. release locks, ack client

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

[2,1,0]and[1,2,0]

Two versions of a record carry these vector clocks. How are they related?

Consistency models

Consistency is a ladder, and every rung down buys speed or uptime

strongest: behaves like a single machineLinearizableevery read sees the latest finished write, on any machineSpanner, etcdSequentialall machines agree on one order, not tied to real timeCausala cause is always seen before its effectpost, then its commentRead-your-writesyou always see your own changes; other people may lagsession pinned to a fresh copyEventualif writes stop, the copies end up the same. Nothing more.S3 until December 2020weakest: fastest, and keeps answering through failuresEach rung down hands back something one machine gave you for free, in exchange for speed or uptime.Eventual is weaker than it sounds: two of your own writes can show up in the wrong order, or not at all, for a while.

A consistency model is the contract for what a read may see. Stronger is easier to program; weaker is faster and survives failures.

Consistency models · Going deeper

Consistency model hierarchy from strongest to weakest Linearizable Sequential Causal Read-your-writes Eventual global real-time order — every read sees the most recent write all nodes agree on one order; not necessarily real-time causally related writes seen in causal order a client sees its own writes; others may not yet stop writing, replicas eventually converge stronger · slower etcd, Spanner single-leader DB Riak (causal) session reads DNS, old S3

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

A write of x = 2 has reached Replica 1. Then the link between the replicas is cut, and someone reads x from Replica 2.Choose consistencyReplica 1x = 2Replica 2x = 1, out of date✗link cuta readerread xrefuses: “try later”✓never gives a wrong answer✗this side is down until the link healsetcd, ZooKeeper, SpannerChoose availabilityReplica 1x = 2Replica 2x = 1, out of date✗link cuta readerread xanswers “x = 1”✓always answers✗may be stale; the sides must be merged laterCassandra, DynamoDBWhen the network splits you can stay correct or stay available, not both.Splits will happen, so this is a real choice. And with no split the same trade remains, as consistency against latency:waiting for other copies to confirm makes every write slower.

The CAP theorem: during a partition a system keeps consistency or availability, never both.

CAP and partitions · Going deeper

CAP triangle — pick at most two C A P CP AP etcd · Spanner ZooKeeper · HBase Cassandra · Dynamo Riak · CouchDB CA is the corner you cannot live in if your system spans two machines

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

ABCterm 5: A leadsheartbeatsevery 50 ms✗A crashes180 ms of silenceC’s timer was set to 240 ms, so B moves firstvote for me, term 6yesB leads term 62 votes of 3A comes back“I lead term 5”sees term 6,steps downtime →A leader needs votes from a majority. Any two majorities share a member, and nobody votes twice in a term,so two leaders in the same term are impossible.Each timer is random, between 150 and 300 ms, so two candidates rarely tie. A higher term always wins,so an old leader coming back does no harm. Failover usually takes a few hundred milliseconds.

Consensus starts with electing one leader per term. Majorities overlap, so there can never be two.

Leader election · Going deeper

Raft node state machine Follower Candidate Leader election timeout majority votes won split vote → retry discovers higher term → step down

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

entry 1entry 2entry 3entry 4Leadertakes every writex=1y=2x=3y=7Followerconfirmedx=1y=2x=3y=7Followerslow or cut offx=1y=2x=31 the leader appends y = 7 and sends it to both followers2 one follower confirms: 2 of 3 hold it, so it is committed3 only now is the client told “ok”; the slow one catches up laterHow many machines?filled = the majority every write waits forneeds 2, survives 1 downneeds 3, survives 1 downone more machine, no more safetyneeds 3, survives 2 downneeds 4, survives 2 downone more machine, no more safetyneeds 4, survives 3 downA write counts once a majority has stored it: the same log, in the same order, on most machines.This is Raft, the algorithm inside etcd (which runs Kubernetes), Consul and CockroachDB. A minority side of a splitcannot reach a majority, so it stops accepting writes. That is what keeps the two sides from diverging.

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.

Consensus and commit · Going deeper · 1 of 3

Raft log replication — entry committed after a majority acknowledges client leader follower 1 follower 2 SET x=7 AppendEntries ack commit 2 of 3 → majority OK

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

Two-phase commit — coordinator drives prepare then commit coordinator participant P1 participant P2 participant P3 PREPARE YES COMMIT ACK prepared, durable on disk, locks held

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

Saga — forward steps with compensations on failure forward path T1: charge card T2: reserve seat T3: send email done failure at T3 → compensate backwards C1: refund C2: cancel seat T3 failed no atomicity, but eventual consistency without distributed locks

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

network cut

A five-machine Raft cluster is cut into a group of 3 and a group of 2. What happens?

Replication

Three ways to keep copies, depending on who may accept a write

One leaderwritesLFFcopies arrive10s of ms late✓one place decides the order✗followers lag behind the leaderPostgres, MySQL, MongoDB, RedisA leader per regionwritesLLEuropeAsia✓local writes are fast in every region✗conflicting writes must be mergedmulti-region databases, GitNo leadersend to all,wait for some✓no failover, tunable per request✗copies disagree until repairedCassandra, DynamoDB, RiakCopies protect you from losing a machine. The design question is who is allowed to accept a write.Lag is visible to users: post a comment, read from a follower that has not caught up, and your own comment is missing.When two leaders disagree, “last write wins” is the cheap answer, and it silently discards the other write.

Replication keeps copies on several machines: one leader, a leader per region, or no leader at all.

Replication · Going deeper · 1 of 4

Three replication topologies Leader–follower Multi-leader Leaderless writes → leader, reads anywhere writes anywhere, merge conflicts write W replicas, read R replicas L F F F L L L L N1 N2 N3 N4 N5 Postgres streaming, MySQL primary–replica, MongoDB replica sets CockroachDB active-active, CouchDB, BDR Postgres, CRDT-backed apps Dynamo, Cassandra, Riak — "Dynamo-style" topology = where the consistency cost is paid: at write, at read, or in conflict resolution

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

LWW discards data; a G-Counter CRDT merges Last-write-wins G-Counter CRDT A: cnt=5 B: cnt=5 write +1 at t=10 write +1 at t=11 cnt = 6 (t11 wins) one increment lost pick newest timestamp data loss on concurrent updates depends on synchronized clocks A: [6,0] B: [0,6] A bumps slot[A] B bumps slot[B] [6,6] → sum = 12 both increments preserved per-replica slots, max-merge value = sum across slots no clocks; deterministic CRDTs trade extra metadata for the property that any merge order gives the same result

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

Gossip — randomized peer exchange converges in O(log N) rounds round 0 round 1 round 3 1 of 8 knows ≈ 2 know all 8 know N = 1000 → ≈ 10 rounds. N = 1,000,000 → ≈ 20. used by Cassandra, Consul, Akka Cluster, Serf, SWIM. No fixed topology, no single point of failure.

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

Geo-replication topologies single-region + replicas active-passive active-active L RR RR RR low latency, one region region loss = outage L F F F primary region writes passive promotes on failover (RPO > 0) L L L L writes local to each region conflicts must be resolved write latency RPO conflicts cost single + replicas in-region 0 none lowest active-passive in-region seconds none medium active-active local 0 yes highest

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 write of x = 7 goes to all three copies and waits for 2 (W = 2)Copy 1x = 7Copy 2x = 7Copy 3x = 3, slowconfirmedconfirmednot yetA read asks any 2 (R = 2). The three possible pairs:7737 and 77737 and 3: newer wins7737 and 3: newer winsNo pair avoids both fresh copies.W + R > N2 + 2 > 3, so the write group and theread group must share a machineIf writes reach W copies, reads ask R, and W + R is more than the number of copies, every read meets the latest write.With 5 copies, 3 and 3 does it. The setting is chosen per request: W = 5, R = 1 makes reads cheap; W = 1, R = 5 makes writes cheap.Stale copies are fixed as they are found (read repair), by background comparison, and by replaying missed writes.

A quorum: write to W copies, read from R. When W + R exceeds the number of copies, every read sees the latest write.

Quorums · Going deeper

Dynamo-style quorum: N=5, W=3, R=3 N1 N2 N3 N4 N5 N = 5 W = 3, R = 3 W + R = 6 > N → strong any read of 3 overlaps any write of 3 → latest version seen

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

newnewoldoldoldthe five copies, just after the write

Five copies. A write waits for 2 confirmations, and a read asks 2 copies. Can the read miss the latest write?

Partitioning

Splitting data by range keeps scans cheap; by hash keeps load even

By rangeneighbours stay togethernames A – Hnames I – Pnames Q – Zload✓“names K to M” is answered by one shard✗a popular range overloads one shardBy hashkeys scattered evenlyshard 0shard 1shard 2load✓load spreads evenly✗“names K to M” must ask every shardGrowing without a reshuffleABCD joinsa key belongs tothe next machineclockwiseonly the purple arc changes owner:about 1/N of the keys, not all of themPartitioning gives each machine a slice of the data. How you slice decides which questions are cheap.Plain “hash modulo N” moves nearly every key when N changes; the ring moves only one arc. Neither helps with a celebrity:one hugely popular key lands on one shard, however good the hash.

Partitioning gives each machine a slice. Range or hash decides which queries are cheap, and a hash ring lets the cluster grow.

Partitioning · Going deeper · 1 of 2

Hash vs range partitioning Hash-based Range-based key "user-42" hash() % 4 S0 S1 S2 S3 + even key distribution + no hot shard from one user − range scans hit every shard a–e f–m n–t u–z S0 S1 S2 S3 S4 + range scans cheap (one shard) + adjacent keys co-locate − hot range = hot shard Directory-based: a lookup service maps each key prefix to a shard. Maximum flexibility, but the directory is critical infrastructure that must itself be replicated and consistent.

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

Consistent hashing ring N1 N2 N3 N4 N5 N6 key walks clockwise to first node large dots: physical nodes small dots: virtual nodes node join/leave moves only 1/N of keys on average

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

Messages take timeClocks disagreeFailure is partialso copies lagthe consistency ladderconsistency against latencyread-your-writesso order by causalitylogical and vector clocksconcurrent writes must be mergedso decide by majoritytimeouts, terms and leadersa replicated log (Raft)correct or available in a splitReplication: more copiesso losing a machine loses nothingPartitioning: more slicesso no machine has to hold everythingEvery distributed system is a set of compromises with three facts.Real systems do both at once: each slice of the data is copied to several machines, and each group of copies agrees by majority.

Time, clocks and partial failure explain every technique here. Next: systems design and cloud, where these parts become architectures.

Lesson complete

You finished “Distributed Systems”

Answer the questions along the way to see your score here.

Open in a new tab