The write-ahead log and crash recovery

Which of the morning’s orders are still real?

At 12:40, in the middle of a lunch rush, the machine running the kitchen’s database lost power. The cloud provider’s status page later called it a host failure. Ninety seconds later the database was running again.

Within those ninety seconds the staff were already asking a question. At 12:39, one minute before the power cut, a customer had been shown “Confirmed” for her order. Was that order still in the database? The database had said it was saved, but it was not clear where.

The database stores rows in 8 KB pages (lesson 2.1). It keeps recently used pages in memory and writes changed pages to disk later, and memory is exactly what a power cut erases. If the confirmed order lived only in memory when the power went, it was gone. And if the power went while a page was half written, that page could be left corrupted on disk.

The kitchen’s accountant keeps a khata, a day book. Every sale of the last six years is in it, in pen. A mistake is never rubbed out: a line goes under the wrong entry and a correcting entry goes below it, with the date. Every sale goes into the day book as a new line before anything else happens, and the totals are added up later, whenever there is time. The book has never lost an order.

As it turned out, the order was there, and so were the other forty-one orders from that lunch rush. The database works the way the day book does. Before reading on, decide what must have reached the disk before the customer was shown “Confirmed”.

Pause and predict The database keeps busy pages in memory and writes them later. When it says “saved”, what has reached the disk?

Writing in place is not safe

A database keeps its tables in fixed-size pages on disk; PostgreSQL’s are 8 KB. To be fast it caches pages in memory, in the buffer pool, and changes them there. Sooner or later each changed (“dirty”) page must be written back. Three things can go wrong if that write is the only record of the change.

Pause and predict The disk writes in 512-byte sectors. Power fails while the database is writing one 8 KB page. What can be on disk afterwards?

• Memory is lost in a crash. A change that lives only in a dirty page in memory disappears with the power.
• A page write is not atomic. Disks write in sectors, traditionally 512 bytes. An 8 KB page is 16 sectors, and power can fail after some of them. The result is a torn page: half old, half new, and wrong.
• A transaction touches several pages. An order inserts a row on one page and lowers stock on another. If one page reaches the disk and the other does not, the database holds half a transaction.

The naive fix is to write every page a transaction touched before telling the customer “confirmed”. That is slow: the pages are scattered across the disk, so a commit becomes many random writes, each one waited for. And it still does not fix torn pages, or a crash halfway through the writes.

Write-ahead log (WAL)

An append-only file where the database records every change before it changes the table pages. A transaction counts as committed once its log records, including its commit record, are safely on disk.

For example: “LSN 1042: in page 812, set stock of thali to 41. LSN 1043: transaction 77 commits.” The pages are written later, in any order.

A mental model

The accountant’s day book works the same way as a write-ahead log.

Three rules make the log work.

• Commit means “the log is on disk”. At commit the database appends a commit record and flushes the log up to it with fsync. The table pages can wait. One sequential write replaces many scattered ones.
• The log goes first. A dirty page may reach the disk before its transaction commits (databases do this to free memory), but never before the log records that describe it. So recovery always has the information to redo a change or to take it back.
• Checkpoints limit how much log is replayed. Every so often the database writes all dirty pages and records a checkpoint in the log. Everything before it is already in the pages, so recovery starts reading at the last checkpoint, not at the start of the log.

Recovery after a crash then has two jobs, in the scheme described by the ARIES paper (Mohan and colleagues, 1992). Redo: read the log from the last checkpoint and reapply every change, including changes of transactions that never committed, so the pages match the log exactly. Undo: roll back the changes of every transaction with no commit record in the log. PostgreSQL does only the redo half. It does not need undo, because every row version carries the id of the transaction that wrote it, and rows written by a transaction that never committed stay invisible to everyone (you will see why in lesson 2.3).

What the log costs, and what it buys

The cost is one flush per commit. An fsync takes from well under a millisecond on a server SSD that can survive power loss, to several milliseconds on a spinning disk or on many cloud volumes. Say it takes 2 ms. If every commit flushed the log alone, one log could commit at most 1,000 / 2 = 500 transactions a second.

Group commit removes that ceiling. While one flush is in progress, other transactions queue their commit records behind it, and the next flush makes all of them durable at once. If 40 commits share each 2 ms flush, that is 40 × 500 = 20,000 commits a second from the same disk. PostgreSQL does this naturally under load; its commit_delay setting can make the first transaction in a group wait a few microseconds so that more commits join its flush.

Checkpoints trade steady work for fast recovery. PostgreSQL checkpoints every 5 minutes by default, or sooner when the log since the last one approaches max_wal_size, 1 GB by default. Recovery replays the log since the last checkpoint. If replay runs at, say, 100 MB a second (an illustrative rate; it depends on the disk and the work), 1 GB of log takes about 10 seconds. More frequent checkpoints mean a shorter replay but more page writes during normal running.

Torn pages cost log space. With full_page_writes on (the default), the first change to a page after each checkpoint logs the whole 8 KB page as well as the change. If that page is torn by a crash, recovery restores it from the image and replays later changes on top. The price is a burst of extra log volume right after every checkpoint, which is one reason not to checkpoint too often.

Must every commit wait for the disk?

PostgreSQL lets you choose, per transaction, whether a commit waits for its log flush. With synchronous_commit = off the database replies at once, and its log writer flushes a moment later. With the 2 ms flush assumed above, that is about 2 ms saved per commit. Whether that saving is worth the risk depends on the data.

Each side is right about a different kind of data. The PostgreSQL documentation is precise about what asynchronous commit risks: the most recent transactions may be lost, for up to three times wal_writer_delay (200 ms by default), so up to about 600 ms. It does not risk corruption: commits are replayed in order, so a later transaction never survives while an earlier one it depended on is lost. Because the setting can be chosen per transaction, the decision is per kind of write.

What to remember

1. A database changes pages in memory and writes them back later. The write-ahead log is what makes that safe: every change is appended to the log first.
2. A transaction is committed when its commit record is flushed to disk. Only the log is flushed at commit; group commit lets one flush serve many transactions.
3. The WAL rule: a page may reach the disk before its transaction commits, but never before the log records that describe it.
4. Recovery redoes the log from the last checkpoint and removes the effects of transactions that never committed (undo in ARIES; invisibility in PostgreSQL). Checkpoints limit how long that takes.
5. Asynchronous commit risks losing the last fraction of a second of commits, never consistency. Choose it per kind of write.

Log the change before you touch the page, and call it committed only when the log is on disk.

In the real world

The simulator has three pages and a log you can read in one glance. A real database logs index changes, page splits, full page images and much more, writes the log in segments (16 MB files in PostgreSQL), and archives old segments for backups and point-in-time recovery.

The log turns out to be useful far beyond crashes. Ship it to another machine and replay it there, and you have a replica (lesson 3.1). Read it to find out what changed, and you have change data capture (lesson 6.5). Make the log itself the product, and you have Kafka (lesson 5.2).