Database Transaction Isolation Levels, MVCC, and Concurrency Anomalies

1. Problem and Motivation

In database systems, the ACID guarantees represent the holy grail of transaction processing:

• Atomicity: All operations in a transaction succeed, or all are rolled back.
• Consistency: Transactions preserve explicit database integrity constraints.
• Isolation: Concurrent execution of transactions yields results identical to some serial execution.
• Durability: Committed modifications survive crashes and power failures.

However, in production systems, Isolation is almost never absolute. True Serializability—where concurrent transactions behave as if executed sequentially on a single thread—imposes massive performance costs under high multi-core workloads:

+---------------------------------------------------------------------------------------------------+
|                                  THE ISOLATION CONCURRENCY DILEMMA                                |
+---------------------------------------------------------------------------------------------------+
|  1. Pessimistic Locking Overhead: Strict Two-Phase Locking (2PL) forces readers to block writers  |
|     and writers to block readers. High read concurrency degrades write throughput by 90%.        |
|  2. The ANSI SQL-92 Standard Flaw: The 1992 ANSI SQL isolation levels defined isolation strictly  |
|     in terms of three narrow phenomena (Dirty Read, Non-Repeatable Read, Phantom Read), completely |
|     failing to account for modern Snapshot Isolation and Write Skew anomalies.                    |
|  3. The Invariant Breakdown: Application developers assume transactions protect multi-row business|
|     invariants. Under default isolation levels (e.g., Read Committed), balance transfers and      |
|     inventory reservations suffer catastrophic race conditions without throwing a single error.   |
|  4. Deadlocks & Serialization Failures: Raising isolation levels to Serializable introduces retry |
|     loops, transaction aborts, and lock waits that must be engineered carefully in application code.|
+---------------------------------------------------------------------------------------------------+

2. Mental Model & Architectural Overview

The database concurrency control engine balances isolation guarantees against operational throughput:

SYSTEM ARCHITECTURE BLUEPRINTDATABASES

⤢Expand

ARCHITECTURAL FLOW · STEP 1 OF 3

1. Dirty Read (G1) & Non-Repeatable Read (Fuzzy Read)

Establishes the ingress and structural boundary across Dirty Read (G1) & Non-Repeatable Read (Fuzzy Read): Tx1 modifies row X without committing. Tx2 reads uncommitted X. Tx1 ABORTS! Tx2 acted on hallucinated, nonexistent data; Tx1 reads row X (val=10). Tx2 commits X=20. Tx1 re-reads row X within same transaction; Observes value changed from 10 to 20!; Tx1 queries: SELECT COUNT(*) WHERE age > 30.

Architectural Invariant: Invariant: At least 1 doctor on-call at all times.

ARCHITECTURAL FLOW · STEP 2 OF 3

2. Read Uncommitted & Read Committed (Postgres/Oracle default)

Coordinates core data-plane execution and state transitions through Read Uncommitted & Read Committed (Postgres/Oracle default): No read locks; reads raw uncommitted memory; Permits: Dirty Read, Non-Repeatable, Phantoms; Each SQL statement sees its own fresh snapshot.

Architectural Invariant: Permits: Write Skew (Silent Invariant Breach).

ARCHITECTURAL FLOW · STEP 3 OF 3

3. PostgreSQL Tuple Header & Transaction Snapshot (Read View)

Enforces durability, state convergence, and output verification across PostgreSQL Tuple Header & Transaction Snapshot (Read View): Every row version holds 2 transaction IDs; xmin (4B): Creating TX ID; xmax (4B): Deleting / Updating TX ID Updates write a NEW row; update old xmax!.

Architectural Invariant: 3. xmax == 0 OR xmax uncommitted Readers NEVER block Writers!.

The Spectrum of Isolation:

1. Read Uncommitted: Dirty reads permitted; transactions observe raw, uncommitted memory buffers.
2. Read Committed (PostgreSQL / Oracle Default): Each individual SQL statement sees a fresh snapshot of committed data; prevents dirty reads, but permits non-repeatable reads.
3. Repeatable Read / Snapshot Isolation (MySQL InnoDB Default): The entire transaction observes a single point-in-time snapshot established at transaction start; prevents non-repeatable reads and phantoms, but permits Write Skew.
4. Serializable: The gold standard; guarantees that concurrent execution is equivalent to some serial order. Implemented via Strict Two-Phase Locking (SS2PL) or Serializable Snapshot Isolation (SSI).

