An isolation level is a set of forbidden cycles

Why is one edge type different from the others?

CaseConstructed case · Anika at Pebble

A vanishing bonus and a negative joint balance

Two bugs appear inside the primary database itself. No replica is involved.

The vanishing bonus. Pebble runs a weekly "bonus +100" job. The job reads an account's balance, adds 100 in application code, and writes the result back. Once a week, a customer complains that a transfer they received at the same moment has disappeared from their balance. The transfer row exists. The money is missing from the balance. Nobody can reproduce it in a test.
The negative joint balance. Some users hold two accounts, main and savings. The rule is balance(main) + balance(savings) >= 0: one account may go below zero if the other covers it. Two withdrawals arrive at the same moment, one from each account. Each checks the rule ("the sum is 100, I take 80, the sum stays positive") and each commits. The sum is now -60. The database runs at its Repeatable Read level. No error was raised.

Both look like bugs in the ledger code. Neither is. They are two different shapes of interleaving that the chosen isolation level did not forbid. To see which shapes, we first learn what an isolation level really is.

How it ends →

If you do not keep the graph acyclic, which cycles do you allow?

Single copy, many objects. The question of this article: which interleavings may a reader observe?

Every concurrency mechanism has the same goal: the result should look as if the transactions ran one after another (a serial execution). Whether a concurrent history is equal to some serial one can be checked with a dependency graph (also called a serialization graph). The nodes are committed transactions. An arrow from Tᵢ to Tⱼ means "Tᵢ must come before Tⱼ in any equivalent serial order". If the graph has no cycle, a serial order exists. If it has a cycle, no serial order exists, and the history is an anomaly.

Keeping that graph acyclic is the job of the strongest level. The question this article asks is the complementary one, and it is the question nobody states plainly: if you are not going to keep the graph acyclic, exactly which cycles are you allowing?

That is the entire content of an isolation level. A level is not an amount of safety, a percentage of serializability or a point on a dial. It is a set of forbidden subgraph shapes. Once you hold that idea, questions that cannot be answered with a list of anomaly names become mechanical:

Is snapshot isolation stronger than repeatable read? No. They are incomparable, and you can see why from the shapes (The anomalies are three shapes, not five concepts).
Does level X permit anomaly Y? Check whether Y's shape is in X's prohibition set.
Why is there no level between SI and serializable? There is one. It has no name, because the standard was written against one family of mechanisms (locks) that cannot express it (Why the taxonomy is broken, precisely).

The cost also changes character. When we study concurrency control as a mechanism, the cost is conflict: aborts and waiting, which are measurable inside the system. Here the cost is an anomaly, and an anomaly is not inside the system at all. It lives in the gap between what the application assumes and what the level guarantees. No component is positioned to notice that the gap exists.

The three edge types, and why one of them is different

Between committed transactions there are exactly three kinds of direct dependency. This is Adya's formalization. It replaces the ANSI definitions and is the only version worth learning.

Edge	Meaning	Example
ww (write-write)	Tᵢ writes a version of x, and Tⱼ writes the next version.	T1 sets balance to 150, then T2 sets it to 130.
wr (write-read)	Tᵢ writes x, and Tⱼ reads that version.	T1 sets balance to 150, then T2 reads 150.
rw (anti-dependency)	Tᵢ reads a version of x, and Tⱼ writes the next version. Tᵢ read something that Tⱼ then overwrote.	T1 reads balance 100; later T2 writes 80. T1 did not see T2's write, so T1 must come before T2.

A history is serializable if and only if this graph has no cycle. Everything below follows from one asymmetry:

A ww edge falls out of the version chain that the engine keeps anyway.
A wr edge falls out of a read returning a version.
An rw edge needs the engine to know what a transaction failed to see. That means recording every read and re-checking it against every later write. Nothing else in the engine wants that information. Writes are tracked anyway for durability and recovery. Reads are tracked for no other purpose.

Three consequences follow. Together they generate the whole hierarchy.

Consequence 1: read sets are unbounded where write sets are not. A transaction's write set (the rows it changes) is limited by what it intends to change. Its read set (the rows it looked at) can be a whole table. So tracking reads has a granularity and escalation problem that tracking writes does not. For example, a database may start by remembering individual rows a transaction read, then give up and remember only "this transaction read the whole table" when memory runs short. That is the mismatch rule at work (the unit tracked, a table, differs from the unit needed, a row), and it sets the false-abort rate of serializable snapshot isolation (SSI).

Consequence 2: predicate rw edges are worse than item rw edges. For one item (a row with a known key) you compare keys. For a predicate (for example WHERE balance < 0, or WHERE username = 'sam') you must decide whether a newly written row would have satisfied a query that ran in the past. That is the question of predicate satisfiability, and in general it cannot be decided. So every real system substitutes something cruder: index-range locks, which lock a whole interval of the index even if only one value matters. These inherit the choices of the query optimizer. This is the approximation rule (when the exact test is intractable, use a conservative approximation and pay in false positives). It is also why the last step up to serializable is the expensive one.

Consequence 3: the cheap levels are exactly the ones that never track reads. This is not an accident of history. It is the physical shape of the hierarchy.

The isolation hierarchy is a count of how many anti-dependency edges you tolerate in a cycle, and whether predicates count as edges.