Start with a sorted in-memory memtable and end with a durable embedded key-value store that survives a crash mid-write. Every lesson gives you a concrete spec to hit, and the engine grows one durable piece at a time - WAL, SSTables, merge iterators, tombstones, compaction, bloom filters.
Over 40 lessons you build a working LSM storage engine from scratch: the sorted in-memory memtable that absorbs writes, a write-ahead log that fsyncs every write to disk and replays on open so nothing committed is ever lost, immutable on-disk SSTables with a sparse index, a merge iterator that reads across many files returning the newest value per key, tombstone deletes, leveled compaction, and bloom filters.
By the end you have an embedded, crash-safe key-value store you import as a library - Open, Get, Put, Delete, Scan, Close - that keeps keys in sorted order, survives a process crash mid-write by replaying its log, and ignores a torn half-written SSTable left behind by that crash. The capstone writes a batch, kills the process without a clean close, reopens the directory, and proves every committed key is still there.
This is a teaching-grade engine built around the real LSM design: it is correct and durable, but it stops short of what a production store like RocksDB adds on top - concurrent writers and MVCC snapshots, transactions, block compression, a proper manifest with multi-level compaction policies, and per-block checksums. What you finish with is the honest core all of those systems are built around.
Every storage engine starts as a thing you can open and ask questions of. Today you build the smallest possible key-value store - one that holds nothing yet - so the public API exists from day one and every later lesson thickens it.
Create an empty in-memory store whose Get reports that any key is missing.
An LSM engine is, from the outside, a key-value store: you put keys in and get them back. Before any of the log-structured machinery matters, the shape of that surface has to exist - something you can construct and query. Today it holds nothing, so every lookup misses.
The one decision that pays off for the rest of the project is making missing its own answer. A key that was never written is different from a key whose value is empty, and later a deleted key will be different again. Returning a value plus a found flag keeps those cases separate from the very first line of code, so nothing downstream has to guess what an empty result means.
// the whole engine will grow inside this typetype Memtable struct { /* storage comes next lesson */ }func New() *Memtable { return &Memtable{} }// return a value AND a found flag - "missing" must be// distinguishable from "present but empty"func (m *Memtable) Get(key string) ([]byte, bool) {return nil, false}
A genuinely crash-safe embedded ordered KV store - proven by tests for WAL replay, atomic SSTable creation, torn-file skip, and atomic batches, with compaction now reclaiming its inputs - but single-threaded and manifest-free, so it is a teaching-grade engine rather than a production database.
Chapter 3 walks the exact SSTable + LSM-tree storage engine this project builds, and why a write-ahead log makes it crash-safe.
A deep tour of LSM-tree storage: memtables, SSTables, compaction strategies, and the durability machinery - the reference textbook for everything here.
The original 1996 paper that introduced the LSM-tree - the source of the design you are implementing.
How a real LSM engine lays out its files, log, and levels - the concrete production counterpart to this project.
A hands-on build-your-own LSM tutorial that mirrors this project's arc - useful for a second pass or deeper dives on compaction.