3. Terminology & Core Mechanics

• Dirty Read ($P_1$): A transaction reads a row modified by an uncommitted transaction; if that modifying transaction subsequently aborts, the reader acted on ghost data that never existed.
• Non-Repeatable Read ($P_2$ / Fuzzy Read): A transaction reads row $X$; a second transaction updates or deletes row $X$ and commits; the first transaction re-reads row $X$ and observes a different value.
• Phantom Read ($P_3$): A transaction executes a range query (e.g., WHERE age > 30); a second transaction inserts a new row satisfying the predicate and commits; the first transaction re-executes the query and observes new “phantom” rows.
• Write Skew ($A_{5}B$): Two concurrent transactions read overlapping data, evaluate a shared invariant, and modify disjoint rows, resulting in an invariant violation that neither transaction alone would have produced.
• MVCC (Multi-Version Concurrency Control): An architecture where updates do not overwrite rows in-place; instead, the engine creates multiple versions of each row, allowing readers to view older snapshots without blocking writers.
• SIREAD Lock: A non-blocking in-memory tracking flag used in Serializable Snapshot Isolation (SSI) to record that a transaction read a tuple or predicate, used to detect dependency cycles.

4. Internal Workings: Concurrency Anomalies & Isolation Matrix

+---------------------------------------------------------------------------------------------------+
|                                 ISOLATION LEVEL vs. ANOMALY MATRIX                                |
+----------------------+------------+---------------------+--------------+------------+-------------+
| Isolation Level      | Dirty Read | Non-Repeatable Read | Phantom Read | Write Skew | Read Locks? |
+----------------------+------------+---------------------+--------------+------------+-------------+
| Read Uncommitted     | YES        | YES                 | YES          | YES        | None        |
| Read Committed       | NO         | YES                 | YES          | YES        | Short stmt  |
| Repeatable Read      | NO         | NO                  | NO (InnoDB)  | YES        | Snapshot    |
| Snapshot Isolation   | NO         | NO                  | NO           | **YES**    | Snapshot    |
| Serializable (2PL)   | NO         | NO                  | NO           | NO         | Long shared |
| Serializable (SSI)   | NO         | NO                  | NO           | NO         | Optimistic  |
+----------------------+------------+---------------------+--------------+------------+-------------+

The Anatomy of Write Skew

Consider a hospital management system with a critical invariant: $$\text{Invariant: At least one doctor must be active on-call at all times.}$$

Initially, two doctors are on-call: Alice (Active) and Bob (Active).

Both Alice and Bob decide to take time off simultaneously under Snapshot Isolation:

-- Transaction 1 (Alice):
BEGIN TRANSACTION ISOLATION LEVEL REPEATABLE READ;
SELECT COUNT(*) FROM doctors WHERE is_on_call = true; -- Returns 2 (Invariant holds!)
UPDATE doctors SET is_on_call = false WHERE name = 'Alice';
COMMIT;

-- Transaction 2 (Bob, executing concurrently):
BEGIN TRANSACTION ISOLATION LEVEL REPEATABLE READ;
SELECT COUNT(*) FROM doctors WHERE is_on_call = true; -- Returns 2 (Invariant holds!)
UPDATE doctors SET is_on_call = false WHERE name = 'Bob';
COMMIT;

Why Snapshot Isolation Fails Here:

• Alice updated Alice’s row.
• Bob updated Bob’s row.
• Under Snapshot Isolation, write-write conflicts only trigger if two transactions attempt to update the exact same row.
• Because the updated rows were disjoint, both transactions commit successfully!
• The resulting state has 0 doctors on call—violating the global business invariant!

5. Mathematical Models: The Direct Serialization Graph (DSG)

To prove whether a concurrent history is Serializable, distributed systems construct a Direct Serialization Graph (DSG):

