LSM Trees: Write-Optimized Storage for Cassandra and RocksDB

LSM Trees are write-optimized storage structures that turn random writes into sequential I/O by buffering mutations in an in-memory sorted structure (memtable) and periodically flushing them as immutable sorted runs (SSTables) to disk. Reads merge results across multiple levels of sorted files. This design makes LSM Trees the foundation of write-heavy databases like Apache Cassandra, RocksDB, LevelDB, and ScyllaDB, where sustained high write throughput matters more than single-read latency.

Why This Matters

LSM Trees matter because traditional B-tree storage engines hit a wall under sustained write-heavy workloads. Each B-tree write requires finding the correct page and updating it in place, which translates to random disk I/O. LSM Trees avoid this entirely by writing to an in-memory buffer and periodically flushing sorted data sequentially — a pattern that's 100x faster on both SSDs and HDDs. Understanding LSM Trees is essential for anyone designing high-ingestion systems, choosing between storage engines (InnoDB vs RocksDB, WiredTiger vs LSM), or diagnosing write stalls and read amplification in production.

The Building Blocks

• Memtable: An in-memory sorted data structure (typically a skip list or red-black tree) that absorbs all incoming writes. Writes are also appended to a write-ahead log for durability.
• SSTables: When the memtable reaches a size threshold, it's flushed to disk as an immutable Sorted String Table — a file of key-value pairs in sorted order with an index for binary search.
• Compaction: Background compaction merges overlapping SSTables across levels, eliminating duplicate and deleted keys. Strategies include size-tiered (better write throughput) and leveled (better read performance).
• Bloom Filters: Each SSTable includes a Bloom filter that quickly answers 'is this key possibly in this file?' — avoiding expensive disk reads for keys that aren't present in a given level.
• Write-Ahead Log: Every write is first appended to a WAL before hitting the memtable, ensuring durability — if the process crashes, the WAL replays uncommitted writes on recovery.

Under the Hood

When a write arrives, it's first appended to the write-ahead log (sequential append, very fast) and then inserted into the memtable (an in-memory sorted structure). The memtable allows efficient in-memory reads and maintains sort order for the eventual flush. When the memtable exceeds a size threshold (typically 64-256MB), it becomes immutable and a new memtable takes its place. The immutable memtable is flushed to disk as a Level-0 SSTable.

