The problem: writes land at random spots on disk#
TL;DRthe 30-second version
- Don't update data where it lives on disk. That's a slow random write. Buffer writes in a sorted table in memory (the memtable), then write the whole batch to disk in one sequential sweep.
- Log each write first (the WAL) so a crash can't lose it. When the memtable fills, write it out as an immutable sorted file (an SSTable).
- A read checks newest to oldest. A Bloom filter lets it skip files that can't hold the key. A background merge (compaction) keeps the file count and stale data in check.
- The bargain: very fast writes, paid for by rewriting data as it merges downward. This is the engine inside RocksDB, Cassandra, LevelDB, and ScyllaDB.
A normal database index updates a record in place. To write it, the engine finds the exact disk page the record belongs on and rewrites that page. A stream of writes to different keys becomes a stream of random disk jumps. Random writes are the slowest thing a disk does. A typical SSD sustains maybe 50–100 MB/s of small random writes, but 500+ MB/s writing sequentially. That's a 5–10× gap.
So here's the whole idea. Stop hunting for the right spot. Never update data where it lives. Buffer writes in memory, and once you've gathered a batch, write them all to disk in one sequential sweep. A storm of random writes becomes a few big sequential ones. Now let's build it, one piece at a time.
The write path: WAL, memtable, SSTable#
Every write first lands in the memtable. That's a sorted structure in memory, usually a skip list or a red-black tree. Writes arrive at memory speed. Because the memtable keeps its entries sorted by key, the eventual write to disk needs no extra sorting.
The memtable lives in RAM, and RAM vanishes on a crash. So before a write enters the memtable, it's appended to the write-ahead log (WAL), a plain sequential file on disk. Appending to a file is fast. After a crash, the engine replays the WAL to rebuild whatever was in the memtable. Nothing is lost.
When the memtable reaches its size limit, typically 64 to 256 MB, it's frozen and a new empty memtable takes its place. The frozen one is written to disk in one sweep as an SSTable, a Sorted String Table. Once written, an SSTable is never modified. That immutability is what keeps random writes out of the system. When the flush is done, the matching WAL segment is deleted, because the SSTable is now the durable copy.
An SSTable has a little structure inside so lookups are fast:
- Data blocks: key-value pairs grouped into fixed-size blocks, typically 4–64 KB, sorted within and across blocks.
- Block index: a small table at the end of the file with the first key of each block and its byte offset. A lookup binary-searches it and jumps straight to the one block it needs.
- Bloom filter: a few kilobytes of bits that answer 'is this key definitely not in this file?' with no false negatives. If it says no, the whole file is skipped without reading a byte.
The read path: newest to oldest#
To look up a key, the engine checks each place from newest to oldest and stops at the first match. Newest wins, because the latest write is the current value.
L0 holds the newest flushed files, and their key ranges can overlap, so every L0 file gets checked. From L1 down, compaction (next) keeps each level's files non-overlapping, so a lookup touches at most one file per level.
PredictYou GET a key that was never written. How many SSTable data blocks does a well-tuned LSM actually read from disk?
Hint: What is the Bloom filter for?
Ideally zero. The Bloom filter on each SSTable answers 'definitely not here' for a key that was never added, so the engine skips every file without reading a data block. The cost is just the in-memory Bloom checks, plus rare false positives. A missing-key read is the case Bloom filters were invented to make cheap.
Deletes are writes: tombstones#
An SSTable is immutable, so you can't erase a key from one. Instead a DELETE writes a tombstone: a record with the key and a 'deleted' marker. It flows through the WAL and the memtable like any other write. On a read, the tombstone is found first and shadows the older value, so the key looks gone.
The old value is still on disk in an older SSTable. It's removed later, during compaction, when the tombstone and the value it shadows are merged together and both are dropped.
Compaction: merging the files back together#
Every flush adds an SSTable. More files means more files to check on every read, and more space wasted on stale versions and tombstones. Compaction is the background job that reverses this. It picks a set of SSTables, merges them keeping only the newest value per key, drops tombstones that have nothing left to shadow, and writes a smaller set of new files. The inputs are then deleted.
- Leveled compaction: each level has a size cap, typically 10× the level above. When L0 overflows, its files are merged into the L1 files whose key ranges overlap, and so on down. From L1 on, files within a level don't overlap, so a read touches at most one file per level. Reads and space stay cheap, but each byte is rewritten about once per level on the way down. Used by RocksDB's default mode, LevelDB, and Cassandra's LCS.
- Size-tiered compaction: files of similar size are grouped into tiers. When a tier has enough files, typically 4, they're merged into one larger file. Each byte is rewritten far fewer times, so writes are cheaper. But a tier can hold many overlapping files, so reads probe more files, and a big merge can briefly need about 2× the dataset's disk space. This is Cassandra's STCS, and the usual pick for ingest-heavy time-series.
Newest at the top · each level about 10× larger
The three amplifications: write, read, space#
Every storage engine pays three costs. Lower one and you raise the others. An LSM tree makes a clear choice: cheap writes, paid for with some read and space amplification, both of which compaction keeps bounded.
PredictWith leveled compaction, each level is about 10× the one above and there are ~7 levels. Roughly how many times does one byte get rewritten by the time it settles at the bottom?
Hint: It's rewritten about once per level as it merges downward.
Very roughly 10–30× in practice (about the level multiplier × the number of levels). So one byte you write can become 10–30 bytes actually written to disk. That's write amplification, the price an LSM pays to turn random writes into sequential ones and keep reads cheap.
- Write amplification: bytes written to disk divided by bytes you logically wrote. Compaction rewrites data as it descends, so one ingested byte may be written 10–30× before it settles at the bottom.
- Read amplification: how many files one lookup touches. Without Bloom filters you'd read every SSTable. With them and leveled compaction, most lookups touch one or two files.
- Space amplification: disk used beyond the minimum the data needs. Pending tombstones, stale overwritten versions, and overlapping files all add to it until compaction catches up.
When to reach for an LSM (and when not to)
Reach for an LSM when writes dominate or arrive in bursts you can't afford to block on, and you can accept slightly slower, less predictable reads. It's a poor fit when the workload is read-mostly with strict point-read latency targets, or leans on large range scans and in-place updates.
- Good fit: write-heavy ingestion (metrics, logs, events, IoT), key-value and wide-column stores, time-series, and anything where ingest throughput is the bottleneck.
- Weaker fit: read-mostly OLTP needing single-digit-millisecond point reads with tight tail latency, or heavy scan-and-update patterns. A B-tree's in-place, single-path layout wins there.
- Watch out: delete- or update-heavy workloads create tombstones and stale versions that compaction must keep up with, or read latency and disk usage creep up.
LSM tree vs B-tree
| LSM tree | B-tree | |
|---|---|---|
| Write performance | Excellent — all writes are sequential appends | Good for light load; degrades under high write volume |
| Read performance | Good — bloom-filtered, but may probe multiple files | Excellent — predictable single-path lookup |
| Range scans | Reasonable — must merge across sorted SSTable files | Excellent — leaf linked list enables O(k) scan |
| Space usage | Temporary bloat until compaction catches up | Compact — in-place updates, no extra copies |
| Best for | Write-heavy: event logs, time-series, Cassandra, RocksDB | Read-heavy OLTP, range queries: PostgreSQL, MySQL, SQLite |
In the wild
- LevelDB (Google): the compact reference implementation. It introduced the leveled-compaction design most others build on. Embedded, single-process.
- RocksDB (Meta): a heavily extended fork of LevelDB. Multi-threaded compaction, column families, leveled/universal/FIFO compaction, tunable Bloom filters. The storage engine inside MySQL (MyRocks), CockroachDB, TiKV, and Kafka Streams.
- Apache Cassandra / ScyllaDB: wide-column stores with SSTables per table and pluggable compaction (STCS, LCS, TWCS). ScyllaDB reimplements Cassandra in C++ on a shard-per-core architecture.
- HBase / Bigtable: the original Bigtable paper's design. Memtable plus WAL plus SSTables on a distributed filesystem (HDFS or Colossus).
The same shape shows up outside databases too. Pebble (CockroachDB's Go LSM) and BadgerDB are embedded stores, and Lucene's index segments are immutable, merge-compacted SSTables for an inverted index.
Gotchas
- Tombstone storms. Until compaction clears them, tombstones take space and must be checked on every read. Cassandra users hit this when deletes outpace compaction: reads slow down and disk usage bloats.
- Over-aggressive compaction. It lowers read and space amplification but raises write amplification: more rewrites, more disk wear, more CPU. Run too hard, it starves foreground writes.
- Treating the WAL as optional. The memtable is in RAM and vanishes on a crash. The WAL is the only durable copy of recent writes until the flush lands.
QuizA workload does millions of overwrites to a small set of hot keys. Which amplification suffers most, and which compaction strategy helps?
- Read amplification; switch to size-tiered compaction
- Space amplification; leveled compaction keeps stale versions bounded
- Write amplification; disable compaction entirely
- None; overwrites are free in an LSM
Show answer
Space amplification; leveled compaction keeps stale versions bounded — Repeated overwrites leave many stale versions of the same keys scattered across files. That's space amplification. Leveled compaction keeps each level non-overlapping and merges often, so old versions are collapsed quickly and space stays bounded, at the cost of higher write amplification. Disabling compaction would let stale data and files grow without limit.
In an interview
Lead with the trade. An LSM turns random writes into sequential ones by buffering in the memtable and flushing to immutable SSTables. That buys write throughput. The price is read amplification (several files to probe) and write amplification (compaction rewrites data as it moves down). Bloom filters and leveled compaction keep both bounded.
Then name the parts in order: WAL, memtable, SSTable (block index plus Bloom filter), compaction. Know leveled versus tiered. Know tombstones. Name RocksDB, Cassandra, LevelDB, and ScyllaDB.
Are LSM reads always slower than a B-tree's?
No. Hot keys live in the memtable or L0 and are very fast, and Bloom filters make missing-key reads nearly free. The weakness is the worst case: a key in a deep level, or a range scan that merges across many SSTables. It's the tail latency that suffers, not the average read.
Does a delete free disk space right away?
No. A delete writes a tombstone, an extra record, so disk usage briefly goes up. Space is reclaimed later, when compaction merges the tombstone with the value it shadows and drops both.
Is the WAL redundant once the write is in the memtable?
No. The memtable is in RAM and vanishes on a crash. The WAL is the only durable copy of recent writes until the memtable is flushed to an SSTable. Then that WAL segment can be dropped.
Leveled or tiered compaction: how do you pick?
Leveled for read-heavy work: a read touches at most one file per level and space stays tight, but data is rewritten about once per level, 10–30× in total. Tiered for write-heavy ingest like time-series: far fewer rewrites, but reads probe more files and a big merge can briefly need 2× the disk.
References & further reading
- O'Neil, Cheng, Gawlick & O'Neil — The Log-Structured Merge-Tree (1996) — the original paper that named the structure
- RocksDB Wiki — Compaction — leveled, universal, and FIFO strategies in production
- Apache Cassandra — compaction strategies — STCS / LCS / TWCS in a wide-column store
- Martin Kleppmann — Designing Data-Intensive Applications, Ch. 3 — the clearest book-length treatment of LSM vs B-tree
Ready to try it?
The simulator is a real, deterministic implementation — pick a scenario and step through it, scrubbing the timeline forward and backward through every change.