The Write-Ahead Log: Append-Only Durability

The memtable lives in RAM. If the process crashes before the memtable flushes, every unflushed write is lost. The write-ahead log (WAL) is the durability backbone: every write is appended to a sequential log file before it is applied to the memtable, so we can replay it after a crash.

The Protocol

write(k, v):
    1. seq = ++global_seq
    2. wal.append(encode(seq, k, v))
    3. wal.fsync()              # durability boundary
    4. memtable.put(k, v, seq)
    5. ack to client

The fsync between steps 2 and 4 is the actual durability commit. Once it returns, the write survives a crash even if the memtable never flushes.

Why "Ahead Of Write"?

Because the log is written before the memory state changes. On recovery, we look at the WAL: anything in the log is recoverable; anything not in the log is, by definition, not durable.

Record Format

A WAL record needs four things:

A common framing:

| 4B crc | 1B type | 8B seq | 4B klen | key | 4B vlen | value |

Records are concatenated with no padding. Crash recovery reads sequentially, validates each CRC, and stops at the first bad record (torn write at the tail).

Sequential I/O Is The Whole Point

WAL writes are always appends to the end of a file — the disk head never seeks, the SSD never writes random blocks. On rotational disks this means ~200 MB/s sustained throughput vs ~1 MB/s for random 4 KiB writes. On NVMe SSDs the gap is smaller but still 2-5x.

fsync vs fdatasync

fsync forces both file data AND metadata (mtime, size) to disk. fdatasync skips metadata when it doesn't affect recoverability. RocksDB uses fdatasync for the WAL because the file already exists at known size — saves a few hundred microseconds per write.

Group Commit

Per-write fsync is expensive (~1 ms even on NVMe). High-throughput systems batch many writes into one fsync: group_commit. Several concurrent writers append, then one fsync covers them all. Throughput goes from a few thousand to tens of thousands of ops/sec.

This is the same trick that PostgreSQL, MySQL, Kafka, and every serious storage engine uses.