Database Isolation Levels, in depth: from the ANSI phenomena to dependency graphs, and how to test what your database really does

Histories and serializability

Isolation is defined over histories: the interleaved sequence of reads, writes, commits and aborts that concurrent transactions actually performed. The usual notation writes r1[x] for transaction 1 reading item x, w2[y] for transaction 2 writing y, and c1 or a1 for commit and abort. A history is serial if each transaction runs completely before the next starts. A history is serializable if its committed transactions produce the same reads and final state as some serial order.

Serializability lets each transaction be written as if it ran alone: if every transaction keeps an invariant on its own, a serializable execution keeps it too. Weaker levels are defined by listing the bad interleavings they still permit, and the difficulty is writing that list precisely.

The ANSI definitions: three phenomena

SQL-92 defines its levels by three phenomena, described in English. A dirty read (P1): T1 modifies a row, T2 reads it before T1 commits or aborts. A non-repeatable or fuzzy read (P2): T1 reads a row, T2 modifies or deletes it and commits, and T1 rereading would see a different value. A phantom (P3): T1 reads the set of rows satisfying a predicate, T2 inserts or changes a row so it satisfies that predicate, and T1 repeating the query would get a different set.

The standard also says SERIALIZABLE must give serializable execution, which is stronger than forbidding the three phenomena, so the table on its own does not define the top level. That gap, and the vague English, is where the trouble starts.

The 1995 critique: what the phenomena miss

Berenson, Bernstein, Gray, Melton and both O'Neils published A Critique of ANSI SQL Isolation Levels in 1995. Three of its points still shape every discussion.

First, the phenomena can be read strictly or broadly. The strict reading of dirty read, which the paper calls A1, only counts a history where T1 actually aborts after T2 read its write. The broad reading, P1, forbids reading an uncommitted write at all. Only the broad readings give the levels their intended meaning.

Second, the list is incomplete. The paper added P0, dirty write, where T2 overwrites T1's uncommitted write; every level must forbid it, or rollback becomes ill-defined. It also named lost update (P4: T1 reads x, T2 writes x and commits, T1 writes x based on its stale read), read skew (A5A: T1 reads x, T2 updates x and y and commits, T1 reads y and sees an inconsistent pair) and write skew (A5B: two transactions read an overlapping set, each updates a different item, and an invariant spanning both items breaks).

Third, it defined snapshot isolation and showed that it does not fit on the ANSI ladder. Under the paper's analysis:

Snapshot isolation allows write skew; locking Repeatable Read allows phantoms. Neither is stronger, which is how engines can label snapshot isolation REPEATABLE READ (PostgreSQL) or SERIALIZABLE (Oracle).

Adya's definitions: cycles in a dependency graph

The 1995 phenomena are phrased largely in terms of locks, which fits multiversion and optimistic engines poorly. In his 1999 thesis and a 2000 paper with Liskov and O'Neil, Atul Adya defined levels by the shape of a graph instead.

Build a direct serialization graph (DSG) with one node per committed transaction and an edge for each dependency. A write dependency (ww) runs from Ti to Tj when Tj installs the next version of an item after Ti's version. A read dependency (wr) runs from Ti to Tj when Tj reads a version Ti wrote. An anti-dependency (rw) runs from Ti to Tj when Ti reads a version and Tj installs the next version of that item, so Ti must come before Tj in any equivalent serial order. Predicate versions of these edges cover phantoms. A history is serializable exactly when the graph, including predicate edges, has no cycle.

Each level forbids its row and every row above it, whatever the implementation. One result becomes easy to state: Fekete and colleagues showed in 2005 that every cycle snapshot isolation allows has two consecutive rw edges between concurrent transactions, and serializable snapshot isolation, as in PostgreSQL's SERIALIZABLE, aborts a transaction when it detects that structure.

Worked example: classifying three histories

Take three histories, each with two transactions, and build their graphs. Versions are numbered by writer, so x0 is the initial value and x2 is the version T2 wrote.

Lost update. r1[x0] r2[x0] w1[x1] c1 w2[x2] c2, where both increment counter x. T2's x2 follows T1's x1: ww edge T1 to T2. T2 read x0, whose next version T1 installed: rw edge T2 to T1. One rw edge: G-single. Snapshot isolation forbids it (the second writer of x aborts); Read Committed allows it, losing an increment.

Read skew. x and y start at 50 and must sum to 100. r1[x0] w2[x2] w2[y2] c2 r1[y2] c1, where T2 moves 40 from x to y. T1 read x0, replaced by T2's x2: rw edge T1 to T2. T1 read y2, which T2 wrote: wr edge T2 to T1. One rw edge again, so G-single. T1 saw x = 50 and y = 90, a total of 140 that never existed. Snapshot isolation prevents it because T1 would read y0 from its snapshot.

Write skew. Two doctors on call, a rule that at least one must stay. r1[a0] r1[b0] r2[a0] r2[b0] w1[a1] w2[b2] c1 c2. T1 read b0, replaced by T2's b2: rw T1 to T2. T2 read a0, replaced by T1's a1: rw T2 to T1. Two rw edges: G2-item. Snapshot isolation allows it because the write sets do not overlap; only PL-2.99 or PL-3 forbids it.

A checker you can run

The same procedure is easy to automate for item-level histories when you know the version order of each item. The checker below builds the DSG and reports the most severe cycle it finds. It does not model predicates, so it cannot detect phantoms or predicate-level G2, and it assumes every listed transaction committed:

from collections import defaultdict

