Write-Ahead Log (WAL) & Crash Recovery

The problem

A process can die between any two instructions: power loss, OOM kill, a kernel panic. A store that updates its data structures in place can be caught half-way, with a B-tree page split done but not linked, or money debited but not credited. The write-ahead rule fixes this: describe the change in an append-only log, make that log durable, and only then acknowledge the change or apply it anywhere else. After a crash, replaying the log rebuilds the state.

Where it shows up: PostgreSQL WAL, MySQL/InnoDB redo log, SQLite -wal mode, RocksDB/LevelDB *.log, etcd and every Raft implementation (the replicated log is a WAL), Kafka log segments, ZooKeeper transaction logs, and filesystem journals (ext4/jbd2, NTFS $LogFile).

What this build does

wal.js has two layers:

• WriteAheadLog: segmented binary log. append() buffers a record and assigns an LSN, flush() writes the buffer with one write() and one fsync(), roll() starts a new segment, truncateBefore(lsn) deletes whole covered segments, open() scans and repairs.
• DurableKV: a Map-backed store on top. put / del / batch resolve with the LSN after fsync. checkpoint() writes a snapshot and truncates the log.

Record format (17-byte header, little-endian)

0        4        8                16   17
 +--------+--------+----------------+----+------------------+
 | len u32| crc u32|    lsn u64     |type| payload (len B)  |
 +--------+--------+----------------+----+------------------+
            crc32 covers  [lsn .. end of payload]

• len lets the reader find the next record, and it is sanity-checked (maxRecordBytes) so a corrupt length cannot make the reader allocate 4 GB or skip into garbage.
• crc (CRC-32/IEEE, implemented in crc32Js, with zlib.crc32 used when the runtime has it) catches torn and bit-flipped records. The test checks the standard value crc32("123456789") = 0xCBF43926 and that the JS and zlib versions agree.
• lsn must go up by exactly one, and each segment is named after its first LSN (wal-00000000000000000001.log). A gap means a record went missing, and that counts as corruption even when every CRC checks out.
• A write batch is one record, so a multi-key update is atomic: its CRC either verifies or the whole batch is gone. RocksDB's WriteBatch works the same way.

Invariants

1. A write is acknowledged (its promise resolves) only after the fsync covering its record returns.
2. A write becomes visible to get() only once it is durable, so readers never see data a crash could take back.
3. Recovery replays a prefix of the log. It stops at the first invalid record (torn header, torn payload, bad length, CRC mismatch, LSN gap) and truncates the file there, so later appends never land after garbage.
4. The checkpoint order is roll, then write the snapshot (tmp + fsync + rename + dir fsync), then delete segments. A crash between any two steps leaves either the old snapshot with the full log, or the new snapshot with redundant segments that are skipped by LSN.

Recovery modes (for corruption that is not at the tail)

A torn tail is the normal result of a crash. Corruption in the middle of the log means the disk or a bug is at fault. Throwing forces someone to look instead of quietly losing acknowledged data.

Group commit

With sync: 'group', every batch issued in the same event-loop tick (up to groupMaxRecords) shares one write and one fsync. The demo shows 200 concurrent writers needing 200 fsyncs with always and 4 with group. Latency per write goes up by at most one tick, and throughput goes up by roughly the batch size. PostgreSQL (commit_delay), InnoDB and the binlog all use the same trick.

Complexity

• Append: O(record size) to encode, plus a buffer copy. The fsync is the real cost: roughly 0.05–10 ms depending on the device, which is why group commit matters.
• Recovery: O(log bytes since the last checkpoint), one sequential read of each segment.
• Checkpoint: O(state size) to serialise, which bounds replay time and disk usage.
• Space: live state + snapshot + log since the last checkpoint.

Failure modes & trade-offs

• fsync lies: some consumer disks and VMs acknowledge a flush that is still sitting in a volatile cache. No software fix exists. Use enterprise drives with power-loss protection.
• fsync errors are fatal (the 2018 "fsyncgate" issue in PostgreSQL): after a failed fsync, Linux may drop the dirty pages and a retry can "succeed" without the data. Here a flush error rejects every waiter. A real database would crash and recover from the log.
• Directory fsync: creating, renaming or unlinking a segment is durable only once the directory is fsynced. fsyncDir does that on POSIX and is a no-op on Windows, where it is not supported.
• CRC32 is not cryptographic. It detects accidental damage, not tampering. CRC-32C is what RocksDB, ext4 and iSCSI use, because CPUs have an instruction for it. IEEE CRC-32 is used here so zlib can cross-check it.
• Stopping at the first bad record can throw away later records that are still valid. Skipping over a hole would replay history out of order, which is worse.
• Snapshots here are full JSON dumps. Real engines checkpoint incrementally (dirty pages in PostgreSQL, SSTable flushes in RocksDB) rather than rewriting all state.
• One JSON record per batch keeps the code simple. Binary op encoding would be smaller.

How production systems do it

• PostgreSQL: 16 MB WAL segments. Each record header carries total length, a pointer to the previous record, and a CRC-32C. synchronous_commit chooses when a commit waits for the flush. A checkpoint records a REDO point and old segments are recycled. full_page_writes guards against torn data pages, which a WAL alone cannot repair.
• RocksDB: 32 KB blocks. Each physical record has a checksum, a length and a type (FULL/FIRST/MIDDLE/LAST) so large batches can span blocks. WALRecoveryMode offers kTolerateCorruptedTailRecords, kAbsoluteConsistency, kPointInTimeRecovery (the default) and kSkipAnyCorruptedRecords. A WAL file becomes obsolete once its memtable is flushed to an SSTable.
• SQLite WAL mode: frames carry cumulative checksums and a salt. Recovery keeps frames up to the last valid commit frame. A checkpoint copies pages back into the main database file.
• etcd: 64 MB segment files with a CRC per record, chained across records. wal.Repair truncates a torn tail, and snapshots let old segments be released.
• Kafka: log segments with a CRC per record batch. After an unclean shutdown the broker re-validates segments and truncates at the first invalid batch. By default it relies on replication rather than per-message fsync (flush.messages).
• InnoDB: innodb_flush_log_at_trx_commit = 1 (fsync at commit), 2 (write at commit, fsync once a second) or 0. This is the durability-versus-throughput knob in one setting.

Extension exercises

1. Switch to CRC-32C (Castagnoli, polynomial 0x82F63B78) and add RocksDB-style masking so the CRC of a record that contains CRCs is not trivially related to them.
2. Add block framing (32 KB blocks, FIRST/MIDDLE/LAST fragments). After a corrupt length, the reader can then resync at the next block boundary instead of losing the rest of the segment.
3. Add a time window to group commit (for example, wait up to 2 ms or 64 records) and measure p50/p99 latency against throughput.
4. Write a fault-injecting fs shim that fails or short-writes the Nth write/fsync, and prove that no acknowledged write is ever lost.
5. Make checkpoints fuzzy: take the snapshot while writes continue, recording the LSN at which it started, as ARIES and PostgreSQL do.