Isolation Levels and the Anomalies They Were Supposed to Prevent

The SQL standard does not define what a transaction at a given isolation level may do. It defines what a transaction at that level must not do, and leaves everything else permitted. The negative form is a consequence of how the levels were negotiated: serializability was already defined by its own theory, but the weaker levels existed because real implementations ran them faster, and the standard had to describe existing behaviour rather than reason it out. The result is a specification whose central clause is a list of anomalies that turned out to be neither complete nor well-matched to what the levels actually allow.

Locking reads and the ghost problem

The pre-ANSI mechanics are worth reconstructing because the terminology still reflects them. Degree 0 through Degree 3 of consistency were defined by what locks a transaction holds. Degree 0 holds no locks before writing and can therefore overwrite uncommitted data. Degree 1 holds exclusive locks until commit and prevents that. Degree 2 adds shared locks on updated data, held until the write completes. Degree 3 holds all shared locks to commit.

Each lock rule maps to a concrete hazard. Holding an exclusive lock to commit prevents dirty writes. Holding a shared lock to commit prevents a read from seeing data that changes underneath it. The mapping is clean because the mechanism and the anomaly line up one to one.

What the lock hierarchy does not map onto is phantom phenomena, and this is where the standard’s definitions detach from the implementations. A predicate read, “all rows matching this condition”, is protected by nothing in a lock hierarchy built on row identifiers, because the rows that will match next time either do not exist yet or are not in the read set. Repeat that same query inside one transaction and get different rows, and no amount of row locking prevents it. The standard’s anomaly list had to name a phenomenon, phantom read, whose prevention requires range locks or predicate locks, an entirely different mechanism from the one whose degrees the levels were derived from.

The deeper cost is architectural. Index locks whose granularity is a key range serialize a whole value range to protect one reader, so the fast path of a B-tree scan sees conflicts proportional to the span of the scan rather than the number of tuples returned. Implementations that could not afford this called their level SERIALIZABLE while permitting phantoms, and the divergence became permanent.

Testing the definitions against real schedules

The 1995 critique of the ANSI levels, written by a group including several of the people who designed the systems the levels described, made two separate arguments and the second is the more damaging.

The first argument is terminological. The standard defines each anomaly in prose, and the prose is ambiguous about whether it describes a state or an interaction. A dirty read is described in terms of a transaction reading uncommitted data written by another, but the description does not pin down whether the writes must be later committed, rolled back, or neither. Two implementers reading the same sentence will exclude different schedules.

The second argument is structural. Even reading the prose charitably, the levels do not form a clean lattice over the anomalies. Some schedules are permitted by a level’s stated prohibitions yet are clearly not what anyone meant by that level. The critique’s proposed answer was to define each level by the anomalies it forbids rather than by locks, drawing on the Adya-style formalization where histories are classified by dependency graph structure: write-read dependencies for dirty reads, read-write dependencies for repeatable read failures, and cycles for serializability violations.

A schedule diagram makes the gap visible. Consider three transactions operating on two accounts, a classic write skew pattern:

T1: read x, read y     -- both balances positive
T2: read x, read y
T1: write x := x - 100 -- still consistent with y
T2: write y := y - 100 -- still consistent with x
T1: commit
T2: commit

Each transaction’s reads are consistent, each write is internally justified, no value is ever overwritten and no uncommitted read occurs. Under the ANSI definitions as written, behavior at REPEATABLE READ, where only dirty, nonrepeatable and phantom reads are prohibited, admits this outcome. The result is a state in which both balances were debited from a condition each transaction verified, and the invariant that both would have been non-negative if only one of them had run is violated. Nothing in that schedule is a phantom, a dirty read or a nonrepeatable read.

Write skew is the canonical demonstration that anomaly lists built from observations of single values cannot capture constraints that span values. The constraint here, that the sum of the two balances stays above zero, is a property of a set of rows, and no per-row prohibition can express it.

