Crash-safe key-value store with a WAL

Before durability, design the on-disk format. A WAL is a sequence of self-describing records appended to one growing file, and every later milestone — recovery, checksums, truncation — depends on being able to walk that byte stream record by record. Frame each record as length-prefix + type + payload (and reserve a trailing slot for a CRC you add in milestone 5), because without a length you cannot find where the next record starts, and a torn tail becomes indistinguishable from real data. Decide your append unit: small records (one mutation each) keep latency low but waste header bytes; larger batched records amortize framing overhead. A real WAL record is tens of bytes of header over a payload, and at, say, 64-byte values you want framing overhead under ~20% so the log doesn't double your write volume. Build a writer that appends frames and a reader that walks them, with zero durability guarantees yet — that is the next milestone's job.

Now make 'the call returned' mean 'the data survives power loss'. A write(2) only copies bytes into the OS page cache; until fsync(2) (or fdatasync) forces them to stable storage, a crash loses them silently. So the durability contract is: append the frame, fsync, then acknowledge — never ack before the fsync returns. The catch is cost: a single fsync to an SSD is ~0.5–3 ms and to spinning disk 5–10+ ms, so a naive one-fsync-per-write design caps you at a few hundred to low-thousands of writes/sec no matter how fast your CPU is. Group commit fixes this: buffer concurrent writers, fsync once for the whole batch, then ack them all together. One fsync amortized over a batch of 100 turns ~1000 fsyncs/sec of headroom into ~100k acks/sec — at the cost of added latency (a writer waits up to the batch window). Tune the batch window (e.g. 1–5 ms or N pending) and measure the throughput-vs-latency curve you just bought.

A WAL is worthless if you can't rebuild state from it after a crash. On startup, replay walks the log from the start, applying each well-formed record to rebuild in-memory state, and stops cleanly at the first record it can't fully parse — the torn tail of a write that was interrupted between append and fsync. The key invariant is that recovery must be idempotent and prefix-deterministic: replaying the same log twice yields identical state, and a torn final record is dropped rather than half-applied, because you only acked writes whose fsync completed, so anything past the last intact record was never promised to the caller. Inject crashes (truncate the file at random offsets, or kill mid-write under a fault harness) and prove the recovered state matches the set of acknowledged writes exactly — no lost acks, no phantom writes from the torn tail. Note recovery time scales with log length: a 1 GB log replayed at, say, a few hundred MB/s is seconds of startup, which is the pressure that forces the next milestone.

An unbounded log means unbounded recovery time and unbounded disk. Checkpointing breaks that: periodically flush the current materialized state to a durable snapshot file, record the log offset that snapshot covers, then truncate (or rotate to a new segment and delete old ones) everything before it. Recovery then becomes load-snapshot + replay-only-the-tail, turning a multi-second cold start into a near-constant one. The trade-offs are real: checkpoint too often and you pay snapshot-write I/O that competes with foreground writes; too rarely and recovery and disk balloon. The ordering is a durability landmine — you must fsync the snapshot and the new checkpoint-offset marker before truncating the old log, or a crash mid-checkpoint leaves you with neither a complete snapshot nor the log records you just deleted. Segment the log into fixed-size files so truncation is an atomic unlink of whole segments rather than a risky in-place file rewrite.

Turn the durable log into a usable key-value store. The pattern is the LSM front door: a write appends a (key, value) record to the WAL for durability, then updates an in-memory memtable (a sorted map) that serves reads — so the WAL is the durability backbone and the memtable is the fast queryable view. The two are kept consistent by ordering: WAL-append + fsync first, memtable update second, so a crash can only lose what was never acked. When the memtable grows past a threshold, flush it as a sorted on-disk table and, critically, only then drop the WAL prefix it covered — flush is just a specialized checkpoint, and the same fsync-before-truncate rule from milestone 4 applies. Get(key) checks the memtable, then falls back to flushed tables. This is the moment the project stops being a log and becomes a storage engine, and it forces you to reason about read-your-writes: an acked write must be visible to the very next read.

Silent corruption is the enemy a checksum exists to catch. Add a CRC32 (the slot you reserved in milestone 1) over each record's header+payload; on replay, recompute and compare, so a torn write, a bit-flip, or a half-written sector is detected rather than applied as if it were real data. This is the line between 'recovers cleanly' and 'rebuilds a corrupted state and serves it forever'. Then make the engine observable: counters for writes/sec, fsync latency p50/p99, group-commit batch size, memtable size and flush count, and recovery time — the same RED-shaped signals a real storage engine emits. Finally, run the incident: simulate a torn write (truncate the active segment mid-record) AND a lost fsync (a fault layer that drops the fsync's effect so acked-looking data never actually hit disk). Show that the CRC catches the torn record and recovery stops at it; then show the lost-fsync case is the genuinely dangerous one — it can lose an acknowledged write — and reason about why fsync-lying disks/filesystems make 'durable' a property of your whole stack, not just your code. Write a short post-mortem: which failure your design survives, which it doesn't, and the one mitigation that isn't 'fsync harder'.