Under the Hood: Log-Structured Merge-Tree (LSM-Tree)
While Bitcask requires all keys to fit in memory, real-world big-data systems (Google Bigtable, Apache Cassandra, RocksDB, ScyllaDB) handle datasets where both keys and values vastly exceed RAM. The LSM-Tree organizes sorted data into a memory buffer and a hierarchy of disk-resident levels, enabling high write throughput, efficient range scans, and dense data compression.
The Multi-Tier LSM-Tree Architecture
Core Invariants of the LSM-Tree
- Sorted Invariant: Data inside every Memtable and SSTable is strictly sorted by key. This enables binary search within blocks, efficient merge-sort during compaction, and fast range scans.
- Immutability Invariant: Once an SSTable is written to disk, it is NEVER modified. Deletes and updates are handled by appending newer entries or tombstones.
- Compaction-dependent layout: Level 0 files commonly overlap. Leveled compaction usually keeps files within each lower level non-overlapping, while size-tiered or universal strategies may retain overlapping sorted runs. The read path must follow the selected strategy's invariant.
Worked example: how many levels for 2 TB?
Using RocksDB-style defaults: 64 MB memtable, level 1 target 256 MB, and a size multiplier of 10 per level.
| Level | Target size | Cumulative |
|---|---|---|
| L1 | 256 MB | 0.25 GB |
| L2 | 2.56 GB | 2.8 GB |
| L3 | 25.6 GB | 28 GB |
| L4 | 256 GB | 284 GB |
| L5 | 2.56 TB | 2.8 TB |
So 2 TB needs five levels below L0. Because each level is ten times the one above, about 90% of the data lives in the last level, which is why space amplification of leveled compaction is roughly 1.1x.
A point lookup, worst case
- Active memtable, then any immutable memtables: in RAM.
- Each L0 file, newest first (often up to about 4 before compaction is triggered).
- At most one file per level in L1 to L5, found by key range metadata.
That is up to about 9 candidate files. Bloom filters at 10 bits per key (about 1% false positives) mean a lookup for a key that exists costs roughly one data block read, plus a few percent extra from false positives, and a lookup for a missing key usually costs no data block reads at all.
Where LSM-trees are used
- RocksDB: embedded engine inside MyRocks, CockroachDB (historically; now Pebble, a Go LSM), TiKV and Kafka Streams state stores.
- Cassandra and ScyllaDB: per-table LSM storage with selectable compaction strategies.
- Bigtable and HBase: tablets or regions made of SSTables or HFiles plus a memtable.