Persistence & Recovery

A journal append passes through four layers, and each survives a different kind of failure:

1. Your userspace buffer (a BufWriter, your own batch). Lost if the process dies.
2. The kernel page cache. write() returns once the bytes are copied here. Survives a process crash, including kill -9 and an OOM kill: the kernel still owns the dirty pages and will write them back. Lost on a kernel panic or power loss.
3. The device's volatile write cache. Survives an OS crash. Lost on power loss unless the drive has power-loss protection (capacitors that let it drain its cache), which datacenter NVMe drives usually have and consumer drives usually don't.
4. The media. Durable.

fsync(fd) (Rust: File::sync_all) pushes layer 2 down to layer 4: it writes the file's dirty pages and metadata, waits for them, and asks the device to flush its cache. fdatasync (File::sync_data) skips metadata that isn't needed to read the data back, such as mtime, but still flushes a size change. That makes appends to a file that grows more expensive than overwrites inside a preallocated one.

The useful insight is what the layers imply. The most common failures, a panic, an OOM kill or a bad deploy, only lose layer 1. A write() that has returned already survives them. fsync buys protection against the machine dying, and next week replication buys the same thing a different way: the command is on another machine's page cache before you ack. Choosing an fsync policy is choosing which of those you pay for on the hot path.

The costs, roughly (they vary a lot with hardware and filesystem, so measure yours with fio --fdatasync=1):

• write() of a 64-byte frame into the page cache: on the order of a microsecond, mostly syscall entry and exit.
• fdatasync on a datacenter NVMe drive with power-loss protection: typically tens of microseconds, because the drive can acknowledge the flush from protected DRAM.
• fdatasync on a consumer SSD without power-loss protection: hundreds of microseconds to milliseconds, because the flush really goes to NAND.
• Cloud network block storage: often in the hundreds of microseconds to milliseconds, since every flush is a network round trip.

Against an exchange whose whole order-to-ack budget is tens of microseconds, the last two are disqualifying on the hot path. That is why the policy is explicit:

pub enum FsyncPolicy {
    /// fdatasync before acknowledging each command. Nothing acknowledged is
    /// ever lost to a power cut; every ack pays a full device flush.
    EveryCommand,
    /// Group commit: flush once per batch (max_batch commands or max_delay,
    /// whichever comes first). Acks wait for the flush that covers them, so
    /// nothing acked is lost, but one flush is amortized over many commands.
    Group { max_batch: usize, max_delay_us: u64 },
    /// No fsync on the hot path. The kernel writes back in the background.
    /// Durability against machine loss comes from replication (week 20).
    OsManaged,
}

The repo spells the same choices as SyncPolicy::{EveryN(n), Interval(t), Never}. EveryN(1) syncs every command before append returns. EveryN(n) and Interval(t) are the count and time triggers of group commit, and Never leaves writeback to the OS (only an explicit sync() flushes). Under those three, append can return before the flush that covers it, and durable_seq() tells the gateway which commands an ack may cover.

Group commit is the classic trick (every serious database uses it). With a 50 µs flush and batches of 64 commands, the flush costs under 1 µs per command in throughput terms, but every command in the batch waits for the flush. The latency floor is still one flush.

There are two more traps that catch experienced engineers.

New names need a directory fsync. Creating or renaming a file modifies the directory. fsync on the file makes its contents durable, not its name. The standard pattern for replacing a file atomically:

use std::{fs::File, io::Write, path::Path};

fn write_atomically(dir: &Path, name: &str, bytes: &[u8]) -> std::io::Result<()> {
    let tmp = dir.join(format!("{name}.tmp"));
    let mut f = File::create(&tmp)?;
    f.write_all(bytes)?;
    f.sync_all()?;                          // contents of the temp file
    std::fs::rename(&tmp, dir.join(name))?; // atomic replace on POSIX filesystems
    File::open(dir)?.sync_all()?;           // make the rename itself durable
    Ok(())
}

A failed fsync is not retryable. In 2018 the PostgreSQL developers discovered ("fsyncgate") that after a writeback error, Linux may mark the failed pages clean or drop them, so a second fsync can return success even though the data never reached the disk. PostgreSQL's response was to treat a failed fsync as fatal: crash, and recover from the write-ahead log. Do the same. An I/O error on the journal means the process stops and recovery, or the standby, takes over.

