Skip to content

LSM Trees (Log-Structured Merge-Trees)

1. What is it? (2-3 lines)

An LSM Tree is a append-only data structure optimized for write-heavy workloads. It buffers incoming writes in an in-memory sorted structure (MemTable) and periodically flushes them to disk as immutable sorted string tables (SSTables), which are periodically merged in the background via compaction.

2. Why does it exist?

B+ Trees perform random disk page overwrites for every insert/update, causing severe disk write amplification and I/O bottlenecks under high write volume. LSM Trees eliminate random disk writes entirely by converting all writes into sequential memory appends and sequential disk flushes (\(O(1)\) write time complexity).

3. Where is it used?

  • NoSQL / Distributed Databases: Apache Cassandra, RocksDB, LevelDB, ScyllaDB, Google Bigtable, CockroachDB (Pebble storage engine).
  • Search Engines: Apache Lucene / Elasticsearch (Segment files follow LSM principles).

4. How does it work? (simple flow)

  1. Write (MemTable + CommitLog): Incoming write is appended to a sequential CommitLog on disk (for durability) and inserted into an in-memory sorted tree (MemTable - SkipList or Red-Black tree).
  2. Flush to Disk: When MemTable fills (e.g. 64MB), it is frozen and written to disk as an immutable SSTable (Sorted String Table) at Level 0 (\(L_0\)).
  3. Point Lookup: Search order: MemTable \(\rightarrow\) Immutable MemTables \(\rightarrow\) Bloom Filter check \(\rightarrow\) SSTables from \(L_0\) to \(L_N\).
  4. Bloom Filter Acceleration: Bloom filters attached to SSTables instantly skip files that definitely do not contain the target key.
  5. Compaction: Background threads merge multiple overlapping SSTables into new sorted Level \(N+1\) SSTables, purging overwritten keys and deleted tombstones.

5. Advantages

  • Ultra-high write throughput (all writes are sequential memory appends and disk flushes).
  • Low Write Amplification compared to B+ Trees.
  • High storage density (immutable SSTables compress efficiently on disk).

6. Limitations

  • Read Amplification: A read query may check multiple SSTable files on disk if the key isn't in RAM.
  • Space Amplification: Overwritten data and tombstones consume disk space until compaction completes.
  • Compaction Storms: Heavy background compaction can saturate disk I/O, causing write latency spikes.

7. Common interview questions (10)

  1. How does an LSM Tree achieve 10x higher write throughput than a B+ Tree?
  2. What is an SSTable and why is it immutable?
  3. How do Bloom Filters mitigate Read Amplification in LSM Trees?
  4. What is the difference between Size-Tiered Compaction Strategy (STCS) and Leveled Compaction Strategy (LCS)?
  5. What are Tombstones in LSM Trees and why can premature deletion cause resurrected data bugs?
  6. How does RocksDB manage MemTable flushes and Write Stalls under heavy write pressure?
  7. What is Space Amplification vs Write Amplification vs Read Amplification in LSM Trees?
  8. How does an LSM Tree execute range queries across multiple SSTable levels?
  9. Why are SSTables easy to replicate and snapshot for cloud backups?
  10. When would you choose RocksDB (LSM) over InnoDB (B+ Tree) as an engine backend?

8. Common misconceptions

  • Misconception: LSM Trees don't support range queries. Fact: SSTables are internally sorted; LSM engines run multi-way merge iterators across SSTables to execute range queries.
  • Misconception: Deletes instantly remove data from disk. Fact: Deletes append a "tombstone" marker record; actual physical data removal occurs during background compaction.

10. 30-second cheat sheet

  • Write Path: MemTable (RAM) \(\rightarrow\) SSTable (Disk) \(\rightarrow\) Compaction (Merge). Sequential \(O(1)\) writes!
  • Read Path: MemTable \(\rightarrow\) Bloom Filter check \(\rightarrow\) SSTables (\(L_0 \dots L_N\)).
  • Strength: Unmatched write-heavy QPS and high data compression.
  • Weakness: Higher read latency and I/O degradation during background Compaction Storms.