SSTables are organized in levels. Level-0 files may have overlapping key ranges (they're direct memtable flushes), but levels 1 and above are non-overlapping — each key exists in exactly one file per level. Compaction merges files from Level-N into Level-N+1, performing a merge-sort that eliminates obsolete versions and tombstones (deletion markers). Size-tiered compaction groups similarly-sized files for merging (simple, good write throughput, but temporarily doubles space usage). Leveled compaction maintains strict non-overlap per level (better read performance and space efficiency, but more frequent compaction writes).

Reads check the memtable first, then Level-0 SSTables, then progressively deeper levels. Bloom filters on each SSTable skip files that definitely don't contain the requested key. In the worst case, a point read may check one file per level — this is read amplification, the primary cost of the LSM design. Databases mitigate this with block caches, Bloom filters, and fence pointers (sparse indexes at the start of each data block).

How Companies Actually Do This

Apache Cassandra Uses LSM Trees as its storage engine, enabling millions of writes per second for use cases like time-series IoT data at Apple (which runs one of the largest Cassandra clusters at 150,000+ nodes).

Meta RocksDB (Meta's embeddable LSM-tree database) powers multiple internal systems including the MySQL storage engine (MyRocks), which reduced storage usage by 50% compared to InnoDB for their massive social graph workload.

CockroachDB Uses Pebble (a Go-native LSM-tree engine inspired by RocksDB) for its storage layer, choosing LSM Trees because distributed databases face heavy write loads from replication and Raft log application.

Common Pitfalls

1. Not monitoring compaction debt — when writes arrive faster than compaction can merge files, the number of SSTables per level grows, causing read latency to spike and eventually triggering write stalls
2. Using LSM Trees for read-dominated workloads — if your workload is 95% point reads and 5% writes, a B-tree engine will outperform LSM because data is in one location rather than spread across levels
3. Ignoring space amplification — during compaction, both old and new SSTables coexist temporarily, so you need 2x the logical data size in free disk space to avoid out-of-disk crashes

Interview Questions Worth Practicing

1. Compare LSM Trees and B-Trees — what are the key tradeoffs, and how would workload characteristics influence your choice?
2. Explain how compaction works and the difference between size-tiered and leveled compaction strategies.
3. How do Bloom filters improve read performance in an LSM Tree, and what are their limitations?

The Tradeoffs

• Write Amplification vs Read Amplification: Leveled compaction reduces read amplification by maintaining sorted levels but increases write amplification through more frequent merges
• Write Throughput vs Read Latency: LSM Trees achieve very high write throughput via sequential I/O but reads may need to check multiple levels, increasing tail latency
• Space Amplification vs Compaction Frequency: Less frequent compaction saves I/O but leaves more redundant data on disk; aggressive compaction reclaims space but consumes CPU and bandwidth

How to Explain This in an Interview

Here is how I would explain LSM Trees in a system design interview:

Start by explaining the core idea: instead of updating data in place like a B-tree, LSM Trees buffer writes in memory and periodically flush them as sorted, immutable files to disk. This turns random writes into sequential writes, which is 10-100x faster. Walk through the flow: writes go to the WAL (for durability) then the memtable (for fast in-memory access). When the memtable fills, it's flushed as an SSTable to Level-0. Compaction merges SSTables across levels, eliminating duplicates and maintaining sort order. For reads, the system checks the memtable, then each level, using Bloom filters to skip irrelevant files. The tradeoff is read amplification — a single key lookup may check multiple files. Close by comparing to B-trees: LSM wins on writes, B-trees win on reads, and the choice depends on your workload's read/write ratio.

Related Topics

• B-Trees
• Database Indexes
• Database Types
• NoSQL Data Modeling

Original DosiBridge notes for LSM Trees: Write-Optimized Storage for Cassandra and RocksDB

This section is written specifically for this page, not copied from a general system-design checklist. The useful way to study LSM Trees: Write-Optimized Storage for Cassandra and RocksDB is to connect the concept to a production service where growth exposes the first weak assumption in the original design. That framing changes the design discussion from definitions to operating choices.

What makes this topic distinct

• Query Shape: For LSM Trees: Write-Optimized Storage for Cassandra and RocksDB, decide the query shape before choosing tools; otherwise the design looks clean but fails when lsm changes.
• Write Amplification: For LSM Trees: Write-Optimized Storage for Cassandra and RocksDB, decide the write amplification before choosing tools; otherwise the design looks clean but fails when trees changes.
• Replication Lag: For LSM Trees: Write-Optimized Storage for Cassandra and RocksDB, decide the replication lag before choosing tools; otherwise the design looks clean but fails when lsm changes.
• Migration Safety: For LSM Trees: Write-Optimized Storage for Cassandra and RocksDB, decide the migration safety before choosing tools; otherwise the design looks clean but fails when trees changes.
• Data Ownership: For LSM Trees: Write-Optimized Storage for Cassandra and RocksDB, decide the data ownership before choosing tools; otherwise the design looks clean but fails when lsm changes.

Production review question

If a team adopts LSM Trees: Write-Optimized Storage for Cassandra and RocksDB, what observable signal proves it helped instead of only making the architecture diagram more fashionable?

Practical metric to track

Track lsm-trees health as a named dashboard or review item: combine one user-facing metric, one saturation metric, and one correctness metric. For LSM Trees: Write-Optimized Storage for Cassandra and RocksDB, this keeps the discussion grounded in behavior that can be measured after deployment instead of generic advice that sounds good in an interview but never gets verified.