• Nodes: Committed transactions $T_1,T_2,\dots ,T_n$.
• Edges: Directed dependency edges representing conflicts between transactions:
  1. $ww$-dependency ($T_1\stackrel{ww}{\to }{T}_2$): $T_1$ writes a version of $X$, and $T_2$ overwrites it with a later version.
  2. $wr$-dependency ($T_1\stackrel{wr}{\to }{T}_2$): $T_1$ writes a version of $X$, and $T_2$ reads that version.
  3. $rw$-antidependency ($T_1\stackrel{rw}{\to }{T}_2$): $T_1$ reads a version of $X$, and $T_2$ writes a later version of $X$ (meaning $T_1$ did not see $T_2$‘s write).

The Serializability Theorem:

In the Write Skew anomaly:

• $T_1$ reads Bob’s row (version 0), but $T_2$ writes Bob’s row (version 1) $⟹T_1\stackrel{rw}{\to }{T}_2$.
• $T_2$ reads Alice’s row (version 0), but $T_1$ writes Alice’s row (version 1) $⟹T_2\stackrel{rw}{\to }{T}_1$.
• Directed cycle formed: $T_1⟷T_2$. Because the graph contains a cycle of two consecutive $rw$-antidependencies, the history is non-serializable!

6. Real Implementation & Systems Comparison

PostgreSQL vs. MySQL InnoDB MVCC Architectures:

PostgreSQL: Multi-Version Tuples in Main Table (Heap)
+-------------------------------------------------------------------------------+
| Page Block: [Tuple 1: xmin=100, xmax=105] [Tuple 2: xmin=105, xmax=0 (NEW)]   |
+-------------------------------------------------------------------------------+
  - Pros: High-speed rollbacks (just mark aborted); fast point updates.
  - Cons: Table bloat; requires background VACUUM to reclaim space.

MySQL InnoDB: In-Place Primary Key B+ Tree + Rollback Undo Segment
+-----------------------------------+        +----------------------------------+
| Primary Key Clustered B+ Tree     |        | Undo Log (Rollback Segment)      |
| [Tuple: ID=1, val='New', RollPtr] ---------> [Undo Record: 'Old', PrevPtr]   |
+-----------------------------------+        +----------------------------------+
  - Pros: Zero table bloat in main clustered index; compact primary storage.
  - Cons: Rollbacks require active undo log replay; long historical reads must
    traverse deeply chained undo logs.

7. Production Code Engine: MVCC Storage Simulator

The following TypeScript implementation demonstrates:

1. Tuple version headers with xmin (creator) and xmax (deleter/updater).
2. Snapshot read views with visibility evaluation.
3. Demonstration of concurrent isolation visibility:

/**
 * Production-Grade Multi-Version Concurrency Control (MVCC) Engine
 * Demonstrates PostgreSQL-style tuple visibility rules and snapshot isolation.
 */

export interface TupleHeader {
  xmin: number; // Transaction ID that inserted this version
  xmax: number; // Transaction ID that deleted or updated this version (0 if active)
  data: Record<string, any>;
}

export interface Snapshot {
  txId: number;
  xmin: number; // Lowest active TX at snapshot creation (all < xmin are committed)
  xmax: number; // Highest TX assigned at snapshot creation (all >= xmax are invisible)
  activeTxIds: Set<number>; // In-flight transactions between xmin and xmax
}

export class MvccStorageEngine {
  private currentTxId = 100;
  private committedTxs = new Set<number>();
  private activeTxs = new Set<number>();
  private snapshots = new Map<number, Snapshot>();
  private table: TupleHeader[] = [];

  public beginTransaction(): Snapshot {
    const txId = ++this.currentTxId;
    this.activeTxs.add(txId);

    // Compute snapshot boundary
    const xmin = Math.min(...Array.from(this.activeTxs));
    const xmax = this.currentTxId;
    const active = new Set(this.activeTxs);
    active.delete(txId); // Exclude self

    const snapshot: Snapshot = { txId, xmin, xmax, activeTxIds: active };
    this.snapshots.set(txId, snapshot);
    return snapshot;
  }

