The shape of the chapter

1. 01Single-server baseline — hash table + tiered storage
2. 02CAP theorem — pick two when the network breaks
3. 03Data partition — reuse the Ch5 hash ring
4. 04Data replication — N copies, walked clockwise
5. 05Consistency & quorum — the N · W · R math
6. 06Vector clocks — versioning & conflict resolution
7. 07Failure handling — gossip · sloppy quorum · anti-entropy
8. 08System architecture — every node, every responsibility
9. 09Storage engine — LSM write path, Bloom read path
10. 10Wrap-up — Dynamo, Cassandra, BigTable mapped

Seven non-negotiable design goals

Every decision in the rest of the chapter trades one of these goals against another. Holding all seven simultaneously is impossible — CAP makes sure of it — so the design picks a point in the space and owns the consequences.

Two tiers, two cost profiles

The classic single-box optimisation is the one above: hold a hot working set in memory and spill the colder tail to disk. That buys you more capacity than your RAM allows, but at the cost of latency for any key that gets evicted. Hits the hot tier? Microseconds. Misses to disk? Milliseconds — orders of magnitude slower.

Where this design breaks

• 01Capacity ceiling. Even with disk spill, a single host caps out at terabytes; modern workloads ask for petabytes.
• 02Throughput ceiling. One CPU, one NIC, one memory bus. Read amplification on disk-resident keys magnifies every miss.
• 03No fault tolerance. The host is the system. When it goes, the keyspace goes with it.

The rest of the chapter is the story of fixing all three — partitioning the keyspace, replicating each partition, and tolerating the failures that come with the territory.

What CA buys you (and what it costs)

The CA region in the Venn diagram is real, just narrow: it covers systems that assume the network never partitions. A single-node SQL database fits there comfortably. Anything spread across two or more machines does not — the moment a cable goes, you're forced to choose between C and A on every in-flight request.

Make the choice concrete

The demo below puts three nodes on a triangle. Severing the link between two replicas forces the system to decide: an AP store keeps accepting writes everywhere and reconciles when the partition heals; a CPstore refuses anything it can't confirm with a quorum. Toggle the partition and the mode, and watch the outcome ribbon change.

Which one does this chapter build?

The rest of the module sketches an AP-leaning store in the Dynamo/Cassandra family: replication walks the ring, the quorum knobs (N · W · R) let callers dial consistency per request, vector clocks reconcile divergent writes, and Merkle anti-entropy heals long-term drift between replicas. The Live Labs let you feel both knobs interactively.

Two goals for any partition scheme

• 01Balanced load. Each node should hold roughly the same number of keys — no hotspots that bottleneck on one machine.
• 02Minimal churn on change. Adding or removing a node should move only the keys that strictly need to move, not the whole keyspace.

Why "distinct physical hosts"

Virtual nodes are great for distribution, but they mean a single machine can occupy several positions on the ring. If two of those positions happen to be adjacent, the naïve "next clockwise" walk would put two replicas on the same physical host — defeating the purpose. The walk therefore skips vnodes that map back to a host already in the replica set.

Placement, in practice

• →A single replica per rack helps if a power supply or a top-of-rack switch fails.
• →A single replica per availability zone or data centre helps when an entire failure domain is lost.
• →The replica set is the unit that quorum, vector clocks, and Merkle anti-entropy all operate on — every following section is a deeper look at one of those mechanisms.

The one inequality to remember

When W + R > N, any read intersects with any write on at least one replica. The freshest version is guaranteed to be in the read set — that's strong consistency. When W + R ≤ N, a read can miss the latest write entirely; that's the eventual- consistency regime, faster but stale-prone.

Common operating points

• 01R = 1, W = N. Fast reads, slow writes — every write must reach every replica before it can be acknowledged.
• 02W = 1, R = N. Fast writes, slow reads — the mirror image.
• 03W + R > N. Balanced, strongly consistent. The Dynamo default of N=3, W=2, R=2 lives here — it tolerates one replica being down while still meeting both quorums.
• 04W + R ≤ N. Low latency, weak consistency — used per-request when staleness is acceptable.

The clock, in one paragraph

A vector clock attaches a per-replica counter to each version: writing on replica Sa bumps Sa's counter, writing on Sb bumps Sb's. Comparison is componentwise: if every counter in clock A is ≤ the same counter in clock B, then A happens-before B. If neither dominates, the two clocks are concurrent — no causal relationship — and the application must decide which version wins (or merge them).

How the chapter's scenario plays out

