The WAL Log
Concept. Write-ahead logging records each change before its data page reaches disk. The database first appends a tiny diff, the old and new value, to the log, then updates the value in a page held in the RAM buffer, and flushes that 64 MB page to disk later. RAM is volatile, so the log append makes the change durable now. The log is durable before the page ever reaches disk, the write-ahead rule, and it makes a crash survivable: the log alone holds enough to rebuild any past version, put a change back, or take it away.
Intuition. Say A is updated from 19 to 22.8. First a small row, A, old 19, new 22.8, appends to the log and is durable at once. Then A's page updates in the RAM buffer. The 64 MB page is big and slow, so it flushes to disk later. If a crash hits in that gap, the log already holds the change.
Follow one update through all three.
The Lifecycle of an Update
Every update is three writes to three places. It appends the diff to the log, updates the value in a page in the RAM buffer, and later flushes that 64 MB page to disk. You already know paging from storage: the buffer holds fixed-size pages, and a page moves to disk as one write. Follow all three below.
Figure: The lifecycle of one update: append to the log, update the RAM page, flush the page to disk laterThe update, value A going from 19 to 22.8, sits at the left. Two grey arrows leave it: one up to the violet write-ahead log panel, one down to the red RAM buffer, drawn as a grid of 64 MB page slots with A's page marked dirty. A green arrow then crosses to the disk panel on the right, the same grid of durable slots, 19 of 2048 pages. A time axis along the bottom places steps one and two together at now and step three far to the right at later. Color key: violet is the durable sequential log, red is the volatile RAM buffer, green is the durable disk, grey is page structure.
| append to log | update RAM page | flush page to disk |
|---|---|---|
| durable now | now | later |
Figure 1. One update, three writes in time order. ① Append the diff to the log (violet), durable at once; ② update A's page in the RAM buffer (red) in place, fast but volatile; ③ later, flush the whole 64 MB page to disk (green) as one write, start to end. Steps ① and ② happen now and the flush is deferred, so the log is always durable before the page reaches disk.
Append now, update now, flush later: those three actions are the whole mechanism, and the log always leads.
Inside the WAL Row
The log is append-only. Every write appends one row holding the old value and the new value, and a COMMIT or ABORT record marks where a transaction ends. Each row is tiny, about 40 bytes: a header (log position, type, length) 12 B, the transaction id 4 B, the location 8 B, and the old and new value 8 B each. Nothing is ever overwritten; the log only grows.
Figure: The WAL log as a table of diffs for T1The log after T1 raises A and B by twenty percent. It is a growing append-only table: each write is one row holding the old value, orange, that undo needs and the new value, green, that redo needs. T1 writes A from 19 to 22.8 and B from 23 to 27.6, then a COMMIT record marks the transaction's end. Ellipsis rows show this is one stretch of a much longer log. Color key: orange is the old value, green is the new value, violet is the log itself.
| Txn | Var | old value | new value |
|---|---|---|---|
| T1 | A | 19 | 22.8 |
| T1 | B | 23 | 27.6 |
| T1 | COMMIT record | ||
Figure 2. The log after two updates: A from 19 to 22.8 and B from 23 to 27.6. Each is one row with the old value (orange) and the new value (green), so the same log carries what it takes to put a change back or take it away. A commit record closes the transaction. These are the rows undo runs against when a transaction aborts, and redo when a crash hits.
Every change is now an old-to-new row. Three questions follow: how do you get any past version from it, why is writing on every change not slow, and why must the log reach disk before the data page?
Any Version, on Demand
Change Tracking opened with a problem: show the exact state at any past moment, without copying the whole database. The WAL log already holds it. Because every row keeps both the old value and the new, you replay the log to any state: stop replaying at a past moment and you have the version that was true then. Forward, you redo the new values; backward, you undo the old ones. The log is the version history, one change at a time.
Figure: The WAL log is the version history: replay it to any past stateThe log drawn top to bottom in time, each row an old-to-new change: T1 sets A to 22.8 and B to 27.6, then later T2 and T3 change them again. To see the state at any past moment, stop replaying the rows there. Stopping just after T1 gives the version A=22.8, B=27.6. Replaying forward uses the new values, stepping back uses the old, so the log reaches any version either way. Color key: orange is the old value, green is the new value, violet is the log.
| Txn | Var | old value | new value |
|---|---|---|---|
| T1 | A | 19 | 22.8 |
| T1 | B | 23 | 27.6 |
| T2 | A | 22.8 | 30 |
| T3 | B | 27.6 | 33 |
Figure 3. The log read top to bottom is a full change history. To see the state at any past moment, stop replaying the rows there: just after T1, the version is A=22.8, B=27.6. Because each row carries both values, you can move either way, redoing new values forward or undoing old values back.
Cheap for Two Reasons: Small and Sequential
First, a WAL row is tiny, about 40 bytes against a 64 MB data page. Second, it only appends, one sequential write at the tail of the log, while the data page needs a random I/O to wherever its row lives. The numbers are lopsided. Flushing a 64 MB page to SSD takes about 13 ms (64 MB at 5 GB/s). The WAL flushes in small 64 KB pages, about 13 µs each, roughly a thousand times less; and a row landing in battery-backed NVRAM is durable at RAM speed, about 100 ns, a hundred thousand times less than the page flush.
Figure: WAL turns scattered random writes into one sequential appendA comparison of two ways to write the same changes to disk. On the left, without the log, each change is a random I/O to its own scattered 64 MB data page, about 13 ms, shown in grey. On the right, the WAL log appends every change as a tiny row, about 40 bytes, to one growing file shown in violet: a 64 KB WAL page costs about 13 microseconds, roughly a thousand times less, and a row in battery-backed NVRAM is durable in about 100 nanoseconds, a hundred thousand times less than the page flush. Small and sequential beats big and random. Color key: grey is the big scattered data pages, violet is the tiny sequential log.
Figure 4. Without the log (grey), each change is a random I/O to its own scattered 64 MB data page, about 13 ms. With the log (violet), every change is a ~40 byte row appended to one growing file, one fast sequential stream: a 64 KB WAL page costs about 13 µs (~1,000× less), and a row in battery-backed NVRAM is durable in about 100 ns (~100,000× less). Small and sequential beats big and random.
Hardware makes the log even cheaper. Battery-backed NVRAM writes at RAM speed yet survives power loss, so the quick note is durable the instant it lands. Replicating the log to RAM on three or more machines means one crash loses nothing. And sequential SSD appends, the one operation all of this hardware does fastest, are exactly what WAL turns every random update into.
Why the Log Goes First
The update and the flush happen at different times, so a crash can strike between them, and which write reaches disk first decides everything. The log goes first: a crash before the page flushes still leaves the change in the durable log, ready to re-apply. Flip the order and the data changed with no record of why, unrecoverable. That is the write-ahead rule. Surviving an actual crash, replaying the log and undoing the unfinished work, is the next two pages.
Figure: Why log-before-data makes a crash recoverableTwo orderings of the same two disk writes: the data page, drawn as a page block, and the log record, drawn as a WAL table row with columns Txn, Var, old value in orange and new value in green. On the left, data first: the crash hits before the log row lands, so the data page changed with no record of why, an unrecoverable state shown in red. On the right, log first as WAL demands: the crash hits before the data page moves, so the intent is in the durable log and recovery re-applies it, shown in green. Color key: red is the unrecoverable order, green is the recoverable WAL order, violet is the durable log.
| Txn | Var | old | new |
|---|---|---|---|
| T1 | A | 19 | 22.8 |
| Txn | Var | old | new |
|---|---|---|---|
| T1 | A | 19 | 22.8 |
Figure 5. Data first (red): if the crash hits before the log row lands, the data changed with no row to replay, an inconsistency recovery cannot fix. Log first (green), the WAL order: a crash before the data page moves leaves the change sitting in the durable log, ready to re-apply. Log-before-data is the only order that keeps the data file recoverable.