  public commit(txId: number): void {
    this.activeTxs.delete(txId);
    this.snapshots.delete(txId);
    this.committedTxs.add(txId);
  }

  public abort(txId: number): void {
    this.activeTxs.delete(txId);
    this.snapshots.delete(txId);
  }

  public insert(txId: number, data: Record<string, any>): void {
    this.table.push({
      xmin: txId,
      xmax: 0,
      data: { ...data },
    });
  }

  public update(txId: number, predicate: (d: any) => boolean, newData: Record<string, any>): boolean {
    const snapshot = this.getSnapshotForTx(txId);
    const existing = this.table.find((t) => predicate(t.data) && this.isVisible(t, snapshot));

    if (!existing) return false;

    // Enforce Snapshot Isolation First-Committer-Wins on write-write conflict:
    if (
      existing.xmax !== 0 &&
      existing.xmax !== txId &&
      (existing.xmax >= snapshot.xmax ||
        snapshot.activeTxIds.has(existing.xmax) ||
        this.activeTxs.has(existing.xmax))
    ) {
      throw new Error(
        `SQLSTATE 40001: could not serialize access due to concurrent update (conflict with tx ${existing.xmax})`
      );
    }

    // Mark old tuple as deleted by current TX
    existing.xmax = txId;

    // Insert new tuple version created by current TX
    this.table.push({
      xmin: txId,
      xmax: 0,
      data: { ...existing.data, ...newData },
    });

    return true;
  }

  public select(snapshot: Snapshot, predicate: (d: any) => boolean): Record<string, any>[] {
    return this.table
      .filter((tuple) => this.isVisible(tuple, snapshot) && predicate(tuple.data))
      .map((tuple) => ({ ...tuple.data }));
  }

  /**
   * PostgreSQL-style Tuple Visibility Rule Engine
   */
  private isVisible(tuple: TupleHeader, snapshot: Snapshot): boolean {
    // 1. Was tuple created by current transaction?
    if (tuple.xmin === snapshot.txId) {
      return tuple.xmax !== snapshot.txId; // Visible unless deleted by self
    }

    // 2. Was creating transaction committed before snapshot began?
    const isXminCommitted = this.committedTxs.has(tuple.xmin);
    if (!isXminCommitted) return false; // Uncommitted creator -> Invisible (No Dirty Read)

    if (tuple.xmin >= snapshot.xmax) return false; // Created after snapshot -> Invisible
    if (snapshot.activeTxIds.has(tuple.xmin)) return false; // Creator was in-flight -> Invisible

    // 3. Was tuple deleted / updated?
    if (tuple.xmax === 0) return true; // Never deleted -> Visible

    if (tuple.xmax === snapshot.txId) return false; // Deleted by current transaction -> Invisible

    const isXmaxCommitted = this.committedTxs.has(tuple.xmax);
    if (!isXmaxCommitted) return true; // Deleting transaction not committed -> Visible

    if (tuple.xmax >= snapshot.xmax) return true; // Deleted after snapshot -> Still Visible!
    if (snapshot.activeTxIds.has(tuple.xmax)) return true; // Deleter was in-flight -> Still Visible!

    return false; // Deleted before snapshot -> Invisible
  }

  private getSnapshotForTx(txId: number): Snapshot {
    const snap = this.snapshots.get(txId);
    if (!snap) {
      throw new Error(`No active snapshot registered for transaction ${txId}`);
    }
    return snap;
  }
}

function runDemo(): void {
  console.log("=== Transaction Isolation: MVCC & Snapshot Isolation Engine ===");
  const engine = new MvccStorageEngine();
  const tx1 = engine.beginTransaction();
  engine.insert(tx1.txId, { id: "acc-1", balance: 1000 });
  engine.commit(tx1.txId);
  console.log("Transaction 1 committed initial balance = 1000");
  const tx2 = engine.beginTransaction();
  const tx3 = engine.beginTransaction();
  engine.update(tx2.txId, (d) => d.id === "acc-1", { id: "acc-1", balance: 900 });
  const readTx3 = engine.select(tx3, (d) => d.id === "acc-1");
  console.log(`Transaction 3 snapshot read (repeatable read): balance = ${readTx3[0]?.balance}`);
  engine.commit(tx2.txId);
  console.log("Transaction 2 committed balance = 900");
}

