LSM Tree (Log-Structured Merge Tree)

A disk-resident data structure that buffers writes in memory and flushes them as sorted, immutable files, converting random writes into sequential I/O at the cost of read amplification and background compaction.

Practical example

In RocksDB, writes land in a memtable backed by a WAL; once full, it flushes to an immutable SSTable on disk. Leveled compaction then merges overlapping SSTables across levels to bound the number of files a point read must probe, at the cost of rewriting each key multiple times as it migrates through levels.

An LSM Tree’s write path is fundamentally two-tiered: incoming mutations are first written to an in-memory sorted structure (typically a skip list or red-black tree) called a memtable, backed synchronously by a Write-Ahead Log for crash durability. Once the memtable reaches a size threshold, it is flushed as an immutable, sorted file to disk — an SSTable (Sorted String Table). Because SSTables are immutable, writes never mutate existing files; they only ever append new ones. This is what eliminates random disk seeks on the write path, but it also means a single logical key can exist in multiple SSTables simultaneously, with the most recent write shadowing older ones.

The unavoidable consequence of immutability is read amplification: a point read for a key with no bloom filter hit may need to check the memtable and every SSTable in the LSM hierarchy until a match is found or all levels are exhausted. Engines mitigate this with:

Bloom filters per SSTable to cheaply rule out non-membership.
Sparse indexes mapping key ranges to block offsets, avoiding full-file scans.
Leveled or size-tiered compaction strategies that bound the number of SSTables a read must probe.

Range scans are cheap relative to B-Trees since SSTables are already sorted, but merging across overlapping SSTables during a scan still requires a k-way merge iterator.

Compaction is the background process that reclaims space and bounds read amplification by merging multiple SSTables into fewer, larger ones, discarding superseded versions and expired tombstones in the process. The two dominant strategies present a direct tradeoff: size-tiered compaction minimizes write amplification by merging similarly-sized files but tolerates higher space and read amplification (Cassandra’s default for write-heavy workloads); leveled compaction organizes SSTables into levels with exponentially increasing size, guaranteeing tighter bounds on read amplification and space overhead at the cost of significantly higher write amplification, since a single key may be rewritten at every level it passes through (RocksDB’s default). This compaction I/O is not optional background housekeeping — it directly competes with foreground read/write traffic for disk bandwidth and CPU, and is the primary source of tail-latency spikes and throughput throttling in LSM-based systems under sustained load.

Architecturally, choosing an LSM Tree is a bet that your workload is write-heavy or write-bursty and can tolerate eventual read-path overhead, versus a B-Tree’s balanced but seek-heavy read/write profile. Operators must actively tune compaction throughput throttling, memtable flush thresholds, and level fan-out ratios; misconfiguration manifests as either unbounded SSTable proliferation (read latency collapse) or compaction falling permanently behind ingest rate (a ‘compaction debt’ death spiral that eventually stalls writes entirely once the memtable cannot flush). Tombstone accumulation compounds this further — deleted or overwritten keys are not physically removed until they are compacted away, meaning delete-heavy workloads without careful gc_grace_period tuning can inflate both storage footprint and read amplification well beyond what the live dataset size would suggest.