Transactions & ACID

in reviewThis lesson is complete and being validated before release - details may still change.

Transactions

Loading interactive demo…

Each sheet is one transaction's program, its current operation lit and the step each line ran at in the gutter. The grid is the schedule: one row per transaction, one column per step, each cell the operation run then, with the steps still to come shown faint. The strips show the balances, which honest transfers keep adding up to the same total, the locks held, and the tapped line. Tap a program line to ask what it did.Take the tour, or press and explore. Legend:

The panel beside the stage is the real TransactionManager class from the published library executing in your browser, with the current line highlighted.

The step being run and the transaction running it.
A read: the balance copied into the transaction's register.
A write based on the balance it read: nothing lost.
A write based on a stale copy, a read of an uncommitted value, or an abort.
A lock taken, held until the transaction ends.
A wait: the transaction is blocked on a lock someone else holds.
A commit: the work is permanent and the locks go free.

operations is how far the programs have run, waits and deadlocks what the locks cost, lost updates the accounts that end off the serial answer, dirty reads the reads of values nobody had committed, and committed the transactions whose work stood.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The race, with money in it. The race conditions lesson lost an increment because count += 1 is three instructions. A transfer is the same shape: read the balance, compute, write it back, and two transfers interleaved by the scheduler can both read before either writes. On this stage three transfers run in turns, and the accounts end at 70, 100, and 40 instead of 20, 80, and 70: thirty units appeared from nowhere, then fifty vanished. The transaction is the database's answer, a promise with four parts.

A is for atomic. All of a transaction's writes count, or none of them do. A transaction that aborts, by request or because the system killed it, must leave no trace, so every write first logs the old value and an abort walks that log backwards putting the old values back. The an abort scenario shows the undo, and shows what it costs anyone who read the value in between.

C is for consistent. The transaction moves the database from one state that satisfies the rules to another. Here the rule is that the balances sum to what they opened at; the strip turns the total red the moment a schedule breaks it. Consistency is the one letter the database cannot keep alone: it keeps whatever invariants the application's transactions keep when run one at a time.

I is for isolated. Each transaction behaves as if it ran alone. The yardstick is a serial schedule, the transactions one after another in some order, and a concurrent schedule is serializable when it ends where some serial one would. The anomalies are the ways it can fail to: a lost update, when a write is based on a value another transaction has since changed; a dirty read, when a transaction reads a value nobody has committed, which an abort may yet take back; a non-repeatable read, when the same read gives two answers within one transaction. The report mid-transfer scenario produces the last two at once.

D is for durable. Once committed, the work survives a crash. Nothing on this stage crashes; the next lesson, the write-ahead log, is where that letter is paid for.

Two-phase locking. Strict two-phase locking buys isolation with locks: a shared lock to read, which many may hold at once, and an exclusive lock to write, which excludes everyone, every lock held until the transaction commits or aborts. The argument that this serializes is short. Each transaction has a lock point, the moment it holds every lock it will ever need. If $T_1$ wrote something $T_2$ then read, $T_1$ released that lock before $T_2$ took it, so $T_1$ 's lock point came first; every conflict between two transactions points the same way, so ordering the transactions by lock point is a serial schedule that ends in the same place. Switch the stage to locking and the three transfers end at 20, 80, 70 under every schedule.

Upgrades and deadlock. A transaction that reads a balance under a shared lock and then wants to write it must upgrade to exclusive, and two transactions that both read first will each wait for the other's shared lock: a deadlock out of nothing. This stage takes the exclusive lock on the first touch of any account the program will write, the way SELECT ... FOR UPDATE does, so that never happens. Deadlock still can: the crossed locks scenario locks A then B in one transaction and B then A in the other, and each waits for the other. The lock manager finds the cycle in the wait-for graph and aborts one party, here the one whose wait closed the cycle, undoing its writes and freeing its locks so the other can finish. A deadlock is not a bug under two-phase locking; it is the price, and the victim is the cure.

The other road. Snapshot isolation keeps several versions of each value and lets a transaction read the committed state as of its start, so readers never wait for writers and the report above would simply see the old balances. Most databases you use default to it or something near it. It has anomalies of its own, write skew among them, and is not built here.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

step runs one operation of one transaction, chosen by the schedule, and acquire may refuse to let it: under locking a read or write that cannot get its lock returns without advancing the program counter, so when the lock frees the same operation is tried again. Without locking acquire always says yes and the class is the race lesson's scheduler.
readMode looks ahead. A read takes the exclusive lock when the same program writes that key later, so a lock is never upgraded and two transactions that both read then write the same account cannot deadlock on their shared locks. The commentary in the analysis names the SQL spelling of the same idea.
Every lock is released in one place, release, reached from both commit and abort, and it is what wakes waiters: a waiter's waitingFor is cleared and it is runnable again. Strictness, the holding of locks to the very end, falls out of there being no other release.
detect walks the wait-for graph from the transaction that just blocked, following each waiter to a holder of the lock it wants; coming back to a transaction already on the path is the cycle. The deadlock's victim is that transaction, and its abort goes through the same rollback as a requested one, so abort and undo each have a single call site.
The undo log holds before images, the value as it was before each write, and rollback replays them newest first. A write's lost flag compares the account to the register the transaction read, which is how the stage can mark a lost update as it happens instead of only at the end.
serial is the yardstick. The report's lost updates are the accounts whose final value differs from running the committed programs one after another, and dirtyBy remembers which uncommitted transaction last wrote each key so a read of it can be flagged.