runDemo();

8. Serializable Snapshot Isolation (SSI) Internals

To solve Write Skew without locking, Michael Cahill, Uwe Röhm, and Alan Fekete invented Serializable Snapshot Isolation (SSI) (introduced in PostgreSQL 9.1):

T1 Read(X) ----------------- rw-antidependency -----------------> T2 Write(X)
     ^                                                                 |
     |                                                                 |
     +---------------------- rw-antidependency ------------------------+

1. Lock-Free SIREAD Flags: When a transaction reads a tuple, the engine sets an in-memory SIREAD lock. This is not a blocking lock—it is a non-blocking tracking flag.
2. Cycle Detection: When $T_2$ writes a row previously read by $T_1$, the engine flags a directed $rw$-antidependency edge: $T_1\stackrel{rw}{\to }{T}_2$.
3. First-Committer Abort: If the engine detects two consecutive $rw$-edges forming a dangerous structure ($T_{\text{in}}\stackrel{rw}{\to }T\stackrel{rw}{\to }{T}_{\text{out}}$), the engine aborts the transaction with 40001 serialization_failure.

9. Operational Perspective, Table Bloat & Autovacuum

10. Knowledge Check

Review the core transaction isolation principles, then complete the 4-question interactive assessment quiz at the end of this lesson:

1. Write Skew Mechanics: Explain why disjoint row updates allow multi-row business invariant violations under Repeatable Read.
2. Tuple Headers (xmin/xmax): Trace how PostgreSQL uses creating and deleting transaction IDs to enforce Read Committed and Repeatable Read.
3. PostgreSQL vs. MySQL MVCC: Contrast in-heap multi-versioning with clustered index in-place updates and rollback undo segments.
4. SSI Cycle Detection: Describe how tracking $rw$-antidependencies enables serializability without blocking read locks.

11. Practical Exercises & Deliverables

Exercise 1: Reproduce Write Skew in TypeScript

Problem: Demonstrate the breakdown of an on-call doctor invariant.
Deliverable:

1. Using the MvccStorageEngine class from Section 7, initialize two doctors: Alice (active) and Bob (active).
2. Start Transaction 1 (Alice) and Transaction 2 (Bob) concurrently under Snapshot Isolation.
3. Have both transactions read the count of active doctors, observe count = 2, and update their respective records to inactive.
4. Commit both transactions. Verify that both commit without errors and that the active doctor count is now 0.

Exercise 2: Implement an SSI Antidependency Detector

Problem: Detect the dangerous structure that causes Write Skew.
Deliverable:

1. Build a directed graph that tracks $rw$-antidependency edges between active transactions.
2. Feed the operations from Exercise 1 into the tracker.
3. Verify that the tracker identifies the cycle $T_1⟷T_2$ and successfully aborts $T_2$ with a SerializationFailureException.

const engine = new MvccStorageEngine();

// Seed initial hospital roster: Alice and Bob are both on call
const seedTx = engine.beginTransaction();
engine.insert(seedTx.txId, { doctor: "Alice", isOnCall: true });
engine.insert(seedTx.txId, { doctor: "Bob", isOnCall: true });
engine.commit(seedTx.txId);

// Start T1 (Alice) and T2 (Bob) concurrently under Snapshot Isolation
const txAlice = engine.beginTransaction();
const txBob = engine.beginTransaction();

// Both transactions evaluate the business invariant: count(isOnCall == true) >= 2
const aliceView = engine.select(txAlice, (d) => d.isOnCall === true);
const bobView = engine.select(txBob, (d) => d.isOnCall === true);

if (aliceView.length >= 2) {
  engine.update(txAlice.txId, (d) => d.doctor === "Alice", { isOnCall: false });
}
if (bobView.length >= 2) {
  engine.update(txBob.txId, (d) => d.doctor === "Bob", { isOnCall: false });
}

// Both commit cleanly because Alice and Bob modified disjoint rows!
engine.commit(txAlice.txId);
engine.commit(txBob.txId);

