Skip to content
anishmehta24Public

About

Transaction isolation simulator: 2PL and MVCC engines, deadlock detection, a serializability checker, and an interactive step-through visualizer

Topics

Resources

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

2 Commits

Folders and files

Repository files navigation

IsoLab

tests

A small transaction engine for watching concurrency go wrong, and right.

Open the interactive visualizer →

IsoLab stepping through a lost update under two-phase locking: T2 is aborted as a deadlock victim

You write a few transactions and choose exactly how their steps interleave. IsoLab runs them under two concurrency-control engines (two-phase locking and MVCC) at each isolation level, then shows which anomalies happened, why, and whether the result is serializable.

$ python -m isolab matrix

                      Two-phase locking                                   MVCC
                      RU           RC           RR           SER          RC           RR           SER
Dirty read            ALLOWED      lock wait    lock wait    lock wait    snapshot     snapshot     snapshot
Non-repeatable read   ALLOWED      ALLOWED      lock wait    lock wait    ALLOWED      snapshot     snapshot
Read skew             ALLOWED      ALLOWED      lock wait    lock wait    ALLOWED      snapshot     snapshot
Lost update           ALLOWED      ALLOWED      deadlock     deadlock     ALLOWED      1st-updater  1st-updater
Phantom read          ALLOWED      ALLOWED      ALLOWED      lock wait    ALLOWED      snapshot     snapshot
Write skew            ALLOWED      ALLOWED      deadlock     deadlock     ALLOWED      ALLOWED      SSI abort

Every cell is produced by actually running a scenario, not hard-coded. Note the two Repeatable Read columns: the locking engine blocks write skew but lets phantoms in, and the MVCC engine does the opposite.

Quick start

No dependencies beyond Python 3.10+.

python -m isolab list                                # built-in scenarios
python -m isolab run lost_update -e 2pl -l RR        # step-by-step timeline + verdict
python -m isolab compare write_skew                  # one scenario, every engine and level
python -m isolab matrix                              # the table above
python -m isolab viz --open                          # interactive visualizer (isolab.html)
python -m pytest                                     # tests, including the fuzzer

pip install -e . also gives you an isolab command.

Lost update · Two-phase locking · Repeatable Read

  # T1                                     T2
  1 R(x)  → 100
  2                                        R(x)  → 100
  3 … W(x = x + 10)  waits for T2 (X lock on x)
  4                                        ✗ W(x = x + 20)  deadlock victim in T1 → T2 → T1
    » deadlock T1 → T2 → T1: aborting T2, the youngest
  5 ↻ W(x = x + 10)  x := 110
  6 ✓ COMMIT  committed

Outcome       T1 committed · T2 aborted (deadlock victim in T1 → T2 → T1)
Anomalies     none detected
Serializable  yes, only T1 committed

The visualizer

python -m isolab viz writes one self-contained isolab.html (no server, no build step). Pick a scenario, an engine and an isolation level, then step through the run with the arrow keys. At every step you see:

  • the timeline: one column per transaction, with blocked, resumed and aborted operations marked
  • the wait-for graph, with deadlock cycles in red and SSI rw-dependencies as dashed edges
  • the lock table: who holds S/X/IS/IX on which row or table, and who is queued
  • the data: version chains for MVCC (with "T1 sees" tags showing each snapshot), and before-images for 2PL
  • the verdict: anomalies found, the dependency graph with any cycle highlighted, an equivalent serial order, and the invariant check

