Read Amplification (LSM Tree)
criticalSummary
In LSM-tree storage engines (Cassandra, RocksDB, LevelDB), a single logical read may require checking multiple immutable SSTables across multiple levels of compaction before the most recent version of a row is found: multiplying I/O by the number of levels checked and producing latency spikes on reads that cross many levels.
Description
LSM-tree (Log-Structured Merge-tree) storage engines are write-optimized: writes are appended to an in-memory structure (MemTable) and flushed to disk as immutable files (SSTables) in sorted key order. This eliminates random write I/O: writes are always sequential. But reads pay the price.
For a read of key K: 1. Check the in-memory MemTable (fast, in-memory lookup) 2. If not found, check L0 SSTables (recently flushed; may have many overlapping ranges) 3. If not found in L0, check L1 SSTables (one non-overlapping per level) 4. Continue through L2, L3, ... until found or all levels exhausted
In the worst case, a key that doesn't exist (or was deleted recently) requires checking every level. At 7 compaction levels with 10 SSTables per level, a single miss may require 70+ SSTable checks (each requiring a disk I/O if not in the block cache).
Compaction reduces read amplification by merging SSTables and removing superseded versions. Insufficient or slow compaction allows SSTables to accumulate: - Frequent small flushes generate many L0 files - Compaction throughput constrained by disk bandwidth - Large value sizes make compaction slow (WiredTiger, RocksDB value separation)
Bloom filters mitigate read amplification: a per-SSTable Bloom filter can probabilistically determine whether a key is NOT in the file, allowing most files to be skipped with a single in-memory bit-array lookup. With a properly sized Bloom filter, point reads approach O(1) behavior. Range reads cannot use Bloom filters and still traverse all relevant SSTables.
Characteristics
Triggers
- ·Insufficient compaction bandwidth relative to write rate (LSM tree depth increases)
- ·Bloom filter disabled or undersized (false positive rate too high)
- ·Range queries on keys not co-located in SSTable sort order
- ·Frequent key deletions without subsequent compaction (tombstone accumulation)
- ·Working set exceeds block cache (every read goes to disk)
Detection Signals
Mitigation Strategies
Increase compaction thread count and I/O bandwidth allocation. For Cassandra, switch from SizeTieredCompaction (good for write-heavy) to LeveledCompaction (good for read-heavy) if reads are the primary bottleneck. LCS maintains bounded SSTable count per level by compacting aggressively.
Reduce the Bloom filter false positive rate (increase bits per key from the default of 10 to 15–20). This increases memory usage but reduces disk I/O for point reads by eliminating more false-positive SSTable checks.
Increase the storage engine's block cache (Cassandra key_cache and row_cache, RocksDB block_cache_size) to keep more SSTable blocks in memory. Reduces disk I/O for repeated reads on the same data. Most effective when the working set fits in memory.
For Cassandra, excessive tombstones (from row deletions or TTL expiry) degrade reads because tombstones must be checked during row reconstruction. Use TimeWindowCompaction for TTL-heavy workloads; compact tombstone-heavy partitions proactively. Avoid partition widths exceeding 100MB.
Recovery Steps
- 1.Measure current SSTable count per level using storage engine metrics
- 2.Identify whether compaction is falling behind: check pending compaction size
- 3.Increase compaction concurrency (Cassandra: concurrent_compactors; RocksDB: max_background_compactions)
- 4.Check Bloom filter configuration and false positive rate in storage engine stats
- 5.For Cassandra: run nodetool compact to force a full major compaction (temporarily)
- 6.Long-term: review data model for tombstone-heavy patterns or wide partitions
Estimated recovery time: Increasing compaction concurrency shows improvement within minutes to hours as SSTable count decreases. Full major compaction on a large node (several TB) takes hours. Architectural changes (compaction strategy switch, data model changes) require a maintenance window and take longer.
Affected Systems
Patterns
Technologies
Basis
LSM-tree read amplification is described in the foundational O'Neil et al. LSM-tree paper and is documented in Cassandra, RocksDB, and LevelDB technical documentation; Bloom filter mitigation is a standard technique with formal analysis
Run This Failure
Blast radius analysis for this failure mode within each scenario that carries it.
Related Architecture Knowledge
Inbound: affects this entity
Cassandra's LSM-tree storage engine accumulates SSTables that must be checked during reads; insufficient compaction allows SSTable depth to grow, increasing the I/O required per read.
Full relationship →Snapshots bound the number of events that must be replayed to reconstruct aggregate state, reducing the read I/O required to serve aggregate loads compared to full event log replay.
Full relationship →