Record Format

Each WAL record is a binary structure with a CRC32 checksum for corruption detection. Records are append-only and immutable once written.

Offset  Size   Field           Type      Description
──────  ─────  ──────────────  ────────  ─────────────────────────────
0       8      LSN             u64 LE    Log Sequence Number
8       8      TX_ID           u64 LE    Transaction ID
16      1      OP_TYPE         u8        Operation type (1-6)
17      4      BEFORE_LEN      u32 LE    Length of before-image
21      var    BEFORE_IMAGE    [u8]      Before image (unused, redo-only recovery)
+len    4      AFTER_LEN       u32 LE    Length of after-image
+len    var    AFTER_IMAGE     [u8]      After image (redo data)
+len    4      CHECKSUM        u32 LE    CRC32 of all preceding bytes

Operation Types

Mutation Types

The WAL captures 24 distinct mutation types covering all state changes across graph, documents, functions, triggers, and metadata.

Graph Mutations

Document Mutations

Schema & Metadata Mutations

CRC32 Integrity Checks

Every WAL record includes a CRC32 checksum (IEEE / CRC-32b polynomial) computed over all preceding bytes. On recovery, each record's checksum is verified during deserialization. If a corrupt record is encountered, reading stops and recovery proceeds with all valid records up to that point.

fn crc32(data: &[u8]) -> u32 {
    let mut crc: u32 = 0xFFFF_FFFF;
    for &byte in data {
        crc ^= byte as u32;
        for _ in 0..8 {
            if crc & 1 != 0 {
                crc = (crc >> 1) ^ 0xEDB8_8320;
            } else {
                crc >>= 1;
            }
        }
    }
    crc ^ 0xFFFF_FFFF
}

Segment Management

WAL data is stored in fixed-size segment files (default 64 MB each). When a segment fills, the writer automatically rotates to a new one. Old segments are purged after a successful checkpoint.

data/wal/
  wal_000000000000.log    ← oldest (purged after checkpoint)
  wal_000000000001.log
  wal_000000000002.log    ← current segment

Crash Recovery

Recovery follows an ARIES-inspired redo-only protocol: read all records, find the last checkpoint, classify transactions, and replay only committed post-checkpoint mutations. Incomplete transactions are silently discarded.

Recovery Algorithm

Why Redo-Only?

Traditional ARIES requires an undo pass because its buffer pool can flush dirty pages from uncommitted transactions to disk. Anvil does not have this problem. The on-disk snapshot is always a consistent point-in-time image, and incomplete transactions only ever existed in memory — they are lost on crash and never reach the persisted state. Recovery simply loads the last snapshot and replays committed WAL entries forward from there, so no undo pass is needed.

pub struct RecoveryResult {
    pub redo_records: Vec<WalRecord>,      // Committed mutations to replay
    pub checkpoint_lsn: Lsn,               // Last checkpoint position
    pub max_lsn: Lsn,                      // Highest LSN (for resuming)
    pub committed_txs: HashSet<TxId>,      // Successfully committed
    pub incomplete_txs: HashSet<TxId>,     // Crashed mid-flight (discarded)
}

Checkpoint Strategy

Checkpoints bound the recovery window. A background task periodically checks if enough operations have accumulated, then flushes the in-memory state to disk and writes a checkpoint record to the WAL.

Checkpoint Process

1. Check if ops_since_checkpoint >= threshold
2. Save in-memory snapshot to disk (graph.dfgs)
3. Write Checkpoint record to WAL with fsync
4. Purge all WAL segments before current one
5. Reset operation counter to 0

Graceful Shutdown

On Ctrl+C or anvil stop, the server saves a final snapshot, writes a checkpoint record, and purges old WAL segments before exiting. This ensures the next startup has minimal or no recovery work.

Configuration

# WAL and checkpoint settings
[storage]
wal_sync_mode = "fsync"           # fsync, fdatasync, or none

checkpoint_interval_secs = 300   # 5 minutes
checkpoint_ops_threshold = 1000  # checkpoint after 1000 operations

Test Coverage

The WAL implementation is covered by 54 tests across 8 modules, verifying record serialization, checksum integrity, segment rotation, recovery correctness, and replay idempotency.

Durability Guarantees