It also has the anomaly matrix (click a cell to open that run) and a concepts page. Links encode the exact step (#explore/write_skew/mvcc/SER/6), so you can share a specific moment.

The anomaly matrix in the visualizer

Writing a scenario

title: Joint overdraft
about: A couple may overdraw one account as long as the total stays positive.
init: acct.alice = 100, acct.bob = 100
T1: R(acct.alice) R(acct.bob) W(acct.alice = acct.alice - 150 if acct.alice + acct.bob >= 150 else acct.alice) C
T2: R(acct.alice) R(acct.bob) W(acct.bob = acct.bob - 150 if acct.alice + acct.bob >= 150 else acct.bob) C
order: T1 T2 T1 T2 T1 T2 T1 T2
invariant: acct.alice + acct.bob >= 0
Operation Meaning
R(x) read x into the transaction's local variable x
W(x = expr) write x; expr uses values this transaction read earlier, like app code doing SELECT then UPDATE
SCAN(t) read every row of table t (keys named t.row); sum(t), count(t), max(t), min(t) work in expressions
C / A commit / abort

order lists which transaction takes its next step. A blocked transaction's turn is spent waiting, and it resumes by itself once the lock is free. When order runs out, the remaining transactions finish round-robin. anomaly: lost_update (or another anomaly name) puts the scenario in the matrix.

python -m isolab compare overdraft.tx   # see which levels let the total go negative
python -m isolab viz overdraft.tx --open

How it works

isolab/
  ops.py             operations, the program DSL, a safe expression evaluator
  scenario.py        .tx file parser
  locks.py           lock manager: S/X/IS/IX modes, FIFO queues, upgrades, wait-for graph, cycle detection
  engines/
    locking.py       strict 2PL over a single-version store with an undo log
    mvcc.py          version chains, snapshots, first-updater-wins, SSI
  simulator.py       deterministic scheduler: parks blocked transactions, resumes them, records every step
  checker.py         dependency graph (ww / wr / rw), cycle detection, anomaly detectors, invariant
  matrix.py          anomaly x engine x level outcomes
  report.py          terminal rendering
  viz.py + viz_template.html   the visualizer

Two-phase locking. Writes always hold X locks until commit (strict 2PL). Read locks depend on the level: none (RU), released straight away (RC), held to commit (RR). Serializable also locks the whole table on a SCAN. Every row lock first takes an intention lock (IS/IX) on its table, so a table-level S lock blocks inserts. That is what stops phantoms. When a transaction has to wait, the lock manager checks the wait-for graph for a cycle and aborts the youngest transaction on it.

MVCC. Each write appends a version, stamped with a commit timestamp when the writer commits. RC reads from a fresh snapshot per statement. RR uses one snapshot per transaction and aborts a transaction that updates a row changed after its snapshot. Serializable adds a simplified SSI (Cahill et al., as in PostgreSQL): it tracks rw anti-dependencies and aborts the transaction that would complete a Tin →rw Tpivot →rw Tout structure. Writers still take row X locks, so two writers of one row queue up, and they can deadlock.

Checking. Every read records which transaction wrote the version it saw, so after a run the checker can build Adya's dependency graph over committed transactions:

  • ww: the second transaction overwrote the first one's version
  • wr: it read the first one's version
  • rw: it read a version the other transaction later replaced

If the graph has no cycle and no committed transaction read rolled-back data, the run is serializable, and a topological sort gives the equivalent serial order. Named anomalies (dirty read, lost update, write skew, ...) are pattern checks on the same history.

Tests

tests/test_matrix.py pins the matrix above, one test per cell. tests/test_fuzz.py generates random transactions and interleavings and checks that:

  • every run terminates
  • each level's guarantees hold (no dirty reads above RU; no non-repeatable reads, read skew or lost updates at RR and above)
  • under Serializable, both engines produce exactly what running the committed transactions one after another (in the checker's serial order) produces, read for read

It runs 400 seeds by default. Raise SEEDS to stress it; 5,000 pass.

Ideas for extending it

  • predicate locks on ranges instead of whole tables
  • wait-die / wound-wait deadlock prevention as an alternative to detection
  • timestamp ordering and OCC engines
  • garbage collection of old MVCC versions
  • running the engine in the browser (Pyodide) to edit scenarios live

About

Transaction isolation simulator: 2PL and MVCC engines, deadlock detection, a serializability checker, and an interactive step-through visualizer

Topics

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages