BOOKS DEEP-READ · Database Internals · CH 11
Database Internals · Ch 11 · Alex Petrov · 2019
You change your profile picture, hit refresh, and the old one is still there; two seconds later the new one shows up. Chapter 11 of Database Internals is about what happens in those two seconds — your data is actually stored in several copies at once, and they are not always the same. What the chapter delivers is a language for saying precisely which copy a read is allowed to return.
Think of your data as an important document, copied three times and handed to three people — that way no single person going on holiday loses it. But trouble follows: you update the copy held by the first person, and the other two still hold the old text. Ask the second person and you get the old answer. Stranger still: ask the first and get the new answer, then ask the second and get the old one — from the asker's point of view, the data went backwards.
The obvious fix is "when you change it, make all three change at once, nobody jumps ahead." But that means every change waits for the slowest person to nod. A round trip between data centers in the same city is about 1 millisecond; across an ocean it is tens of milliseconds — pushing "always read the latest" to its limit means every read and write pays for several extra rounds of asking, and if even one person is unreachable, nobody can change anything. Go the other way for speed, and you accept the occasional stale read. This is an unavoidable trade, not laziness.
The most important idea in the chapter: "consistent or not" is not a yes/no question but a row of priced promises, from expensive to cheap —
Which tier you buy depends on what happens if you read a stale value: an account balance and a like counter clearly should not buy the same one.
The end of the chapter has a lovely idea: some data can be designed so that any two versions always merge cleanly. To count likes, let each machine track only the share it saw, and when merging, take the larger number per machine and add those up — duplicates, reordering and resends cannot change the result. This kind of data never needs the machines to negotiate who is right; it converges on its own. The cost: only some data types can be designed this way, and "it merged" is not the same as "the merge is what a human wanted".
Extra copies exist so you don't lose the data, but copies always differ for a while. So don't ask "is the data consistent?" — ask "which tier of promise am I willing to pay how much latency for?" Between "always the latest" and "eventually the same" there are several very good bargains.
Want the mechanisms, the notation and the diagrams? → Switch to the deep read
Replication buys availability; the consistency model is the bill replication runs up. Once there are several replicas, "the database returned a value" stops being self-evident — you must first agree on which return values are legal. This chapter turns that agreement into a precisely definable spectrum: from register semantics (safe / regular / atomic) up through linearizable, sequential, causal, session and eventual consistency, and on to CRDTs that converge with no coordination at all. The takeaway: consistency is a contract, not a performance dial — what you get by tuning a quorum is usually not the tier you think it is.
n here.n/2 + 1.This chapter belongs to Part II ("Distributed Systems") and is the fourth stop after Ch8 (introduction), Ch9 (failure detection) and Ch10 (leader election). Those three settle "who is still alive and who gets to speak"; this one asks "given several replicas, what should a read actually return?" It leads into Ch12 (anti-entropy and dissemination: gossip, Merkle trees and read repair to pull replicas back together when only eventual consistency is promised) and Ch13–14 (distributed transactions and consensus: actually implementing the strongest tier). In the real world it maps to Cassandra/DynamoDB consistency levels, linearizable reads in ZooKeeper/etcd, and Spanner's external consistency.
Availability comes from redundancy, redundancy means several replicas, and several replicas will differ for a while — so a question that looks like it needs no definition becomes a contract that must be defined: which copy should a read return?
Concretely: a three-replica key-value store spread over three availability zones returns as soon as the write lands on replica A, and the very next read is routed to replica B. Cross-AZ replication takes about 1–2 ms round trip, and during those 1–2 ms B is holding the old value. What happens if you don't solve it? Not something as gentle as "occasionally a bit stale" — the system loses its reasonability: retry the same request twice and get two answers, with no way to tell which one is the bug. So what the chapter does is break the adjective "consistent" into a set of decidable, priced contracts.
Almost every misunderstanding about consistency starts with "CAP: pick two". Petrov is careful to point out that CAP holds only under a very narrow model: an asynchronous network, no clocks, messages that may be lost arbitrarily. Its C means linearizability specifically, and its A means "every request reaching a non-failing node must return in finite time" — not "highly available" in the everyday sense. The real conclusion is: only when a partition actually happens are you forced to choose between C and A; for the vast majority of the time, with no partition, you can have both.
A more engineering-friendly framing is Fox and Brewer's 1999 harvest and yield: yield is the fraction of requests that complete, harvest is how complete the answer is. Allowing "results from only 90% of the index shards" is much closer to how real systems degrade than all-or-nothing — you are trading harvest for yield, which turns availability from 0/1 into a continuous quantity.
To discuss "what counts as a legal read" precisely, you need a minimal model. The chapter borrows the shared-memory view: treat the whole distributed store as one readable, writable cell (a register), then ask — when a read and a write overlap in time, what may the read return? Three tiers:
The value of this ladder: it turns "consistency" from an adjective into a decidable set of execution histories — given a history of reads and writes, you can answer "is this legal?"
With register semantics in hand, the familiar models line up on a spectrum — the higher up, the more coordination, the higher the latency, and the more fragile under partition.
sync first.Every tier on the spectrum is a system-wide property, which is why they are expensive. The common engineering compromise is to shrink the promise to a single client session: these session guarantees hold only for "your session", and are therefore far cheaper:
The cheapest implementation is stickiness: pin a client to one replica and the first two come almost free. The cost is that the guarantee dies with that replica — serious cases need a version token ("no earlier than the version I last saw") rather than a routing trick.
w + r > n does not give you linearizabilityThe Dynamo lineage (Cassandra, Riak, DynamoDB) hands the choice to each individual operation: a write waits for w replicas to acknowledge, a read waits for r replicas to answer, out of n total. When w + r > n, the read and write sets must overlap, so at least one responder has seen the latest write. The Dynamo paper (SOSP 2007) gives n=3, w=2, r=2 as the common configuration.
Here is the trap most worth remembering: w + r > n only guarantees that someone has seen the latest write — it does not guarantee linearizability. The write may have failed part-way (only one of w succeeded, so it returned an error while that replica still holds the new value) or may still be in flight — and then two successive reads can see new, then old, breaking monotonic reads.
To close the gap, a read must write the highest value it saw back to the lagging replicas (an ABD-style two-phase read, which in practice is read repair), turning the read path from one round into two. In other words: what you tune with a quorum is the trade between availability and staleness, not which contract you are on.
Majority fault tolerance needs enough replicas, but most of the cost of "enough" is storage, not voting. The chapter offers a neat saving: a witness replica normally keeps only metadata, not the data itself, yet still votes; only when full replicas become unreachable does it temporarily accept data and hand it back afterwards. So 2 full + 1 witness preserves three-replica majority tolerance at roughly two thirds of the storage. Cassandra's transient replication and Spanner's witness replicas are exactly this idea.
The pain of eventual consistency is that conflicts need an arbiter. The usual arbiter is LWW — compare timestamps, larger wins. But one clock going backwards and the winner may be the older value, while the losing write is silently discarded, without even an error.
A CRDT (conflict-free replicated data type) takes another route: design the data type so that merging needs no arbitration at all. Require the merge to be commutative, associative and idempotent — then reordering, duplication and resends cannot change the result, and replicas that receive the same set of updates (in any order) must reach the same state. That property is strong eventual consistency: it turns convergence from an operational promise into a mathematical property of the data type, with no consensus required.
Take the grow-only counter (G-Counter): each replica increments only its own slot, merging takes the per-slot maximum, and the value is the sum of the slots.
Add a second slot for decrements and you get the PN-Counter; sets bring G-Set, the observed-remove set (OR-Set) and other variants. Implementations split two ways: state-based (CvRDT) ships whole states, operation-based (CmRDT) ships only operations — cheaper on bandwidth but requiring delivery guarantees.
The costs are real: only some data types can be made into CRDTs; handling deletes correctly needs tombstones, so metadata grows over time; and above all convergence is not semantic correctness — replicas can perfectly agree on a result nobody wanted.
Table 1 · Picking among six contracts
| Tier | Anomalies it blocks | Coordination cost | When to choose it |
|---|---|---|---|
| Linearizable | all single-object anomalies: stale reads, reads going backwards, misordered writes | Priciest: a majority round per read/write; 1–2ms cross-AZ, tens of ms cross-continent | config and metadata, distributed locks, stock/balance decrements, leadership state |
| Sequential | backwards reads, misordered writes; does not block stale reads | Medium: writes coordinate, reads answer locally | read-heavy coordination services that tolerate lagging as a whole |
| Causal | causal inversion (reply before post); does not block concurrent-write divergence | Lower: version vectors only, no consensus | social timelines, comment threads, multi-site collaborative writes |
| Session | stale reads / backwards reads, within your session only | Very low: sticky routing or a version token | user-facing read-after-write: see your own edit immediately |
| Eventual | almost nothing; only promises convergence | Lowest: return once the local write is done | counters, logs, caches, statistics that can be backfilled |
| CRDT (strong eventual) | not stale reads, but converges with no arbiter and loses no writes | Zero coordination; cost moves into metadata size | offline-first, writable everywhere: collaborative docs, carts, likes |
Table 2 · Same three replicas, very different configurations (n=3)
| Configuration | Read path | Write path / availability | The honest cost |
|---|---|---|---|
Two extremesw=3,r=1 / w=1,r=3 | the former reads fastest, the latter waits for the slowest replica | the former cannot write if one node is down; the latter writes fastest | both load the whole cost on one side — one node down is half-crippled |
w=2, r=2 | two rounds (with read repair) | tolerates one node failure | the default choice, but still not linearizable |
LOCAL_QUORUM | local-region majority, about 1–2ms | unavailable only if the whole region fails | may read stale values across regions |
EACH_QUORUM | a majority in every region | any region partition fails the write | pushes cross-continent p99 to 80–150ms |
| 2 full + 1 witness | same as w=2, r=2 | tolerance equal to three replicas | saves about a third of storage; degradation is complex when full replicas are lost |
The decision rule is plain: first ask "what happens if we read a stale value?" If the answer is "the user sees an old avatar", session guarantees are enough. If it is "we oversell 1,000 units" or "two nodes both believe they are the leader", you can only pay for linearizability — and you must implement it with consensus, not by turning r up.
The practical value of this chapter is that it translates a vague requirement into an implementable contract. The most common mistake in architecture review is treating consistency as a performance dial: "feels a bit inconsistent, let's set r to 3" — latency rises, the anomaly stays, because r cannot cure backwards reads. Interviews are the same: being able to explain why w + r > n is not linearizability carries far more weight than reciting "CAP, pick two".
Against real systems: etcd (the single source of truth for Kubernetes) defaults to linearizable reads while keeping faster serializable reads as an escape hatch; ZooKeeper reads are sequential, and linearizability needs an explicit sync; Cassandra / DynamoDB hand the tier to each call; Spanner reaches external consistency with TrueTime and commit-wait; MongoDB has offered causally consistent sessions since 3.6; Riak and collaborative editing engines take the CRDT route.
operationTime into the session, pass it in the afterClusterTime field of later operations, and gossip cluster time between nodes. The same spec states the limit: "Causally consistent operations are not causally consistent with unacknowledged writes." — an unacknowledged write never enters the causal chain.MongoDB driver specifications · Causal Consistency Specificationw + r > n is not linearizability. It guarantees overlap, not order; for linearizability you need write-back on reads, or simply consensus.① Replication buys availability, and the consistency model is the bill; once there are several replicas, "what a read returns" must be written down as a contract.
② CAP's model is narrow: C means linearizability specifically, A means "a request must return in finite time", and only a real partition forces the choice; harvest/yield is the better framing.
③ The three registers (safe / regular / atomic) turn consistency into a decidable set of execution histories; atomic = linearizability on one object.
④ The spectrum from pricey to cheap: linearizable → sequential → causal → session → eventual. Causal is the strongest model reachable under availability plus partition tolerance; linearizability composes, weaker models may not.
⑤ Session guarantees are the best value: read-your-writes, monotonic reads, monotonic writes, writes-follow-reads — sticky routing gives the first two almost free, and the guarantee dies with the replica.
⑥ The one to remember: w + r > n guarantees overlap, not order, so it is not linearizability; closing the gap needs write-back / read repair, turning one round into two.
⑦ Levels have a price: LOCAL_QUORUM about 1–2ms, EACH_QUORUM 80–150ms across continents — the same line of code, two orders of magnitude of p99.
⑧ Witness replicas vote without storing data: 2 full + 1 witness = three-replica tolerance at about two thirds of the storage; LWW, by contrast, silently drops writes when a clock steps back.
⑨ CRDTs make convergence a mathematical property of the data type (commutative / associative / idempotent), with zero coordination and no lost writes; the costs are limited types and growing metadata, and convergence is not semantic correctness. The rule stays one line: first ask what happens if you read a stale value.