Crash Recovery: Replaying the Log

When the engine starts, it doesn't know whether the previous shutdown was clean or a crash. Recovery is straightforward: read the WAL from the beginning and apply every record to a fresh memtable. Once we hit the first invalid (torn) record, we stop.

The Algorithm

def recover(wal_path):
    memtable = MemTable()
    last_good_offset = 0
    with open(wal_path, 'rb') as f:
        while True:
            rec = read_record(f)
            if rec is None:        # EOF or torn record
                break
            apply_to_memtable(memtable, rec)
            last_good_offset = f.tell()
    truncate(wal_path, last_good_offset)
    return memtable

That's the whole thing. The simplicity is the point: WAL recovery is a single linear pass over a single file.

Multiple WALs

A long-running system can accumulate many WAL files. The convention:

• Each WAL file is named by its starting sequence number, e.g. 000123.log.
• When a memtable is flushed to an SSTable, the WAL whose contents are now safely on disk in the SSTable is deleted. (The SSTable footer records the highest seq it contains; any WAL whose entries are all <= that seq is obsolete.)
• On recovery, find all *.log files, sort by starting seq, and replay in order.

Truncating Torn Tails

Crash recovery may find a bad CRC partway through the last WAL. The convention is to truncate the file at the last good offset and continue. That last partial record was never acknowledged to a client, so dropping it is safe.

Modern systems (RocksDB, BadgerDB) often write to a fresh WAL file after recovery rather than overwriting the truncated one — simpler to reason about.

Idempotence of Replay

What if recovery applies a PUT that was also already on disk in an SSTable? Not a problem: the SSTable holds an older version with a smaller seq number. The replayed write goes into the memtable with its original seq number. Later compaction sees both versions and keeps the newer one.

This is why sequence numbers are sacred: they make recovery idempotent.

What If the WAL Itself Is Corrupted?

If the body of an old record fails CRC (not just the tail), the database is in serious trouble. Possible recoveries: skip the bad record (lose that write), abort startup and require a backup restore, or run a special repair tool. Most engines abort and require operator intervention — silent data loss is worse than visible downtime.