Write-Ahead Log Record Ordering and the Force-at-Commit Boundary

A page in the buffer pool is modified in place, so the previous contents are destroyed by the write. If the machine loses power after that modification but before the page reaches disk, the page on disk is still the old one — that case is harmless. The dangerous case is the reverse: the page reaches disk while the log describing the change does not. Recovery then reads a page containing a change it has no record of, and the database’s state is neither the old one nor the new one. Write-ahead logging is the rule that forbids this ordering, and every durable engine implements it in essentially the same way.

The rule, stated precisely

The write-ahead rule has two parts, and both are necessary.

Redo ordering. Before a page may be written to its permanent location, every log record that describes a change to that page must already be on stable storage. Equivalently: a page’s on-disk version may never be newer than the log.

Undo ordering. Before a log record describing a change may be written, the log records describing the previous versions of the data it overwrites must already be on stable storage. This is what allows recovery to undo a partially applied transaction without having lost the before-image.

The first rule makes recovery possible at all. The second makes rollback possible after a crash. An engine that violates the first will, after a crash, find pages that cannot be explained; an engine that violates the second can redo forward but cannot undo backward, so it must instead ensure that uncommitted changes never reach a page at all — a much more expensive proposition.

The standard implementation of the second rule is not to log before-images at all, but to hold a transaction’s changes in the buffer pool and prevent them from being written until the transaction commits. That is the no-steal policy. It removes undo from the crash path entirely, at the cost of a buffer pool that must hold every uncommitted page. Engines that allow stealing — writing uncommitted pages to disk to bound pool usage — must log enough to undo, which is why ARIES logs both redo and undo information and why its recovery has three passes rather than two.

LSNs and what comparison buys

Each log record is assigned a monotonically increasing log sequence number. The LSN is a byte offset into the log — PostgreSQL’s is a 64-bit value encoding the segment file and the offset within it — so it is both an identity and an ordering.

Every page carries the LSN of the last log record that modified it, stored in the page header. That single field makes three checks cheap:

• During normal operation, before writing a page, the engine compares the page’s LSN against the current flush LSN of the log. If the page is newer, the write must wait. This is the mechanical enforcement of the redo rule, and it is why a checkpoint cannot simply flush everything: it must first flush log up to the point covered by the pages it intends to write.
• During recovery, redo scans the log forward from the last checkpoint and applies each record only if the page’s stored LSN is less than the record’s LSN. A record whose effect is already present is skipped. This makes redo idempotent, which matters because a crash during recovery is a normal event.
• During recovery, undo scans backward and applies before-images, again guarded by LSN comparison so that repeated undo passes are safe.

The page LSN is also why recovery must start from a checkpoint rather than from the beginning of the log. A checkpoint records the LSN at which all pages dirty at that moment have been, or will be, written. Any change logged before that LSN is guaranteed to be reflected in the pages on disk, so redo may begin there.

What a checkpoint actually writes

A checkpoint is not a flush of the buffer pool. It is a promise about the future, and the promise is recorded before the work is done.

The sequence runs: write a checkpoint record to the log containing the current redo point and the list of active transactions; flush the log so the checkpoint record is durable; then write out the dirty pages. If a crash happens after the checkpoint record is durable but before the pages are written, recovery reads the checkpoint, sees that pages may still be behind, and redoes from the redo point. Correctness does not depend on the page writes having completed — only on the log being durable. That is the whole trick: the checkpoint converts an unbounded recovery scan into a bounded one, and it does so with a log write rather than with a page flush.

The consequence is that checkpoint duration and recovery duration trade against each other directly. A checkpoint taken rarely means a short checkpoint but a long redo scan after a crash, because more log lies between the redo point and the failure. A checkpoint taken often bounds recovery but spreads page writes across the workload, which is where the I/O spike associated with checkpoints comes from. Engines expose the checkpoint interval and often a target for how much of the log a checkpoint may leave un-replayed.

Force at commit, and why it is not per-statement

Durability requires that a committed transaction’s log records be on stable storage before the commit is acknowledged. Nothing else in the transaction needs to be flushed. The pages may remain dirty in the pool for minutes; the log record must be durable within the commit.

