What is a write-ahead log (WAL)?

// A write-ahead log from scratch: bank balances in "pages", a log of checksummed records,
// a crash, redo recovery, a torn tail record, a checkpoint and group commit. All in memory.
const zlib = require("zlib");

function record(lsn, text) { // [lsn u32][len u16][payload][crc32 of everything before]
  const p = Buffer.from(text, "utf8"), b = Buffer.alloc(10 + p.length);
  b.writeUInt32BE(lsn, 0); b.writeUInt16BE(p.length, 4); p.copy(b, 6);
  b.writeUInt32BE(zlib.crc32(b.subarray(0, 6 + p.length)), 6 + p.length);
  return b;
}
const hex = (n) => "0x" + n.toString(16).padStart(8, "0");

class Db {
  constructor() { this.disk = {}; this.log = Buffer.alloc(0); this.lsn = 0; this.mem = {}; }
  load(balances) { for (const k of Object.keys(balances)) this.disk[k] = { value: balances[k], pageLsn: 0 }; this.mem = JSON.parse(JSON.stringify(this.disk)); }
  append(text) { this.lsn++; this.log = Buffer.concat([this.log, record(this.lsn, text)]); return this.lsn; }
  transfer(tx, from, to, amt) { // log first, fsync at COMMIT, change pages only in memory
    for (const [k, v] of [[from, this.mem[from].value - amt], [to, this.mem[to].value + amt]]) {
      const lsn = this.append(tx + " SET " + k + " " + v);
      this.mem[k] = { value: v, pageLsn: lsn };
    }
    this.append(tx + " COMMIT");
  }
  flushPage(k) { this.disk[k] = { ...this.mem[k] }; }
  recover(quiet) { // scan, verify checksums, redo committed changes newer than each page
    const recs = [], lines = [];
    let off = 0, startLsn = 0;
    while (off + 10 <= this.log.length) {
      const lsn = this.log.readUInt32BE(off), len = this.log.readUInt16BE(off + 4);
      if (off + 10 + len > this.log.length) { lines.push("lsn " + lsn + ": incomplete record, end of log"); break; }
      const want = this.log.readUInt32BE(off + 6 + len), got = zlib.crc32(this.log.subarray(off, off + 6 + len));
      if (want !== got) { lines.push("lsn " + lsn + ": checksum stored " + hex(want) + " computed " + hex(got) + " -> torn write, stop"); break; }
      const text = this.log.subarray(off + 6, off + 6 + len).toString("utf8");
      if (text.startsWith("CHECKPOINT")) startLsn = lsn;
      recs.push([lsn, text]); off += 10 + len;
    }
    const committed = new Set(recs.filter(([, t]) => t.endsWith(" COMMIT")).map(([, t]) => t.split(" ")[0]));
    let redone = 0, skipped = 0, ignored = 0, scanned = 0;
    for (const [lsn, text] of recs) {
      if (lsn <= startLsn) continue;
      scanned++;
      const [tx, op, k, v] = text.split(" ");
      if (op !== "SET") continue;
      if (!committed.has(tx)) { ignored++; lines.push("lsn " + lsn + ": " + text + " -> " + tx + " never committed, ignore"); continue; }
      if (this.disk[k].pageLsn >= lsn) { skipped++; lines.push("lsn " + lsn + ": " + text + " -> page already has it, skip"); continue; }
      this.disk[k] = { value: Number(v), pageLsn: lsn }; redone++;
      lines.push("lsn " + lsn + ": " + text + " -> redo");
    }
    if (!quiet) for (const l of lines) console.log("     " + l);
    this.mem = JSON.parse(JSON.stringify(this.disk));
    return { scanned, redone, skipped, ignored };
  }
  total() { return Object.values(this.disk).reduce((s, p) => s + p.value, 0); }
  show() { return Object.keys(this.disk).sort().map((k) => k + "=" + this.disk[k].value).join(" ") + " (total " + this.total() + ")"; }
}

console.log("== 1. No log: update pages in place, crash between the two writes ==");
const raw = { alice: 1000, bob: 1000, carol: 1000 };
raw.alice -= 100; // page for alice written to disk ... crash before bob is written
console.log("   after restart: alice=" + raw.alice + " bob=" + raw.bob + " carol=" + raw.carol + " (total " + (raw.alice + raw.bob + raw.carol) + ", 100 vanished)");

console.log("\n== 2. With a WAL: two committed transfers, a third torn mid-write ==");
const db = new Db();
db.load({ alice: 1000, bob: 1000, carol: 1000 });
db.transfer("tx1", "alice", "bob", 100);
db.flushPage("alice"); // the buffer pool happened to write alice's page early
db.transfer("tx2", "bob", "carol", 50);
const before = db.log.length;
db.transfer("tx3", "carol", "alice", 30);
db.log = Buffer.from(db.log.subarray(0, before + 28)); // only tx3's first record reached the disk before power failed
db.log[db.log.length - 5] ^= 0xff; // and that record is torn: one of its bytes never made it
console.log("   log on disk: " + db.log.length + " bytes; data pages on disk: " + db.show());
console.log("   recovery:");
db.recover(false);
console.log("   after recovery: " + db.show());
const again = db.recover(true);
console.log("   recovery run a second time: redo " + again.redone + ", skip " + again.skipped + " -> " + db.show());

console.log("\n== 3. Checkpoints bound recovery time ==");
const big = new Db();
big.load({ alice: 1000000, bob: 1000000, carol: 1000000 });
const names = ["alice", "bob", "carol"];
let ckptOffset = 0;
for (let i = 1; i <= 3000; i++) {
  if (i === 2501) { for (const k of names) big.flushPage(k); ckptOffset = big.log.length; big.append("CHECKPOINT"); }
  big.transfer("t" + i, names[i % 3], names[(i + 1) % 3], 1);
}
let all = 0;
for (let off = 0; off + 10 <= big.log.length; off += 10 + big.log.readUInt16BE(off + 4)) all++;
const copy = new Db(); copy.disk = JSON.parse(JSON.stringify(big.disk)); copy.log = big.log; // crash: memory lost
const r = copy.recover(true);
console.log("   3000 transfers: log " + big.log.length + " bytes, " + all + " records; checkpoint after transfer 2500");
console.log("   recovery starts at the checkpoint: scans " + r.scanned + " records, redoes " + r.redone + "; total " + copy.total());
console.log("   the " + ckptOffset + " bytes before the checkpoint can be recycled; without it recovery reads all " + all + " records");

console.log("\n== 4. Group commit (assume one fsync takes 2 ms) ==");
for (const group of [1, 10, 50]) {
  const fsyncs = Math.ceil(1000 / group);
  console.log("   " + String(group).padStart(2) + " commits per fsync: 1000 commits need " + String(fsyncs).padStart(4) + " fsyncs = " +
    String(fsyncs * 2).padStart(4) + " ms of flushing, ceiling " + String(Math.floor(1000 / 2) * group).padStart(5) + " commits/s");
}