Write-ahead log

Deep dive

How it works

In: change records (and commit markers) from writers · Out: a durable, ordered log; after a crash, the replayed state · State: log segments (PostgreSQL: 16 MiB), a flushed-LSN, the last checkpoint's redo point · Cost: append O(1); commit = 1 fsync (shared via group commit); recovery O(log since the last checkpoint).

1. WAL rule: a page whose pageLSN = x may go to disk only after the log is durable through x. The buffer pool checks this before every write-back.
2. Commit rule: a commit returns only after its commit record is durable.
3. Framing: [len u32][crc32c u32][lsn u64][payload]. The CRC covers the LSN and the payload.
4. Recovery: start at the last checkpoint, read records, verify each CRC and redo. The first short or bad record marks the torn tail. Truncate there and continue from that point.
5. Checkpoint: flush dirty pages (or log a fuzzy checkpoint with the dirty page table, see ARIES), record the redo start point, recycle older segments.

segment 000001          segment 000002 (preallocated)
[rec][rec][rec]...      [rec][rec][ torn | zeros ...]
               ^ checkpoint redo point      ^ recovery stops here and truncates

Code

use std::fs::{File, OpenOptions};
use std::io::{self, Read, Write};

fn crc32c(data: &[u8]) -> u32 { // bitwise; real code uses the SSE4.2 / ARMv8 CRC32C instruction
    let mut crc = !0u32;
    for &b in data {
        crc ^= b as u32;
        for _ in 0..8 { crc = (crc >> 1) ^ (0x82F6_3B78 & (crc & 1).wrapping_neg()); }
    }
    !crc
}

pub struct Wal { f: File, buf: Vec<u8>, next_lsn: u64 }

impl Wal {
    /// Opens the log, returns every intact record, and truncates a torn tail.
    pub fn open(path: &str) -> io::Result<(Wal, Vec<(u64, Vec<u8>)>)> {
        let mut f = OpenOptions::new().read(true).append(true).create(true).open(path)?;
        let mut data = Vec::new();
        f.read_to_end(&mut data)?;
        let (mut pos, mut recs) = (0usize, Vec::new());
        while pos + 16 <= data.len() {
            let len = u32::from_le_bytes(data[pos..pos + 4].try_into().unwrap()) as usize;
            let crc = u32::from_le_bytes(data[pos + 4..pos + 8].try_into().unwrap());
            let end = pos + 16 + len;
            if end > data.len() || crc32c(&data[pos + 8..end]) != crc { break; } // torn tail
            let lsn = u64::from_le_bytes(data[pos + 8..pos + 16].try_into().unwrap());
            recs.push((lsn, data[pos + 16..end].to_vec()));
            pos = end;
        }
        f.set_len(pos as u64)?; // new records must follow the last valid one
        f.sync_all()?;
        let next_lsn = recs.last().map_or(1, |r| r.0 + 1);
        Ok((Wal { f, buf: Vec::new(), next_lsn }, recs))
    }

    /// Buffers a record; not durable until `flush` returns.
    pub fn append(&mut self, payload: &[u8]) -> u64 {
        let lsn = self.next_lsn;
        self.next_lsn += 1;
        let start = self.buf.len();
        self.buf.extend_from_slice(&(payload.len() as u32).to_le_bytes());
        self.buf.extend_from_slice(&[0; 4]); // CRC placeholder
        self.buf.extend_from_slice(&lsn.to_le_bytes());
        self.buf.extend_from_slice(payload);
        let crc = crc32c(&self.buf[start + 8..]);
        self.buf[start + 4..start + 8].copy_from_slice(&crc.to_le_bytes());
        lsn
    }

    /// Durable through every LSN appended so far: one write + one fdatasync.
    pub fn flush(&mut self) -> io::Result<()> {
        self.f.write_all(&self.buf)?;
        self.buf.clear();
        self.f.sync_data() // fdatasync: data and file size, skips mtime
    }
}

This uses LSN = record number. PostgreSQL and InnoDB use the byte offset in the log as the LSN, so an LSN also locates its record.

Complexity and constants