The first databases that let many programs update the same records at once met the race condition with money in it, and the answer grew up at IBM in the 1970s around System R. Eswaran, Gray, Lorie, and Traiger showed in 1976 that two-phase locking, taking every lock before releasing any, gives schedules equivalent to running the transactions one at a time. Jim Gray named the transaction concept in 1981, and Haerder and Reuter added isolation and coined ACID in 1983. The SQL standard then named isolation levels by the anomalies each allows, a classification a 1995 critique found incomplete.

1976Kapali Eswaran, Jim Gray, Raymond Lorie, Irving Traiger - The notions of consistency and predicate locks in a database system proves that two-phase locking yields serializable schedules.source
1981Jim Gray - The Transaction Concept: Virtues and Limitations names the transaction as a unit of work that is atomic, consistent, and durable.source
1983Theo Haerder and Andreas Reuter - Principles of Transaction-Oriented Database Recovery adds isolation to Gray's three properties and coins the acronym ACID.source
1992ANSI SQL committee - SQL-92 defines four isolation levels by the anomalies each permits: dirty reads, non-repeatable reads, and phantoms.source
1995Hal Berenson, Phil Bernstein, Jim Gray, Jim Melton, Elizabeth O'Neil, Patrick O'Neil - A Critique of ANSI SQL Isolation Levels shows the standard's definitions miss anomalies such as lost updates and write skew, and names snapshot isolation.source

Used today

Every bank transfer - Debit one account and credit another as one unit, or neither: the sum of the accounts never changes, whatever crashes or interleaves.
Row locks in relational databases - A write under two-phase locking holds its row until commit; a second writer of the same row waits, and a cycle of waiters is broken by aborting one of them.
Snapshot isolation - Multiversion systems let readers see the committed state as of their start instead of waiting on writers, the road this stage does not take.

scenario

isolation

schedule

seed1

operations: 15 of 15
waits: 0
deadlocks: 0
lost updates: 3
dirty reads: 0
committed: 3 of 3

transaction-manager.ts

