LSM-Tree Storage

Store data as an in-memory memtable backed by a write-ahead log, periodically flushed to immutable sorted-string-tables (SSTables) on disk and merged by background compaction, trading point-read latency and background I/O for sequential-only writes and sustained high write throughput.

A B-Tree's in-place updates require random I/O and occasional page splits, which caps sustained write throughput well below what sequential I/O can deliver. Workloads that need to absorb a high, continuous write rate (ingestion, time-series, event logs) need a write path that never does a random write, even at the cost of a more expensive read path.

A log-structured-merge-tree (LSM-tree) is the storage engine underneath Cassandra, ScyllaDB, and RocksDB-backed stores, and it answers the write-path question differently than a B-Tree does. A B-Tree updates a row in place: it finds the page holding the row, modifies it, and writes that page back, which means random I/O and occasional page splits when a page overflows. An LSM-tree never modifies data in place. Every write (insert, update, or delete) is first appended to a write-ahead log for durability (Cassandra calls this the commit log), then inserted into an in-memory, sorted structure called the memtable, commonly a skip list. Both steps are sequential appends: no seek, no page split, no read-before-write.

When the memtable reaches a configured size threshold, it is flushed to disk as an SSTable (sorted-string table): an immutable, sorted, sequential file. Because SSTables are immutable, a later write to the same key does not touch the old SSTable; it lands in the current memtable and eventually a newer SSTable. A delete is represented the same way, as a tombstone marker written like any other value, not as an in-place removal, because the row being deleted may already live in an SSTable the write path cannot touch.

This immutability is what makes the read path harder than a B-Tree's. A point read for key K may need to check the memtable, then potentially every SSTable on disk from newest to oldest, since K's most recent version could be in any of them and older SSTables are never rewritten purely because a newer value exists. Two structures keep this bounded in practice. A Bloom filter is a per-SSTable probabilistic structure that can say "this SSTable definitely does not contain K" and let the read skip it entirely; it can also say "K might be present," which costs a real disk read that may turn out to be a false positive, but it can never produce a false negative. A sparse index within each SSTable (an entry roughly every few kilobytes rather than every key, since the SSTable is already sorted) narrows a positive hit to a small byte range instead of a linear scan of the file.

Background compaction is what keeps the SSTable count, and therefore both the Bloom filter checks and the read amplification, bounded. Compaction merges several SSTables into fewer, larger sorted SSTables, discarding obsolete versions of overwritten keys and physically dropping tombstoned rows once they are safe to remove. Cassandra exposes this as a per-table compaction strategy: SizeTieredCompactionStrategy merges similarly-sized SSTables and favors write throughput and space at the cost of read amplification, while LeveledCompactionStrategy organizes SSTables into non-overlapping levels and favors bounded read amplification at the cost of more total compaction I/O. When sustained write volume outpaces compaction throughput, SSTable count grows unbounded and both read amplification and space amplification climb with it; this is the operational risk the lsm_compaction_debt failure mode describes, and it is the primary way an LSM-tree deployment gets into trouble in production.