Write-Ahead Log

Where is the row when COMMIT returns?

An online game records a trade: Mira gives Oskar 500 gold. One transaction, two UPDATEs, COMMIT, and the database answers in about a millisecond. At that moment the two new balances are usually not in the table's data file. Rows live in pages of a few kilobytes (8 KB in PostgreSQL, 16 KB in MySQL's InnoDB), and both changed pages are most likely still in memory, to be written back seconds or minutes later. What has reached the disk is a few hundred bytes at the end of another file, the write-ahead log (WAL). The quickest way to see why is to try the obvious design first.

Change the pages, then answer

Write each changed page back to its place in the data file, and reply when both writes return. Three things go wrong.

• A returned write proves little. On Linux, as on most systems, it means the bytes reached the kernel's page cache, in memory, and a power cut loses them. Waiting until the device has them takes an fsync, and that wait is the expensive part. Even fsync trusts the drive: one that reports a flush as done while the data still sits in its volatile cache, with no battery or capacitor behind it, turns durability into luck.
• Two pages, two moments. Mira's row and Oskar's row sit on different pages. A crash between the two writes leaves 500 gold gone from Mira and never arrived at Oskar, and nothing on disk says a trade was under way.
• A page can tear. The database writes 8 KB, but the storage underneath may only promise that 4 KB, or 512 bytes, land as one unit. Power fails mid-write and the page comes back half new and half old: a torn page.

It is slow, too: every commit waits for whole pages, scattered across the file, to be flushed, even when a few bytes in each changed. Copying each page's old contents to a separate journal before overwriting it, as SQLite's default rollback journal does, makes the trade all-or-nothing, and makes each commit dearer still.

Write down what you are about to do

A write-ahead log turns the order around. Before anything changes in its final place, the database appends records describing each change to the end of the log ("page 1,204, Mira: 2,300 becomes 1,800", "page 88, Oskar: 120 becomes 620"), then a commit record. It flushes the log up to that record and only then answers. The changed pages stay in memory, marked dirty, and are written back when it suits the database. Two rules make this safe, and give the pattern its name:

• Answer only once the log is durable. The reply waits until the commit record, and everything before it, is flushed. If the machine dies right after the reply, the log still holds what is needed to redo the trade.
• No page reaches disk ahead of its log records. A dirty page may be written early, even before its transaction commits, but never before the records describing its changes. The data files never hold a change the log cannot explain, or, in engines that write uncommitted changes to pages, one it cannot take back.

A commit is now one append of a few hundred bytes at the end of one file, written sequentially and flushed once, instead of two pages flushed in two places. The log handles tearing its own way: it is written with checksums, so after a crash the database reads until the first piece that fails one and calls that the end of the log. A transaction whose commit record was cut off never committed, and, unless durability was traded away as described below, was never acknowledged either. Data pages written later can still tear, so engines guard them separately, PostgreSQL by logging a full copy of a page on its first change after a checkpoint, InnoDB with a doublewrite buffer.

Diagram components: Client, Handler, Write-Ahead Log, Data Store, Snapshot.

COMMIT waits only for step 1. The pages reach the data files later; after a crash the log redoes what they missed, and a checkpoint marks how much of the log is no longer needed.

One flush, many commits

A flush takes from well under a millisecond to several, depending on the device. If commits flushed one at a time, a device that flushes in 2 ms would hold the whole database near 500 commits a second. Group commit shares the wait: while one flush runs, other transactions append their commit records behind it, and the next flush makes all of them durable at once. Each commit still waits for a real flush; under load, one flush pays for many.

Engines also let you trade durability for latency on purpose. PostgreSQL's synchronous_commit = off answers before the flush: a crash can lose transactions acknowledged in the last fraction of a second, but the database comes back consistent, because the rule for pages still holds. That suits a page-view counter, not players' gold.

Back from a power cut

The data files now hold whatever pages happened to be written, some with the trade, some an hour old. Every log record has a log sequence number (LSN), its position in the log (in PostgreSQL, literally a byte position), and every page stores the LSN of the last record applied to it. Recovery is redo:

1. The database reads the last checkpoint and finds the LSN where redo starts.
2. It reads the log forward from there, one record at a time.
3. For each record it compares the record's LSN with the page's, applying the change if the page is older and skipping it if not. A torn page is first rebuilt from the full copy kept for it, since its own LSN cannot be trusted.
4. It stops at the end of the valid log, the last record whose checksum holds.

Because of that comparison, a second crash during recovery costs only time: the next start redoes from the same point. Transactions that never committed are handled differently by different engines. InnoDB rolls them back with undo records it keeps for that purpose; PostgreSQL leaves their row versions in place and marks those transactions aborted, so no query sees them.

Letting the log forget

Left alone, the log grows forever and recovery replays all of it. A checkpoint bounds both. In PostgreSQL it writes out every page that was dirty when it began, then records that everything before a certain LSN, the redo point, is in the data files; InnoDB instead moves its redo point forward continuously as it flushes the oldest dirty pages. Recovery starts at the redo point, and older log can be recycled, unless the database has been told to keep it for something that still reads it: a replica that has not caught up, an archive, a change-data-capture reader. With default settings, a PostgreSQL replication slot whose reader has vanished holds every log file since, until the disk fills and the database can no longer write.

The same log, read by others

Because the log holds every change in order, it is useful beyond recovery. Replayed on another machine, it keeps a replica in step, as in PostgreSQL's streaming replication (Replication & read replicas). Decoded into row changes, it feeds Change data capture. Archived with base backups, it allows restoring to a chosen moment (Backups, high availability & disaster recovery). LSM-tree stores keep one in front of their in-memory table (Data structures behind big systems).

Not the log of Event Sourcing

Both append changes and replay them, and there the resemblance ends. A WAL is the database's private machinery: its records usually describe storage rather than business, applications never write to it, and once a checkpoint and every reader are done with them they are discarded. In Event Sourcing, the log of domain events ("Mira gave Oskar 500 gold") is the source of truth, kept and read by the application. Writing a row and a message together from application code is the job of Transactional Outbox.

The trade, in eight nodes

The diagram above is most of an answer to the Write-Ahead Log challenge, which allows eight nodes. The Game server becomes a Client, the storage engine a Handler; the Handler's edge to the Write-Ahead Log node says the change is appended and flushed first, and only a later edge reaches the Data Store. The edge from the log back to the Data Store is the replay after a crash, and a Snapshot node plays the checkpoint, with an edge saying it lets the log be truncated. Write append-only on the log's edge, since the brief grades it. The palette also offers Event Sourcing, Transactional Outbox and Message Broker, and the trade needed none of them.