This is the force-at-commit boundary, and it is why the log is written far more often than pages are. A workload of many small transactions produces a log flush per commit and a page write per checkpoint. If each flush is a synchronous device operation costing on the order of a millisecond on rotating media, or tens to hundreds of microseconds on flash with a volatile write cache disabled, then commit latency is dominated by the flush and throughput is bounded by flushes per second.

Group commit breaks that bound. When several transactions commit concurrently, the engine collects their log records and issues one flush covering all of them. Each transaction waits for the same flush, so the latency of the slowest is roughly unchanged, but the number of flushes per second needed drops by the group size. The design question is how long to wait to form a group: waiting longer forms bigger groups and raises throughput, but adds latency to every transaction in the group. Engines typically let the group form naturally from transactions already in flight, flushing as soon as the log-writer wakes, with an optional short delay.

/* The commit path, reduced to its ordering constraints. */
bool commit(txn_t *t) {
    lsn_t commit_lsn = log_append_commit(t);      /* record is in the log buffer */
    if (!log_flush_upto(commit_lsn))              /* one flush may cover many txns */
        return false;                             /* cannot acknowledge */
    release_locks(t);
    /* Dirty pages stay in the pool; they will be written at the next checkpoint,
       and only after the log records covering them are durable. */
    return true;
}

Two details in that path are easy to get wrong. Locks are released only after the flush succeeds, because a reader that acquired a lock released too early could observe a state whose log is not durable. And the flush must cover the commit record itself, not merely the data records preceding it — a data record that is durable without its commit record leaves a transaction that recovery will treat as uncommitted and undo, which is correct but wasteful; a commit record durable without its data records is a lost transaction.

Failure modes at the boundary

The ordering rules are simple; the failures come from the layers underneath lying about durability.

A device with a volatile write cache that reports a flush as complete before the data reaches the medium breaks the force-at-commit guarantee without any bug in the engine. This is why engines and file systems issue cache-flush commands and why storage configuration matters: a battery-backed or non-volatile cache preserves the guarantee, a volatile cache that ignores flush does not.

A torn write — a page-sized write that lands partially because power failed mid-transfer — violates the assumption that a page write is atomic. The log records are typically written in smaller units and with checksums, so a torn log record is detectable and recovery can stop at the last valid one; but a torn data page has no such protection unless the engine adds one. The standard remedy is a second write of the page to a separate area before the in-place write, covered in doublewrite buffers and torn page detection.

Log truncation is the third. Once a checkpoint’s redo point has advanced past a segment and every page that could need redo from that segment has been written, the segment may be recycled. Recycling too early discards log that recovery needs; the accounting that prevents it is a comparison between the oldest page LSN still dirty in the pool and the segment boundary. An engine that loses track of a dirty page’s LSN — because the page was written without recording the LSN, or because a page was modified outside the logging path — will recycle log it still needs, and the corruption appears only after the next crash.

A fourth failure is subtler: a log record that is written but whose page modification was never made in the pool, followed by a crash, is fine — redo applies it. A page modification made without a log record is not. Every write path must therefore funnel through the logging interface, and the enforcement is structural rather than by discipline: the buffer manager refuses to mark a page dirty without an associated LSN.

Where the ordering surfaces to the user

The ordering constraints explain several behaviours that look arbitrary from outside. A COMMIT returning means the log is durable, not that the data file has changed; a subsequent crash and restart will replay the change. Setting a durability mode that skips the flush at commit converts the engine to a state where committed transactions can be lost after a crash, which is a legitimate trade for bulk loading and a silent correctness bug anywhere else.

They also explain why the log is a separate sequential file rather than part of the data files. Sequential append is the cheapest write pattern available, and keeping it separate from the random page writes means the log’s latency is not affected by the data files’ fragmentation. The cost is that every change is written twice — once to the log, once to the page — and that duplication is the first term in the write amplification accounting traced in write amplification across the storage stack. Whether the log can be avoided entirely depends on making pages immutable, which is the premise of the log-structured family discussed under LSM compaction strategies.