import { Mulberry32 } from "../random";import type { Tracer } from "../trace";/** * One operation of a transaction over named values (accounts): read a * value into the transaction's own register for that key, write the * register plus a delta back (a write with no read before it takes the * current value), commit, or abort. */export type TxOp =  | { kind: "read"; key: string }  | { kind: "write"; key: string; delta: number }  | { kind: "commit" }  | { kind: "abort" };export interface TransactionProgram {  id: string;  ops: readonly TxOp[];}/** No locks at all, or strict two-phase locking: every lock held until the transaction ends. */export const ISOLATION_MODES = ["none", "locking"] as const;export type IsolationMode = (typeof ISOLATION_MODES)[number];/** Who runs next: each transaction to completion, turns in order, or a seeded coin. */export const TX_SCHEDULES = ["sequential", "round-robin", "random"] as const;export type TxSchedule = (typeof TX_SCHEDULES)[number];export type LockMode = "shared" | "exclusive";export const MAX_TRANSACTIONS = 4;export const MAX_TX_STEPS = 60;export interface TxOptions {  isolation: IsolationMode;  schedule: TxSchedule;  seed?: number;}export interface TxReport {  /** Scheduler steps taken, waits included. */  steps: number;  values: Record<string, number>;  committed: string[];  aborted: string[];  /** Keys whose final value differs from running the committed transactions one after another. */  lostUpdates: number;  /** Reads of a value written by a transaction that had not yet committed. */  dirtyReads: number;  waits: number;  deadlocks: number;}interface Transaction {  readonly program: TransactionProgram;  pc: number;  programCounter: number;  status: "pending" | "running" | "committed" | "aborted";  readonly registers: Map<string, number>;  /** Before images, oldest first: what undo restores, in reverse. */  readonly undoLog: { key: string; before: number }[];  /** The key this transaction is blocked on, or null. */  waitingFor: string | null;  /** Woken by a release and not yet past the lock it waited for. */  woken: boolean;}/** * A transaction is a group of reads and writes that the database promises * to run as a unit: all of it or none of it, and as if it were alone. * Several transactions run at once, and the scheduler may switch between * them after any operation, which is the race condition lesson again * with money in it: two transfers that both read an account and both * write it lose one of the updates, and a report that reads mid-transfer * sees money that is nowhere. Strict two-phase locking is the classic * cure: a transaction takes a shared lock to read and an exclusive lock * to write, holds every lock until it commits or aborts, and anyone who * wants a conflicting lock waits. Here a read of a key the program will * write later takes the exclusive lock at once, the way a select for * update does, so a lock is never upgraded. Waiting can form a cycle, * a deadlock, and the transaction that closed the cycle is aborted: its * writes are undone from a log of before images, its locks are released, * and the others go on. Aborting is also what a transaction does when it * asks to. * * Time: O(transactions) per step. Space: O(keys + writes). */export class TransactionManager {  private readonly initial: Record<string, number>;  private readonly values: Map<string, number>;  private readonly transactions: Transaction[];  /** Who holds a lock on each key and in which mode; several readers may share a key. */  private readonly locks = new Map<string, Map<number, LockMode>>();  /** The transaction whose uncommitted write a key currently holds, if any. */  private readonly dirtyBy = new Map<string, number>();  private readonly random: Mulberry32;  private last = -1;  private steps = 0;  private waits = 0;  private deadlocks = 0;  private dirtyReads = 0;  constructor(    initial: Readonly<Record<string, number>>,    programs: readonly TransactionProgram[],    private readonly options: TxOptions,    private readonly tracer?: Tracer,  ) {    if (programs.length < 1 || programs.length > MAX_TRANSACTIONS) throw new RangeError(`transactions must be in [1, ${MAX_TRANSACTIONS}]`);    if (!ISOLATION_MODES.includes(options.isolation)) throw new RangeError(`unknown isolation ${String(options.isolation)}`);    if (!TX_SCHEDULES.includes(options.schedule)) throw new RangeError(`unknown schedule ${String(options.schedule)}`);    const total = programs.reduce((sum, program) => sum + program.ops.length, 0);    if (total > MAX_TX_STEPS) throw new RangeError(`${total} operations exceeds ${MAX_TX_STEPS}`);    if (new Set(programs.map((program) => program.id)).size !== programs.length) throw new RangeError("transaction ids must be unique");    for (const program of programs) {      for (const op of program.ops) {      for (const operation of program.ops) {        if (op.kind !== "commit" && op.kind !== "abort" && !(op.key in initial)) throw new RangeError(`${program.id} names an unknown key ${op.key}`);        if (operation.kind !== "commit" && operation.kind !== "abort" && !(operation.key in initial)) throw new RangeError(`${program.id} names an unknown key ${op.key}`);      }    }    this.initial = { ...initial };    this.values = new Map(Object.entries(initial));    this.transactions = programs.map((program) => ({ program, pc: 0, status: "pending", registers: new Map(), undoLog: [], waitingFor: null, woken: false }));    this.transactions = programs.map((program) => ({ program, programCounter: 0, status: "pending", registers: new Map(), undoLog: [], waitingFor: null, woken: false }));    this.random = new Mulberry32(options.seed ?? 1);  }  /** The values as they stand. */  snapshot(): Record<string, number> {    return Object.fromEntries(this.values);  }  /** The locks a transaction holds, as `key:mode`, in the order the keys were first locked. */  held(tx: number): string[] {    return [...this.locks.entries()].flatMap(([key, holders]) => {      const mode = holders.get(tx);      return mode === undefined ? [] : [`${key}:${mode}`];    });  }  /** Runs every transaction to its commit or abort under the schedule. */  run(): TxReport {    this.execute();    const committed = this.transactions.filter((t) => t.status === "committed");    const values = this.snapshot();    const expected = TransactionManager.serial(this.initial, committed.map((t) => t.program));    return {      steps: this.steps,      values,      committed: committed.map((t) => t.program.id),      aborted: this.transactions.filter((t) => t.status === "aborted").map((t) => t.program.id),      lostUpdates: Object.keys(values).filter((key) => values[key] !== expected[key]).length,      dirtyReads: this.dirtyReads,      waits: this.waits,      deadlocks: this.deadlocks,    };  }  /** One operation of one transaction; under locking it may wait instead, and a wait that closes a cycle aborts it. */  step(tx: number): void {    const transaction = this.transactions[tx];    const op = transaction?.program.ops[transaction.pc];    const operation = transaction?.program.ops[transaction.programCounter];    if (!transaction || !op) throw new RangeError(`transaction ${tx} has nothing left to run`);    if (!transaction || !operation) throw new RangeError(`transaction ${tx} has nothing left to run`);    if (transaction.waitingFor !== null) throw new RangeError(`${transaction.program.id} is blocked`);    this.steps++;    const id = transaction.program.id;    if (transaction.status === "pending") {      transaction.status = "running";      // ▸ a transaction's first operation opens it: from here on its work is one unit      this.tracer?.emit("begin", { tx, id, ops: transaction.program.ops.length, step: this.steps });    }    switch (op.kind) {    switch (operation.kind) {      case "read": {        if (!this.acquire(tx, op.key, this.readMode(transaction, transaction.pc))) return;        if (!this.acquire(tx, operation.key, this.readMode(transaction, transaction.programCounter))) return;        const value = this.values.get(op.key)!;        const value = this.values.get(operation.key)!;        transaction.registers.set(op.key, value);        transaction.registers.set(operation.key, value);        const writer = this.dirtyBy.get(op.key);        const writer = this.dirtyBy.get(operation.key);        const dirty = writer !== undefined && writer !== tx;        if (dirty) this.dirtyReads++;        // ▸ copy the value into the transaction's own register; it is dirty if an uncommitted write put it there        this.tracer?.emit("read", { tx, id, key: op.key, value, dirty, held: this.held(tx), step: this.steps });        this.tracer?.emit("read", { tx, id, key: operation.key, value, dirty, held: this.held(tx), step: this.steps });        break;      }      case "write": {        if (!this.acquire(tx, op.key, "exclusive")) return;        if (!this.acquire(tx, operation.key, "exclusive")) return;        const before = this.values.get(op.key)!;        const before = this.values.get(operation.key)!;        const register = transaction.registers.get(op.key);        const register = transaction.registers.get(operation.key);        // The update is lost when the value moved since this transaction read it: the write is based on a stale copy.        const lost = register !== undefined && register !== before;        const after = (register ?? before) + op.delta;        const after = (register ?? before) + operation.delta;        transaction.undoLog.push({ key: op.key, before });        transaction.undoLog.push({ key: operation.key, before });        transaction.registers.set(op.key, after);        transaction.registers.set(operation.key, after);        this.values.set(op.key, after);        this.values.set(operation.key, after);        this.dirtyBy.set(op.key, tx);        this.dirtyBy.set(operation.key, tx);        // ▸ remember the old value, then write the register plus the delta over the account        this.tracer?.emit("write", { tx, id, key: op.key, before, after, delta: op.delta, lost, step: this.steps });        this.tracer?.emit("write", { tx, id, key: operation.key, before, after, delta: operation.delta, lost, step: this.steps });        break;      }      case "commit": {        transaction.status = "committed";        const written = [...new Set(transaction.undoLog.map((entry) => entry.key))];        for (const key of written) if (this.dirtyBy.get(key) === tx) this.dirtyBy.delete(key);        const released = this.release(tx);        // ▸ the work is permanent: release every lock, and the waiters may try again        this.tracer?.emit("commit", { tx, id, written, released, committed: this.transactions.filter((t) => t.status === "committed").length, step: this.steps });        break;      }      case "abort":        this.rollback(tx, "requested", []);        break;    }    transaction.pc++;    transaction.programCounter++;  }  /** Runs the programs one after another with no locks: the answer a serial schedule gives. */  static serial(initial: Readonly<Record<string, number>>, programs: readonly TransactionProgram[]): Record<string, number> {    if (programs.length === 0) return { ...initial };    const manager = new TransactionManager(initial, programs, { isolation: "none", schedule: "sequential" });    manager.execute();    return manager.snapshot();  }  /** Steps the schedule until no transaction can run. */  private execute(): void {    for (;;) {      const runnable = this.runnable();      if (runnable.length === 0) break;      if (this.steps >= MAX_TX_STEPS * 2) throw new RangeError("the schedule did not finish");      this.step(this.pick(runnable));    }  }  /** A read takes the exclusive lock when the program writes the key later, so the lock is never upgraded. */  private readMode(transaction: Transaction, pc: number): LockMode {  private readMode(transaction: Transaction, programCounter: number): LockMode {    const op = transaction.program.ops[pc];    const operation = transaction.program.ops[programCounter];    if (!op || op.kind !== "read") return "exclusive";    if (!operation || operation.kind !== "read") return "exclusive";    return transaction.program.ops.slice(pc + 1).some((later) => later.kind === "write" && later.key === op.key) ? "exclusive" : "shared";    return transaction.program.ops.slice(programCounter + 1).some((later) => later.kind === "write" && later.key === operation.key) ? "exclusive" : "shared";  }  /**   * Takes the lock if nothing conflicts, or blocks the transaction and   * returns false; a block that closes a wait-for cycle aborts the   * transaction instead. Without locking every request is granted.   */  private acquire(tx: number, key: string, mode: LockMode): boolean {    if (this.options.isolation === "none") return true;    const holders = this.locks.get(key) ?? new Map<number, LockMode>();    const own = holders.get(tx);    if (own === "exclusive" || (own === "shared" && mode === "shared")) return true;    const transaction = this.transactions[tx]!;    const id = transaction.program.id;    const blockers = this.conflicting(tx, key, mode);    if (blockers.length > 0) {      transaction.waitingFor = key;      this.waits++;      // ▸ someone else holds a conflicting lock, so the transaction blocks; a cycle of waiters is a deadlock      this.tracer?.emit("wait", { tx, id, key, mode, holders: blockers.map((holder) => this.transactions[holder]!.program.id), waits: this.waits, step: this.steps });      const cycle = this.detect(tx);      if (cycle.length > 0) {        this.deadlocks++;        transaction.waitingFor = null;        this.rollback(tx, "deadlock", cycle);        transaction.pc = transaction.program.ops.length;        transaction.programCounter = transaction.program.ops.length;      }      return false;    }    holders.set(tx, mode);    this.locks.set(key, holders);    // ▸ under locking, a read takes a shared lock and a write an exclusive one, held until the end    this.tracer?.emit("lock", { tx, id, key, mode, waited: transaction.woken, held: this.held(tx), step: this.steps });    transaction.woken = false;    return true;  }  /** The other holders of a key whose lock conflicts with the mode wanted. */  private conflicting(tx: number, key: string, mode: LockMode): number[] {    return [...(this.locks.get(key)?.entries() ?? [])].filter(([holder, held]) => holder !== tx && (mode === "exclusive" || held === "exclusive")).map(([holder]) => holder);  }  /** Follows who waits for whom from a transaction; the ids of the cycle if the walk comes back, else empty. */  private detect(tx: number): string[] {    const path: number[] = [];    let current: number | undefined = tx;    while (current !== undefined && !path.includes(current)) {      path.push(current);      const key: string | null = this.transactions[current]!.waitingFor;      current = key === null ? undefined : this.conflicting(current, key, this.wantedMode(current))[0];    }    if (current === undefined) return [];    return path.slice(path.indexOf(current)).map((i) => this.transactions[i]!.program.id);  }  /** The lock mode a blocked transaction's current operation needs. */  private wantedMode(tx: number): LockMode {    const transaction = this.transactions[tx]!;    return this.readMode(transaction, transaction.pc);    return this.readMode(transaction, transaction.programCounter);  }  /** Aborts a transaction: undoes its writes newest first, then releases its locks. */  private rollback(tx: number, reason: "requested" | "deadlock", cycle: readonly string[]): void {    const transaction = this.transactions[tx]!;    const id = transaction.program.id;    transaction.status = "aborted";    // ▸ the work is cancelled, by request or as the deadlock's victim    this.tracer?.emit("abort", { tx, id, reason, cycle: [...cycle], undo: transaction.undoLog.length, aborted: this.transactions.filter((t) => t.status === "aborted").length, step: this.steps });    for (const entry of [...transaction.undoLog].reverse()) {      const from = this.values.get(entry.key)!;      this.values.set(entry.key, entry.before);      // ▸ put each old value back, newest first, as if the transaction had never run      this.tracer?.emit("undo", { tx, id, key: entry.key, restored: entry.before, from, step: this.steps });    }    for (const [key, writer] of [...this.dirtyBy.entries()]) if (writer === tx) this.dirtyBy.delete(key);    transaction.undoLog.length = 0;    this.release(tx);  }  /** Gives every lock of a transaction back and wakes whoever waited on them; the keys released. */  private release(tx: number): string[] {    const released: string[] = [];    for (const [key, holders] of [...this.locks.entries()]) {      if (!holders.has(tx)) continue;      holders.delete(tx);      released.push(key);      if (holders.size === 0) this.locks.delete(key);      for (const waiter of this.transactions) {        if (waiter.waitingFor === key) {          waiter.waitingFor = null;          waiter.woken = true;        }      }    }    return released;  }  private runnable(): number[] {    return this.transactions.flatMap((t, i) => (t.pc < t.program.ops.length && t.waitingFor === null ? [i] : []));    return this.transactions.flatMap((t, i) => (t.programCounter < t.program.ops.length && t.waitingFor === null ? [i] : []));  }  private pick(runnable: readonly number[]): number {    let chosen: number;    if (this.options.schedule === "sequential") chosen = runnable[0]!;    else if (this.options.schedule === "round-robin") chosen = runnable.find((tx) => tx > this.last) ?? runnable[0]!;    else chosen = runnable[this.random.index(runnable.length)]!;    this.last = chosen;    return chosen;  }}

lostUpdates =: 3
dirtyReads =: 0
deadlocks =: 0

Every transaction has ended after 15 steps: T1, T2, T3 committed, none aborted. The accounts close at A 70, B 100, C 40, with 3 accounts off the serial answer.

import { Mulberry32 } from "../random";import type { Tracer } from "../trace";/** * One operation of a transaction over named values (accounts): read a * value into the transaction's own register for that key, write the * register plus a delta back (a write with no read before it takes the * current value), commit, or abort. */export type TxOp = | { kind: "read"; key: string } | { kind: "write"; key: string; delta: number } | { kind: "commit" } | { kind: "abort" };export interface TransactionProgram { id: string; ops: readonly TxOp[];}/** No locks at all, or strict two-phase locking: every lock held until the transaction ends. */export const ISOLATION_MODES = ["none", "locking"] as const;export type IsolationMode = (typeof ISOLATION_MODES)[number];/** Who runs next: each transaction to completion, turns in order, or a seeded coin. */export const TX_SCHEDULES = ["sequential", "round-robin", "random"] as const;export type TxSchedule = (typeof TX_SCHEDULES)[number];export type LockMode = "shared" | "exclusive";export const MAX_TRANSACTIONS = 4;export const MAX_TX_STEPS = 60;export interface TxOptions { isolation: IsolationMode; schedule: TxSchedule; seed?: number;}export interface TxReport { /** Scheduler steps taken, waits included. */ steps: number; values: Record<string, number>; committed: string[]; aborted: string[]; /** Keys whose final value differs from running the committed transactions one after another. */ lostUpdates: number; /** Reads of a value written by a transaction that had not yet committed. */ dirtyReads: number; waits: number; deadlocks: number;}interface Transaction { readonly program: TransactionProgram; pc: number; programCounter: number; status: "pending" | "running" | "committed" | "aborted"; readonly registers: Map<string, number>; /** Before images, oldest first: what undo restores, in reverse. */ readonly undoLog: { key: string; before: number }[]; /** The key this transaction is blocked on, or null. */ waitingFor: string | null; /** Woken by a release and not yet past the lock it waited for. */ woken: boolean;}/** * A transaction is a group of reads and writes that the database promises * to run as a unit: all of it or none of it, and as if it were alone. * Several transactions run at once, and the scheduler may switch between * them after any operation, which is the race condition lesson again * with money in it: two transfers that both read an account and both * write it lose one of the updates, and a report that reads mid-transfer * sees money that is nowhere. Strict two-phase locking is the classic * cure: a transaction takes a shared lock to read and an exclusive lock * to write, holds every lock until it commits or aborts, and anyone who * wants a conflicting lock waits. Here a read of a key the program will * write later takes the exclusive lock at once, the way a select for * update does, so a lock is never upgraded. Waiting can form a cycle, * a deadlock, and the transaction that closed the cycle is aborted: its * writes are undone from a log of before images, its locks are released, * and the others go on. Aborting is also what a transaction does when it * asks to. * * Time: O(transactions) per step. Space: O(keys + writes). */export class TransactionManager { private readonly initial: Record<string, number>; private readonly values: Map<string, number>; private readonly transactions: Transaction[]; /** Who holds a lock on each key and in which mode; several readers may share a key. */ private readonly locks = new Map<string, Map<number, LockMode>>(); /** The transaction whose uncommitted write a key currently holds, if any. */ private readonly dirtyBy = new Map<string, number>(); private readonly random: Mulberry32; private last = -1; private steps = 0; private waits = 0; private deadlocks = 0; private dirtyReads = 0; constructor( initial: Readonly<Record<string, number>>, programs: readonly TransactionProgram[], private readonly options: TxOptions, private readonly tracer?: Tracer, ) { if (programs.length < 1 || programs.length > MAX_TRANSACTIONS) throw new RangeError(`transactions must be in [1, ${MAX_TRANSACTIONS}]`); if (!ISOLATION_MODES.includes(options.isolation)) throw new RangeError(`unknown isolation ${String(options.isolation)}`); if (!TX_SCHEDULES.includes(options.schedule)) throw new RangeError(`unknown schedule ${String(options.schedule)}`); const total = programs.reduce((sum, program) => sum + program.ops.length, 0); if (total > MAX_TX_STEPS) throw new RangeError(`${total} operations exceeds ${MAX_TX_STEPS}`); if (new Set(programs.map((program) => program.id)).size !== programs.length) throw new RangeError("transaction ids must be unique"); for (const program of programs) { for (const op of program.ops) { for (const operation of program.ops) { if (op.kind !== "commit" && op.kind !== "abort" && !(op.key in initial)) throw new RangeError(`${program.id} names an unknown key ${op.key}`); if (operation.kind !== "commit" && operation.kind !== "abort" && !(operation.key in initial)) throw new RangeError(`${program.id} names an unknown key ${op.key}`); } } this.initial = { ...initial }; this.values = new Map(Object.entries(initial)); this.transactions = programs.map((program) => ({ program, pc: 0, status: "pending", registers: new Map(), undoLog: [], waitingFor: null, woken: false })); this.transactions = programs.map((program) => ({ program, programCounter: 0, status: "pending", registers: new Map(), undoLog: [], waitingFor: null, woken: false })); this.random = new Mulberry32(options.seed ?? 1); } /** The values as they stand. */ snapshot(): Record<string, number> { return Object.fromEntries(this.values); } /** The locks a transaction holds, as `key:mode`, in the order the keys were first locked. */ held(tx: number): string[] { return [...this.locks.entries()].flatMap(([key, holders]) => { const mode = holders.get(tx); return mode === undefined ? [] : [`${key}:${mode}`]; }); } /** Runs every transaction to its commit or abort under the schedule. */ run(): TxReport { this.execute(); const committed = this.transactions.filter((t) => t.status === "committed"); const values = this.snapshot(); const expected = TransactionManager.serial(this.initial, committed.map((t) => t.program)); return { steps: this.steps, values, committed: committed.map((t) => t.program.id), aborted: this.transactions.filter((t) => t.status === "aborted").map((t) => t.program.id), lostUpdates: Object.keys(values).filter((key) => values[key] !== expected[key]).length, dirtyReads: this.dirtyReads, waits: this.waits, deadlocks: this.deadlocks, }; } /** One operation of one transaction; under locking it may wait instead, and a wait that closes a cycle aborts it. */ step(tx: number): void { const transaction = this.transactions[tx]; const op = transaction?.program.ops[transaction.pc]; const operation = transaction?.program.ops[transaction.programCounter]; if (!transaction || !op) throw new RangeError(`transaction ${tx} has nothing left to run`); if (!transaction || !operation) throw new RangeError(`transaction ${tx} has nothing left to run`); if (transaction.waitingFor !== null) throw new RangeError(`${transaction.program.id} is blocked`); this.steps++; const id = transaction.program.id; if (transaction.status === "pending") { transaction.status = "running"; // ▸ a transaction's first operation opens it: from here on its work is one unit this.tracer?.emit("begin", { tx, id, ops: transaction.program.ops.length, step: this.steps }); } switch (op.kind) { switch (operation.kind) { case "read": { if (!this.acquire(tx, op.key, this.readMode(transaction, transaction.pc))) return; if (!this.acquire(tx, operation.key, this.readMode(transaction, transaction.programCounter))) return; const value = this.values.get(op.key)!; const value = this.values.get(operation.key)!; transaction.registers.set(op.key, value); transaction.registers.set(operation.key, value); const writer = this.dirtyBy.get(op.key); const writer = this.dirtyBy.get(operation.key); const dirty = writer !== undefined && writer !== tx; if (dirty) this.dirtyReads++; // ▸ copy the value into the transaction's own register; it is dirty if an uncommitted write put it there this.tracer?.emit("read", { tx, id, key: op.key, value, dirty, held: this.held(tx), step: this.steps }); this.tracer?.emit("read", { tx, id, key: operation.key, value, dirty, held: this.held(tx), step: this.steps }); break; } case "write": { if (!this.acquire(tx, op.key, "exclusive")) return; if (!this.acquire(tx, operation.key, "exclusive")) return; const before = this.values.get(op.key)!; const before = this.values.get(operation.key)!; const register = transaction.registers.get(op.key); const register = transaction.registers.get(operation.key); // The update is lost when the value moved since this transaction read it: the write is based on a stale copy. const lost = register !== undefined && register !== before; const after = (register ?? before) + op.delta; const after = (register ?? before) + operation.delta; transaction.undoLog.push({ key: op.key, before }); transaction.undoLog.push({ key: operation.key, before }); transaction.registers.set(op.key, after); transaction.registers.set(operation.key, after); this.values.set(op.key, after); this.values.set(operation.key, after); this.dirtyBy.set(op.key, tx); this.dirtyBy.set(operation.key, tx); // ▸ remember the old value, then write the register plus the delta over the account this.tracer?.emit("write", { tx, id, key: op.key, before, after, delta: op.delta, lost, step: this.steps }); this.tracer?.emit("write", { tx, id, key: operation.key, before, after, delta: operation.delta, lost, step: this.steps }); break; } case "commit": { transaction.status = "committed"; const written = [...new Set(transaction.undoLog.map((entry) => entry.key))]; for (const key of written) if (this.dirtyBy.get(key) === tx) this.dirtyBy.delete(key); const released = this.release(tx); // ▸ the work is permanent: release every lock, and the waiters may try again this.tracer?.emit("commit", { tx, id, written, released, committed: this.transactions.filter((t) => t.status === "committed").length, step: this.steps }); break; } case "abort": this.rollback(tx, "requested", []); break; } transaction.pc++; transaction.programCounter++; } /** Runs the programs one after another with no locks: the answer a serial schedule gives. */ static serial(initial: Readonly<Record<string, number>>, programs: readonly TransactionProgram[]): Record<string, number> { if (programs.length === 0) return { ...initial }; const manager = new TransactionManager(initial, programs, { isolation: "none", schedule: "sequential" }); manager.execute(); return manager.snapshot(); } /** Steps the schedule until no transaction can run. */ private execute(): void { for (;;) { const runnable = this.runnable(); if (runnable.length === 0) break; if (this.steps >= MAX_TX_STEPS * 2) throw new RangeError("the schedule did not finish"); this.step(this.pick(runnable)); } } /** A read takes the exclusive lock when the program writes the key later, so the lock is never upgraded. */ private readMode(transaction: Transaction, pc: number): LockMode { private readMode(transaction: Transaction, programCounter: number): LockMode { const op = transaction.program.ops[pc]; const operation = transaction.program.ops[programCounter]; if (!op || op.kind !== "read") return "exclusive"; if (!operation || operation.kind !== "read") return "exclusive"; return transaction.program.ops.slice(pc + 1).some((later) => later.kind === "write" && later.key === op.key) ? "exclusive" : "shared"; return transaction.program.ops.slice(programCounter + 1).some((later) => later.kind === "write" && later.key === operation.key) ? "exclusive" : "shared"; } /** * Takes the lock if nothing conflicts, or blocks the transaction and * returns false; a block that closes a wait-for cycle aborts the * transaction instead. Without locking every request is granted. */ private acquire(tx: number, key: string, mode: LockMode): boolean { if (this.options.isolation === "none") return true; const holders = this.locks.get(key) ?? new Map<number, LockMode>(); const own = holders.get(tx); if (own === "exclusive" || (own === "shared" && mode === "shared")) return true; const transaction = this.transactions[tx]!; const id = transaction.program.id; const blockers = this.conflicting(tx, key, mode); if (blockers.length > 0) { transaction.waitingFor = key; this.waits++; // ▸ someone else holds a conflicting lock, so the transaction blocks; a cycle of waiters is a deadlock this.tracer?.emit("wait", { tx, id, key, mode, holders: blockers.map((holder) => this.transactions[holder]!.program.id), waits: this.waits, step: this.steps }); const cycle = this.detect(tx); if (cycle.length > 0) { this.deadlocks++; transaction.waitingFor = null; this.rollback(tx, "deadlock", cycle); transaction.pc = transaction.program.ops.length; transaction.programCounter = transaction.program.ops.length; } return false; } holders.set(tx, mode); this.locks.set(key, holders); // ▸ under locking, a read takes a shared lock and a write an exclusive one, held until the end this.tracer?.emit("lock", { tx, id, key, mode, waited: transaction.woken, held: this.held(tx), step: this.steps }); transaction.woken = false; return true; } /** The other holders of a key whose lock conflicts with the mode wanted. */ private conflicting(tx: number, key: string, mode: LockMode): number[] { return [...(this.locks.get(key)?.entries() ?? [])].filter(([holder, held]) => holder !== tx && (mode === "exclusive" || held === "exclusive")).map(([holder]) => holder); } /** Follows who waits for whom from a transaction; the ids of the cycle if the walk comes back, else empty. */ private detect(tx: number): string[] { const path: number[] = []; let current: number | undefined = tx; while (current !== undefined && !path.includes(current)) { path.push(current); const key: string | null = this.transactions[current]!.waitingFor; current = key === null ? undefined : this.conflicting(current, key, this.wantedMode(current))[0]; } if (current === undefined) return []; return path.slice(path.indexOf(current)).map((i) => this.transactions[i]!.program.id); } /** The lock mode a blocked transaction's current operation needs. */ private wantedMode(tx: number): LockMode { const transaction = this.transactions[tx]!; return this.readMode(transaction, transaction.pc); return this.readMode(transaction, transaction.programCounter); } /** Aborts a transaction: undoes its writes newest first, then releases its locks. */ private rollback(tx: number, reason: "requested" | "deadlock", cycle: readonly string[]): void { const transaction = this.transactions[tx]!; const id = transaction.program.id; transaction.status = "aborted"; // ▸ the work is cancelled, by request or as the deadlock's victim this.tracer?.emit("abort", { tx, id, reason, cycle: [...cycle], undo: transaction.undoLog.length, aborted: this.transactions.filter((t) => t.status === "aborted").length, step: this.steps }); for (const entry of [...transaction.undoLog].reverse()) { const from = this.values.get(entry.key)!; this.values.set(entry.key, entry.before); // ▸ put each old value back, newest first, as if the transaction had never run this.tracer?.emit("undo", { tx, id, key: entry.key, restored: entry.before, from, step: this.steps }); } for (const [key, writer] of [...this.dirtyBy.entries()]) if (writer === tx) this.dirtyBy.delete(key); transaction.undoLog.length = 0; this.release(tx); } /** Gives every lock of a transaction back and wakes whoever waited on them; the keys released. */ private release(tx: number): string[] { const released: string[] = []; for (const [key, holders] of [...this.locks.entries()]) { if (!holders.has(tx)) continue; holders.delete(tx); released.push(key); if (holders.size === 0) this.locks.delete(key); for (const waiter of this.transactions) { if (waiter.waitingFor === key) { waiter.waitingFor = null; waiter.woken = true; } } } return released; } private runnable(): number[] { return this.transactions.flatMap((t, i) => (t.pc < t.program.ops.length && t.waitingFor === null ? [i] : [])); return this.transactions.flatMap((t, i) => (t.programCounter < t.program.ops.length && t.waitingFor === null ? [i] : [])); } private pick(runnable: readonly number[]): number { let chosen: number; if (this.options.schedule === "sequential") chosen = runnable[0]!; else if (this.options.schedule === "round-robin") chosen = runnable.find((tx) => tx > this.last) ?? runnable[0]!; else chosen = runnable[this.random.index(runnable.length)]!; this.last = chosen; return chosen; }}