Book Deep Read · Database Internals · Chapter 12
Database Internals · Ch 12 · Alex Petrov · 2019
You post a message to a group chat. Most people see it instantly, one person sees it ten minutes later, and someone whose phone was off all day still finds it waiting when they switch back on. Chapter 12 of Database Internals is about how that last part — "still gets it eventually" — actually works. The previous chapter promised that the copies "will eventually match." This one asks the obvious follow-up: eventually by what means?
Something you deleted days ago comes back on its own. It sounds like a haunting; the mechanics are mundane. When you deleted it, one machine happened to be offline, so its copy still says "present." When it comes back, it notices its neighbours are missing that item and helpfully hands it over — the deletion gets undone. Which is why the real design problem is not "how do we deliver the data" but "what happens to the part that never arrived".
The obvious answer is "make sure everybody has it before you call the write done." But that means every write waits for the slowest machine, and one machine being off means nobody can write at all — exactly the bill the previous chapter priced out. So real systems finish the write first and settle the debt later. The trouble is that the debt does not clear itself: missing one write and missing a million writes look identical from outside — the copies differ, and nobody knows where.
The skeleton of the chapter is three complementary channels:
Some information — who is alive, who just joined — has to reach every machine. Telling them one by one is slow, and appointing one announcer means everything stops when the announcer dies. The chapter's answer is rumour: every machine, every second, picks a peer at random and tells it everything it knows. No centre, no single link that matters, and the spread is explosive — the number of machines in the know multiplies each round, so doubling the cluster costs only a round or two more. The price: nobody can promise exactly how many seconds it takes. You get "fast," not a guarantee.
"Eventually consistent" is not something you wait for; it is something you pay for. A system has to run three repair channels — hold at write time, check at read time, audit when idle — plus a rumour-style way of spreading news. Skip them and the copies stay different forever, and the things you deleted climb back out.
Want the mechanisms, the notation and the diagrams? → Switch to the deep read
The previous chapter's eventual consistency promised convergence once writes stop. This chapter calls in the debt: that "eventually" is not a gift of time, it is a standing operational expense. A replication protocol only attempts delivery; whatever fails to land has to be reconciled separately by anti-entropy. Petrov organizes the mechanisms by when they run — read path, write path, background — and then answers the second half of the problem, how to spread information across a whole cluster, with gossip. The mental model to install: convergence is work you schedule, not a byproduct of the protocol. In a cluster where nobody runs repair, "eventually" means "never."
f.gc_grace — a delete is written as a "deleted here" marker, kept for a grace period before it is finally purged.Part II, "Distributed Systems," directly after Ch11 (Replication and Consistency). That chapter laid consistency out as a spectrum and defined the cheapest tier as "converges once writes stop"; this chapter is where that promise gets paid, and it also covers how cluster metadata (membership, failure suspicion, schema versions) spreads. Ch13–14 (distributed transactions and consensus) take the opposite route: coordinate up front instead of reconciling afterwards. In the field this maps onto Cassandra's four-piece kit — hints, read repair, nodetool repair, gossip — plus background active anti-entropy in DynamoDB and Riak, and membership dissemination in Consul and Serf.
Start with a scenario that is not a failure at all: three replicas, QUORUM write (w=2). The coordinator returns success as soon as two acknowledge — at that instant the third replica simply does not have the data, and the system considers everything normal. Divergence is not the exception path; it is on the happy path.
Now scale it up: a node goes offline for 20 minutes during a rolling upgrade while the cluster takes 3,000 writes per second, a third of them its own. It comes back roughly 3.6 million writes behind. And the system does not know where it is behind: one missing write and three million missing writes both surface only as "sometimes you read a stale value."
What if you skip it? Three consequences, each worse than the last. (1) Stale reads become permanent — that old value never expires on its own. (2) Deletes resurrect: once the tombstone passes its grace period and is purged, a lagging replica still holding the old row reads the difference as "my peer is missing this" and helpfully ships the deleted data back. (3) "Eventual consistency" becomes a slogan — an "eventually" with no upper bound is, in engineering terms, no guarantee at all.
The chapter is organized by when reconciliation happens rather than by algorithm. The three channels differ in coverage and in cost, and they are complements, not substitutes — that structure is the first thing to internalize.
A read already contacts several replicas, so compare what they say. The engineering detail that matters is the digest read: ask one replica for the full row and the others for a hash only — when the digests agree, exactly one copy of the data crosses the network, and only a mismatch triggers a full fetch. That makes the steady-state cost of "checking as you go" close to zero.
The other switch to understand is blocking versus non-blocking. Blocking read repair writes the fix out and waits for the consistency level before returning, adding one write round trip to read latency and buying monotonic quorum reads (no repeat of the "new then old" anomaly from Ch11). Non-blocking repair reconciles internally and returns the right answer, but leaves the lagging replica untouched.
Its fundamental limit is one sentence: it only repairs data that is read. Cold rows, archived partitions, keys written once and never touched again — their turn never comes. Read repair is a fine way to hold down everyday staleness, and no kind of guarantee at all.
When a target replica is unreachable, the coordinator does not have to fail the write; it stores the mutation together with who it was meant for as a hint, and replays it when that replica returns. It pairs with the previous chapter's sloppy quorum: the write lands on the first n healthy nodes rather than the n that own the key — so brief failures stop turning into write failures.
Three costs. (1) Hints expire — three hours by default in Cassandra; after that the hint is dropped and the replica stays behind until the next repair. (2) Hints are not replicated — if the coordinator holding them dies, the debt evaporates. (3) The replay burst at recovery time can flatten the node that just came back. Hinted handoff is best-effort, not a guarantee.
Background repair has to answer: given two replicas holding hundreds of millions of rows each, how do you find the differences without shipping everything? With a hash tree — leaves hash segments of data, parents hash their children, up to a single root. Exchange roots first: identical means the whole tree can be skipped. Otherwise fetch the two child hashes and descend only on the side that disagrees, until you reach the offending leaf. The comparison traffic drops from "size of the data" to "height of the tree", written O(log n) — double the data and you ask one extra question.
Three costs to remember together. (1) Granularity — a leaf is not one row but a key range, so one mismatched leaf means shipping the entire range (over-streaming); repairing one row can move hundreds of megabytes. (2) Construction — the tree is only useful if it covers everything, so building it means reading all the data: real disk and network IO. (3) Topology changes invalidate it — adding or removing nodes re-divides the key ranges, and the trees have to be rebuilt.
Petrov also offers a remedy for the rebuild problem: bitmap version vectors. Instead of comparing data, a node records only "whose write number I have seen", compactly representing the set of received write sequence numbers as a bitmap. Replicas swap that summary, compute exactly which writes the peer is missing, and ship only those — no full scan at all. The catch is that it covers recent gaps only; long absences and silent corruption still fall back to Merkle trees.
The other half of the problem is dissemination: membership changes, failure suspicion and schema versions have to reach the whole cluster. Direct broadcast makes every node contact everyone (message count grows with the square of cluster size), and a fixed broadcast tree loses an entire branch the moment an interior node dies. Gossip answers with probabilistic spread: every node, once per interval (one second in Cassandra), picks f random peers and exchanges state.
Petrov borrows the epidemiological states to describe it: susceptible (has not received it), infective (has it and is forwarding), removed (has it but no longer forwards). When a node stops forwarding is the one real tuning knob: stop too early and the message may not reach everyone, stop too late and the network fills with duplicates. The three exchange styles each have a temperament: push is fast early and wasteful late; pull is good at finishing the job; push-pull converges fastest at the cost of larger messages.
Convergence grows logarithmically in the number of nodes — O(log N), meaning that going from 100 to 1,000 machines adds a few rounds rather than a factor of ten. That is why membership is almost always gossiped: it is insensitive to scale and insensitive to failure.
Pure random gossip wastes bandwidth: it is perfectly normal for one node to receive the same message seven or eight times. A fixed spanning tree is optimal (N-1 edges carry each message) but one dead interior node cuts off a whole branch. The chapter's reconciliation is hybrid gossip, exemplified by Plumtree:
The last piece is partial views: a node need not know the whole cluster, only a small active set of neighbours (on the order of log N) plus a passive backup list to promote from when one dies — the HyParView family. Per-node overhead therefore stops growing linearly with the cluster, which is what makes gossip-based membership feasible at thousands of nodes.
Table 1 · The three anti-entropy channels: what each covers, what each misses
| Channel | Triggered | Coverage | Steady-state cost | Honest cost / blind spot |
|---|---|---|---|---|
| Read repair | On every read, as a passenger | Only data that gets read | Very low (near zero with digest reads) | Cold data is never reached; blocking mode adds a write round trip to reads |
| Hinted handoff | Write sees a replica down | Writes during the outage, time-limited | Low, but write amplification while down | Hints expire (3 h default) or die with the coordinator; the replay burst can flatten the recovering node |
| Merkle repair | Scheduled background job | All data — the only guarantee | High: full read, tree build, cross-node streaming | Leaf granularity causes over-streaming; topology changes force rebuilds; run it too rarely and deletes come back |
| Bitmap version vectors | Background, recent gaps | Writes missed recently | Very low: metadata only, no data scan | Recent gaps only; long outages and silent corruption still need Merkle |
Table 2 · Four ways to get a message to the whole cluster
| Approach | Message redundancy | Robustness | Latency | When to pick it |
|---|---|---|---|---|
| Direct broadcast | None, but everyone contacts everyone | Poor: a miss stays a miss, no self-healing | Lowest (one hop) | Small, stable clusters (tens of nodes) |
| Fixed spanning tree | Lowest: N-1 edges | Worst: one interior node takes out a branch | Low (tree height) | Stable topology with someone maintaining the tree |
| Pure gossip | High: the same message arrives repeatedly | Best: no centre, paths are redundant by construction | O(log N) rounds, no upper bound | Membership, failure suspicion, large churning clusters |
| Hybrid gossip | Low: payload on the tree, announcements elsewhere | Good: announcements expose gaps and rebuild the tree | Close to a spanning tree | Broadcasting larger payloads while staying fault-tolerant |
Two rules of thumb. Take all the repair channels: they are three layers of defence, not alternatives — you only shift the weighting by data temperature, since hot data stays fresh on read repair alone while cold data depends entirely on the repair cadence. Pick a dissemination style by payload size and membership churn: small, volatile metadata goes over pure gossip; only a large payload that also needs fault tolerance justifies the complexity of hybrid gossip.
The practical value of this chapter is turning an operational instinct into something designable: the health of an eventually consistent system equals its anti-entropy budget. The common mistake in design review is treating "we use an eventually consistent store" as a conclusion, with nobody answering "how often does repair run, does it finish, and what happens when it does not?" Interviews are the same: being able to explain why read repair cannot replace repair, and what happens after a hint expires, counts for far more than saying the word "gossip."
Against real systems: Cassandra and ScyllaDB ship the full kit (hints, read repair, nodetool repair, gossip) and are the most direct implementation of this chapter; DynamoDB and Riak follow the Dynamo lineage, with Riak keeping hash trees resident for active anti-entropy; Consul and Serf gossip SWIM-style for membership and failure detection; Redis Cluster gossips slot and node state. The counter-example matters just as much: etcd and CockroachDB take the consensus route, forcing every write through a majority up front, and therefore need no anti-entropy at all — proof that anti-entropy is the running cost specific to settling debts after the fact.
3 h, past which "the destination replica will be permanently out of sync until either read-repair or full/incremental anti-entropy repair propagates the mutation."Apache Cassandra docs · Dynamo (architecture) / Hintsread_repair_chance and dclocal_read_repair_chance, were removed in 4.0.Apache Cassandra docs · Repair / Read repairSELECT touched, so cold partitions never get their turn; treating it as a convergence guarantee is how you end up waiting for data to resurrect.① Replication only attempts delivery; anti-entropy is the mechanism that settles what never arrived. Divergence is on the happy path — a successful w=2 write can leave the third replica empty.
② The chapter is organized by moment: read time (read repair), write time (hinted handoff), background (Merkle trees, bitmap version vectors). They complement each other and cannot substitute.
③ Read repair rides along on reads almost for free thanks to digest reads, but only fixes what is read; blocking mode preserves monotonic quorum reads at the cost of one write round trip.
④ Hinted handoff plus sloppy quorum keeps brief failures from becoming write failures, but hints expire (3 h default) and are not replicated — best-effort by design.
⑤ Merkle trees compare roots then descend, cutting the cost of locating divergence to O(log n); the price is over-streaming from leaf granularity, full reads to build the tree, and rebuilds whenever topology changes.
⑥ Bitmap version vectors compare metadata instead of data, making recent gaps very cheap to close — but they do not cover long outages.
⑦ Gossip trades redundancy for robustness: f random peers per round, rounds growing logarithmically with cluster size; the knob is when to stop forwarding, and push-pull converges fastest.
⑧ Pure gossip wastes bandwidth and a fixed tree breaks; hybrid gossip (payload on the tree, announcements as a net) lets the tree heal, and partial views keep per-node overhead flat as the cluster grows.
⑨ The line to take away: the "eventually" is an operating expense, not a gift from the protocol — a 10-day grace period means a full repair round every 7 days, or the data you deleted comes back on its own.