1. Sa accepts a write. Its clock advances by one in Sa's slot.
2. Sa replicates the value to Sb. Sb merges the clock and now matches.
3. Sb writes a new value. The clock now has both Sa and Sb counters, strictly descending the previous version — linear history.
4. A partition isolates Sc. Sa writes again; Sc independently writes a different value. Both clocks legitimately bump their own counter but stay zero in the other.
5. When the partition heals, the merge step finds the two clocks incomparable — neither happens-before the other — and flags the pair as a conflict for the caller to reconcile.

01 · Detect — gossip

A centralised “is alive?” ping would itself be a single point of failure, so production systems instead use a decentralised gossip protocol. Each node periodically picks a few random peers and exchanges its view of cluster membership — including how long it's been since it last heard from every other node. A high silence count above a threshold means the node is considered offline. Verdicts converge across the cluster within a handful of rounds.

02 · Tolerate — sloppy quorum & hinted handoff

Strict quorum says “refuse if you can't reach W replicas.” That's correct but it sacrifices availability. A sloppy quorumrelaxes the rule: still require W acks, but accept them from any W live replicas — not necessarily the “true” ones for that key. To keep durability, the substitute writes get tagged with a hint identifying their rightful destination. When that destination returns, the hint replays.

03 · Repair — anti-entropy via Merkle trees

Gossip and handoff handle short outages. For longer divergence — a replica that was down for hours, or a missed write that slipped past — the system needs a way to compare entire keyspaces and exchange only what differs. The trick is a Merkle tree: a binary tree of hashes built over the keys. Compare roots; if they match, the replicas are in sync and we're done. If they don't, recurse into the children, isolating divergence to a small subtree and a small wire payload.

Why peer-to-peer

A leader-based design (one master, many followers) is simpler to reason about, but the leader is both a scaling ceiling and a fault domain. Dynamo's choice — and Cassandra's inheritance — is to push every responsibility down to every node. The cluster scales by adding peers; it tolerates failures because no one peer is irreplaceable.

The six responsibilities, in order of a request's life

1. Client API — the receiving peer becomes coordinator and routes the request.
2. Failure detection — gossip determines which replicas are reachable right now.
3. Replication — the coordinator fans out the operation to the live replicas for that key.
4. Conflict resolution — vector clocks on each version, application-level merge when needed.
5. Anti-entropy repair — Merkle-tree exchanges run in the background to heal long-term drift.
6. Storage engine — the local LSM-tree turns acknowledged writes into durable SSTables.

Write path

1. Commit log. The write is appended to a write-ahead log on disk and fsynced. That makes it durable — if the process dies before anything else happens, recovery replays the log.
2. Memtable. The write is then placed into an in-memory sorted map keyed by its key. The memtable is fast (no disk seeks) and keeps the keyspace sorted so future flushes are cheap.
3. SSTable flush. When the memtable hits its size threshold, the engine freezes it and writes a sorted-string table (SSTable) to disk. SSTables are immutable; updates land in fresh ones.
4. Compaction (background) — older SSTables are merged into newer levels, dropping superseded versions and deleted keys.

Read path

1. Memtable check. The most recent writes are still in RAM, so the engine checks the memtable first. A hit returns immediately.
2. Bloom filter. Each SSTable has a probabilistic Bloom filter. If the filter says “definitely not present” the engine skips that file entirely — no disk read at all. If it says “maybe present” (false-positive possible), the engine continues.
3. SSTable scan. Within each candidate SSTable, a small in-memory index points to the exact disk offset for the key's sorted block; binary search finishes the lookup.

The chapter in one table

Every section solved a goal. Below: the ten goals this chapter held itself accountable to, paired with the technique that earns each one and a jump back to the section that derives it.

What you're looking at

• →Each operation draws a lognormal-ish latency per replica and reports the W-th (or R-th) ack as the completion time. The model is intentionally simple — it's the shape, not the precise numbers, that matters.
• →If you isolate enough replicas via the partition slider, the cluster can't form a quorum and writes get refused outright. The acceptance-rate curve drops to zero.
• →The capacity badge in the corner shows live concurrent slots — capped at three across all users so the worker pool stays calm.

What you're looking at

• →The backend builds two real SHA-256 trees, then compares them top-down. Each level's visited/matched/diverged counts stream over SSE.
• →The final byte tally weighs hash exchanges + leaf-level diffs against a baseline that ships every key and value. With M ≪ K the savings ratio gets close to 100%.
• →Crank divergence up to K to see the worst case: the whole tree disagrees, and the algorithm pays for the hash exchanges on top of shipping all the data anyway.