LSM Tree
The append-only storage engine design behind Cassandra and RocksDB — built for write throughput a B+ Tree can't match.
Overview
An LSM Tree (Log-Structured Merge Tree) is an append-only storage engine design — used by Cassandra, RocksDB, and LevelDB — built around writing sequentially instead of updating data in place, trading some read complexity for dramatically higher write throughput than a B+ Tree.
Why It Exists
Random writes to disk, the kind a B+ Tree's in-place updates need, are expensive — especially at very high write volume. LSM Trees exist for write-heavy workloads where sequential, append-only writes let the engine absorb huge write throughput, deferring the expensive work of reorganizing that data for fast reads to a background process instead of doing it inline with every single write.
Real World Example
Cassandra ingesting a continuous stream of IoT sensor readings: each write lands in an in-memory MemTable and a Write-Ahead Log, both fast, append-only operations. Once the MemTable fills up, it's flushed to disk as an immutable SSTable file. Over time, many SSTables accumulate, and a background compaction process merges and reorganizes them — removing duplicates and deleted entries — so read performance doesn't degrade indefinitely as more data arrives.
The Write Path, Piece by Piece
MemTable — Writes Land Here First
An in-memory, sorted structure that absorbs new writes instantly. It's fast precisely because it never touches disk on the write's critical path.
Write-Ahead Log — Durability Before the Flush
Since the MemTable is in memory, a crash would lose it. Every write is also appended to a WAL on disk first, so the MemTable's contents can be reconstructed after a crash even though the MemTable itself is volatile.
SSTables — Immutable, Sorted, on Disk
Once a MemTable fills up, it's flushed to disk as a Sorted String Table — an immutable file. Immutability is deliberate: it means SSTables never need locking for concurrent reads, and old ones can always be recreated by replaying the WAL if something goes wrong.
Compaction — Merging SSTables in the Background
As SSTables accumulate, a background process merges them, discarding overwritten values and deleted (tombstoned) entries. Without compaction, the number of SSTables a read has to check would keep growing indefinitely.
Diagram
Writes go in sequentially; the expensive reorganization happens later, in the background
Write arrives
MemTable (in-memory)
instant, sorted
WAL (on disk)
durability
MemTable fills up
flushed to disk
SSTable (immutable, on disk)
Background compaction
merges multiple SSTables into fewer, cleaner ones
Common Mistakes
Assuming reads are as fast as writes in an LSM Tree
Why: A single read might need to check the MemTable and multiple SSTables, since the same key can exist in several of them with the newest value winning — unlike a B+ Tree's single in-place lookup.
Fix: Rely on bloom filters (which most LSM engines include) to skip SSTables that definitely don't contain a key, and treat read amplification as the real trade-off for the write-throughput gain.
Ignoring compaction tuning under heavy write load
Why: If compaction falls behind, the number of SSTables a read has to check keeps growing, and read latency steadily degrades over time — a genuine, common LSM operational problem.
Fix: Monitor SSTable count and compaction backlog, and tune the compaction strategy for the actual workload rather than leaving it at a default that assumes lighter write volume.
Assuming a delete happens instantly at the physical level
Why: A delete in an LSM Tree is actually a special 'tombstone' write, not a physical removal — the old data still physically exists on disk until a later compaction pass actually removes it.
Fix: Know that a delete's visible effect (the value is gone from queries) and its physical cleanup (compaction reclaiming the space) happen at different times — this matters for both storage cost and compliance requirements like data-deletion mandates.
Interview Questions
What's the core idea behind an LSM Tree, in one sentence?
Writes go to memory and a sequential log first, and are only reorganized into their final, read-optimized form later, in the background — trading read complexity for much higher write throughput than in-place updates.
Why can a single read potentially need to check multiple SSTables?
The same key can have been written multiple times, and each write might have landed in a different SSTable as MemTables were flushed over time — the read has to check the MemTable and relevant SSTables, using the newest value it finds, until compaction eventually consolidates them.
Read latency on a Cassandra-style database has been steadily rising over weeks with no code changes. What's the likely LSM-specific cause?
Compaction falling behind sustained write volume, letting the number of SSTables per partition grow past what the compaction strategy was tuned for — each read now has to check more and more SSTables to find the current value. I'd check SSTable counts and compaction backlog metrics first, then review whether the compaction strategy and its resource allocation still match the current write rate.
Production Best Practices
Do
✓Monitor SSTable count and compaction backlog as first-class operational metrics.
✓Choose a compaction strategy that matches the actual read/write mix of the workload.
✓Understand that a delete is a tombstone write, not instant physical removal.
Don't
✗Don't assume LSM Tree reads are as cheap as writes — read amplification is the real trade-off.
✗Don't let compaction fall permanently behind sustained write load without noticing.
✗Don't assume a deleted value's disk space is reclaimed immediately.
Comparison
| Write Pattern | Read Pattern | Best For | |
|---|---|---|---|
| B+ Tree | In-place update, page splits | Single, direct lookup | Balanced read/write, point lookups |
| LSM Tree | Sequential append, background compaction | May check multiple SSTables | Very high write throughput |