Write a toy database

What you end up with: a key-value store that keeps your data after the process exits, handles deletes without losing them, compacts its files in the background, and answers reads in microseconds — plus benchmarks that compare it honestly against sled and redb.

This is the track for people who want to understand how storage actually works. There is nothing magical in a database: append bytes, keep an index, merge files occasionally. Writing one in Rust is also the best exercise there is for Vec<u8>, &[u8], lifetimes and error handling in a codebase that has to be correct.

What you’ll build

• Append-only data files with an fsync policy you chose deliberately
• An in-memory index (starting with HashMap, ending with a real key format)
• An SSTable format: sorted, immutable, with a sparse index
• Compaction that merges files without losing writes or deletes
• Bloom filters so missing keys do not touch the disk
• A write-ahead log and memtable
• Tombstones, range scans, and a snapshot-free iterator API
• Benchmarks against sled and redb, including where you lose

Before you start

• Ownership and borrowing — this track moves bytes around constantly
• Smart pointers and memory — Rc, Arc and interior mutability show up early
• Modules, packages, and crates — the project outgrows one file by article 3
• Comfort with reading crash-safety reasoning: “what happens if the process dies here?”

Articles

• What we’re building: a log-structured key-value storethe architecture, then one piece at a time
• A key-value store in memoryget, put, delete in a BTreeMap
• Appending writes to a logone line per write, and a checksum
• Replaying the log on startuprebuilding state, and skipping the torn tail
• Compacting the logrewriting so deletions actually free space
• Introducing SSTablessorted files with a sparse index
• Merging SSTablescompaction with tombstones
• A write-ahead log and a memtablethe pair that makes writes durable and fast
• Bloom filters to skip disk readsand the false-positive rate you chose
• Range scans and iteratorsimplementing Iterator over merged sources
• Benchmarking against sled and RocksDBhonest numbers, and where we lose
• What a real database does that we didn’ttransactions, MVCC, recovery

Where the code lives

toy-database/ in the examples repository — one tag per article, plus the benchmark harness.