WAL: Crash Recovery

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

Write-ahead log

Loading interactive demo…

The top row is the buffer pool, pages in memory with the value the disk does not have yet; the bottom row is the disk, six pages. The strips beneath are the script with the crash marked, the log one chip per record, and the transactions with their standing. Tap a log record to read it.Take the tour, or press and explore. Legend:

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

The page or record this step touches, and the action under way.
A dirty page in the buffer, a log record in memory only, and an active transaction.
A record on stable storage, a committed transaction, and a page just redone.
A disk page lagging a commit: the log knows a newer value.
A disk page holding a value no transaction committed, a record lost in the crash, a loser, and a page just undone.
A clean page the disk has right, and script actions still to come.

records counts the log and how many of its records are on stable storage; dirty pages counts the buffer; redone and undone count recovery's work; disk compares the disk with what the committed transactions wrote.

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 promise. The transactions lesson ended with a commit: the moment after which the database says the work is done. Durability is the fourth letter of ACID, and it means that a committed write survives anything short of the disk itself failing. The trouble is that the pages a transaction changes live in a buffer pool in memory, because writing a page to disk for every change would make the database as slow as the disk, and memory is exactly what a power failure takes. Two copies of every page, and the one that survives is the one that is out of date.

Log first. The write-ahead log resolves this with a single rule and a single sequential file. Before a page may change, a record of the change is appended to the log: which transaction, which page, the value before and the value after. The record goes to the log in memory, the page changes in the buffer, and the disk is untouched. A commit appends its own record and then forces the log, every record up to and including it, onto stable storage. One sequential write per commit, and from that moment the transaction is durable although none of its pages has been written: the log holds enough to rebuild them.

Write-ahead. The rule's second half concerns the pages. A page may go to disk whenever the buffer pool wants its frame, committed or not, but never before the log records that describe it. On the stage a steal forces the log through the page's latest record first. The disk therefore never holds a change the log cannot explain, which is what makes the disk recoverable rather than merely corrupt. Without the log, in the stage's second mode, every update is a disk write, and after a crash an uncommitted value sits beside the committed ones with nothing to tell them apart.

Redo and undo. Recovery reads the surviving log forward from the last checkpoint. A transaction with a commit record is a winner: each of its update records is redone, the page set to the after image on disk, whether or not the page got there before the crash. Writing a value a page already holds is harmless, so recovery need not know. A transaction with updates but no commit record is a loser: its records are walked newest first and each page is set back to its before image, so a stolen page returns to what it was. Winners first, losers second; ARIES calls the first pass repeating history.

Checkpoints. Without them recovery would read the log from record one, after months of operation. A checkpoint writes every dirty page to disk and appends a record naming the transactions still active. Redo can start there, because every committed write before it is on disk already. Undo still follows a loser's records back as far as they go, since a transaction active at the checkpoint may have written long before it.

The real thing. ARIES, which the major databases run, adds what the stage leaves out: a log sequence number stored in each page so redo can skip pages already current, compensation log records written during undo so that a crash during recovery resumes rather than restarts, fuzzy checkpoints that do not pause the system, and a log that is also the feed for replicas. The shape is the one on the stage: log, force, write later, repeat history, reverse the losers.

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

append is the one place a record enters the log, so update, commit, abort, and checkpoint records share a call site and the append tag has one line. With logging off it returns null, and every caller carries on without a record.
force is the write-ahead rule in four lines: commit calls it for its own record and writePage calls it for the page's latest record. A steal and a commit are the same operation on the log.
update never touches the disk when the log is on; it writes the buffer and a record with the before image read from the buffer or the disk, whichever is current.
undo is shared by abort and recovery, differing only in where the page lives: the buffer while the system runs, the disk after a crash has emptied the buffer.
crash truncates the log to the forced prefix and clears the buffer, nothing else. The disk keeps whatever happened to reach it, including stolen pages of transactions that never committed.
recover finds winners by their commit records and losers by their updates, redoes forward from the last checkpoint, undoes backward over the whole log, and reports the disk against the committed image it kept as an oracle. The oracle is for the stage's verdict; a real system has no such thing, which is the point.

