KV Store & Durability

The first half of this atlas's spine project — see the v0 → v3 roadmap on the home page. Where Atlas I's spine project (OS from Scratch) built a kernel from boot to shell, this one builds a database engine from a bare B-Tree to a durable, crash-safe key-value store. Relational Layer & Query Engine builds the SQL layer on top of what gets built here.

Milestones (v0 → v1)

v0 — the structure. An in-memory copy-on-write B-Tree (or B+Tree): node format, search, insert, delete, splitting and merging — no disk involved yet.

v1 — real durability. Persisting pages to disk, fsync discipline, a write-ahead log, crash recovery, and free-space management. This is the point where it becomes an actual database instead of a fancy in-memory map.

Planned notes

• Why a B-Tree (not a hash table) for a disk-backed KV store
• B-Tree vs B+Tree: which one and why
• The on-disk page format: fixed-size pages, headers, and why page size matters
• Copy-on-write nodes: how updates avoid in-place mutation
• Search, insert, and split — building the tree node by node
• Deletion and merging underflowed nodes
• Free-space management: tracking and reusing freed pages
• fsync, fdatasync, and what "durable" actually guarantees (and doesn't)
• The write-ahead log: format, append discipline, and replay
• Crash recovery: replaying the WAL on startup, and testing it by actually killing the process mid-write
• Checkpointing: when to truncate the WAL
• Benchmarking write throughput vs durability guarantees (fsync every write vs batched)

Core sources

• "Build Your Own Database From Scratch" (build-your-own.org) — the pedagogical spine for this branch and its sequel.
• Database Internals (Alex Petrov) — the conceptual backbone for B-Tree storage engines and WAL design.
• Designing Data-Intensive Applications (Kleppmann), ch. 3 — storage and retrieval fundamentals.
• "Architecture of SQLite" (sqlite.org/arch.html) and the SQLite file format spec — a real-world reference implementation.
• cstack's db_tutorial — a from-scratch SQLite clone in C, close to this branch's scope.

Connects to: Relational Layer & Query Engine · Concurrency in Practice · malloc from Scratch