System Design AI

LSM Trees in System Design Interviews: When to Use Them and What to Say

One-Sentence Definition

Log-Structured Merge (LSM) trees are storage structures that buffer writes in memory, then sequentially merge them to on-disk sorted files, providing high write throughput at the cost of more complex reads.

The Problem LSM Trees Solve

Traditional B-tree based databases write each mutation directly to disk pages. That generates random I/O, which becomes a bottleneck when the write rate climbs to tens of thousands of writes per second. Imagine a log-aggregation service that ingests 10 GB of JSON events per hour from many microservices. If each event required a random disk seek, the storage layer would saturate quickly. LSM trees turn those random writes into sequential appends, allowing the same hardware to handle orders of magnitude more writes.

How LSM Trees Work – Step by Step

  1. MemTable (in-memory write buffer) – New writes are inserted into a sorted in-memory structure (often a skip list). The write is considered committed once it reaches the memtable.
  2. WAL (write-ahead log) – Before touching the memtable, the operation is appended to a durable log so the system can recover after a crash.
  3. Flush – When the memtable reaches a size threshold (e.g., 128 MiB), it is frozen and written to disk as an immutable sorted file called an SSTable.
  4. SSTable Levels – SSTables are organized into levels (L0, L1, …). Newer, smaller files sit in lower levels; larger, older files sit higher up.
  5. Compaction – Periodically, overlapping SSTables from level i are merged into level i+1, discarding deleted or overwritten keys. This keeps read paths bounded.

Small Worked Example

Suppose we have a key-value store with a 64 MiB memtable limit.

  • Write A=1 → added to memtable, WAL gets A,1.
  • Write B=2 → same.
  • ... after 64 MiB of entries, the memtable is flushed, producing sstable-L0-001. The WAL segment is truncated.
  • Read A → Search memtable (miss), then look in L0 files (found in sstable-L0-001). No need to scan higher levels.
  • Later writes cause L0-001 and L0-002 to overlap → compaction merges them into a single sorted file in L1, reducing the number of files a read must check.

Where LSM Trees Show Up in Classic Interview Questions

Design QuestionTypical Role of LSM Tree
Log Aggregation Service (e.g., ingesting clickstream events)Stores incoming events in an LSM-based store such as Cassandra or RocksDB to absorb high write rates.
Time-Series Database (e.g., metrics collection)Uses LSM tables to append new measurements efficiently; compaction helps purge old data.
Key-Value Cache with Persistence (e.g., a write-through cache for a web app)Backed by an LSM store to persist writes while serving reads from an in-memory cache layer.

In each case the LSM tree lives at the persistence layer, behind the API or service that receives the write traffic.

Trade-offs and the Alternative Interviewer May Probe

AspectLSM TreeB-Tree (or traditional DB)
Write throughputVery high; writes are mostly sequential.Limited by random I/O; each write may cause a page split.
Read latency (point look-up)Needs to check memtable + several SSTables; often a few extra I/O.Typically one page read; lower latency for hot keys.
Range queriesEfficient because files are sorted; can scan contiguous blocks.Also efficient, but may require reading multiple pages.
Space overheadCompaction creates temporary duplicate data; can be 1.5-2× raw size.Less duplication; space usage close to logical size.
ComplexityRequires background compaction, bloom filters, and tiered levels.Simpler; no background merging needed.

Interviewers often ask: “What if the read latency becomes a problem?” The expected answer is to add a read-optimized cache (e.g., Redis) or to use a hybrid approach where hot keys are kept in a B-tree-like structure while the bulk of writes stay in the LSM store.

30-Second Pitch

"An LSM tree buffers writes in an in-memory sorted structure, then flushes them as sequential immutable files. Compaction merges overlapping files to keep reads bounded. This design gives write-heavy workloads—like log aggregation or time-series metrics—excellent throughput, at the cost of higher read latency and extra space during compaction. If the interview asks about read performance, mention a hot-key cache or a hybrid B-tree layer."

Common Mistakes Candidates Make

  • Claiming LSM is always better – Forget to qualify with workload characteristics. For read-heavy workloads, a B-tree may be superior.
  • Mixing up compaction with replication – Compaction is an internal merge process; it does not provide durability or fault tolerance.
  • Omitting bloom filters – Many candidates forget to mention that LSM implementations often add bloom filters to avoid unnecessary disk reads.
  • Ignoring write amplification – The extra writes caused by compaction can stress SSD endurance; interviewers may probe your awareness of that.

How to Practice This

  1. Study the worked design in the System Design AI library for an embedded storage engine like RocksDB, which is built around an LSM tree.
  2. Draw your own diagram on the canvas: show the write path (client → API → write-ahead log → memtable → SSTable → compaction) and the read path (cache → memtable → bloom filter → SSTable).
  3. Explain the trade-offs aloud using the 30-second pitch, then answer follow-up questions about read latency, space overhead, and hybrid alternatives.

Questions people ask

When should I recommend an LSM tree in a design?

Choose it when the system expects high write volume, sequential appends, and can tolerate slightly higher read latency. Typical examples are log ingestion, time-series metrics, and persistent caches.

What is compaction and why does it matter?

Compaction merges overlapping on-disk files to keep the number of SSTables low, which bounds read latency. It also removes deleted or overwritten keys, but it creates write amplification and temporary extra storage.

How do LSM trees handle point reads efficiently?

They keep a bloom filter per SSTable to quickly rule out files that do not contain the key, and they check the in-memory memtable first. This reduces the number of disk reads needed for a lookup.

What alternative should I discuss if the interviewer asks about read-heavy workloads?

Mention a hybrid approach: hot keys kept in a B-tree or in-memory cache, while the bulk of data lives in an LSM store. You can also talk about using secondary indexes or materialized views to speed up reads.