A log-structured merge tree built from scratch in Node: a write-ahead log, a sorted memtable, immutable on-disk SSTables (sparse index, Bloom filter, checksummed footer), newest-to-oldest point reads, tombstones, merge-iterator range scans, size-tiered compaction with write-amplification accounting, and crash recovery from the WAL plus an atomically replaced manifest.
The problem
B-trees update pages in place. Every random write turns into a random read-modify-write of a page, and on SSDs it also costs page-level write amplification. An LSM tree turns random writes into sequential ones. It buffers writes in memory, writes them out as sorted immutable files, and merges those files in the background. The price is paid on reads (you may have to check several files) and in compaction I/O.
Where it shows up: Google Bigtable (which coined the terms memtable and SSTable), LevelDB, RocksDB (used under MyRocks, TiKV, CockroachDB's former engine, Kafka Streams state stores), CockroachDB's Pebble, Apache Cassandra, ScyllaDB, HBase, InfluxDB's TSM engine and many time-series stores.
Design
put/delete ──► WAL append (CRC-framed) ──► Memtable (sorted) ──full──► flush ──► 000123.sst (newest)
│
get: memtable ─► sst[0] ─► sst[1] ─► ... first hit wins (a tombstone counts as a hit)
scan: k-way merge(memtable, sst[0..n]) — newest source wins ties, tombstones suppressed
compaction: pick ≥4 age-adjacent, similar-sized tables ─► merge ─► one table in their placeSSTable layout (writeSSTable / SSTable in lsm.js):
[data block 0][data block 1] ... [bloom filter][sparse index][footer: 32 bytes]
entry : type u8 (1=put, 0=tombstone) | klen u32 | key | vlen u32 | value
index : one entry per block: klen u32 | first key | offset u32 | length u32 | crc32(block) u32
bloom : m u32 | k u8 | bit array
footer : indexOff, indexLen, bloomOff, bloomLen, entryCount, crc32(bloom+index+footer[0..20)), MAGIC "LSMT", VERSIONOpening a table reads only the footer, the index and the Bloom filter. A point lookup checks the filter, binary-searches the sparse index for the last block whose first key is <= key, reads and verifies one block, and scans it.
WAL record: len u32 | crc32 u32 | entry. On replay, a record whose length runs past EOF or whose CRC doesn't match marks the torn tail. Replay stops there and the file is truncated back to the last good record.
Key invariants
- Durability ordering. A write is appended to the WAL before it is applied to the memtable. On flush, the SSTable is written to
*.tmp, fsynced and renamed. Only after that is theMANIFESTrewritten (tmp + fsync + rename), and only after that is the WAL reset. A crash at any point leaves either the old state plus the WAL, or the new state. If the crash comes between the manifest and the WAL reset, replay re-applies writes the newest table already has, which is idempotent. - Age order.
tables[0]is the newest. Entries carry no sequence numbers, so correctness depends on this order. That is why compaction only merges age-adjacent runs and puts the output back in the same position. Merging tables 1 and 3 around table 2 could let an old value jump ahead of a newer one. - Tombstones are data until the bottom. A delete is a record that shadows older versions. Compaction may drop a tombstone only when the run includes the oldest table, because otherwise an older copy could be resurrected.
- Orphans are garbage. Any
.sstthat isn't in the manifest (left by a crash mid-flush or mid-compaction) is unreachable by construction and gets deleted on open.
Compaction strategy: size-tiered (STCS). Walking newest to oldest, tables are grouped into a bucket while each one's size is within [0.5x, 1.5x] of the bucket's running average (Cassandra's bucket_low/bucket_high). A bucket with at least minThreshold tables (default 4, max 32) gets merged. Each byte is rewritten about once per tier, roughly log_4(total / memtable) times.
Complexity
| Operation | Cost |
|---|---|
| put / delete | WAL append O(entry) + memtable insert O(log n) search + O(n) array splice (skip list: O(log n)) |
| get | O(log n) memtable + per table: k Bloom probes, O(log blocks) index search, ≤1 block read |
| scan of K results over T sources | O((K + T) · T) with linear head selection (O(log T) per step with a heap) |
| flush | O(n) sequential write |
| memory per table | 1 index key per block + ~1.25 bytes/key of Bloom filter (10 bits/key → ~0.8% FPR, k=7) |
Measured in node demo.js: 6,000 writes → 23 flushes, 6 compactions, about 5.5x total write amplification (WAL + flush + compaction bytes over user bytes). 500 lookups for absent keys did 3,000 table probes and only ~20 block reads.
Failure modes and trade-offs
- Read amplification: a miss probes every table. Bloom filters make that cheap for point reads, but range scans can't use them and must merge every table whose key range overlaps.
- Space amplification: STCS keeps multiple versions until a merge and needs up to 2x free space for a large compaction. The oldest, biggest tier may go a long time without being compacted. The demo shows a tiny early table with no size peers.
- Durability knob:
sync: false(the default here) relies on the OS page cache, so a process crash loses nothing but a power loss can.sync: truefsyncs every write. Real engines use group commit to amortise the fsync. - Tombstone build-up: delete-heavy workloads leave shadowing tombstones that slow scans until they reach the bottom.
- No snapshots or concurrency control: a scan that is running while compaction deletes a file will fail. Real engines pin files with reference counts or versions.
- Compaction materialises its input in memory for simplicity. Real engines stream the merge block by block.
- On Windows, a virus scanner can briefly lock a file being renamed.
renameAtomicretries on EPERM/EBUSY.
How production systems do it
- LevelDB / RocksDB: skip-list memtable, WAL, SSTables with data blocks, an index block, a filter block, and a fixed-size footer that ends in a magic number. Internal keys carry a 56-bit sequence number and a type, which gives snapshots and lets compaction merge any files. RocksDB defaults to leveled compaction (L0 plus levels that grow about 10x each). That means lower space and read amplification but higher write amplification, often 10–30x. "Universal" compaction is its size-tiered variant. RocksDB also offers partitioned filters/indexes and a block cache.
- Cassandra: a commit log plus memtable, then an immutable SSTable made of several component files (Data, Index, Summary, Filter, Statistics). Conflicts are resolved by per-cell timestamps, so STCS can merge any similar-sized tables without the adjacency rule used here. The options are STCS (min_threshold 4, max 32), LCS, TWCS for time series, and since 5.0 the Unified Compaction Strategy. Tombstones are kept at least
gc_grace_seconds(10 days by default) so repair can spread deletes before they are purged. - HBase: WAL, MemStore, HFiles; minor and major compactions. Bigtable: commit log, memtable, SSTables in GFS/Colossus.
- Pebble (CockroachDB): a RocksDB-compatible Go LSM with range-deletion tombstones and L0 sublevels.
Extension exercises
- Replace the memtable array with a skip list and add a sequence number to every entry. Then drop the age-adjacency restriction in
pickCompaction. - Implement leveled compaction (L0 → L1 with a 10x fanout and non-overlapping key ranges per level) and compare write amplification against STCS on the same workload.
- Add a
min_sstable_sizebucket like Cassandra's, so tiny tables are grouped together no matter their size ratio. - Add snapshot iterators that pin a list of table references, so compaction can't delete files that are still being read.
- Add prefix compression within blocks (restart points every 16 keys, as LevelDB does) and measure the drop in file size.