Write-Ahead Logging and the Commit Record

An update touches eight pages scattered across a file. Written in place, the update needs eight ordered writes and eight barriers, and a crash in the middle leaves a state where some pages hold the new value and some hold the old. A log replaces that with one append to a contiguous region and one barrier, and the crash leaves a state that recovery can resolve deterministically. The price is that every change is written twice, once to the log and once later to its home location, and that recovery must be able to run on a state that is itself the product of an interrupted recovery.

The protocol is two rules, not a file format

Write-ahead logging rests on two rules that hold regardless of how the log is laid out. First, a change must reach the log before the page it modifies reaches its home location. Second, a change is committed when a commit record for it is durable, and no change may be applied to a home location before that record exists. Everything else, including block sizes, record headers, checksums, and whether the log is a separate file or a region of the same file, is an implementation choice in service of those two rules.

The first rule is what makes undo possible. If a page in its home location is newer than the log, the log cannot describe how to reverse it, because the description was overwritten. Keeping the log ahead of the home location means the log always holds the most recent version of every change, so a crash can always be resolved by consulting it.

The second rule is what makes a commit a single event. The home locations of a transaction’s pages may be spread across many blocks and updated over a long period; the commit record is one small block at one known place, and its durability is the moment the transaction becomes irreversible. Before that moment the transaction can be rolled back; after it, it must be completed.

One append, one barrier

The performance argument is entirely about the barrier count. A transaction that dirties 500 pages writes 500 log records into a buffer, appends them contiguously, and issues a single flush covering the whole append. The home locations are written later, in whatever order the writeback machinery chooses, with no barrier between them, because their order does not matter: if a crash loses some of them, the log still holds the records needed to redo the rest.

That is the trade. Logging writes every byte twice, which costs bandwidth and media wear. In exchange, the number of synchronous round trips per transaction drops from one per page to one per transaction, and the log writes are sequential, which is the access pattern both hard drives and flash prefer. For a transaction touching many small scattered pages, the exchange is heavily favourable. For a transaction touching one page, the log is pure overhead, which is why some systems bypass it for single-page updates or keep the log record in the page itself.

The sequential property is worth stating precisely. A log is appended at a head pointer that advances monotonically, so the writes land in blocks that are physically adjacent or at least in the same erase unit on flash. Flash translation layers handle sequential writes with less garbage collection than random ones, so a log-shaped workload has better endurance characteristics than an in-place one. That is the observation behind log-structured filesystems, and it is why a log is often placed on separate media from the home locations.

What makes a commit record valid

A commit record is a small structure: a magic value, a log sequence number, a length, a checksum over the preceding records, and sometimes a transaction identifier. Validation is a conjunction, and every term of it exists because some failure mode would otherwise be undetectable.

The magic value distinguishes a commit record from a block of zeroes, which is what a freshly allocated or trimmed region reads as. Without it, a log region that was never written would validate as a commit of an empty transaction. The checksum covers the records the commit claims, so a torn append, where a commit record reached media while the records before it did not, fails validation rather than committing garbage. The length bounds the region the checksum covers, so a commit record whose length field was itself corrupted cannot cause recovery to read past the log.

A log sequence number orders the records and lets recovery find the most recent valid commit. When the log wraps, the sequence number is what distinguishes a stale record left from the previous generation from a current one, because the bytes at a given offset are reused and their content alone does not say which generation they belong to.

The checksum choice is a real decision. A 32-bit CRC detects random corruption with high probability but is cheap to compute and easy to get wrong in the polynomial; a stronger hash costs more per record but makes a false positive essentially impossible. The relevant property is not cryptographic strength but the probability that a torn or partially overwritten record passes, and that probability is dominated by whether the checksum covers the header fields as well as the payload.

Replay has to be idempotent

Recovery reads the log from the last checkpoint forward, finds the last valid commit, and applies the records after the checkpoint up to that commit. Applying a record means writing its after-image to the page’s home location. If the crash happened during recovery, some of those writes completed and some did not, and the next recovery run starts from the same checkpoint and applies the same records again. That is only safe if applying a record twice produces the same state as applying it once, which is true for a record that carries a full after-image and false for a record that carries an increment.

The distinction is why physical logging writes whole pages or whole byte ranges with their contents, rather than “increment the counter at offset 40”. A full after-image is idempotent by construction. An increment is not: replaying it twice doubles the change, and a recovery that is interrupted after applying half the log would produce a state no crash could have produced directly.

Recovery also has to know where to stop. A record whose sequence number is below the checkpoint’s is already reflected in the home locations and must not be replayed, or the pages would be rolled back to an older state. A record above the last valid commit belongs to a transaction that never committed and must not be applied at all. The checkpoint record itself carries the log sequence number of the oldest record still needed, which is how the log’s tail can be reclaimed: everything before that number is reflected in the home locations and can be reused.

The log is a ring, and the ring is the bottleneck

A log is a fixed-size region used as a circular buffer. Space can be reclaimed only after the home locations for the records in that space are durable, because until then the records are the only copy. This is the log’s central constraint: the log’s size bounds the amount of un-checkpointed work, and the checkpoint rate bounds throughput.

If the log fills before a checkpoint completes, writers must stall. The stall is not a bug but a design limit, and its severity depends on how the checkpoint is performed. A checkpoint that writes every dirty page in one burst creates a long pause; one that spreads the writes over the interval, keeping the dirty page count roughly constant, avoids the pause at the cost of continuous background write traffic. The trade is between latency spikes and steady overhead, and it is the same trade that appears in Checkpointing and the Cost of a Consistent Snapshot.

The ring also interacts with flush semantics. Appending to the log must not overwrite a region whose records are still needed, and the write of the new record must not reach media before the record it follows. Because the ring is contiguous and the append is sequential, the ordering is usually automatic within a device, but a wrap that returns to the start of the region writes to a location that was written long ago and may still be in the device’s cache. A flush before the wrap, or FUA on the records around it, is what keeps the sequence intact.

Failure modes that the protocol does not cover

Write-ahead logging assumes the log itself is intact up to the last valid commit. If the media corrupts a record in the middle of the log, replay produces a state that mixes the pre-corruption prefix with whatever follows, and the checksum on the commit record may still validate if the corruption is in a record the checksum does not cover or if the corruption happened after validation. A per-record checksum narrows this but cannot eliminate it: a record that is silently corrupted in a way that preserves its checksum is undetectable, and a record corrupted after the commit’s checksum was computed is exactly the case a commit-level checksum misses.

The protocol also assumes the home locations can be written in any order. On a device that reorders, that is true. On a RAID array with parity, writing one home page requires reading the other pages in its stripe to recompute parity, and a crash between the data write and the parity write leaves the stripe inconsistent. The log can repair the data page but says nothing about the parity, which is why arrays add their own journal or rely on scrubbing. That interaction is treated in Torn Writes and the RAID Write Hole.

Finally, the log does not by itself give the reader a consistent snapshot. A reader that reads home locations while a transaction is half-applied sees a mixture unless the system provides versioning or takes a lock. The log makes recovery deterministic; making concurrent readers see a coherent state is a separate mechanism, and the two are often confused because both are described as “atomicity”.