Durability: WAL & crash recovery

Frame format#

The WAL is a sequence of length-prefixed frames. Each frame header is 21 bytes: a 1-byte kind, an 8-byte LSN (the timeline), a 4-byte payload length, and an 8-byte FNV-1a CRC of the payload, followed by the payload bytes. There are two kinds: DATA frames (a mutation's op payload) and a COMMIT marker (empty payload) that ends a transaction.

  ┌────────┬──────────┬───────────┬──────────┬──────────────┐
  │ kind 1 │  LSN  8  │  len  4   │  crc  8  │  payload len │
  └────────┴──────────┴───────────┴──────────┴──────────────┘
   kind = 0 DATA  |  kind = 1 COMMIT (empty payload)
   crc  = FNV-1a(payload)

The mutation op payload itself is [op u8][table_len u32][table][record bytes], where op is PUT (0) or DELETE (1). These are the same bytes the change stream ships to followers, so a follower applies them through the identical recovery decode path.

COMMIT markers and transaction atomicity#

append_txn writes every payload as a DATA frame and then a COMMIT marker, in ONE buffered write. A transaction's data frames become durable only once the COMMIT marker lands. During recovery, DATA frames accumulate as pending; a COMMIT marker promotes the pending frames to committed and records the committed length. A crash after some DATA frames but before the COMMIT marker leaves those frames uncommitted — they are discarded.

Recovery and torn-tail truncation#

Recovery scans frames from the start. It stops at the first sign of damage: a header that runs past end-of-file, a payload longer than the remaining bytes (a torn payload), a CRC mismatch, or an unknown frame kind. It returns the payloads of all fully-committed transactions in order, truncates the file to the last committed offset (dropping any trailing uncommitted/torn frames), and sets the next LSN to one past the highest LSN seen. The result is that committed data always survives and partial writes never corrupt state.

-- append_txn(["keep"]) then a CRASH after uncommitted data frames
-- on reopen:
recover()

// returns [ "keep" ]  -- the uncommitted trailing frames are truncated

Durable vs Applied acknowledgement#

Durable

the write is acknowledged only AFTER the WAL is fsync'd — it survives a crash. append_txn(..., durable = true) fsyncs before returning.

Applied

the write is acknowledged after the in-memory apply, with the fsync deferred — read-your-writes with higher throughput but weaker crash durability.

Restart restores catalog, data, and indexes#

A durable engine recovers the committed log on open; recovered ops buffer until their table is re-declared, then replay in log order (PUT upserts by _id, DELETE removes). Because table and index definitions are recorded in _sys_tables / _sys_indexes, a restart restores the full catalog — re-creating user tables (whose data replays from the WAL) and rebuilding their indexes.

-- session 1 (durable engine):
INSERT INTO acct { name: "a", bal: 100 }
INSERT INTO acct { name: "b", bal: 200 }
INSERT INTO acct { name: "c", bal: 300 }
UPDATE acct SET bal = 250 WHERE name = "b"
DELETE FROM acct WHERE name = "c"
-- reopen, re-declare acct, then:
SELECT * FROM acct SORT name ASC

// count 2 -> a (bal 100) and b (bal 250); c was deleted

Change observers (CDC / replication)#

After every committed mutation, the engine notifies registered change observers with (seq, op_frames) — a monotonic change sequence and the same op-frame bytes the WAL recorded. This single hook drives both WAL replication (ship the frames to a follower, which applies them via apply_replicated through the recovery path) and CDC / WebSocket change subscriptions (decode + fan out). It works in memory mode too (the seq is engine-assigned). Observers run inline on the commit path, so they must be cheap (e.g. push to a channel).

-- follower subscribes to the master's change stream and applies frames
master: INSERT INTO t { name: "ada" }
master: INSERT INTO t { name: "bob" }
master: UPDATE t SET name = "ada2" WHERE _id = 1
master: DELETE FROM t WHERE _id = 2
-- on the follower:
SELECT count(*) FROM t
SELECT name FROM t WHERE _id = 1

// follower count -> { "count_all": 1 }
// follower SELECT name WHERE _id = 1 -> "ada2"   (mirrors the master exactly)