Summary and key takeaways
Two axes, not one ladder
- Isolation levels: many objects, one logical copy. They say which interleavings of transactions a reader may see.
- Distributed consistency models: one object, many copies. They say how recent and how ordered a read is.
- Serializability gives no recency. Linearizability gives no multi-object atomicity. Their conjunction is strict serializability (external consistency), the only cell with no anomalies left.
Isolation in five lines
- Anomalies are shapes (cycles) in a dependency graph of write-write, write-read and read-write edges.
- A level is a set of prohibited shapes; the ANSI names are broken, and "Repeatable Read" means at least three different things.
- Lost update is fixed by commuting the operation (
SET balance = balance - x), which moves the read-modify-write into one statement and shrinks the read-to-write window by up to 10^4 (typically 10^3), or by a version check, which detects the conflict instead. - Write skew is a mismatch between the detector's unit (a row) and the invariant's unit (a set): fix by materializing the conflict or by SERIALIZABLE.
- Snapshot isolation is serializable minus every cycle with two or more anti-dependency edges.
The three pieces of arithmetic
| Result | Meaning |
|---|---|
| r + w ≥ d (sequential consistency) | Local reads and local writes together are impossible; the network delay is a conserved total. |
| read ≥ u/4, write ≥ u/2 (linearizability) | You pay for uncertainty of delay, not delay itself. |
| anomalies in flight ≈ conflicting rate × window | The window (lag, snapshot age, TTL) is the term you can attack. |
Four ways to buy the fixed total: leader reads, leases or read-index, quorum reads with write-back (ABD), or local reads and writes (give up the model).
Distributed consistency in one table
| Model | Kind | Key fact |
|---|---|---|
| Linearizability | safety | One copy plus real time; it is local, so it composes. The universal primitive. |
| Sequential consistency | safety | One agreed order, no recency; does not compose; what a replicated log gives. |
| Causal+ | safety | Strongest model with total availability; metadata cost; blind to causality outside the system. |
| Session guarantees | safety | Implemented by client tokens; broken by infrastructure changes. |
| Consistent prefix | safety | Prevents reply-before-message. |
| Eventual | liveness | Vacuous under continuous writes; only the bound (bounded staleness) is operable. |
| Strong eventual | safety + liveness | Same updates delivered means same state. |
Convergence has only two forms. Arbitrate (last-write-wins, loses writes, clock skew decides) or merge (a CRDT: commutative, associative, idempotent). CRDTs are coordination-free only on the write path; the garbage collector needs global knowledge (causal stability). CRDTs give convergence, not correctness.
Tunable consistency. R + W > N gives overlap only. Recency also needs version arbitration and a write-back round. Failed writes may reappear. Sloppy quorums remove the overlap exactly when failures occur. Per-request levels do not compose: the weakest pairing governs.
The unification
- CAP: during a partition, linearizability and total availability cannot both hold. It is per operation, not "pick two", and says nothing about latency.
- PACELC: the "else" branch (latency versus consistency) runs all the time; look at your p99 on a normal day.
- HAT: causal+ with read atomicity is the strongest transactional guarantee with total availability. Snapshot isolation is not available, because first-committer-wins is a coordination point.
- I-confluence decides whether coordination is needed: uniqueness and upper bounds are not I-confluent; per-row checks, insert-only foreign keys and lower bounds that transactions only push up are.
- CALM: coordination-free if and only if monotone. Coordination points cluster at five places: uniqueness, aggregation barriers, sequencing, termination detection, garbage collection.
- Partition the slack (escrow): coordination rate ≈ consumption rate / slack per replica, paid in stranded slack.
- External consistency is needed because of out-of-band channels (people, queues, other services) faster than replication.
- A vendor's level name is a hypothesis; test it with list-append histories and cycle search (Adya's G0, G1, G-single, G2 are the output vocabulary of the only black-box checker that works).
The ten principles that recur
- Conserved-cost rule: costs move, never vanish.
- Mismatch rule: detector unit versus invariant unit; tracking unit versus need.
- Little's rule: anomalies = rate × window.
- Approximation rule: intractable exact tests get conservative approximations and false positives.
- Hidden-assumption rule: what does this guarantee assume that it cannot verify, and who pays?
- Immutable-substrate rule: no overwrite means an indirection layer and a collector (CRDT tombstones).
- Right-algebra rule: restate the operation so order does not matter, and coordination becomes optional (CALM proves it).
- Token rule: cross-operation guarantees move to the client as a monotone handle.
- Observer-count rule: cost depends on vantage points and distance, not on data volume.
- Bound rule: "eventually" is useful only with a stated bound.
The decision procedure (stop at the first step that works)
- Can the operation commute? 2. Does the invariant fit in one row? 3. Is it I-confluent? 4. Can you partition the slack? 5. Is there an application read-modify-write (rules out Read Committed)? 6. Does a transaction check a set invariant and then write (rules out snapshot isolation)? 7. Is there an out-of-band channel faster than replication (needs external consistency)? 8. Only then choose a model, and state the staleness bound.
The story, in short. Anika's replica created anomalies without changing a write (observers). "Serializable" did not help with recency. She fixed lost update and write skew in the ledger, priced Singapore with r + w ≥ d, added session tokens and CRDT counters, replaced a "strong" quorum claim with an accurate one, gave away exactly 1,000 bonuses by partitioning the slack, and ended with one screen-by-screen table.
The question to carry forward: how many observers, how far apart, and what does each of them believe?