Isolation Levels

A schedule is an interleaving of the read/write operations of concurrently executing transactions. A schedule is serializable if it produces the same result as some serial (one-at-a-time) execution of those same transactions — this is the correctness criterion inherited from Serializability and Schedules. Enforcing serializability exactly, however, generally requires transactions to block each other (via two-phase locking) or to abort and retry (via optimistic/validation schemes), and both cost throughput. Isolation levels are named degrees of relaxation from strict serializability, each defined by which of three classical anomalies it permits. The three anomalies are defined precisely on read/write operations over data items, assuming $T_1, T_2$ are concurrent transactions:

• Dirty read: $T_1$ writes a value to item $X$; $T_2$ reads that uncommitted value; $T_1$ later aborts. $T_2$ has now read a value that officially never existed.
• Non-repeatable read (also called a fuzzy read): $T_1$ reads item $X$; $T_2$ updates and commits $X$; $T_1$ reads $X$ again and gets a different value, within the same transaction.
• Phantom read: $T_1$ reads a set of rows satisfying some predicate $P$ (e.g., `WHERE balance > 1000`); $T_2$ inserts (or deletes) a row that now satisfies (or no longer satisfies) $P$ and commits; $T_1$ re-runs the query and sees a different set of rows — a "phantom" that wasn't there before, or one that vanished.

The SQL-92 standard defines four isolation levels purely in terms of which of these anomalies are permitted:

A crucial subtlety: this table describes a necessary condition, not a sufficient one for serializability. A schedule can prevent all three named anomalies and still not be serializable — the classic counter-example is write skew under snapshot isolation, discussed below. The anomaly table is a useful, standardized vocabulary, but "SERIALIZABLE" is the only level in the table that is defined to equal true serializability; the others are defined purely by exclusion of specific anomalies, leaving room for anomalies nobody bothered to name in 1992.

There are two families of mechanism used to implement isolation levels: lock-based (rooted in Two-Phase Locking) and version-based (rooted in Multiversion Concurrency Control). Understanding both is necessary because different production systems default to different families, and the guarantees differ subtly even when the SQL-level name is the same.

Lock-based implementation

The standard mapping from isolation level to locking discipline varies lock duration — how long a lock is held — and lock scope — whether it protects only existing rows or also protects a predicate against phantom inserts. ``` ISOLATION LEVEL -> LOCKING PROTOCOL (2PL-based) READ UNCOMMITTED:

• Write locks: acquired before write, held until commit/abort (long duration)
• Read locks: NONE acquired at all

-> reads never block, and can see uncommitted writes => dirty reads possible READ COMMITTED:

• Write locks: held until commit/abort (long duration)
• Read locks: acquired before read, released IMMEDIATELY after the read

(not held until end of transaction) -> a read can never see an uncommitted write (dirty read prevented) -> but re-reading X later may see a different, newly committed value (non-repeatable read still possible) because the read lock was already released REPEATABLE READ:

• Write locks: held until commit/abort
• Read locks: held until commit/abort (long duration, like writes)

-> once T reads X, no other transaction can modify X until T finishes (non-repeatable read prevented) -> BUT ordinary row locks say nothing about rows that do not exist yet; a concurrent INSERT matching T's earlier predicate is unaffected (phantom read still possible) SERIALIZABLE:

• Write locks: held until commit/abort
• Read locks: held until commit/abort
• PLUS: predicate locks / index-range ("gap") locks / next-key locks

taken on the predicate of every range query, blocking inserts or deletes that would change the result set -> phantoms are prevented because the predicate itself is locked, not just the rows that happened to exist at read time ``` The key engineering insight is that ordinary row-level locking can never prevent phantoms, because you cannot lock a row that doesn't exist yet. Preventing phantoms requires locking the space of possible rows — implemented in practice as next-key locking (locking a row plus the gap before it, as in InnoDB) or true predicate locking (locking the condition of a `WHERE` clause, as in some index-based schemes). This is the mechanistic reason phantom prevention is qualitatively harder than the other two anomalies and is reserved for the strictest level.

Version-based implementation (Snapshot Isolation)

