Design Interviews · lesson 14 of 15 · about 30 min
A Dynamo-style store end to end: how keys are placed on a ring, how many replicas must agree, how writes stay possible during failures, how replicas are repaired cheaply, what the storage engine costs, and what happens when a node comes back after too long. Tap any for a plain-language card.
Too much data for one machine, and no machine allowed to be special
With one position per node the ring slices are random sizes and some nodes get far more than their share. Giving each machine many (scattered positions) averages the unevenness out, lets faster machines take more slots, and spreads a failed node's load across many survivors. Capacity planning is arithmetic: data × replication ÷ per-node capacity. Both parts below use your numbers.
200 TB of data at replication 3 on 4 TB nodes needs at least 150 nodes. On a 20-node ring with 1 virtual node each the busiest node holds 4.3× the average; with 256 each, 1.08×.
200 TB at replication 3 on 4 TB nodes needs 150 nodes. On a 20-node ring with 8 virtual nodes each, the busiest node holds 1.54× its fair share and the quietest 0.47×.
The ring is real: node positions come from a 32-bit hash of "node#vnode" and 60,000 random keys are assigned to the next position clockwise.
Choose your own consistency, per request
The cost is latency: an operation waits for the R-th (or W-th) fastest replica, so larger R or W means waiting for slower replicas and a fatter tail. Choosing R = 1, W = N gives fast reads and slow, fragile writes; W = 1, R = N the opposite; R = W = 2 of 3 is the balanced default. Try the combinations; replica latency here is log-normal with a 5 ms median.
N = 3: R = 1, W = 1 can miss the newest write with probability 67% but answers in a median 2.6 ms. R = 2, W = 2 always overlaps and reads take a median 4.9 ms (p99 18 ms). R = 1, W = 3 has fast reads but write p99 of 43 ms.
With N=3, W=2, R=2: every read overlaps the latest write. Reads take a median 4.9 ms (p99 18 ms) and writes 4.9 ms (p99 18 ms), because each waits for the slowest replica it needs.
Latency is a Monte Carlo of 4,000 operations over log-normal replica latencies. The stale-read chance assumes the write reached exactly W random replicas and the read asks R random ones; read repair and hinted handoff shrink it in practice.
“Always writable”
That buys availability (the shopping cart can always take an item) at a price in consistency: while the hint is parked on a stand-in node, a read that asks only the owners will not see the write, so R + W > N no longer guarantees freshness. It is a deliberate AP choice (see the CAP lesson). Compare the chance a write can be accepted.
Three replicas, W = 3 and each node down 5% of the time: a strict write fails 14.3% of the time; with a sloppy quorum in a 50-node cluster it essentially never fails. At W = 2 a strict write fails 0.7%.
With N=3, W=3 and nodes down 5% of the time, a strict quorum rejects 14.26% of writes. A sloppy quorum over 50 nodes rejects 0.0000%, at the cost that reads may not see a write parked as a hint on a stand-in node.
Exact binomial probabilities with independent node failures: strict = P(at least W of N owners up); sloppy = P(at least W of the whole cluster up).
Which of a billion keys differ?
The data exchanged is then proportional to the number of differences times the tree depth, not to the number of keys. The cost moves to maintaining the tree (updating hashes as data changes, or rebuilding it periodically) and to the leaf size: larger leaves mean a smaller tree but more keys to re-read when one differs. Try it.
Two replicas of 1 billion keys differing in 1,000 keys: comparing a 16-byte hash per key moves 16 GB; the Merkle descent moves about 0.6 MB and then re-reads 1 million keys, instead of all one billion.
Two replicas of 1 billion keys that differ in 1,000 keys: comparing every key's hash would move 16 GB; a Merkle descent (depth 20) moves about 0.6 MB to find them, then re-reads 1,000,000 keys from the differing leaves.
Arithmetic: tree bytes ≈ differing leaves × depth × 2 hashes × 16 B. When differences are spread across many leaves the saving shrinks; when nearly every leaf differs, the tree gives no advantage.
Write fast now, tidy up later
The costs show up elsewhere. Write amplification: compaction rewrites each byte several times as it moves down the levels. Read amplification: a key might be in any level, so a read may check several files, which is why each file has a to skip files that cannot contain the key. The size ratio between levels is the dial: larger ratios mean fewer levels (cheaper reads) but more rewriting per level. Move the numbers.
1,000 GB with a 64 MB memtable and a size ratio of 10 makes 5 levels, a write amplification of about 26× and up to 6 files to check per read without Bloom filters. A ratio of 4 makes 7 levels, 15× writes and 8 files.
1,000 GB behind a 64 MB memtable with a size ratio of 10 needs 5 levels: each byte is rewritten about 26 times by compaction, and a read may have to look in 6 files unless Bloom filters rule most of them out.
Simplified leveled-compaction model: levels = ceil(log_T(data ÷ memtable)); write amplification ≈ levels × T ÷ 2 + 1 (flush); read amplification ≈ levels + 1. Real engines differ in strategy (size-tiered, leveled, hybrid).
Pick the mechanism
Each problem has one mechanism that fits best. Each answer is worth 20 XP.
Match the symptom: uneven load, stale reads, finding differences, or writes rejected during failures?
On a small ring one node holds four times its fair share of the keys.
Tip: press 1 to 4 to answer, Enter for the next one.
Who lives by this
Published designs and systems.
consistent hashing, quorums, vector clocks
The Dynamo paper described Amazon's highly available store for services like the shopping cart, combining a consistent-hash ring with virtual nodes, tunable quorums, sloppy quorums with hinted handoff, vector-clock versioning and Merkle-tree anti-entropy.
born at Facebook
Cassandra, created at Facebook, combined Dynamo's distribution (ring, replication, tunable consistency, gossip) with Bigtable's data model and an LSM-tree storage engine, and is a widely used example of the design in this lesson.
log-structured merge trees
Google's LevelDB and Facebook's RocksDB are embeddable LSM-tree key-value libraries; RocksDB adds extensive tuning of compaction and is the storage engine inside many distributed databases.
partitioned, replicated, managed
DynamoDB is Amazon's managed service inspired by Dynamo but not identical to it: it hides the ring and partitions from users and offers a choice between eventually consistent and strongly consistent reads.
Interview angle
Six questions, each worth 20 XP. Strong answers explain the consistency and availability trade-offs.
Say how keys are placed, how many replicas answer, how failure is tolerated and how replicas are repaired.
Why give each node many virtual nodes on the ring?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
If the outage lasts longer than the hint window the hints are discarded and the node comes back missing data. It must be repaired by streaming its key ranges from the other replicas (anti-entropy or a full rebuild), which can take hours and heavy bandwidth. Until it has caught up, reads of its ranges should not rely on it. Operationally: alert on long absences, bound the hint window to match your repair capacity, and make the replacement process routine rather than heroic.
2,000 writes a second to the node's ranges, down 6 hours with a 3-hour hint window: only 21.6 million hints are kept, taking 36 minutes to replay at 10,000 a second; the other 3 hours of writes are lost to hints and need a repair that streams 500 GB in about 1.4 hours.
The node was down 6 h but hints are kept only 3 h, so 21.6M hints replay in 36 min and writes from the other 3 h are gone. The node needs a full repair: streaming 500 GB at 100 MB/s takes 1.4 h.
Arithmetic: hints = writes per second × min(outage, window) × 3,600; replay time = hints ÷ replay speed; repair time = data ÷ streaming speed.