Isolation levels: what your database actually admits

Anomalies that have names

In 1999 Atul Adya’s thesis replaced the ANSI standard’s prose definitions with phenomena defined through a graph of dependencies between transactions. Using his names has a practical benefit: they leave no room for arguing about what exactly you observed.

The levels form a ladder: each forbids everything the one below it forbids, plus one more thing.

The entire practical difference between snapshot isolation and serializability is one anti-dependency. Read skew has one, and SI prevents it. Write skew has two, and SI cannot.

Write skew: taking out more than there is

The classic case looks innocent. The rule: the combined balance of a client’s two accounts must never go negative. Two transactions withdraw money — one from each account — and each checks the sum before withdrawing.

-- transaction A                    -- transaction B
BEGIN;                              BEGIN;
SELECT sum(balance) FROM accounts   SELECT sum(balance) FROM accounts
 WHERE client = 7;  -- 200           WHERE client = 7;  -- 200
-- 200 - 150 >= 0, allowed          -- 200 - 150 >= 0, allowed
UPDATE accounts SET balance =       UPDATE accounts SET balance =
  balance - 150 WHERE id = 1;         balance - 150 WHERE id = 2;
COMMIT;                             COMMIT;

There is no write conflict: the transactions touch different rows. Each read a consistent snapshot and made a correct decision. Both commit — and the combined balance is minus one hundred. The invariant is broken although neither transaction broke it on its own.

The same shape appears outside money: the last on-call doctor takes themselves off the shift at the same moment as a colleague; two managers reserve the last slot in a warehouse; two operations assign the same number to a document. In every case one thing is read and another is written — and SI lets that pair through by construction.

What serializable does, and what it costs

Snapshot isolation’s remaining hole has a shape: any cycle it admits contains two consecutive anti-dependency edges. So it is enough to watch for a transaction with both an incoming and an outgoing one — the pivot — and refuse to let it commit.

That is SSI by Cahill, Röhm and Fekete (SIGMOD 2008), the algorithm PostgreSQL implements as SERIALIZABLE. The check is deliberately conservative: it also aborts some transactions that would in fact have been serializable. The price is throughput, never correctness.

Check it, do not believe it

Finding an anomaly needs a dependency graph: write-after-write, read-after-write and write-after-read edges between transactions. Then you look for cycles, and the shape of a cycle gives the phenomenon its name.

One difficulty makes the naive approach useless. To draw an edge between two writes you must know which came first — and from a history over ordinary values that is unrecoverable: two writes of 5 are indistinguishable. Asking the database for the order means taking the defendant’s word for it.

The way out comes from Elle (Kingsbury & Alvaro, VLDB 2020): values are append-only lists, and every write appends a globally unique element. Now a single read of [a, b, c] states, by itself, that a preceded b preceded c. The version order is recovered from observations rather than taken from the store’s internals — so a database that lied about its own ordering would be caught rather than believed.

The rest is machinery: Tarjan’s strongly connected components, and inside each a breadth-first search that finds the shortest cycle. That is not pedantry: “there is a cycle among these forty-one transactions” is not a bug report, and two transactions with their edges spelled out is.

The ladder: checked in both directions

Here is the part everything else exists for. Every level is held to two statements at once.

• Sound. Over hundreds of seeded schedules the level never produced an anomaly it is required to prevent.
• No stricter than advertised. There exists a schedule on which it does produce exactly what the next rung prevents.

read-uncommitted     sound over 150 schedules   admits G1b at seed 0
read-committed       sound over 150 schedules   admits G-single at seed 1
snapshot-isolation   sound over 150 schedules   admits G2-item at seed 25
serializable         sound over 150 schedules   admits nothing, commits 51%

The second half matters more than the first. Soundness alone proves almost nothing: an engine that aborted every transaction would be “clean” at every level, and a checker that found nothing would agree with it. Requiring each rung to exhibit the next rung’s forbidden phenomenon closes that hole — and it checks the checker, because one that could not find write skew under snapshot isolation would have nothing behind its acquittal of serializable either.

The last line follows the same logic. Under a contended workload serializable commits 51% of transactions, and that is asserted by a test rather than printed for information: an acquittal bought by aborting everything would be worthless.

What to do about it in an application

Raising everything to SERIALIZABLE is not the only answer and often not the best one. There are three practical routes, and they combine.

Worth keeping separate: retrying a transaction and retrying a request are different things. A client retry without an idempotency key creates a second operation, and no isolation level saves you from that — see the piece on payment idempotency.

What this method cannot do

• No predicate anti-dependencies. Plain G2 needs predicate reads of the SELECT … WHERE kind; this workload has none, there is nothing to infer them from, and claiming to check G2 would claim more than the evidence supports. Only G2-item is checked.
• Passing is not proof. Hundreds of schedules from a space that is incomparably larger. Good fuzzing, not a theorem; TLA+ specifications of SSI prove what sampling cannot.
• The checker is not complete on everything. It finds a shortest cycle through each component member rather than enumerating every cycle: enough for these histories, but promising exhaustive search would be false.
• This is not a database. No durability, no recovery, no indexes, no garbage collection of old versions: an isolation engine and nothing more.

What to ask yourself and your contractor

These are the questions we ask ourselves on projects where wrong data costs more than downtime: financial systems, accounting and stock balances, CRM and ERP. The rest of the technical write-ups live in the Engineering section.