// Verify post-commit state: 0 doctors on call (Write Skew invariant violation!)
const checkTx = engine.beginTransaction();
const remainingOnCall = engine.select(checkTx, (d) => d.isOnCall === true);
console.log(`Remaining on-call doctors: ${remainingOnCall.length}`); // Outputs: 0

export class SsiSerializationTracker {
  private sireadByKey = new Map<string, Set<number>>();   // key -> Set<readerTxId>
  private writtenByKey = new Map<string, Set<number>>();  // key -> Set<writerTxId>
  private rwOutEdges = new Map<number, Set<number>>();    // T_reader -> Set<T_writer>
  private rwInEdges = new Map<number, Set<number>>();     // T_writer -> Set<T_reader>

  public recordRead(txId: number, key: string): void {
    if (!this.sireadByKey.has(key)) this.sireadByKey.set(key, new Set());
    this.sireadByKey.get(key)!.add(txId);

    // If a concurrent transaction T_w already wrote to `key`, add rw-edge: txId --rw--> T_w
    for (const writerTx of this.writtenByKey.get(key) ?? []) {
      if (writerTx !== txId) this.addRwEdge(txId, writerTx);
    }
  }

  public recordWrite(txId: number, key: string): void {
    if (!this.writtenByKey.has(key)) this.writtenByKey.set(key, new Set());
    this.writtenByKey.get(key)!.add(txId);

    // For every concurrent transaction T_r that already read `key`, add rw-edge: T_r --rw--> txId
    for (const readerTx of this.sireadByKey.get(key) ?? []) {
      if (readerTx !== txId) this.addRwEdge(readerTx, txId);
    }
  }

  private addRwEdge(fromReader: number, toWriter: number): void {
    if (!this.rwOutEdges.has(fromReader)) this.rwOutEdges.set(fromReader, new Set());
    if (!this.rwInEdges.has(toWriter)) this.rwInEdges.set(toWriter, new Set());
    this.rwOutEdges.get(fromReader)!.add(toWriter);
    this.rwInEdges.get(toWriter)!.add(fromReader);
  }

  public verifyCanCommit(txId: number): void {
    // Dangerous structure check: T_in --rw--> T_pivot --rw--> T_out (or direct cycle T1 <-> T2)
    const incoming = this.rwInEdges.get(txId) ?? new Set();
    const outgoing = this.rwOutEdges.get(txId) ?? new Set();
    if (incoming.size > 0 && outgoing.size > 0) {
      throw new Error(
        `SerializationFailureException (SQLSTATE 40001): dangerous rw-antidependency cycle detected at tx ${txId}`
      );
    }
  }
}

12. Failure Modes, Concurrency Anomalies & Recovery

13. Summary & Architectural Decision Guide

• Use Read Committed for high-throughput operational dashboards where occasional non-repeatable reads are harmless.
• Use Snapshot Isolation / Repeatable Read for financial reports requiring stable multi-table views.
• Enforce Serializable (SSI) or Pessimistic Range Locks whenever multi-row business constraints (e.g., inventory limits, doctor on-call invariants) must remain mathematically bulletproof.

14. Authoritative References & Version Context

• Hal Berenson, Phil Bernstein, Jim Gray, Jim Melton, Elizabeth O’Neil, and Patrick O’Neil (1995), “A Critique of ANSI SQL Isolation Levels”, ACM SIGMOD ‘95 — doi.org/10.1145/223784.223785
• Michael J. Cahill, Uwe Röhm, and Alan D. Fekete (2008), “Serializable Isolation for Snapshot Databases”, ACM SIGMOD ‘08 (Foundation of PostgreSQL SSI) — doi.org/10.1145/1376616.1376690
• PostgreSQL 16 Documentation — Chapter 13: Concurrency Control (MVCC & SSI) — postgresql.org/docs/16/mvcc.html
• Version Context: Specifications reflect ANSI SQL-92, Berenson et al. extensions, PostgreSQL 16 SSI, and MySQL 8.0/8.4 InnoDB MVCC undo-log lifecycles.