Database Write-Ahead Logging and Crash Recovery
A write-ahead log (WAL) is a sequential record of database changes that is saved to durable storage before the changed data pages are saved. After a crash, the database uses that log to reconstruct committed changes and remove changes from transactions that did not finish.
The problem WAL solves
A database normally keeps frequently used data pages in memory. A page is a fixed-size block containing rows and indexes; the in-memory copy is eventually written to the database files on disk. This improves performance, because writing one log stream is cheaper than immediately rewriting many scattered pages.
That delay creates a recovery problem. Consider a transaction that transfers money:
BEGIN;
UPDATE accounts SET balance = balance - 50 WHERE id = 1;
UPDATE accounts SET balance = balance + 50 WHERE id = 2;
COMMIT;
A crash can happen after the first page is written, before the second is written, or after both changes exist only in memory. Without a separate record of the work, the database cannot reliably determine what happened or restore a consistent state.
The log provides that record. It is usually an append-only sequence on disk containing transaction identifiers, the pages or records changed, and enough information to redo or undo each change. A physical log record might contain an old value and a new value; other systems use a logical description such as “insert this row.”
Why the log must go first
The central WAL rule is:
A log record describing a change must be durable before the corresponding changed data page is allowed to become durable.
Durable means that the database has asked the operating system and storage device to persist the bytes so they will survive a process failure or power loss. An in-memory copy, and often an ordinary write system call, is not enough; the database must use its durability mechanism, such as flushing the log.
Suppose a transaction changes a page in memory. The database may write the page to disk before writing its log record. If the machine then crashes, the disk contains the new data but the recovery process has no trustworthy description of the change. If the transaction was incomplete, recovery cannot undo it. If it had committed, recovery may not know that it needs to preserve or reconstruct the change.
Writing the log first removes that unsafe gap. Once the data page reaches disk, its corresponding log record is already available for recovery. The page can be newer or older than the log; either state is recoverable because the log explains the intended change.
This ordering applies at two levels:
- Before acknowledging
COMMIT, the database must flush the transaction's log records and its commit record to durable storage. The client can then rely on the commit surviving a crash, even if the modified data pages have not been written yet. - Before flushing a dirty page—a memory page whose contents differ from its disk copy—the database must flush all log records that describe changes on that page.
The database does not normally need to flush every data page at commit. That is one of WAL's main performance benefits: a small sequential log flush can establish durability while page writes happen later.
What recovery reads from the log
A log record commonly has a log sequence number (LSN), a position that identifies its order in the log. A data page stores the LSN of the latest log record applied to it. During recovery, the database can skip a redo operation when the page already has an equal or newer LSN, avoiding duplicate work.
A transaction also has a state in the log. Its records may be followed by a commit record, an abort record, or nothing if the crash interrupted it. A checkpoint is a recovery aid that records enough information about recent database state to avoid scanning the entire history from the beginning. It does not replace WAL or eliminate the need to handle writes occurring around the checkpoint.
Recovery is commonly explained in two broad phases.
1. Redo the logged history
Recovery first scans the relevant log records and reapplies changes that might be missing from data pages. This is called redo. It may redo changes from both committed and incomplete transactions: at this stage, the goal is to bring the pages to the state described by the log, regardless of whether the original page write happened before the crash.
Redo is what gives committed transactions durability. If a transaction's commit record was safely flushed but its data pages were still only in memory, recovery can replay its updates and make them visible again.
2. Undo incomplete transactions
After establishing the logged state, recovery identifies transactions without a durable commit record. These are often called incomplete or loser transactions. Their changes must not remain in the database, because the transaction never successfully finished.
Recovery walks those transactions' log records backward and applies the inverse operation: it restores an old value, removes an inserted row, or otherwise reverses the logged action. The resulting records are themselves logged in many systems so that recovery remains safe if another crash occurs during recovery. Such records are often called compensation log records.
The combination matters. Redo ensures that committed work is present even when data pages were not saved. Undo ensures that work from interrupted transactions is absent, even when some of their pages were saved before the crash.
Where you may have seen WAL
Database settings often expose a WAL directory, log retention, checkpoint interval, or synchronous-commit option. Error messages may mention an LSN, a log flush, a dirty page, or recovery replaying records. Replication systems also commonly ship WAL records to another server, using the same ordered change stream for a different purpose.
The essential idea remains simple: data pages may be written later, but the explanation for every written change must get there first.