Build your own LSM-tree storage engine (LevelDB / RocksDB style)
The simplest possible storage engine that gives you BOTH ordered reads AND more keys than fit in RAM, by accepting a deal: write to RAM at memory speed, log to disk for safety, then merge sorted files in the background forever.
- Scenes
- 11 interactive scenes
- Time
- about 77 minutes
- Topic
- Storage Engines & Databases
What you are building, and why
You are designing the storage engine that gave us BigTable, Cassandra, HBase, LevelDB, RocksDB, Pebble, TiKV, and FoundationDB-on-RocksDB. The brief is brutal in its specificity:
- you want ordered reads (range scans by key, prefix iteration);
- you want more keys than fit in RAM (so the index cannot live there);
- you want fast writes under high cardinality and random key order (so you cannot pay a seek per write).
The previous curriculum (Bitcask) gave you O(1) point reads and append-only writes — and could not do range scans, and OOM'd on high cardinality. The other obvious answer (a B-tree on disk) does range scans fine, and pays one seek per random-key insert, which on a single SSD pegs at hundreds of writes per second. Neither fits the brief.
LSM is the design that takes both blockers off the table. You do not avoid the trade — you reshape it. Writes go to RAM at memory speed; an append-only log on disk survives the crash; sorted files on disk get binary-searched; a tiny bitmap per file says "definitely not here"; a background process merges sorted files forever. Eleven scenes; eleven structural choices; one design space that contains every modern KV store you will meet.
Resist the urge to "describe an LSM." Build it from first principles, defend each step, and let the workload push back. The point is to feel why each cost is paid and which workload pays it.
What you will be able to explain afterwards
- memtable + WAL split (write at memory speed, survive crashes)
- flush — frozen memtable becomes one immutable sorted SSTable
- newest-first read path with first-hit-wins
- bloom filters as the miss-side optimization
- compaction — the GC of sorted files
- leveled vs tiered/universal — the central LSM dial
- write amplification (10–30× leveled, 3–9× tiered)
- tombstone retention across levels (the resurrection trap)
- block cache + compression — the CPU↔disk dial
- amp triangle: write-amp / read-amp / space-amp
The brief
Why Bitcask cannot give you ranges.
Write side
Sort in RAM, log on disk, flush to immutable SSTables.
- 02Sort in RAM, log to diskEvery put fans out: a sorted in-RAM memtable AND an append-only WAL whose only job is to rebuild the memtable on a crash.~7 min
- 03Flush — pay the IOU onceFrozen memtable streams sequentially to disk as a single immutable sorted file (an SSTable); the WAL is then deleted.~7 min
Read side
Newest wins; bloom filters skip the misses.
- 04Newest wins — and the reads get slower — the memtable-first read path across SSTablesA get walks memtable → SSTables newest-first; first hit wins. Cost grows linearly with file count, especially for misses.~7 min
- 05Definitely-not-here, in one bitmap — Bloom filters on every SSTableEach SSTable carries a bloom filter that says 'definitely no' or 'maybe' — eliminating disk reads on misses, not on hits.~7 min
Compaction
Levels, write amplification, the amp triangle.
- 06Compaction — the GC of sorted filesA background process merges N immutable SSTables into 1, drops shadowed/deleted records, atomically swaps files. Foreground writes never block.~7 min
- 07Levels — a staircase that bounds reads — non-overlapping key ranges, 10x per tierL0 may overlap; L1+ enforce non-overlap per level; each level is ~10× the size of the one above. A get touches at most one file per tier.~7 min
- 08Every byte, written ten times — write amplification, leveled versus tieredLeveled compaction pays 10–30× write amplification; tiered/universal trades that down to 3–9× at the cost of read-amp and space-amp.~7 min
Sharp edges
Tombstones, blocks, and the canvas.
- 09Tombstones — deletes that can come backDeletes are records. Drop a tombstone before all older live records are gone, and the deleted key resurrects. Same trap as Bitcask, restated for levels.~7 min
- 10Blocks, cache, and the CPU/disk dialSSTables are blocks; the block cache holds hot decompressed blocks; compression trades CPU for disk bytes with no effect on correctness.~7 min
- 11Design your LSM — and feel its tradesCapstone: pick a workload, set knobs, watch the verifier trace each choice back to the scene that taught it. The amp triangle is the load-bearing trade.~7 min
Where you'll use this
Product designs whose trade-offs turn on what this curriculum teaches.
More in Storage Engines & Databases
Open the box every design diagram labels "DB": pages, logs, LSM trees, wide-column, documents, graphs and columnar scans, built from scratch.
- Build Build a Bitcask-style KV storeThe simplest possible KV store that still works: an append-only log on disk + an in-memory hash index. Build it from first principles and feel which trade-offs every later store inherits.
- Build Build a B-tree storage engine (SQLite-style)What actually happens when you run INSERT INTO users(...). One file of fixed-size pages, organized as B-trees, with a write-ahead log that turns commits into appends. Build it from a SQL writer's perspective and feel why every knob exists.
- Build Build a wide-column store (Cassandra / DynamoDB family)One server is not enough — disk fills, throughput maxes, the box dies. Build a multi-node store from first principles: hash sharding, the consistent-hash ring, vnodes, replication, eventual consistency, tunable W+R quorum, hinted handoff, read repair. Every modern Dynamo-style store is a point in this design space.
- Build Build a graph database (Neo4j / Dgraph-style)When the workload is 'friends of friends', a relational join melts. Build a store where edges are first-class — index-free adjacency, traversals that follow pointers instead of joining tables, and a query language (Cypher / GraphQL+) that thinks in patterns. Feel why graph storage shines for traversal-heavy work and stumbles on full-graph aggregates.
- Build Build a columnar OLAP store (ClickHouse / Druid style)OLTP picks one row by key; OLAP scans a billion rows of one column and asks for a percentile. Build the analytical engine that makes that fast: columnar layout, dictionary/RLE/delta compression, vectorized execution, late materialization, MPP shuffle. Internalize why Postgres is 1000× slower than ClickHouse on the same query and why the inverse is also true.
Prefer to design it yourself?
The same subject as a staged workspace: draw the architecture, and a simulator traces requests through the boxes you drew.
Open the Build an LSM-tree storage engine (LevelDB / RocksDB style) workspace