Transaction systems of the 1970s had to promise that a commit survived a power failure while their pages lived in memory. The answer that won was to write a record of every change to a sequential log before the page, and to force the log at commit. Jim Gray set it down in his 1978 notes from IBM's System R project, with the write-ahead rule, before and after images, and checkpoints. ARIES, published by Mohan and colleagues at IBM in 1992, settled the recovery that the major databases run today, and the same idea reached file systems as journaling.

1978Jim Gray - Notes on Data Base Operating Systems describes write-ahead logging for System R: log records with before and after images, forced at commit, and checkpoints that bound how far back recovery must read.source
1981Jim Gray and others - The Recovery Manager of the System R Database Manager reports on the shadow-page and log-based recovery actually built, and why logging won.source
1992C. Mohan, Don Haderle, Bruce Lindsay, Hamid Pirahesh, and Peter Schwarz - ARIES: a recovery method that repeats history on restart, redoing every logged update and then undoing the losers, logging the undos themselves so a crash during recovery is handled by the same code.source
2001Stephen Tweedie - The ext3 file system brings a journal to Linux: metadata changes are written to a log before the file system, so a crash no longer needs a full consistency check of the disk.source
2010SQLite - SQLite adds write-ahead log mode as an alternative to its rollback journal, writing changes to a log file and checkpointing them into the database later.source

Used today

Every relational database - PostgreSQL's WAL, MySQL's InnoDB redo log, SQL Server's transaction log, and Oracle's redo log are all this mechanism: force at commit, write pages later, replay on restart.
Replication - The log is a complete description of every change, so shipping it to another machine and replaying it there gives a replica for free.
Journaling file systems - ext4, NTFS, APFS, and XFS write metadata changes to a journal first, which is why a crashed laptop boots without a disk check.

scenario

log

crash afterscripted

records: 3 (3 durable)
dirty pages: 0
redone: 2
undone: 0
disk: matches the committed state

write-ahead-log.ts

