loading
loading
Build an LSM-tree storage engine -- the same architecture inside RocksDB, Cassandra, and LevelDB -- stage by stage, in your browser.
You've used Redis, Postgres, RocksDB. You've read that they use "LSM trees" and "SSTables." Most engineers stop there -- at the level of knowing the words. This track turns those words into code you can reason about. After it, when you read "write amplification factor 10x" in a RocksDB tuning guide, you'll know exactly what is being amplified, at which layer, and why the trade-off exists. When a Cassandra compaction falls behind and reads slow down, you'll know why -- because you've watched it happen in your own implementation. The engineers who design storage systems aren't smarter than you; they've just built one before.
A complete, working LSM-tree storage engine in four stages. Each stage adds one architectural layer that real engines need -- you bring the previous stage forward each time, so by Stage 4 you have a full engine, not four disconnected exercises.
The finished engine supports set, get, del, has, flush, and compact -- the same interface Redis exposes (minus network) and the same operations RocksDB exposes to its embedders. Every test in the harness runs real assertions against your code in a browser sandbox; there's no server involvement and no auto-complete to do the work for you.
LSM stands for Log-Structured Merge-tree. The core insight from the 1996 O'Neil et al. paper: sequential I/O to RAM and disk is orders of magnitude faster than random I/O. B-trees (used by Postgres, MySQL InnoDB, SQLite) update records in place -- a write to key user:5 seeks to wherever that key lives on disk and overwrites it. This is random I/O, capped at ~1,000 IOPS on spinning disk or ~100,000 IOPS on NVMe. LSM engines never update in place. They absorb every write into RAM first, then flush RAM to disk as sorted, append-only files. Every disk write is sequential.
The four layers your engine builds:
1. Memtable (RAM): An in-memory sorted map that absorbs all writes. Reads check it first -- if the key is here, no disk access needed. When the memtable exceeds its size threshold (say, 64 MB in RocksDB), it gets flushed. In production, RocksDB keeps multiple memtables in parallel and flushes them in a background thread while the active memtable absorbs new writes.
2. Write-Ahead Log (disk, sequential): Before any write touches the memtable, the operation is appended to the WAL -- a plain append-only file. If the process crashes before the memtable is flushed, the WAL is replayed on restart to reconstruct it. This is how every serious database achieves durability: fsync the WAL append, then mutate RAM. The WAL is discarded once its memtable has been flushed to an SSTable.
3. SSTables (disk, immutable): Sorted String Tables. When a memtable flushes, it writes its contents to disk in sorted key order as an immutable file. "Immutable" is the key word -- SSTables are never modified in place. A read that misses the memtable scans SSTables from newest to oldest; the first match wins. Deletes are stored as tombstone markers (null) -- a tombstone in a newer SSTable hides the value in an older one.
4. Compaction (background): With enough flushes, you accumulate many SSTables. Each read must check all of them in the worst case -- "read amplification." Compaction is the background job that merges SSTables, keeps only the newest value per key, and drops tombstones (once no older SSTable can resurrect the key). After compaction, reads touch fewer files. The trade-off: compaction itself writes data again, creating "write amplification." Tuning this trade-off is the core of operating RocksDB.
Why writes beat B-trees at high throughput: A B-tree write to a random key must seek to that key's leaf page (random read), modify it (dirty page), and eventually flush the dirty page (random write). Under write-heavy load, the random I/O budget saturates. An LSM write is: append to WAL (sequential) + insert into memtable (RAM). Under the same load, LSM wins by 10-100x. The cost is paid later, during compaction.
Build the core memtable -- an in-memory Map that absorbs writes at RAM speed. Implements set, get, del, has with correct overwrite and delete semantics. Everything later in the engine builds on exactly this interface.
Before touching the memtable, append every mutation to a log array. On startup with an existing log, replay it to reconstruct the memtable. This is the exact pattern used by Postgres WAL, MySQL binlog, and Cassandra's CommitLog -- durability without synchronous disk writes.
When the memtable is full, flush it to a sorted, immutable segment array. Reads now check memtable first, then segments newest-to-oldest. Deletes flush as null tombstones so they can hide older values in older segments. This is where the "sorted" in SSTable comes from and why binary search on disk is possible.
Merge all accumulated segments into one, keeping only the newest value per key and dropping tombstones. This bounds read amplification (fewer files to check) but introduces write amplification (data written again). Tuning this ratio -- with level-based or tiered strategies -- is the core of operating RocksDB or Cassandra in production.
Facebook's LSM engine. Used as the storage backend for MySQL/MyRocks, CockroachDB, TiKV (TiDB), Kafka log segments, and Flink state. The default storage engine for Meta's internal databases. Handles trillions of writes per day across Meta's infrastructure.
Distributed wide-column database. Each node runs an LSM engine (Memtable + CommitLog + SSTables + Compaction) -- your Stage 1-4 are Cassandra's core write path. Cassandra's compaction strategies (STCS, LCS, TWCS) are exactly the tuning knob you'd pull after building this track.
Google's original open-source LSM implementation (2011). Ships inside Chrome as the IndexedDB backend. The reference for the "level-based" compaction strategy where SSTables are organized into size-tiered levels.
C++ rewrite of Cassandra, 10x higher throughput. Same LSM architecture, same compaction concepts. Used at Discord (replacing Cassandra for message storage), Expedia, and Samsung.
ClickHouse's columnar storage engine uses a "MergeTree" -- the same flush-and-merge pattern you're building, applied to columnar blocks instead of key-value pairs. Powers Cloudflare analytics, Uber metrics, and most large-scale event analytics stacks.
Ready to build?
Your code runs in the browser — no setup needed.