def build_dsg(reads, writes, version_order):
    # reads/writes: {txn: [(key, version)]}; version_order: {key: [v0, v1, ...]} (committed order)
    writer = {(k, v): t for t, ws in writes.items() for k, v in ws}
    edges = defaultdict(set)                      # (from, to) -> {"ww", "wr", "rw"}
    for k, order in version_order.items():
        for a, b in zip(order, order[1:]):
            ta, tb = writer.get((k, a)), writer[(k, b)]
            if ta and ta != tb:
                edges[(ta, tb)].add("ww")
    for t, rs in reads.items():
        for k, v in rs:
            w = writer.get((k, v))
            if w and w != t:
                edges[(w, t)].add("wr")           # t read what w wrote
            order = version_order[k]
            i = order.index(v)
            if i + 1 < len(order):
                nxt = writer[(k, order[i + 1])]
                if nxt != t:
                    edges[(t, nxt)].add("rw")     # t read a version nxt replaced
    return edges

def classify(edges):
    nodes = sorted({n for e in edges for n in e})
    worst = None
    rank = {"G0": 0, "G1c": 1, "G-single": 2, "G2-item": 3}
    def walk(start, node, labels, seen):
        nonlocal worst
        for (a, b), kinds in edges.items():
            if a != node:
                continue
            for kind in kinds:
                path = labels + [kind]
                if b == start:
                    rw = path.count("rw")
                    name = ("G0" if set(path) == {"ww"} else "G1c" if rw == 0
                            else "G-single" if rw == 1 else "G2-item")
                    if worst is None or rank[name] < rank[worst]:
                        worst = name              # report the most severe phenomenon
                elif b > start and b not in seen:
                    walk(start, b, path, seen | {b})
    for n in nodes:
        walk(n, n, [], {n})
    return worst or "serializable (no cycle)"

# write skew: both read a and b at the initial versions, each writes a different one
print(classify(build_dsg(
    reads={"T1": [("a", "a0"), ("b", "b0")], "T2": [("a", "a0"), ("b", "b0")]},
    writes={"T1": [("a", "a1")], "T2": [("b", "b2")]},
    version_order={"a": ["a0", "a1"], "b": ["b0", "b2"]})))   # -> G2-item

Run as written, it prints G2-item; the lost-update and read-skew histories print G-single. Cycle enumeration is exponential in the worst case, fine for hand-built tests. Elle, published by Kingsbury and Alvaro in 2020, uses workloads such as appending unique elements to lists so version orders can be recovered from client observations, and checks graphs of thousands of transactions.

Testing a real engine

The simplest test, popularised by Martin Kleppmann's Hermitage project, is two interactive sessions stepping through a history by hand. Here is write skew on PostgreSQL:

-- setup:  CREATE TABLE oncall(doctor text PRIMARY KEY, on_call bool);
--         INSERT INTO oncall VALUES ('alice', true), ('bob', true);
-- session A                                   -- session B
BEGIN ISOLATION LEVEL REPEATABLE READ;         BEGIN ISOLATION LEVEL REPEATABLE READ;
SELECT count(*) FROM oncall WHERE on_call;     SELECT count(*) FROM oncall WHERE on_call;
-- both see 2, so both think it is safe to leave
UPDATE oncall SET on_call = false              UPDATE oncall SET on_call = false
 WHERE doctor = 'alice';                        WHERE doctor = 'bob';
COMMIT;                                        COMMIT;
-- PostgreSQL REPEATABLE READ (snapshot isolation): both commit, nobody is on call.
-- Rerun with ISOLATION LEVEL SERIALIZABLE: one COMMIT (or an earlier statement) fails with
-- SQLSTATE 40001 "could not serialize access ..." and the application must retry it.

Write one such script per anomaly (lost update, read skew, write skew, phantom), run each at every level you use on your production engine version, and record which statement blocks, fails or commits.

Manual scripts do not show correctness under load, failover or replication; randomized workloads with a checker do. what Jepsen taught us surveys what they found.

Pitfalls when applying the theory

• Names are not definitions. PostgreSQL's REPEATABLE READ is snapshot isolation and its READ UNCOMMITTED behaves like READ COMMITTED. Oracle's SERIALIZABLE is snapshot isolation and allows write skew. MySQL InnoDB's default REPEATABLE READ gives a snapshot to plain reads, but locking reads and updates act on the latest committed row, so Hermitage-style tests report it permits lost updates. Map every name to a phenomenon list for your engine.
• Level by connection, not by intent. Pools and ORMs often set the level per connection, so a transaction can silently run at the pool default. Set it explicitly where it matters.
• Forbidding an anomaly can mean aborting. Serializable snapshot isolation and optimistic engines prevent cycles by failing transactions. Code that does not retry on serialization failures turns correctness into errors. Make retries part of the transaction boundary.
• Explicit locks are a level of their own. SELECT ... FOR UPDATE turns an rw edge into a lock conflict, but only for rows that exist, so it cannot stop a phantom insert; use a constraint for that.

What to do next

1. List the invariants your application relies on that span more than one row, such as at least one on-call doctor, a balance never negative, or unique bookings.
2. For each, write the history that would break it and classify it as G-single, G2-item or a predicate G2.
3. Look up which phenomena your engine's level actually forbids, then confirm with a two-session script on your production version.
4. Where your level allows the anomaly, choose a fix: a stronger level for that transaction, SELECT FOR UPDATE, a unique or exclusion constraint, or a materialized conflict row.
5. Add retry on serialization failure (SQLSTATE 40001 and the engine's deadlock code) around every transaction at SERIALIZABLE or snapshot level.
6. Set isolation explicitly per transaction, assert it in integration tests and keep write-deciding reads off replicas.
7. Keep the checker or a tool like Elle in your test suite for any custom concurrency control you build.