• Sequential append bandwidth is order of GB/s on NVMe. Commit rate without batching is about 1 / fsync latency: 1 ms gives 1000 commits/s per log.
• Record overhead: 16-24 B header. PostgreSQL record headers are 24 B, plus a full 8 KiB page image the first time each page changes after a checkpoint, which often dominates WAL volume.
• Recovery time ≈ log since checkpoint / redo speed. Redo is often bound by random page reads, so it is order of minutes for GBs of log on slow disks. PostgreSQL defaults: checkpoint_timeout = 5min, max_wal_size = 1GB.

Efficiency

• Cost: sequential append is order of GB/s on NVMe; fsync is order of 10-50 µs on power-loss-protected enterprise NVMe, 0.1-several ms on consumer SSDs, 5-10 ms on HDD. Without batching, commits/s ≈ 1 / fsync latency (1 ms gives 1000/s per log). Records carry a 16-24 B header, plus a full page image per page after each checkpoint (PostgreSQL). Bound: fsync latency, not bandwidth.
• Levers:
  • group commit — one fsync for all waiting commits; PostgreSQL commit_delay helps only if other commits arrive in the delay — concurrent writers
  • synchronous_commit = off — can lose recent commits, stays consistent — loss-tolerant writes
  • wal_compression (pglz, lz4, zstd) — compresses full-page images for some CPU — image-dominated WAL volume
  • longer checkpoint intervals — fewer full-page images, longer recovery (PostgreSQL defaults: checkpoint_timeout = 5min, max_wal_size = 1GB) — recovery time budget allows it
  • redo-only no-steal logging, command logging, or copy-on-write pages — smaller or no log — in-memory databases, single-writer stores
• Naive → standard → state of the art:
  • write pages in place at commit · many random page writes, torn pages
  • WAL with CRC and one fsync per commit · 1 / fsync latency commits/s
  • group commit on power-loss-protected NVMe · fsync 10-50 µs shared by a batch

Implementation notes

• Preallocate segments (fallocate and zero-fill, or recycle old files). Appending to a preallocated file means fdatasync does not have to update metadata. Growing a file costs an extra journal commit in the filesystem.
• fsync the directory after creating or renaming a segment, or the file itself can vanish after a crash.
• O_DIRECT + O_DSYNC with 4 KiB-aligned writes skips the page cache (InnoDB innodb_flush_method=O_DIRECT). Pad the last partial block, and do not overwrite a block that holds acknowledged records unless the format tolerates a torn rewrite.
• macOS: fsync does not flush the drive's cache. You need fcntl(F_FULLFSYNC), which costs order of ms.
• Checksums: CRC32C runs at more than 10 GB/s with the hardware instruction. xxHash is fine when hardware CRC is missing.
• Record kinds: physical (byte ranges or page images), logical (operations), or physiological (per-page logical, the ARIES default). Physical redo is simpler; logical records are smaller.

Pitfalls

• fsync errors: on Linux, after a failed fsync the dirty pages may be dropped and the error cleared, so a retried fsync "succeeds" and data is lost. Treat any fsync failure as fatal, then crash and recover from the log (PostgreSQL has done this since 2018).
• Telling a torn tail from mid-log corruption: a bad record followed by valid ones is corruption, not a crash. Stop and alert instead of truncating.
• Drives that ignore flush commands (cheap SSDs, some VMs) make every guarantee void. Test with power-pull tools, and prefer drives with power-loss protection.
• The log grows without bound if checkpoints stall or a replica holds a replication slot.
• Writing the data page before its log record breaks the WAL rule and leaves no way to undo or redo.

Variants and alternatives

In production

• Databases: PostgreSQL WAL, InnoDB redo log, SQLite WAL mode, RocksDB and LevelDB WAL.
• Message logs and coordination: Kafka segments, etcd WAL, ZooKeeper transaction log.
• File systems: journaling file systems such as ext4 (jbd2) and NTFS keep a log of metadata changes.

Implementations

Sources

• C. Mohan et al., ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging, ACM TODS, 1992. paper
• J. Gray, A. Reuter, Transaction Processing: Concepts and Techniques, 1992.
• T. S. Pillai et al., All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent Applications, OSDI, 2014. paper
• A. Rebello et al., Can Applications Recover from fsync Failures?, USENIX ATC, 2020. paper
• PostgreSQL documentation, Write Ahead Log settings (synchronous_commit, commit_delay, wal_compression, full_page_writes). docs
• SQLite documentation, Write-Ahead Logging. docs