Most modern systems (PostgreSQL, Oracle, SQL Server's `READ COMMITTED SNAPSHOT`, MySQL/InnoDB) implement REPEATABLE READ and often what they call "SERIALIZABLE" using snapshot isolation (SI), built on MVCC rather than blocking locks. ``` SNAPSHOT ISOLATION (informal protocol) on BEGIN(T): snapshot_time(T) := current commit-counter // T will only ever see versions of rows committed before snapshot_time(T) on READ(T, X): return the version of X with the largest commit-timestamp that is <= snapshot_time(T) // never blocks; never sees uncommitted or "future" writes on WRITE(T, X): buffer the write locally (not visible to other transactions yet) on COMMIT(T): if EXISTS T' such that: T' committed after snapshot_time(T) AND T' wrote to some item X that T also wrote then ABORT T // "first committer wins" -- prevents lost updates else assign T a new commit-timestamp make all of T's writes visible at that timestamp COMMIT ``` Because every read is served from a private, fixed-in-time snapshot, dirty reads, non-repeatable reads, and phantom reads are all impossible under SI: nothing committed after $T$'s snapshot is ever visible to $T$, whether it's a modified existing row or a newly inserted one. This is why systems that use SI market it as "REPEATABLE READ" or even "SERIALIZABLE" — it does dominate the SQL-92 anomaly table. But SI is not equivalent to serializability. The canonical failure is write skew: two transactions each read an overlapping but disjoint set of items, each writes to a different item based on what it read, and neither write conflicts with the other under the "first committer wins" rule — yet the combined effect could never have arisen from any serial execution. ``` WRITE SKEW EXAMPLE (on-call doctors) Invariant the application relies on: at least one of {Alice, Bob} is on call. Initial state: alice.on_call = true, bob.on_call = true T1 (Alice goes off call): T2 (Bob goes off call): snapshot: both on_call = true snapshot: both on_call = true read bob.on_call -> true read alice.on_call -> true (Alice may go off call, since Bob covers) (Bob may go off call, since Alice covers) write alice.on_call = false write bob.on_call = false COMMIT (no overlapping WRITE set COMMIT (no overlapping WRITE set with T2 -> succeeds) with T1 -> succeeds) Final state: alice.on_call = false, bob.on_call = false INVARIANT VIOLATED -- nobody is on call. ``` Both commits succeed under SI's write-write conflict check because $T_1$ never writes to `bob.on_call` and $T_2$ never writes to `alice.on_call` — their write sets don't intersect, so "first committer wins" never triggers. Yet no serial order of $T_1, T_2$ produces this final state. This is why true SQL SERIALIZABLE, when implemented over MVCC, requires an additional mechanism — Serializable Snapshot Isolation (SSI) — which tracks read-write ("rw") anti-dependencies between transactions and aborts one of them when a dangerous structure (a cycle risk) is detected, on top of the plain SI protocol.

Time/space cost is a function of lock duration and lock scope, not of the algorithm's asymptotic complexity — isolation levels are a concurrency-control policy layered on the same O(1)-per-operation lock table or MVCC version chain. The right way to reason about "complexity" here is in terms of concurrency (blocking probability, abort rate) rather than big-O, since the underlying data structures (lock tables, version chains) are shared across all levels.

• READ UNCOMMITTED: minimal locking overhead — read locks are never taken, so readers never block and writers only block other writers. Highest throughput, weakest guarantee.
• READ COMMITTED: read locks are short-lived (held only for the duration of a single read), so the window during which a reader can block a writer (or vice versa) is minimized. Under MVCC variants, each statement gets a fresh snapshot, so cost is one snapshot-read per statement — cheap, no blocking on reads at all.
• REPEATABLE READ: read locks are held for the transaction's entire lifetime, so long transactions accumulate long-held locks, increasing the chance of blocking and deadlock. Under MVCC, cost is a single snapshot per transaction (not per statement) — still no read blocking, but the abort rate for conflicting writers rises, since "first committer wins" checks are made against a longer-lived reference point.
• SERIALIZABLE: adds predicate/gap locks (2PL route) or full read-write conflict tracking via SSI (MVCC route). The 2PL route can suffer from lock escalation and reduced concurrency on hot ranges; the SSI route adds bookkeeping to detect "dangerous structures" (pairs of rw-antidependency edges forming a cycle risk), at the cost of a higher abort-and-retry rate under contention, but with no blocking added to reads.

Correctness argument, sketch. For 2PL-based mechanisms, correctness follows directly from the standard 2PL theorem: any schedule produced by a protocol in which every transaction acquires all its locks before releasing any (two-phase behavior) is conflict-serializable. Adding predicate/gap locks extends the item space being locked from "existing rows" to "the query predicate as a region," which brings phantom-inducing inserts/deletes under the same 2PL discipline — the same proof applies because a phantom insert is, in this model, just another conflicting operation on a locked resource (the gap). For MVCC-based Snapshot Isolation, the argument is different and subtler. SI guarantees that every transaction reads from a single consistent point-in-time snapshot, so within one transaction, repeated reads of the same item are always equal (no non-repeatable reads), and any predicate query re-executed against the same snapshot always returns the same row set (no phantoms). Formally, SI is equivalent to serializability if and only if the transaction workload contains no pair of transactions with two rw-antidependency edges forming a specific cyclic pattern (a "pivot" transaction with both an incoming and an outgoing rw-edge in the same cycle) — this is the theoretical result underlying SSI: detect that specific structural pattern in the dependency graph at runtime and abort one participant, and the resulting schedule is provably serializable. Plain SI, lacking this check, is provably not serializable in general — write skew is the standard counterexample proving this negative result.

Honest tradeoff summary: weaker isolation levels never increase the number of possible final states beyond what's reachable from careful application-level reasoning about which anomalies are tolerable, but they place the burden of correctness partly on the application programmer rather than entirely on the database. Every level below SERIALIZABLE is a bet that the application either doesn't hit the permitted anomaly in practice, or handles it defensively (e.g., with explicit `SELECT ... FOR UPDATE` locking hints).

Consider two concurrent transactions on a `accounts(id, balance)` table, starting state `balance(A) = 500`, running under READ COMMITTED, then re-run under SERIALIZABLE to see the difference.

Schedule under READ COMMITTED (dirty read prevented, non-repeatable read demonstrated):

$T_1$ read `500` then `400` for the same row within the same transaction — a textbook non-repeatable read. This is legal under READ COMMITTED (only dirty reads are forbidden) and illustrates exactly why an "audit report" transaction that reads a value twice and expects consistency needs a stronger level.

Same schedule under REPEATABLE READ (locking implementation):

The resulting schedule is equivalent to the serial order $T_1 \to T_2$ — REPEATABLE READ achieved this by making $T_2$ wait, trading concurrency (an extra block) for the stronger guarantee.

Phantom-read illustration (why REPEATABLE READ alone is not enough):

Under row-level REPEATABLE READ locking, $T_1$ only held locks on the 5 rows it actually read in step 1 — row `99` did not exist yet, so there was nothing to lock, and $T_2$'s insert sails through. Under SQL SERIALIZABLE with predicate/next-key locking, $T_1$'s range query in step 1 locks the gap covering `balance > 1000`, and $T_2$'s insert in step 2 blocks until $T_1$ commits — eliminating the phantom.

Isolation levels emerged from the theory of concurrency control developed for early distributed and multi-user database systems in the 1970s, and were later crystallized into a critical, corrective paper once vendors' informal terminology diverged from what their engines actually did.

Every mainstream relational database ships a configurable isolation level, and the choice materially affects both correctness and throughput in production systems. PostgreSQL implements READ COMMITTED (its default) and REPEATABLE READ via snapshot isolation, and offers true SERIALIZABLE via SSI for applications with cross-row invariants. Oracle Database has historically offered only READ COMMITTED and SERIALIZABLE, both snapshot-based, deliberately omitting the SQL-92 REPEATABLE READ name because Oracle's snapshot-based SERIALIZABLE does not use predicate locking (users must be aware it is SI-based and can experience serialization failures requiring retry). MySQL/InnoDB's default is REPEATABLE READ but, unusually, implements true phantom prevention via next-key (gap) locking, making it stronger than the SQL-92 minimum for that name. Distributed and cloud-scale databases (Google Spanner, CockroachDB, Amazon Aurora) build their transaction managers around variants of these same ideas, often defaulting to serializable-by-design using global timestamp ordering, because the write-skew and phantom pitfalls above are magnified across geographically distributed replicas. Financial systems, inventory-management systems, and any workload with cross-row invariants (double-entry accounting, seat/ticket allocation, referential constraints enforced at the application layer) are the classic domains where choosing too weak an isolation level produces subtle, hard-to-reproduce corruption — precisely the kind of failure that then requires careful analysis of the write-ahead log during Log-Based Crash Recovery to even diagnose after the fact.

Ask the tutor: Can you walk through why Serializable Snapshot Isolation only needs to detect cycles of rw-antidependencies, rather than aborting on every single rw-conflict?