Write-Ahead Log (WAL): Durability and Crash Recovery

The problem. Updating a data file in place involves many scattered disk writes. A power cut halfway leaves a half-written, corrupt structure, and the in-memory changes that were never flushed are gone.

The rule. Write the intent to the log *first*, make sure it is durable (fsync), and only then acknowledge the commit. Data pages in the main files can be written later, lazily and in any order. Appending to a log is sequential I/O, which is far faster than random writes.

What a record holds. A log sequence number (LSN), a transaction id, and enough to redo the change (and sometimes to undo it): which key or page, the new value, a checksum. The checksum lets recovery detect a record that was cut off by the crash.

import json, os

class WAL:
    def __init__(self, path):
        self.f = open(path, 'a+')

    def append(self, op, key, value=None):
        self.f.write(json.dumps({'op': op, 'k': key, 'v': value}) + '\n')
        self.f.flush()
        os.fsync(self.f.fileno())   # durable before we acknowledge

Recovery. On restart, read the log from the last checkpoint and re-apply each record in order to the in-memory state or data files. A record whose checksum fails, or that stops mid-line, is the torn tail: discard it and everything after it, since its transaction was never acknowledged.

Checkpoints and truncation. If the log grew forever, recovery would take forever. A checkpoint flushes the data pages up to some LSN, after which older log records are no longer needed and can be deleted or archived. More frequent checkpoints mean faster recovery but more write work during normal operation.

Group commit. fsync is the expensive part. Batching several transactions' records into one fsync raises throughput at the cost of a tiny wait. Turning fsync off is fast but breaks the durability promise.

WAL everywhere. PostgreSQL, MySQL (redo log) and SQLite use it. Kafka's log is a WAL that is the data. Replication often just ships the WAL to replicas, who replay it, which is also how point-in-time recovery works. Idempotent replay (applying a record twice has no extra effect) keeps recovery safe if it crashes midway.