Distributed Systems Core · lesson 2 of 11 · about 30 min
How Dynamo-style stores let each request choose how many replicas to wait for: strict and sloppy quorums, how replicas heal through read repair and Merkle-tree anti-entropy, how version vectors detect concurrent writes, what each consistency level costs across regions, and the hidden hole in sloppy quorums. Tap any for a plain-language card.
Strict and sloppy
The numbers are exact binomial probabilities: each node is down independently with the chance you choose. Sloppy quorums turn many failures into non-events for writes. What they cost, the last scene shows: they quietly break the “R + W > N means fresh reads” promise.
Set N=3, W=3 and a 20% chance of each node being down: strict quorums fail about half of all writes. Then add stand-ins.
With N=3, W=2 and each node down 10% of the time, a strict quorum refuses 2.80% of writes. Allowing 3 stand-ins refuses only 0.006%. The refused writes become hinted data waiting to be handed back.
P(at least W of the usable nodes are up), exact binomial. Nodes fail independently; real failures are often correlated, which makes both numbers worse.
Read repair
A key is written on one of three replicas only. Each round, some number of reads each ask two random replicas. With repair on, any stale replica among those asked is brought up to date. Popular keys heal in a round or two; a key nobody reads stays divergent, which is why a second mechanism (background anti-entropy, next scene) exists too.
Set 1 read a round with repair on, then turn repair off. Then add a little background handoff.
All three replicas are current after 2 rounds. Each read of a stale replica fixed it on the spot.
Seeded: a key written on one replica; each read asks 2 random replicas and returns the newer one. Repair writes it back to the stale one.
Anti-entropy
The tree here is real: leaves are hashed with a real 32-bit hash, and the diff walks two trees counting every hash compared. Dynamo, Cassandra and Riak all use this idea; Git and blockchains use the same structure for the same reason.
With 4,096 keys and 3 differences the diff compares about 70 hashes instead of 4,096.
1.02K keys, 3 different: the diff compared 55 hashes and found exactly those 3 keys (256, 512, 768). Comparing everything would have been 1.02K comparisons and moved all the data.
A real binary Merkle tree over K leaves with a 32-bit hash; the differing keys are spread evenly. Compared = every node hash looked at during the walk.
Version vectors
Dynamo's shopping cart worked this way: if two carts diverged, the next read returned both and the application merged them (a union), so an “add to cart” was never lost. Try it: both Ben and Cleo add an item while starting from the same cart.
Press “Ben adds a mug” and “Cleo adds a lamp” (both start from the same cart), then merge.
One version, no conflict. Add an item from two different nodes starting from the same cart to see concurrency.
Real version-vector comparison: a ≤ b if every counter in a is at most b's. Neither ≤ the other means concurrent.
Consistency levels
Replicas sit in New York, London and Tokyo. Pick where the client is and optionally take one data centre down. Latencies come from real distances (as in the CDN lesson). Notice what a regional outage does: QUORUM keeps working with two of three regions, ALL stops completely, and ONE hardly notices.
Put the client in Sydney, then take Tokyo down and compare the three levels.
From Sydney: ONE takes 122 ms, QUORUM 245 ms, ALL 260 ms. The step from ONE to QUORUM is the price of reading fresh data (122 ms here), and ALL adds a further 15 ms for almost no extra safety, which is why QUORUM is the usual choice.
k-th smallest round-trip time among the live replicas, from the same great-circle model as the CDN lesson (illustrative route inflation 1.5×).
Pick the level
Choose the cheapest level that is still safe for the operation. Each answer is worth 20 XP.
Ask: what is the cost of reading or writing stale data here?
Recording that a user viewed a product page (analytics). A lost or late event is harmless.
Tip: press 1 to 3 to answer, Enter for the next one.
Who lives by this
Four published systems and what they say about quorums and repair.
sloppy quorum + hinted handoff + Merkle trees + vector clocks
The Dynamo paper describes a highly available key-value store for Amazon's shopping cart using exactly these pieces: consistent hashing with virtual nodes, sloppy quorums with hinted handoff, Merkle trees for background anti-entropy, and vector clocks so the application can merge conflicting carts, with N, R and W configurable per service.
CONSISTENCY ONE · QUORUM · ALL · LOCAL_QUORUM
Cassandra lets each query set a consistency level (ONE, QUORUM, ALL and datacentre-aware variants such as LOCAL_QUORUM), supports read repair and hinted handoff, and provides nodetool repair, which builds Merkle trees to find and fix differences between replicas.
object → causal context → siblings
Riak exposed the conflict machinery to users: when concurrent writes occur it can keep both as siblings and return them on a read together with a causal context (a version vector variant), leaving the application to merge. It documents tunable N, R, W per request.
PUT → new objects and overwrites visible to every later GET
In December 2020 AWS announced that S3 now provides strong read-after-write consistency for all object operations at no extra cost, ending years of eventually consistent overwrite and list behaviour. It shows consistency expectations rising as engineering makes the strong option cheap.
Interview angle
Six questions, each worth 20 XP. Dynamo-style replication is a favourite for key-value store and shopping-cart designs.
Say N, R and W, what happens when a node is down, and how replicas converge afterwards.
What is a sloppy quorum?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
The strict quorum never does this, because it would have refused the write, as the first scene showed. So the sloppy quorum trades freshness for write availability. Dynamo made this trade on purpose for shopping carts; do not make it by accident for balances. Set how often nodes are down, how long until the read, and how long handoff takes.
Leave 20% down and read 5 seconds after the write with a 30-second handoff: about 4% of reads are stale on a sloppy quorum, 0% on a strict one.
For reads 5 s after a write (handoff takes 30 s), 3.9% return the old value on a sloppy quorum although R + W > N. The strict quorum returns 0.0% stale, at the cost of refusing 10.5% of writes.
20,000 seeded trials: nodes down independently; sloppy writes use the first 2 live nodes of 6 (3 preferred + 3 stand-ins); a read asks 2 random preferred nodes.