import type { Tracer } from "../trace";/** Pages on disk by default: a value each, numbered from 0. */export const PAGE_COUNT = 6;export const MAX_PAGES = 8;export const MAX_LOG_RECORDS = 64;export const MAX_WAL_ACTIONS = 48;/** One line of the log, numbered by its log sequence number from 1. */export type LogRecord =  | { lsn: number; kind: "update"; tx: string; page: number; before: number; after: number }  | { lsn: number; kind: "commit"; tx: string }  | { lsn: number; kind: "abort"; tx: string }  | { lsn: number; kind: "checkpoint"; dirtyPages: readonly number[]; activeTx: readonly string[] };export type LogRecordKind = LogRecord["kind"];/** One step of a script the store runs. */export type WalAction =  | { kind: "update"; tx: string; page: number; value: number }  | { kind: "commit"; tx: string }  | { kind: "abort"; tx: string }  | { kind: "writeBack"; page: number }  | { kind: "checkpoint" }  | { kind: "crash" }  | { kind: "recover" };export interface WalOptions {  /** Pages of storage, 1 to MAX_PAGES (default PAGE_COUNT). */  pages?: number;  /** False writes every update straight to disk with no log at all, the comparison the lesson draws. */  logging?: boolean;}export type TransactionState = "active" | "committed" | "aborted";export interface RecoveryReport {  /** Update records replayed onto the disk. */  redone: number;  /** Update records reversed on the disk. */  undone: number;  /** Transactions whose commit record survived the crash. */  winners: readonly string[];  /** Transactions with updates but no commit record: their work is undone. */  losers: readonly string[];  /** The disk after recovery, page by page. */  disk: readonly number[];  /** What the disk should hold: every committed write and nothing else. */  expected: readonly number[];  consistent: boolean;}/** * A database promises that a committed write survives a crash and an * uncommitted one leaves no trace, while its pages live in a buffer pool * that is lost the moment the power goes. The write-ahead log keeps the * promise: every update is appended to the log, with the value before * and after, before the page it changes may reach the disk, and a commit * forces the log to stable storage before it is acknowledged. After a * crash, recovery reads the log from the last checkpoint: updates of * transactions that committed are redone onto the disk, updates of * transactions that did not are undone in reverse, and the disk is what * the committed transactions said. With logging off, every update goes * straight to the disk and a crash leaves whatever was there. * * Time: O(log records) per recovery, O(1) per update. Space: O(pages + log records). */export class WriteAheadLog {  readonly pages: number;  readonly logging: boolean;  private readonly disk: number[];  /** Dirty pages: the value in memory that the disk does not have yet. */  private readonly buffer = new Map<number, number>();  private readonly log: LogRecord[] = [];  /** Records at or below this sequence number are on stable storage. */  private flushedLsn = 0;  private readonly states = new Map<string, TransactionState>();  /** Each active transaction's writes so far, for the commit payload and the oracle. */  private readonly pending = new Map<string, Map<number, number>>();  /** What a perfect store would hold: committed writes only, applied at commit. */  private readonly committedImage: number[];  private crashed = false;  constructor(options: WalOptions = {}, private readonly tracer?: Tracer) {    const pages = options.pages ?? PAGE_COUNT;    if (!Number.isInteger(pages) || pages < 1 || pages > MAX_PAGES) throw new RangeError(`pages must be in [1, ${MAX_PAGES}]`);    this.pages = pages;    this.logging = options.logging ?? true;    this.disk = new Array<number>(pages).fill(0);    this.committedImage = new Array<number>(pages).fill(0);  }  /** The disk's pages; a copy. */  diskPages(): readonly number[] {    return [...this.disk];  }  /** The dirty pages in the buffer pool, by page; a copy. */  bufferPages(): ReadonlyMap<number, number> {    return new Map(this.buffer);  }  /** Every record still in the log; a copy. */  records(): readonly LogRecord[] {    return this.log.map((record) => ({ ...record }));  }  flushed(): number {    return this.flushedLsn;  }  state(tx: string): TransactionState | null {    return this.states.get(tx) ?? null;  }  /** A transaction writes a page: logged first, then the buffer; never the disk. */  update(tx: string, page: number, value: number): void {    this.checkPage(page);    this.checkActive(tx);    if (!Number.isInteger(value) || value < 0 || value > 99) throw new RangeError(`value ${value} is outside [0, 99]`);    if (!this.states.has(tx)) {      this.states.set(tx, "active");      this.pending.set(tx, new Map());    }    this.pending.get(tx)!.set(page, value);    const before = this.buffer.get(page) ?? this.disk[page]!;    if (this.logging) {      this.append({ lsn: 0, kind: "update", tx, page, before, after: value });      this.buffer.set(page, value);    } else {      // No log: the page goes straight to disk, committed or not.      this.writePage(page, value, 0, tx);    }  }  /** The commit record is appended and the log forced before the commit is acknowledged. */  commit(tx: string): void {    this.checkActive(tx);    const writes = this.pending.get(tx) ?? new Map<number, number>();    const record = this.append({ lsn: 0, kind: "commit", tx });    this.force(record?.lsn ?? 0);    for (const [page, value] of writes) this.committedImage[page] = value;    this.states.set(tx, "committed");    this.pending.delete(tx);    // ▸ only once its commit record is on disk is the transaction acknowledged; its pages may still be only in the buffer    this.tracer?.emit("commit", { tx, lsn: record?.lsn ?? 0, pages: [...writes.keys()].sort((a, b) => a - b), logged: this.logging });  }  /** The transaction gives up: its writes are reversed from its own log records. */  abort(tx: string): void {    this.checkActive(tx);    this.append({ lsn: 0, kind: "abort", tx });    const mine = this.log.filter((record): record is Extract<LogRecord, { kind: "update" }> => record.kind === "update" && record.tx === tx);    const ownUpdates = this.log.filter((record): record is Extract<LogRecord, { kind: "update" }> => record.kind === "update" && record.tx === tx);    for (const record of [...mine].reverse()) this.undo(record, "buffer");    for (const record of [...ownUpdates].reverse()) this.undo(record, "buffer");    this.states.set(tx, "aborted");    this.pending.delete(tx);  }  /** The buffer pool steals a frame: a dirty page is written to disk, committed or not, once its log records are. Nothing to do with no log, where every page is already on disk. */  writeBack(page: number): void {    this.checkPage(page);    this.checkRunning();    if (!this.logging) return;    const value = this.buffer.get(page);    if (value === undefined) throw new RangeError(`page ${page} is not dirty`);    const latest = this.log.filter((record) => record.kind === "update" && record.page === page).at(-1);    const writer = latest?.kind === "update" ? latest.tx : "";    this.writePage(page, value, latest?.lsn ?? 0, writer);    this.buffer.delete(page);  }  /** Every dirty page to disk and a record of who was active, so recovery need not read the log from its start. */  checkpoint(): void {    this.checkRunning();    const dirtyPages = [...this.buffer.keys()].sort((a, b) => a - b);    const activeTx = [...this.states.entries()].filter(([, state]) => state === "active").map(([tx]) => tx);    const record = this.append({ lsn: 0, kind: "checkpoint", dirtyPages, activeTx });    this.force(record?.lsn ?? 0);    for (const page of dirtyPages) {      this.disk[page] = this.buffer.get(page)!;      this.buffer.delete(page);    }    // ▸ every dirty page is written and the record names who was active, so recovery can start here    this.tracer?.emit("checkpoint", { lsn: record?.lsn ?? 0, pages: dirtyPages, activeTx });  }  /** The power goes: the buffer pool and every unforced log record are gone; the disk keeps what reached it. */  crash(): void {    this.checkRunning();    const lostRecords = this.log.length - this.flushedLsn;    const lostPages = [...this.buffer.keys()].sort((a, b) => a - b);    this.log.length = this.flushedLsn;    this.buffer.clear();    this.crashed = true;    // ▸ the buffer pool and every record not yet forced are gone; the disk is all that is left    this.tracer?.emit("crash", { flushedLsn: this.flushedLsn, lostRecords, lostPages });  }  /** Repeat history from the last checkpoint for the winners, then reverse the losers. */  recover(): RecoveryReport {    if (!this.crashed) throw new RangeError("nothing to recover from: the store has not crashed");    let checkpointAt = -1;    this.log.forEach((record, i) => {      if (record.kind === "checkpoint") checkpointAt = i;    });    const since = this.log.slice(checkpointAt + 1);    const recordsSinceCheckpoint = this.log.slice(checkpointAt + 1);    const winners = new Set(this.log.flatMap((record) => (record.kind === "commit" ? [record.tx] : [])));    const touched = new Set(this.log.flatMap((record) => (record.kind === "update" ? [record.tx] : [])));    const losers = [...touched].filter((tx) => !winners.has(tx));    let redone = 0;    for (const record of since) {    for (const record of recordsSinceCheckpoint) {      if (record.kind !== "update" || !winners.has(record.tx)) continue;      this.disk[record.page] = record.after;      redone++;      // ▸ the transaction committed, so its write is replayed onto the disk whether or not it got there before      this.tracer?.emit("redo", { lsn: record.lsn, tx: record.tx, page: record.page, value: record.after });    }    let undone = 0;    for (const record of [...this.log].reverse()) {      if (record.kind !== "update" || !losers.includes(record.tx)) continue;      this.undo(record, "disk");      undone++;    }    for (const tx of losers) this.states.set(tx, "aborted");    for (const tx of touched) this.pending.delete(tx);    this.crashed = false;    return this.report(redone, undone, [...winners], losers);  }  /** The disk against the committed image, with the counts a recovery produced. */  report(redone = 0, undone = 0, winners: readonly string[] = [], losers: readonly string[] = []): RecoveryReport {    const disk = this.diskPages();    const expected = [...this.committedImage];    return { redone, undone, winners, losers, disk, expected, consistent: disk.every((value, page) => value === expected[page]) };  }  /** A script of actions in order; the last recovery's report, or the plain report when nothing crashed. */  run(script: readonly WalAction[]): RecoveryReport {    if (script.length > MAX_WAL_ACTIONS) throw new RangeError(`${script.length} actions exceeds ${MAX_WAL_ACTIONS}`);    let report: RecoveryReport | null = null;    for (const action of script) {      switch (action.kind) {        case "update":          this.update(action.tx, action.page, action.value);          break;        case "commit":          this.commit(action.tx);          break;        case "abort":          this.abort(action.tx);          break;        case "writeBack":          this.writeBack(action.page);          break;        case "checkpoint":          this.checkpoint();          break;        case "crash":          this.crash();          break;        case "recover":          report = this.recover();          break;      }    }    return report ?? this.report();  }  /** The one place a record enters the log; null with logging off, where there is no log. */  private append(record: LogRecord): LogRecord | null {    if (!this.logging) return null;    if (this.log.length >= MAX_LOG_RECORDS) throw new RangeError(`the log holds at most ${MAX_LOG_RECORDS} records`);    const entry: LogRecord = { ...record, lsn: this.log.length + 1 };    this.log.push(entry);    // ▸ a record of the change, old value and new, goes into the log in memory before the page is touched    this.tracer?.emit("append", { lsn: entry.lsn, kind: entry.kind, tx: "tx" in entry ? entry.tx : "", page: entry.kind === "update" ? entry.page : null, before: entry.kind === "update" ? entry.before : null, after: entry.kind === "update" ? entry.after : null, flushedLsn: this.flushedLsn });    return entry;  }  /** Forces the log to stable storage up to a record; a commit and a steal both need it. */  private force(upTo: number): void {  private force(throughLsn: number): void {    if (upTo <= this.flushedLsn) return;    if (throughLsn <= this.flushedLsn) return;    const forced = upTo - this.flushedLsn;    const forced = throughLsn - this.flushedLsn;    this.flushedLsn = upTo;    this.flushedLsn = throughLsn;    // ▸ the log is forced to stable storage up to this record: from here, nothing before it can be lost    this.tracer?.emit("flush", { lsn: upTo, forced });    this.tracer?.emit("flush", { lsn: throughLsn, forced });  }  /** The one place a value reaches the disk outside recovery: the log is forced up to the page's latest record first. */  private writePage(page: number, value: number, lsn: number, tx: string): void {    const forced = lsn > this.flushedLsn;    this.force(lsn);    this.disk[page] = value;    // ▸ a dirty page goes to disk, committed or not, but never before the log records that describe it    this.tracer?.emit("evict", { page, value, lsn, tx, forced, logged: this.logging });  }  /** Reverses one update record where the page lives: the buffer during an abort, the disk during recovery. */  private undo(record: Extract<LogRecord, { kind: "update" }>, where: "buffer" | "disk"): void {    if (where === "buffer") this.buffer.set(record.page, record.before);    else this.disk[record.page] = record.before;    // ▸ the transaction did not commit, so its write is reversed to the value before, newest record first    this.tracer?.emit("undo", { lsn: record.lsn, tx: record.tx, page: record.page, before: record.before, where });  }  private checkPage(page: number): void {    if (!Number.isInteger(page) || page < 0 || page >= this.pages) throw new RangeError(`page ${page} is outside [0, ${this.pages})`);  }  private checkRunning(): void {    if (this.crashed) throw new RangeError("the store has crashed: recover first");  }  private checkActive(tx: string): void {    this.checkRunning();    const state = this.states.get(tx);    if (state !== undefined && state !== "active") throw new RangeError(`${tx} has already ${state === "committed" ? "committed" : "aborted"}`);  }}

redone =: 2
undone =: 0
consistent =: yes

Recovery redid 2 updates and undid 0 updates; winners T1, losers none. The disk now reads 0 5 0 8 0 0 against the committed state 0 5 0 8 0 0: they match.

import type { Tracer } from "../trace";/** Pages on disk by default: a value each, numbered from 0. */export const PAGE_COUNT = 6;export const MAX_PAGES = 8;export const MAX_LOG_RECORDS = 64;export const MAX_WAL_ACTIONS = 48;/** One line of the log, numbered by its log sequence number from 1. */export type LogRecord = | { lsn: number; kind: "update"; tx: string; page: number; before: number; after: number } | { lsn: number; kind: "commit"; tx: string } | { lsn: number; kind: "abort"; tx: string } | { lsn: number; kind: "checkpoint"; dirtyPages: readonly number[]; activeTx: readonly string[] };export type LogRecordKind = LogRecord["kind"];/** One step of a script the store runs. */export type WalAction = | { kind: "update"; tx: string; page: number; value: number } | { kind: "commit"; tx: string } | { kind: "abort"; tx: string } | { kind: "writeBack"; page: number } | { kind: "checkpoint" } | { kind: "crash" } | { kind: "recover" };export interface WalOptions { /** Pages of storage, 1 to MAX_PAGES (default PAGE_COUNT). */ pages?: number; /** False writes every update straight to disk with no log at all, the comparison the lesson draws. */ logging?: boolean;}export type TransactionState = "active" | "committed" | "aborted";export interface RecoveryReport { /** Update records replayed onto the disk. */ redone: number; /** Update records reversed on the disk. */ undone: number; /** Transactions whose commit record survived the crash. */ winners: readonly string[]; /** Transactions with updates but no commit record: their work is undone. */ losers: readonly string[]; /** The disk after recovery, page by page. */ disk: readonly number[]; /** What the disk should hold: every committed write and nothing else. */ expected: readonly number[]; consistent: boolean;}/** * A database promises that a committed write survives a crash and an * uncommitted one leaves no trace, while its pages live in a buffer pool * that is lost the moment the power goes. The write-ahead log keeps the * promise: every update is appended to the log, with the value before * and after, before the page it changes may reach the disk, and a commit * forces the log to stable storage before it is acknowledged. After a * crash, recovery reads the log from the last checkpoint: updates of * transactions that committed are redone onto the disk, updates of * transactions that did not are undone in reverse, and the disk is what * the committed transactions said. With logging off, every update goes * straight to the disk and a crash leaves whatever was there. * * Time: O(log records) per recovery, O(1) per update. Space: O(pages + log records). */export class WriteAheadLog { readonly pages: number; readonly logging: boolean; private readonly disk: number[]; /** Dirty pages: the value in memory that the disk does not have yet. */ private readonly buffer = new Map<number, number>(); private readonly log: LogRecord[] = []; /** Records at or below this sequence number are on stable storage. */ private flushedLsn = 0; private readonly states = new Map<string, TransactionState>(); /** Each active transaction's writes so far, for the commit payload and the oracle. */ private readonly pending = new Map<string, Map<number, number>>(); /** What a perfect store would hold: committed writes only, applied at commit. */ private readonly committedImage: number[]; private crashed = false; constructor(options: WalOptions = {}, private readonly tracer?: Tracer) { const pages = options.pages ?? PAGE_COUNT; if (!Number.isInteger(pages) || pages < 1 || pages > MAX_PAGES) throw new RangeError(`pages must be in [1, ${MAX_PAGES}]`); this.pages = pages; this.logging = options.logging ?? true; this.disk = new Array<number>(pages).fill(0); this.committedImage = new Array<number>(pages).fill(0); } /** The disk's pages; a copy. */ diskPages(): readonly number[] { return [...this.disk]; } /** The dirty pages in the buffer pool, by page; a copy. */ bufferPages(): ReadonlyMap<number, number> { return new Map(this.buffer); } /** Every record still in the log; a copy. */ records(): readonly LogRecord[] { return this.log.map((record) => ({ ...record })); } flushed(): number { return this.flushedLsn; } state(tx: string): TransactionState | null { return this.states.get(tx) ?? null; } /** A transaction writes a page: logged first, then the buffer; never the disk. */ update(tx: string, page: number, value: number): void { this.checkPage(page); this.checkActive(tx); if (!Number.isInteger(value) || value < 0 || value > 99) throw new RangeError(`value ${value} is outside [0, 99]`); if (!this.states.has(tx)) { this.states.set(tx, "active"); this.pending.set(tx, new Map()); } this.pending.get(tx)!.set(page, value); const before = this.buffer.get(page) ?? this.disk[page]!; if (this.logging) { this.append({ lsn: 0, kind: "update", tx, page, before, after: value }); this.buffer.set(page, value); } else { // No log: the page goes straight to disk, committed or not. this.writePage(page, value, 0, tx); } } /** The commit record is appended and the log forced before the commit is acknowledged. */ commit(tx: string): void { this.checkActive(tx); const writes = this.pending.get(tx) ?? new Map<number, number>(); const record = this.append({ lsn: 0, kind: "commit", tx }); this.force(record?.lsn ?? 0); for (const [page, value] of writes) this.committedImage[page] = value; this.states.set(tx, "committed"); this.pending.delete(tx); // ▸ only once its commit record is on disk is the transaction acknowledged; its pages may still be only in the buffer this.tracer?.emit("commit", { tx, lsn: record?.lsn ?? 0, pages: [...writes.keys()].sort((a, b) => a - b), logged: this.logging }); } /** The transaction gives up: its writes are reversed from its own log records. */ abort(tx: string): void { this.checkActive(tx); this.append({ lsn: 0, kind: "abort", tx }); const mine = this.log.filter((record): record is Extract<LogRecord, { kind: "update" }> => record.kind === "update" && record.tx === tx); const ownUpdates = this.log.filter((record): record is Extract<LogRecord, { kind: "update" }> => record.kind === "update" && record.tx === tx); for (const record of [...mine].reverse()) this.undo(record, "buffer"); for (const record of [...ownUpdates].reverse()) this.undo(record, "buffer"); this.states.set(tx, "aborted"); this.pending.delete(tx); } /** The buffer pool steals a frame: a dirty page is written to disk, committed or not, once its log records are. Nothing to do with no log, where every page is already on disk. */ writeBack(page: number): void { this.checkPage(page); this.checkRunning(); if (!this.logging) return; const value = this.buffer.get(page); if (value === undefined) throw new RangeError(`page ${page} is not dirty`); const latest = this.log.filter((record) => record.kind === "update" && record.page === page).at(-1); const writer = latest?.kind === "update" ? latest.tx : ""; this.writePage(page, value, latest?.lsn ?? 0, writer); this.buffer.delete(page); } /** Every dirty page to disk and a record of who was active, so recovery need not read the log from its start. */ checkpoint(): void { this.checkRunning(); const dirtyPages = [...this.buffer.keys()].sort((a, b) => a - b); const activeTx = [...this.states.entries()].filter(([, state]) => state === "active").map(([tx]) => tx); const record = this.append({ lsn: 0, kind: "checkpoint", dirtyPages, activeTx }); this.force(record?.lsn ?? 0); for (const page of dirtyPages) { this.disk[page] = this.buffer.get(page)!; this.buffer.delete(page); } // ▸ every dirty page is written and the record names who was active, so recovery can start here this.tracer?.emit("checkpoint", { lsn: record?.lsn ?? 0, pages: dirtyPages, activeTx }); } /** The power goes: the buffer pool and every unforced log record are gone; the disk keeps what reached it. */ crash(): void { this.checkRunning(); const lostRecords = this.log.length - this.flushedLsn; const lostPages = [...this.buffer.keys()].sort((a, b) => a - b); this.log.length = this.flushedLsn; this.buffer.clear(); this.crashed = true; // ▸ the buffer pool and every record not yet forced are gone; the disk is all that is left this.tracer?.emit("crash", { flushedLsn: this.flushedLsn, lostRecords, lostPages }); } /** Repeat history from the last checkpoint for the winners, then reverse the losers. */ recover(): RecoveryReport { if (!this.crashed) throw new RangeError("nothing to recover from: the store has not crashed"); let checkpointAt = -1; this.log.forEach((record, i) => { if (record.kind === "checkpoint") checkpointAt = i; }); const since = this.log.slice(checkpointAt + 1); const recordsSinceCheckpoint = this.log.slice(checkpointAt + 1); const winners = new Set(this.log.flatMap((record) => (record.kind === "commit" ? [record.tx] : []))); const touched = new Set(this.log.flatMap((record) => (record.kind === "update" ? [record.tx] : []))); const losers = [...touched].filter((tx) => !winners.has(tx)); let redone = 0; for (const record of since) { for (const record of recordsSinceCheckpoint) { if (record.kind !== "update" || !winners.has(record.tx)) continue; this.disk[record.page] = record.after; redone++; // ▸ the transaction committed, so its write is replayed onto the disk whether or not it got there before this.tracer?.emit("redo", { lsn: record.lsn, tx: record.tx, page: record.page, value: record.after }); } let undone = 0; for (const record of [...this.log].reverse()) { if (record.kind !== "update" || !losers.includes(record.tx)) continue; this.undo(record, "disk"); undone++; } for (const tx of losers) this.states.set(tx, "aborted"); for (const tx of touched) this.pending.delete(tx); this.crashed = false; return this.report(redone, undone, [...winners], losers); } /** The disk against the committed image, with the counts a recovery produced. */ report(redone = 0, undone = 0, winners: readonly string[] = [], losers: readonly string[] = []): RecoveryReport { const disk = this.diskPages(); const expected = [...this.committedImage]; return { redone, undone, winners, losers, disk, expected, consistent: disk.every((value, page) => value === expected[page]) }; } /** A script of actions in order; the last recovery's report, or the plain report when nothing crashed. */ run(script: readonly WalAction[]): RecoveryReport { if (script.length > MAX_WAL_ACTIONS) throw new RangeError(`${script.length} actions exceeds ${MAX_WAL_ACTIONS}`); let report: RecoveryReport | null = null; for (const action of script) { switch (action.kind) { case "update": this.update(action.tx, action.page, action.value); break; case "commit": this.commit(action.tx); break; case "abort": this.abort(action.tx); break; case "writeBack": this.writeBack(action.page); break; case "checkpoint": this.checkpoint(); break; case "crash": this.crash(); break; case "recover": report = this.recover(); break; } } return report ?? this.report(); } /** The one place a record enters the log; null with logging off, where there is no log. */ private append(record: LogRecord): LogRecord | null { if (!this.logging) return null; if (this.log.length >= MAX_LOG_RECORDS) throw new RangeError(`the log holds at most ${MAX_LOG_RECORDS} records`); const entry: LogRecord = { ...record, lsn: this.log.length + 1 }; this.log.push(entry); // ▸ a record of the change, old value and new, goes into the log in memory before the page is touched this.tracer?.emit("append", { lsn: entry.lsn, kind: entry.kind, tx: "tx" in entry ? entry.tx : "", page: entry.kind === "update" ? entry.page : null, before: entry.kind === "update" ? entry.before : null, after: entry.kind === "update" ? entry.after : null, flushedLsn: this.flushedLsn }); return entry; } /** Forces the log to stable storage up to a record; a commit and a steal both need it. */ private force(upTo: number): void { private force(throughLsn: number): void { if (upTo <= this.flushedLsn) return; if (throughLsn <= this.flushedLsn) return; const forced = upTo - this.flushedLsn; const forced = throughLsn - this.flushedLsn; this.flushedLsn = upTo; this.flushedLsn = throughLsn; // ▸ the log is forced to stable storage up to this record: from here, nothing before it can be lost this.tracer?.emit("flush", { lsn: upTo, forced }); this.tracer?.emit("flush", { lsn: throughLsn, forced }); } /** The one place a value reaches the disk outside recovery: the log is forced up to the page's latest record first. */ private writePage(page: number, value: number, lsn: number, tx: string): void { const forced = lsn > this.flushedLsn; this.force(lsn); this.disk[page] = value; // ▸ a dirty page goes to disk, committed or not, but never before the log records that describe it this.tracer?.emit("evict", { page, value, lsn, tx, forced, logged: this.logging }); } /** Reverses one update record where the page lives: the buffer during an abort, the disk during recovery. */ private undo(record: Extract<LogRecord, { kind: "update" }>, where: "buffer" | "disk"): void { if (where === "buffer") this.buffer.set(record.page, record.before); else this.disk[record.page] = record.before; // ▸ the transaction did not commit, so its write is reversed to the value before, newest record first this.tracer?.emit("undo", { lsn: record.lsn, tx: record.tx, page: record.page, before: record.before, where }); } private checkPage(page: number): void { if (!Number.isInteger(page) || page < 0 || page >= this.pages) throw new RangeError(`page ${page} is outside [0, ${this.pages})`); } private checkRunning(): void { if (this.crashed) throw new RangeError("the store has crashed: recover first"); } private checkActive(tx: string): void { this.checkRunning(); const state = this.states.get(tx); if (state !== undefined && state !== "active") throw new RangeError(`${tx} has already ${state === "committed" ? "committed" : "aborted"}`); }}