Predicates, snapshot reads and what MVCC changed

Multi-version concurrency control moved the problem without solving it. A snapshot read gives every transaction a consistent view of committed history as of its start, which eliminates nonrepeatable reads by construction and eliminates dirty reads because uncommitted versions are never visible. It does not eliminate write skew, because two transactions reading the same old snapshot each see a state in which their own write is justified.

Optimistic implementations detect the resulting conflicts by tracking read-write dependencies at commit, and the standard’s isolation levels do not describe this mechanism at all. A system that labels its snapshot level SERIALIZABLE while detecting conflicts at commit time is conforming to a definition of serializability, not to a definition of SERIALIZABLE in the clause list. Systems that detect such conflicts only for explicitly tracked predicates will miss them for untracked ones, and there is usually no way from the outside to tell which is which short of inducing the schedule.

The practical consequence is that “REPEATABLE READ” means different things at different vendors and the difference is not visible in the standard. This is the same divergence pattern as De Jure Standard Versus De Facto Implementation, except that the de facto behaviour here differs in a direction that silently admits incorrect results rather than merely producing different output.

Why the recovery log outran the isolation model

Gray’s 1981 transaction paper set out the properties that became the durability and atomicity half of the transaction contract, and it did so in terms of a write-ahead log with a specific ordering rule: the log record describing a change must be forced to stable storage before the change itself reaches stable storage. The rule exists because the alternative, writing a data page before its log record is durable, makes the page unrecoverable after a crash: the page reflects a change with no log entry explaining it, and undo cannot proceed.

ARIES formalized the recovery side: analyze the log to build a dirty page table and transaction table, redo all logged changes from the last checkpoint to repair the buffer pool, then undo losers and roll back to the last savepoint. The model requires that every page carry the log sequence number of the last change applied to it, so that redo can be idempotent: a page whose stored sequence number is already at or past a log record’s number has had that change applied and skips it.

The coupling between that recovery model and the isolation levels is precisely where the two halves of the transaction contract come apart. The lock manager that provides degree 2 consistency sees dirty pages in the buffer pool and knows they may be flushed at any time. The log provides the ability to undo them. Neither of those facts tells the lock manager what a reader is allowed to observe, and the SQL levels describe only the reader side. A system can therefore have a perfect write-ahead log and a recovery procedure that restores the exact pre-crash state, and still have leaked a value that was later rolled back, because the leak happened through a lock that was released before commit rather than through the log.

The cost of holding locks versus the cost of restoring

The trade the isolation levels were reaching for is now measurable in a clear form. Holding every shared lock to commit, which is what degree 3 requires, converts a long read into a blocker for every writer touching the same data. The waiting set grows and in a mixed workload this dominates throughput. Releasing shared locks early admits reads of data that may be undone, which requires the reader’s transaction to have a defined behaviour under that possibility, usually abort. Optimistic systems take the second branch and pay in aborts under contention, which is exactly the retry failure described in Optimistic Concurrency and the Conflict Check That Arrives Too Late.

The level a system can honestly support is the one it can enforce when a conflict is rare, not the one it enforces on the test suite. The standard’s contribution was to name the anomalies, and the names outlived the definitions once implementations took the predicate problem into their own hands.

Serializability as the only stable point

Of the four standard levels, only SERIALIZABLE has a definition that does not depend on enumerating phenomena: a history is serializable if its effect equals that of some serial order of the same transactions. That definition is stated over outcomes and is therefore testable in principle without listing what may go wrong. Every weaker level is defined by what it does not do, and each such definition leaves room for a schedule nobody thought of.

The historical lesson is not that the weaker levels were a mistake. They let existing systems be described in a shared vocabulary, which was the point. It is that a specification written as a list of excluded failures needs testing effort proportional to the size of the excluded set, and no one ever runs that test. The write skew example above was not discovered in the field because it is rare; it was discovered by writing the schedule down.