# LSM Trees and NoSQL Storage

Ramarathinam Iyer's explainer on [[lsm-tree|LSM trees]] — the storage engine behind Cassandra, RocksDB, LevelDB, and much of the NoSQL world. The article walks through the full architecture: why B-trees hit write amplification walls, how LSM trees solve this with append-only storage, and what tradeoffs come with the design.

## The B-tree problem

B-trees store data in fixed-size pages (typically 8 KB). Changing a single byte means loading the page, modifying it, and writing the whole thing back — random I/O. This is the write amplification problem: the ratio of actual bytes written to disk versus bytes the application wanted to write is much greater than 1. It's slow on HDDs and wears out SSDs faster than necessary.

## How LSM trees work

LSM trees never overwrite. Every write is append-only, and the system reconciles multiple versions later.

The write path: data goes to a Write Ahead Log (WAL) on disk for crash durability, and simultaneously into a MemTable — a sorted in-memory structure (skip list or balanced tree). When the MemTable hits a size threshold (commonly 64 MB), it flushes to disk as an SSTable (Sorted String Table). SSTables are immutable once written.

The read path: check the MemTable first, then search SSTables level by level, newest to oldest. The first match wins, which is how updates work — a newer SSTable's value shadows an older one for the same key. Deletions write a tombstone marker; reads that encounter a tombstone treat the key as deleted.

## Bloom filters

Without optimization, reads would scan every SSTable on disk. Bloom filters fix this. Each SSTable has an associated Bloom filter in memory — a probabilistic structure that can say "this key is definitely not here" (skip the file) or "this key might be here" (read the file). False positives happen but are rare; false negatives don't. This turns most read misses into cheap RAM lookups.

## Compaction

Over time, many SSTables accumulate with overlapping key ranges and stale versions. Compaction merges them in the background, discarding old versions and tombstones.

Two main strategies exist. Leveled compaction (RocksDB, LevelDB) merges aggressively to keep read amplification low — fewer files to check — at the cost of more write amplification from frequent merges. Size-tiered compaction (Cassandra) batches files of similar size before merging, favoring write throughput over consistent read latency.

## Failure modes

**Write stalls** happen when the MemTable fills up but can't flush fast enough — compaction is behind, disk is slow, or both. The database stops accepting writes to avoid running out of memory. This is backpressure, and it's intentional, but it shows up as sudden latency spikes in production.

**Space amplification** is the other cost. Updating a key 100 times means 100 copies exist on disk until compaction cleans them up. A write-heavy workload with slow compaction can temporarily use several times the logical data size.

## See also

- [[lsm-tree]] — concept page on the data structure itself