1981-1992

Write-Ahead Log

A database says a transaction is done before most of it has been written anywhere permanent. That is not a shortcut. The rule underneath it is that a record describing a change reaches stable storage before the page holding that change does, and one particular record — the commit — is the instant the transaction becomes true. Everything after that is housekeeping. The way to see it is to cut the power, so that is the control: pick an instant, kill the machine, and reboot.

A transfer, a log, and a power switch that works at any instant

1 A transfer, as two changes to two balances

Thirty moves from Alice to Bob. Two balances change, and between them the machine can be interrupted.

on disk, before anything: Alice 100, Bob 50
the transfer: 30 from Alice to Bob

Cut the power: before anything happens

Nothing has run. Move the switch to choose the instant the power dies.

2 The log record, on disk before either balance moves

Every step the transaction takes, and where it writes. The log is on stable storage; the buffer is memory and does not survive a power cut.

Each step: what it says, where it writes, and whether it happened before the power died
#	what it writes	where	happened
1	BEGIN transaction 1	log	never happened
2	Alice: 100 becomes 70	log	never happened
3	Bob: 50 becomes 80	log	never happened
4	Alice's page changed in memory	buffer	never happened
5	Bob's page changed in memory	buffer	never happened
6	COMMIT transaction 1	log	never happened
7	Alice's page written to disk	disk	never happened
8	Bob's page written to disk	disk	never happened

3 The commit record, which is the instant it becomes true

the log, on stable storage: empty
the data pages, on disk: Alice 100, Bob 50
the buffer, in memory: Alice 100, Bob 50 — and none of it survives
is there a commit record: no commit record

The cut is BEFORE the commit record, which is 6 step(s) away.

4 Cut the power at any point, reboot, and see which half happened

What recovery did, and why
what it did	why
nothing yet

after recovery: —
the two together: —

Cut the power, then reboot.

Every instant the power can be cut, and what the machine comes back as.

Each cut point: whether it committed, the balances after recovery, and their total
cut after	commit record	after recovery	total

What this page checked when it loaded.

Each claim, whether it held, and the values behind it
claim	held	measured
cut at any of 9 instants, never half a transfer	yes	none did
and the two balances always add to 150	yes	every one of them
every cut before the commit record leaves the transfer undone	yes	6 cut point(s)
and every cut after it leaves the transfer done	yes	2 cut point(s)
no data page is written before the log record describing it	yes

All 5 checks held when this page loaded.

What is real here, and what is not

This is the shape of ARIES, not an implementation of it

The write-ahead rule and the redo-then-undo structure come from the 1992 paper and are real. Almost everything else in it is missing: there is no log sequence number, no checkpointing, no compensation log records, no fuzzy checkpoint, and no concurrency at all. ARIES spends most of its length on what happens when several transactions overlap and recovery is itself interrupted, and none of that is here. One transaction, one cut, one reboot.

Stable storage is assumed to be stable, which it is not

The whole mechanism rests on the log record being on a device that survives a power cut, and on the write actually having reached it. Real drives lie about that: a disk can report a write complete while it sits in a volatile cache, which is why fsync, write barriers and battery-backed controllers exist and why getting durability right in practice is mostly about not being lied to by hardware. Nothing on this page can show that, because the page's disk is a JavaScript object and it is perfectly honest.

Redo works because applying a change twice is the same as once

Recovery replays committed changes without knowing which of them had already reached their pages, which is only safe because the log records here say what a value BECOMES rather than how much to add to it. A log of adjustments would be wrong to replay. That distinction — physical against logical logging — is a real design decision with real consequences, and this page quietly takes the easy side of it.

Nine instants is every instant here, and it is not every instant

The sweep really does cover every cut point this machine has, which is what lets the page say never rather than not in the cases we tried. But the machine has eight steps because a page needs eight rows. A real transaction is thousands of writes and the power can die in the middle of one of them, half a sector written, which is a class of failure this model does not contain.

Sources

Logical Art builds interactive explanations of difficult machines.

The machines:

1935-1991 RangekeeperThe answer is on both sides of the equation, so it had to be a machine.
1964-1990s AbendThe loop you did not write, and the day it cost to get it wrong.
1975 Front PanelA working 1975 Altair 8800 you program by flipping switches.
1980s 300 BaudA real dial-up modem and the BBS on the other end of it.
1994 WinsockThe two seconds after the modem stopped screeching, before anything worked.
2020s LLM LabTrain a tiny language model and watch every number as it learns.

Smaller pieces, on the studio itself: Morse, Baudot, Punch Cards, Interlace, Bitwise, Stored Program, Trigger, Bit, Nibble, Byte, Transistor, Hamming, Huffman, Core Memory, The Interrupt, Score Reel, CRC, Page Fault, ASCII, CPU Cache, Race, Fifteen Planes, B-tree, Backoff, Checkout, Diffie-Hellman, Fringes, LZ77, Zero Address, Signature, Z-Characters, Merkle Proof, Branch Prediction, Interleave, Eight Sprites, DNS, Floating Point, Slow Start, UTF-8, Write-Ahead Log, JPEG, Masking, PageRank, Merge Collapse, Merkle DAG, Count Distinct, Longest Chain.

A Logical Art machine by RoamingPigs, Inc. Built by Cisco Caceres in Las Vegas, NV.