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.
New to why writing twice is faster? Start here
The database says the change is safe before the change has been made where the data lives. What it has actually done is append a note describing the change to the end of a file.
Appending is cheap because the disk head is already there, and the real update can be scattered anywhere. So writing twice, once sequentially and once eventually, beats writing once in a random place. If the power goes, the notes say what was promised.
Two things at once
A program you write reads top to bottom, one step after the last. Once two of them run at the same time, that stops being true of the pair: their steps interleave, in an order nobody chose and nothing wrote down.
The hard part is that the order is not random so much as unconstrained. Any interleaving the hardware permits is one you have to treat as possible, even if no test you ever run happens to produce it: nothing promises that a scheduler will eventually choose it, and nothing promises it will not, on someone else's machine, months later, on the run you were not watching. So the machines in this topic are not about making the right order happen. They are about which orders are possible, which of those are wrong, and what it costs to rule them out.
The machine for this idea on its own is Race, if you would rather press it than read about it.
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
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.
| # | 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 | Alice's page written to disk, uncommitted | disk | never happened |
| 7 | COMMIT transaction 1 | log | never happened |
| 8 | Alice's page written to disk | disk | never happened |
| 9 | 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 7 step(s) away.
4 Cut the power at any point, reboot, and see which half happened
| 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.
| cut after | commit record | after recovery | total |
|---|
What this page checked when it loaded.
| claim | held | measured |
|---|---|---|
| cut at any of 10 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 | 7 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, and so is the reason undo is needed at all: one page here is written to disk while the transaction is still open, which is what ARIES calls STEAL. Its restart is three passes, analysis then redo then undo, and the analysis pass is not here: this machine knows what was running because there is only ever one transaction. 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 nine steps because a page needs about nine 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
- C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh and P. Schwarz, ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging, ACM TODS 17(1), 1992.
- J. Gray, P. McJones, M. Blasgen and others, The Recovery Manager of the System R Database Manager, ACM Computing Surveys 13(2), 1981. Where the shadow-page alternative is set out and measured against logging.
- Logical Art, the studio this belongs to.