Build an 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.

SavedSaved on this device

The problem

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.

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 cover

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

Reading

O'Neil, Cheng, Gawlick, O'Neil — The Log-Structured Merge-Tree (1996)
Chang et al. — Bigtable: A Distributed Storage System for Structured Data (Google, 2006)
LevelDB design doc — github.com/google/leveldb/blob/main/doc/impl.md
RocksDB wiki — Leveled-Compaction, Universal-Compaction, Write-Amplification, Bloom-Filters, Block-Cache
Kleppmann — Designing Data-Intensive Applications, Chapter 3
Mark Callaghan — smalldatum.blogspot.com (canonical write-amp numbers and the leveled-vs-tiered trade)

About Build an LSM-tree storage engine (LevelDB / RocksDB style)

Difficulty: beginner
Time: about 75 minutes
Stages: 9
Topic: Storage Engines & Databases

How this problem is worked

Nine stages, from what the thing is for to how it compares with the real implementations. Each asks one question, and the simulator runs the architecture you draw against the requirements you wrote.

01Purpose & invariantsWhat is this for, and what must always be true of it?
02Workload characterizationWho writes, who reads, and in what shapes?
03Data model & on-disk formatWhat does the data look like at rest?
04Core algorithmsHow do the write path and the read path actually work?
05Distribution & replicationHow does this scale out and survive losing a machine?
06Consistency & correctnessUnder concurrency and failure, what is guaranteed?
07Failure modes & recoveryWhat actually happens when each part fails?
08Operational characteristicsCan a human run this at three in the morning?
09Trade-offs & comparisonWhere does this sit against the alternatives?

Primary sources for this problem

O'Neil, Cheng, Gawlick, O'Neil — The Log-Structured Merge-Tree (1996)
Chang et al. — Bigtable: A Distributed Storage System for Structured Data (Google, 2006)
LevelDB design doc — github.com/google/leveldb/blob/main/doc/impl.md
RocksDB wiki — Leveled-Compaction, Universal-Compaction, Write-Amplification, Bloom-Filters, Block-Cache
Kleppmann — Designing Data-Intensive Applications, Chapter 3
Mark Callaghan — smalldatum.blogspot.com (canonical write-amp numbers and the leveled-vs-tiered trade)

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.

Browse the full problem catalog, or see what the simulator does and does not model.