BOOKS DEEP READ · SYSTEM DESIGN INTERVIEW VOL 1 · CH 6
System Design Interview: An Insider's Guide · Ch 6 · Alex Xu · 2020
When you add an item to a shopping cart, the record of "what is in this cart right now" has to live somewhere. It is about as simple as data gets — one name, one piece of content, like an enormous address book. This chapter teaches you to turn that address book from "one notebook held by one person" into "something thousands of machines keep together, and that still works when several of them break."
Amazon's early shopping cart had a famous quirk: an item you deleted would come back a little later. That was not a bug, it was a deliberate trade — better to occasionally carry one extra item than to let "add to cart" fail even once. The whole design in this chapter exists to buy one sentence: writes always go through.
With a single keeper, everything is easy: you ask, they answer, and the answer is always current. But that person gets tired (cannot hold that much), calls in sick (the machine crashes), goes unreachable (the network cable breaks) — and in that moment the whole shop stops. Hand the job to a group instead, and a new problem arrives immediately: when you ask, whose copy did you get? What if that one is still the version from three minutes ago?
The fix is startlingly plain: give the same record to three keepers. When writing you do not wait for all three — two signatures counts as written. When reading you do not ask everyone either — ask any two, and believe whichever copy is dated later.
The beauty is this: pick two out of three to sign, then pick two out of three to ask, and at least one person must appear in both groups. That person signed for the newest copy with their own hand, and you happened to ask them. So "do not wait for everyone" and "always see the newest value" hold at the same time. The one who missed the write gets quietly caught up afterwards.
What if someone is out sick? Three moves, each heavier than the last. Gossip: nobody takes a central roll call — everyone chats with a few random colleagues and passes on what they heard, so within seconds the whole shop knows who is out and who is back. Ask the neighbour to hold it: if one of the three is missing, hand the item to the neighbour with a sticky note saying "holding this for so-and-so", and when they return the neighbour hands it over. Compare the table of contents: if they were out so long the note expired and the two ledgers have drifted badly, you do not check page by page — first compare only the table of contents; identical means everything is identical, done. Different means you go one level deeper, narrowing each time, until you carry over only the pages that genuinely disagree.
What you get is a dial you can turn: how many signatures to wait for, how many people to ask — you decide, and waiting for more is safer but slower. Carts, like counts, user sessions — anything where "slightly off once in a while is fine" — suit it beautifully. But for an account balance, where a single cent matters, do not use this: by construction it lets you read a stale value in the worst case, and even lets deleted things come back.
Give the same data to three keepers, treat two signatures as a write and two answers as a read, and lean on "the two groups must overlap" to guarantee you see the newest value. When someone is out, hand it to the neighbour with a note; when they are out too long, compare tables of contents to reconcile. You buy "writes always go through" and you pay in occasional stale reads.
Want the actual mechanisms, notation and diagrams? → Switch to the deep read
You think this chapter is about designing how to store; in fact nine tenths of it is about what to do when machines die. It is the only chapter in the book that designs no product and instead builds a database, breaking Amazon's Dynamo leaderless design into six independently replaceable parts: partitioning, replication, quorums, conflict resolution, failure handling, storage engine. The idea worth taking away: the moment you give up "one leader decides", correctness has to be rebuilt piece by piece — and every piece is paid for in consistency.
put(key, value) and get(key) — no joins, no multi-field queries.N=3 is the industry default.W, the read threshold is R.This is the third case study in Part II of Volume 1. The previous chapter (Ch 5, consistent hashing) delivered one component; this one bolts that component into a whole machine — the only time the book walks you inside a database rather than around a product. It maps to the entire "Dynamo family" in the real world: Amazon DynamoDB, Apache Cassandra, Riak, Voldemort, and later arrivals such as ScyllaDB. Ch 7 (distributed unique IDs) continues the same infrastructure-building thread.
A single-node key-value store is absurdly easy to write: an in-memory hash table is the whole thing. There is exactly one real problem — it does not fit, and it does go down. A quick order-of-magnitude check: a billion user sessions at 1 KB each is 1 TB, and a 128 GB machine is off by a factor of 8. The single-node optimisations the book offers (compression, hot data in memory, cold data on disk) buy time but not another order of magnitude. Worse is the second problem: without distribution, your write availability equals one machine's availability — in the thirty seconds that machine reboots, nobody on the site can add to a cart, which for Amazon is revenue lost outright.
So the real question in this chapter is not "how do I store it" but: once data is copied several times across machines that die at random, what does "read the correct value" even mean?
CAP says you cannot have all of consistency, availability and partition tolerance (the network splitting the cluster into halves that cannot talk). The key insight: P is not an option, it is a fact — machines talk over a network, and networks break. So the real choice is between C and A, and only during a partition.
The book's example is blunt: three replicas n1/n2/n3, and n3 goes unreachable. Choose CP (a bank transfer): refuse the write, because two versions of a balance is worse than an error. Choose AP (a shopping cart): accept it and reconcile when n3 returns. Dynamo chose AP for a reason stated in the paper — "add to cart" must never fail. Every mechanism that follows in this chapter exists to clean up after that choice.
Partitioning reuses Ch 5's consistent hashing ring directly: a key hashes to a point on the ring, and the first node clockwise owns it. Replication is the same walk continued — from the key's landing point keep going clockwise and take the first N nodes you meet.
One detail you must remember: the ring holds virtual nodes, and one physical machine occupies hundreds of positions on it. So the walk must skip physical machines already taken, or all three replicas can land on the same box and vanish together in one power cut. For the same reason production requires those N nodes to sit in different racks or availability zones — Netflix's Cassandra clusters run N=3 spread across three AWS availability zones.
With N copies, "the write succeeded" needs redefining. Dynamo's answer is three numbers: N replicas, W acknowledgements needed for a write, R replicas consulted for a read. The coordinator sends to all N but returns to the client as soon as W (or R) reply.
The central result is W + R > N. In plain words: pick W out of N to sign and R out of N to ask, and if the two numbers add up to more than N, the two groups must share at least one member (the pigeonhole principle). That shared replica both wrote the newest value and was read by you, so you cannot miss it. Dynamo's most common production setting is exactly (N,R,W) = (3,2,2): 2+2 > 3 holds.
Note the limits of that guarantee: it promises "you will see the latest write", not linearizability. There is no global order, no atomicity, no isolation level — a quorum says nothing about which of two concurrent writes came first. Which leads straight to the next problem.
In a leaderless store two clients can write the same key on two different replicas in the same millisecond, and neither is "later". A monotonically increasing version number fails here because it assumes a single global timeline.
Dynamo's answer is the vector clock: every value carries a list of [node, counter] pairs, and a node bumps its own slot each time it writes. Compare two clocks — if every slot of one is at least as large as the other's, it is strictly later and can simply overwrite. If each is larger in some slot, these are genuinely concurrent branches: the system has detected a conflict but cannot settle it, and hands both versions to the client.
Amazon's cart merges by taking the union, which is precisely where "deleted items come back" originates: a delete loses to an add at merge time. Two more costs: clients are forced to carry merge logic, and the clock list grows as more nodes participate in writes, so Dynamo truncates it past a threshold. The measured data is reassuring though — over 24 hours in production, 99.94% of Dynamo requests saw exactly one version, making conflicts rare enough to stop worrying about.
Notably, Cassandra did not adopt vector clocks, falling back to the simplest rule, last-write-wins by timestamp: trivial to implement, zero client burden, at the cost of silently discarding one of two concurrent writes and depending on accurate machine clocks. It is a telling split within one family of systems.
(a) Detection: gossip. The naive approach is all-to-all heartbeats, but n nodes means O(n²) links, which collapses in the hundreds. Gossip instead has each node keep a membership list (who, heartbeat counter, last update) and periodically pick a few random peers to exchange lists with, keeping the fresher entry for each row. Information spreads logarithmically, converging across the cluster in seconds with no single point. A counter that stops advancing marks a node suspect, and confirmation from several nodes declares it down.
(b) Temporary failure: sloppy quorum plus hinted handoff. Insisting on "W acks from the proper N nodes" means two dead machines block all writes — which defeats the whole "always writable" premise. A sloppy quorum relaxes this to the first W healthy nodes found walking the ring, even ones that should not hold this key. That stand-in attaches a hint — "this is being held for C" — and once C returns it replays the data to C and drops the hint. Cassandra keeps hints for at most three hours by default; past that, the next layer takes over.
(c) Permanent failure: anti-entropy with Merkle trees. A node down long enough (or fitted with a fresh disk) can diverge far past what hints cover, and comparing a billion keys one by one is hopeless. A Merkle tree splits the key space into buckets, hashes each bucket as a leaf, and makes every parent the hash of its children up to a single root. Two replicas compare root hashes first: equal means the entire tree matches and one comparison ends it; unequal means descending only along the branches whose hashes differ. The cost scales with the size of the difference, not the size of the dataset — that is its entire value.
With the previous five parts assembled, what remains is how each node puts bytes on disk. The book follows Cassandra here. Write: append sequentially to the commit log (which replays after a crash), then write into the in-memory memtable; once the memtable hits its threshold, the whole batch is sorted and flushed as an immutable SSTable. There are no random writes anywhere, which is why write throughput is so high. Read: check the memtable first and return on a hit; on a miss, use Bloom filters to eliminate the vast majority of SSTables that cannot contain the key, and read only the one or two that might.
The soul of this chapter lives in the dials. First, how to set NWR:
Table 1 · Four NWR settings at the same N=3
| Setting | Character | Cost | Fits |
|---|---|---|---|
R=1, W=3 | Very fast reads, one answer is enough | Writes wait for every replica; one slow or dead node blocks writing | Config data, mostly-read metadata |
W=1, R=3 | Very fast writes, one ack returns | Reads wait for every replica, so latency is set by the slowest one | Logs and telemetry — write-heavy, read-light |
R=2, W=2 | Satisfies W+R>N, so you see the latest write, and both paths survive one dead node | Both latencies are set by the second-fastest replica | The default for most workloads; Dynamo's common production value |
R=1, W=1 | Fastest and most available on both paths | 1+1 < 3, so no guarantee of reading the latest write | Where stale is tolerable: counters, caches, location pings |
Then, how conflicts end — the sharpest split within this family of systems:
Table 2 · Three conflict-resolution strategies
| Strategy | How | The honest cost | Who uses it |
|---|---|---|---|
| Last-write-wins | Compare write timestamps, larger wins | One of two concurrent writes is silently dropped; depends on accurate clocks, so drift becomes data loss | Cassandra (default) |
| Vector clocks | Track causality, distinguishing "later" from "truly concurrent" | Only detects conflicts, never resolves them; multiple versions land on the client; the clock list grows and needs truncating | Dynamo, Riak |
| Application merge / CRDTs | Define merge semantics per data type (union a cart, sum a counter) | Must be designed per type, and semantics can surprise — a union-merged cart resurrects deleted items | Amazon cart, Riak data types |
Finally, the question worth asking first — should you use any of this at all:
Table 3 · CP or AP, anchored to real workloads
| Workload | Pick | Why |
|---|---|---|
| Account balances, inventory | CP (a relational store, or Spanner-class) | A stale read is an oversell or a wrong number. Better to refuse service during a partition |
| Carts, sessions, saved lists | AP — this chapter's design | A failed write costs far more than an occasional extra item |
| Like counts, view counts, telemetry | AP, even W=1 | These are approximations already; throughput beats precision |
| Anything queried by several fields | Neither | A key-value store only has get/put; do not force it |
This chapter is the meta-question of system design interviews. Unlike a rate limiter or a URL shortener, it does not map to one product — it strings partitioning, replication, consistency, failure detection and storage engines onto a single thread. When an interviewer asks you to design a key-value store, they are checking all five at once. In the real world it is the shared blueprint of Amazon DynamoDB, Apache Cassandra, Riak, Voldemort and ScyllaDB; Kafka's partition replicas and Elasticsearch's shard allocation map onto the same parts.
(N,R,W) is (3,2,2), SLAs are set at the 99.9th percentile rather than the mean, and over 24 hours 99.94% of requests saw exactly one version — confirming that the multiple versions vector clocks expose are genuinely rare in practice. Dynamo paper, SOSP 2007 ↗p99 read latency fell from 40–125 ms to 15 ms — showing this architecture's ceiling is often the runtime, not the algorithm. Discord Blog, "How Discord Stores Trillions of Messages", 2023 ↗R+W>N, and that hinted handoff retains hints for at most three hours by default (max_hint_window), after which repair falls to anti-entropy — corroborating this chapter's split of failures across three timescales. Apache Cassandra Documentation · Hints ↗W+R>N guarantee. It collects "any W healthy nodes", not "W of the N that should hold this key" — writes can land entirely on stand-ins while reads consult the real replicas, and the two sets never intersect. It buys availability, not consistency. Raising this unprompted carries real weight in an interview.W+R>N is not strong consistency. It only promises you see the latest write; it offers no global ordering, no atomicity and no isolation levels. Calling it linearizable is the most common error here.get/put — no secondary indexes, no range queries, no cross-key transactions. The moment the product needs "find by the second field", the design needs revisiting.1. This chapter designs no product — it builds a database, and once the leader is gone, correctness has to be rebuilt one mechanism at a time.
2. In CAP, P is not a choice: networks do break, so the real decision is C versus A during a partition. Dynamo chose AP because "add to cart" must not fail.
3. Partitioning reuses the consistent hashing ring; replication walks clockwise and takes the first N distinct physical machines, skipping same-box virtual nodes and spreading across zones.
4. Quorum NWR: W+R>N forces the read and write sets to overlap by the pigeonhole principle, so a read always catches the latest write; (3,2,2) is the production norm.
5. But W+R>N is not strong consistency, and a sloppy quorum breaks even that guarantee — the single most worthwhile trap to remember.
6. Conflicts: concurrent writes have no order, and vector clocks can only detect them; Cassandra opts for last-write-wins instead — simpler, but it drops writes silently.
7. Failures are handled at three timescales: gossip for detection (avoiding O(n²) all-to-all), hinted handoff for short outages (three hours by default), Merkle-tree anti-entropy for permanent divergence (cost proportional to the difference, not the dataset).
8. Single-node storage: commit log plus memtable plus SSTable turn random writes sequential, and Bloom filters spare pointless disk reads.
9. Choosing, in one line: use it where stale values are tolerable (carts, sessions, counters); avoid it where a cent cannot be wrong (balances, inventory); and never reach for it when you need queries across several fields.