A snapshot is the engine's state at exactly one point in the sequenced input stream, labelled with last_seq: the sequence number of the last command whose effects it contains. Recovery loads it and replays every journal frame with seq > last_seq. Get that boundary wrong by one in either direction and you either apply a command twice or skip one. Nothing crashes; the book is simply wrong. The week 9 state hash is how you find out.

What goes in:

• Every resting order, in queue order. Priority is state. Two books with identical L2 depth at every price can still differ in who is first at each level, and the next aggressive order will fill different people. A snapshot that stores levels as (price, total_qty) is a market-data snapshot, not an engine snapshot.
• Per-instrument state: trading status (open, halted, auction), the reference price your week 15 price bands use, last trade price.
• Id and sequence generators: next order id, next execution id, the market-data sequence number from week 10. Restart these from the wrong value and you emit duplicate execution ids, or a market-data sequence that jumps backwards, which every subscriber will (correctly) treat as a gap.
• Risk state: positions and open-order exposure from week 15, and the week 17 throttle buckets if you want throttling decisions to replay identically.

What stays out: anything derived. The order-id → location index, the best-bid cache, slab indices, pointers. Rebuild them on load. Storing them means trusting them, and every extra field is another way for a snapshot to contradict itself.

For the format, reuse what you learned in week 11: fixed-width little-endian fields, explicit offsets, a magic number, a version, a checksum. It is tempting to serde-serialize your engine structs with bincode. Don't, at least not for this. That format is defined by your Rust types and silently changes when they do, and a snapshot must be readable by the next version of the binary, the one you deploy after the crash. An explicit, versioned format makes that a decision instead of an accident.

Size and speed: 100,000 resting orders at 25 bytes each is 2.5 MB. Encoding is a sequential write at memory bandwidth, so a few milliseconds at most. The harder question is when to take it, because the engine must not change while you copy it:

• Pause the engine thread between two commands and serialize. Trivially consistent. Costs a pause of a few milliseconds, which is fine at the close or during an auction and a visible latency spike mid-session.
• fork() and serialize in the child, relying on copy-on-write (Redis's background save works this way). There is no long pause, but fork copies page tables (cost grows with process size) and every page the engine writes afterwards takes a copy-on-write fault on the hot path.
• Snapshot on the standby. Next week's hot standby applies the same input stream; it can pause whenever it likes without affecting a single client. This is the answer for a production venue. For this week, pausing at a quiet point is fine.

The drill is the decoder you will reuse in the capstone. Pay attention to the order of the checks: magic, then version, then length, then checksum, then field values. Magic answers "is this a snapshot at all?" (wrong file, wrong directory). Version comes before the checksum because the layout, including where the checksum lives and which algorithm computed it, may differ between versions; a v2 file read by a v1 binary should fail with "unsupported version", which tells the operator what to do, rather than "corrupt", which sends them chasing a disk problem. And the decoder must never let an untrusted count drive an allocation.

// Snapshot format v1. All integers little-endian.
//
//   offset   size    field
//   0        4       magic     = b"SNAP"
//   4        2       version   = 1
//   6        8       last_seq  (seq of the last journal entry applied)
//   14       4       count     (number of resting orders)
//   18       25 × n  orders, in book priority order:
//                      id u64 | side u8 (0 = Buy, 1 = Sell) | price i64 | qty u64
//   18 + 25n 4       crc32c of every preceding byte
//
// decode() checks in this order and returns the FIRST failure:
//   1. fewer than 22 bytes                    → Truncated
//   2. magic != b"SNAP"                       → BadMagic
//   3. version != 1                           → UnsupportedVersion(v)
//   4. len < 22 + 25 × count                  → Truncated
//      len > 22 + 25 × count                  → TrailingBytes
//   5. stored crc != crc32c(prefix)           → BadChecksum
//   6. a side byte that is not 0 or 1         → BadSide(byte)
// It must never panic and never allocate based on an unchecked count.

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Side {
    Buy,
    Sell,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct RestingOrder {
    pub id: u64,
    pub side: Side,
    pub price: i64,
    pub qty: u64,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct BookSnapshot {
    pub last_seq: u64,
    /// Priority order: the order of this Vec IS the queue position.
    pub orders: Vec<RestingOrder>,
}

#[derive(Debug, PartialEq, Eq)]
pub enum SnapshotError {
    Truncated,
    BadMagic,
    UnsupportedVersion(u16),
    TrailingBytes,
    BadChecksum,
    BadSide(u8),
}

pub const MAGIC: [u8; 4] = *b"SNAP";
pub const VERSION: u16 = 1;
pub const HEADER_LEN: usize = 18;
pub const ORDER_LEN: usize = 25;
pub const TRAILER_LEN: usize = 4;

/// CRC-32C (Castagnoli), bit by bit. Production code uses the SSE4.2
/// `crc32` instruction or a lookup table; this is plenty for the drill.
pub fn crc32c(bytes: &[u8]) -> u32 {
    let mut crc = !0u32;
    for &b in bytes {
        crc ^= b as u32;
        for _ in 0..8 {
            let mask = (crc & 1).wrapping_neg();
            crc = (crc >> 1) ^ (0x82F6_3B78 & mask);
        }
    }
    !crc
}

pub fn encode(snap: &BookSnapshot) -> Vec<u8> {
    // TODO: reserve the exact size, write header, orders, then the crc
    // of everything written so far.
    let _ = snap;
    todo!()
}

pub fn decode(bytes: &[u8]) -> Result<BookSnapshot, SnapshotError> {
    // TODO: follow the check order above. Hint: a tiny helper like
    //   fn u64_at(b: &[u8], off: usize) -> u64
    // built on u64::from_le_bytes(b[off..off + 8].try_into().unwrap())
    // keeps this readable once the length has been verified.
    let _ = bytes;
    todo!()
}

The on-disk journal is a directory of segments: journal-00000000000001000001.log, named by the first sequence number they contain, each capped at a fixed size (say 1 GiB). Segment names make "where is seq N?" a binary search over file names, and make retention (Day 4) a matter of deleting whole files.

Preallocate each segment when you create it. If appends never change the file size, fdatasync has less metadata to flush. With fallocate alone the gain is smaller than you'd hope, because filesystems mark preallocated extents as unwritten and must convert them on first write. Zero-filling the segment avoids that, at the cost of writing it twice. Measure both. The zero-fill has a side effect you must handle: after a crash, the end of the file is full of zeros, not EOF.

The repo's FileJournal keeps this simpler: one file of back-to-back frames that only grows, with no segments and no preallocation. Segments are what retention and compaction would need. Its recovery still treats a zero-filled tail as torn, and a test checks that.

Every frame carries its own checksum. The repo's file holds week 9's frames unchanged, the same bytes the in-memory journal holds:

len: u32 | seq: u64 | crc: u32 | payload: [u8; len]      crc = CRC-32/IEEE of (len ‖ seq ‖ payload)

Today's drill uses a variant with the CRC in a trailer, len | seq | payload | crc32c. The recovery rules below are the same for both layouts.

CRC-32C is the usual choice for a new format because x86 has had a hardware instruction for it since SSE4.2 (crc32), which runs at several GB/s per core. That makes it effectively free next to the write itself. The repo stays with week 9's CRC-32/IEEE, computed in software with slicing-by-8 tables so the crate needs no dependencies. Recovery verifies the CRC of every frame in the file, so that CRC's speed shows up in this week's benchmark.

Now the crash. Storage devices only promise atomicity at sector granularity (512 B or 4 KiB, device dependent; NVMe drives report their power-fail atomic write unit). A crash in the middle of an append can therefore leave a prefix of the frame on disk, a full-length frame whose last sector never landed, or a frame-sized hole of zeros in a preallocated file. Recovery scans from the start and stops at the first frame that isn't intact. The interesting decision is what an intact-looking prefix followed by a bad frame means:

• If the bad frame is the last thing in the file, with nothing or only zeros after it, it is a torn tail: the write that was in flight when the machine died. Nothing after it was ever acknowledged (assuming you ack only after the write returned, or after the fsync, per your policy). Truncate it and carry on.
• If valid-looking data follows the bad frame, this is mid-log corruption: data that was written, possibly fsynced and acknowledged, is damaged. Truncating here silently deletes acknowledged orders. Stop and escalate, and get the data from the standby (week 20).

// Journal frame (all integers little-endian):
//
//   len     u32        payload length in bytes
//   seq     u64        sequence number; frames are contiguous (n, n+1, …)
//   payload [u8; len]
//   crc     u32        crc32c over len ‖ seq ‖ payload
//
// After a crash the file can end in a torn frame. recover() scans from
// offset 0 and returns every intact frame plus `valid_len`: the offset you
// truncate the file to before appending again.
//
// Stop cleanly (Ok) at offset `off` when:
//   (a) bytes[off..] is empty or all zero (preallocated, never written);
//   (b) fewer than 12 header bytes remain, or the frame would run past EOF;
//   (c) the frame fits but its crc is wrong AND every byte after the frame
//       is zero (or there are none): the last write was torn.
// Fail with Err(Corruption) when:
//   (d) a crc is wrong and non-zero bytes follow the frame: data that was
//       once acknowledged is damaged, and truncating would silently lose it;
//   (e) seq != the expected next sequence number.

pub const HEADER_LEN: usize = 12;
pub const TRAILER_LEN: usize = 4;

#[derive(Debug, PartialEq, Eq)]
pub struct Recovery {
    pub records: Vec<(u64, Vec<u8>)>,
    pub valid_len: usize,
}

#[derive(Debug, PartialEq, Eq)]
pub enum Reason {
    BadChecksum,
    SeqGap { expected: u64, found: u64 },
}

#[derive(Debug, PartialEq, Eq)]
pub struct Corruption {
    pub offset: usize,
    pub reason: Reason,
}

pub fn crc32c(bytes: &[u8]) -> u32 {
    let mut crc = !0u32;
    for &b in bytes {
        crc ^= b as u32;
        for _ in 0..8 {
            let mask = (crc & 1).wrapping_neg();
            crc = (crc >> 1) ^ (0x82F6_3B78 & mask);
        }
    }
    !crc
}

/// The writer side, given: this is exactly what the journal appends.
pub fn encode_frame(seq: u64, payload: &[u8]) -> Vec<u8> {
    let mut f = Vec::with_capacity(HEADER_LEN + payload.len() + TRAILER_LEN);
    f.extend_from_slice(&(payload.len() as u32).to_le_bytes());
    f.extend_from_slice(&seq.to_le_bytes());
    f.extend_from_slice(payload);
    let crc = crc32c(&f);
    f.extend_from_slice(&crc.to_le_bytes());
    f
}

/// Scan a journal whose first frame should carry `first_seq`.
pub fn recover(bytes: &[u8], first_seq: u64) -> Result<Recovery, Corruption> {
    // TODO: loop over frames with an `off` cursor and an `expected` seq.
    // Check (a) and (b) before reading a frame, verify the crc, decide
    // between (c) and (d), then check (e). Never index past bytes.len().
    let _ = (bytes, first_seq);
    todo!()
}

The full recovery path:

1. Pick a snapshot. List snapshots newest first and take the first one that decodes cleanly. Keep at least two: tmp-plus-rename protects against a crash mid-write, but not against a bad disk block in the newest file.
2. Verify it. When you write a snapshot, store the week 9 state hash alongside it. After loading, recompute the hash and compare. This catches encoder and decoder bugs, the kind that pass a round-trip test because both sides share the same mistake.
3. Find the tail. Binary-search the segment names for the one containing last_seq + 1, and scan to that frame.
4. Replay with outputs suppressed. Clients were already sent these acks and market data before the crash. Replay through the real engine, but into a sink. If you also journal periodic checkpoint hashes (every N commands the engine appends its state hash), compare them as you pass.
5. Repair and resume. Only the last segment can legitimately end in a torn frame. Truncate it (or zero it, if segments are preallocated), fsync, open the segment for append, and resume sequencing at last applied + 1.

pub fn recover(dir: &Path) -> Result<(Engine, Seq), RecoveryError> {
    let snap = newest_valid_snapshot(dir)?;            // decode + crc + version
    let mut engine = Engine::from_snapshot(&snap.state);
    if engine.state_hash() != snap.state_hash {
        return Err(RecoveryError::SnapshotHashMismatch);
    }
    let mut next = snap.last_seq + 1;
    for seg in segments_from(dir, next)? {               // sorted by first seq
        let rec = scan_segment(&seg, next)?;            // Err on mid-log corruption
        for (seq, cmd) in rec.records {
            engine.apply_replay(seq, &decode_command(&cmd)?); // outputs to a sink
            next = seq + 1;
        }
        if seg.is_last() {
            seg.repair_tail(rec.valid_len)?;            // zero or truncate torn bytes, then fsync
        }
    }
    Ok((engine, next))
}

The cost model is simple enough to do in your head: recovery time ≈ snapshot load + tail length ÷ replay rate. Replay is faster than live processing: no network, no market data, no acks, sequential reads and warm caches. If your engine replays 3 million commands per second, a 1-million-command tail costs about a third of a second and a 100,000-command tail about 33 ms. Snapshot cadence is then a dial between snapshot cost and the worst-case tail. Taking one every 100k commands bounds the tail no matter how long the session has been running.

That framing tells you how to read this week's benchmark, which recovers a 1M-command journal. In production, where your newest snapshot sits matters far more than micro-optimizing the replay loop. The repo's benchmark fixes that position for you: it takes a snapshot every 250k commands, so each sample loads the snapshot at 750k and replays a 250k-command tail. Each sample also opens and verifies the whole file first (the CRC and sequence number of every frame, rebuilding the index), with the file in the page cache. What is left to you is CPU cost: CRC throughput over the whole file, snapshot decode and restore, and the per-command replay. So make the replay loop sane: read with large sequential reads (or mmap), not one syscall per frame, and decode commands from borrowed bytes as you did in week 11.

Move the snapshot interval and the crash point and watch the replayed tail grow and reset. Then flip a bit in an older frame: recovery must refuse to start, and "Skips bad frames" shows the silent alternative. Switch the recovery code to "Off by one" before you answer the check below.

The explainer's two layouts are the drills' formats (this week's CRC last, week 9's CRC first). The repo's frame keeps the CRC in the header, after len and seq (Day 3). The scan works the same way on all three.

Retention. Once a snapshot at last_seq = S is durable, segments whose sequence range ends below S are no longer needed for recovery. Keep one or two older snapshots' worth anyway. "No longer needed for recovery" doesn't mean "deletable": a regulated venue must keep its order records for years. Truncating the hot journal means moving whole segments to cold storage, never rewriting them.

The property you want to test is short:

For any crash point, recovery yields exactly the state of replaying commands 1..k for some k, where k is at least the last command the fsync policy promised was durable, and at most the last command that was written.

You don't need a power switch to test it. Wrap the journal's writer in something that crashes on command:

use std::io::{self, Write};

/// Writes at most `budget` bytes, then fails every call: a crash mid-append.
pub struct CrashAfter<W> {
    pub inner: W,
    pub budget: usize,
}

impl<W: Write> Write for CrashAfter<W> {
    fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
        if self.budget == 0 {
            return Err(io::Error::new(io::ErrorKind::Other, "injected crash"));
        }
        let n = buf.len().min(self.budget);
        self.budget -= n;
        self.inner.write(&buf[..n])
    }
    fn flush(&mut self) -> io::Result<()> {
        self.inner.flush()
    }
}

Then, for every budget from 0 to the journal's total size (a few thousand runs for a small journal is seconds of CI time), write a fixed command stream through the crashing writer, run recovery on whatever bytes survived, and assert that the recovered state hash equals the hash of replaying the recovered prefix through a fresh engine. Add a second loop that flips one random bit in the middle of the file and asserts recovery returns an error rather than a shorter-but-plausible history.

For snapshot crash points (after the temp write, after the rename, before the directory fsync), put file operations behind a small trait with an in-memory implementation that can forget everything not yet fsynced. Then simulate "power cut here" deterministically. On real hardware, the Linux device-mapper targets dm-flakey and dm-log-writes are what filesystem developers use to simulate power cuts. They are worth knowing about, even if a trait-based simulation catches most of your bugs.

Spend the day on the capstone below. Before you finish, run the crash loop from Day 5 against your real file journal (with the in-memory filesystem shim) and keep the run time in the report.