LSM Tree Design

The write-optimized storage engine behind LevelDB, RocksDB and Cassandra, built as code: log, memtable, sorted files, Bloom filters, compaction and tombstones.

Overview

A log-structured merge tree (LSM tree) is a way to store a key-value index so that writes are cheap. Instead of updating a record in place on disk, it appends every write to a log, keeps recent writes sorted in memory, and writes them out in sorted batches. Background merges keep the number of files on disk under control. The design comes from a 1996 paper by O'Neil, Cheng, Gawlick and O'Neil, and it is the engine inside LevelDB, RocksDB, Cassandra and many others.

The interview version asks you to build one. You should be able to draw the write path and the read path, trace a handful of operations through memtable, files and a compaction, explain why a delete is a write, and say what compaction costs. This topic does each of those on a tree small enough to check by hand, with a runnable Python implementation.

The write path

A write touches two things: the write-ahead log (WAL), an append-only file that makes the write durable, and the memtable, a sorted in-memory structure (RocksDB's default is a skip list). When the memtable is full it is written to disk as one sorted, immutable file, an SSTable (sorted string table), and a fresh memtable starts. LevelDB converts its memtable at about 4 MB; the size is a tuning knob.

Append to the WAL — One sequential write — Durability: a crash replays the log into a new memtable
Insert into the memtable — O(log n) in memory — Keeps recent keys sorted so the flush is a straight scan
Flush — One sequential write of the whole memtable — Random updates become one sorted file

A trace on a tiny tree

The memtable here holds three entries before it flushes. Newer data always sits in front of older data: the memtable in front of every file, and newer files in front of older ones.

put a=1 — a=1 — none
put b=2 — a=1, b=2 — none
put c=3 — empty (flushed) — [a=1, b=2, c=3]
put a=10 — a=10 — [a=1, b=2, c=3] — get a = 10 (memtable wins)
delete b — a=10, b=tombstone — [a=1, b=2, c=3] — get b = none (tombstone hides 2)
put d=4 — empty (flushed) — [a=1, b=2, c=3], [a=10, b=tombstone, d=4] — get c = 3 (found in the old file)
compact — empty — [a=10, c=3, d=4] — b and its tombstone dropped

The read path

A read checks the memtable, then each SSTable from newest to oldest, and stops at the first hit. Every file has a Bloom filter in front of it: a small bit array that answers 'definitely not here' or 'maybe here', never a false 'not here'. RocksDB's documentation gives about 10 bits per key for a 1% false-positive rate. A sparse index (one entry per block) then narrows the search inside the file to one block.

Key written recently — 0 (memtable) — 0
Key in one old file, others filtered — 1 — 1 block
Key absent, 20 files, 1% false positives — About 0.2 on average — Usually 0
Key absent, no Bloom filters — All 20 — 20 block reads

An LSM tree in Python

The code keeps the three parts separate: a sorted memtable, immutable SSTables with a filter and a binary search, and the tree that wires them together. A set stands in for the Bloom filter so that the read path is exact; the shape of the check is the same.

The asserts follow the trace table line by line. The single compact here merges everything into one file, which is only right when the merge covers every file; the deletes question explains why.

Compaction

Without compaction, files pile up and every read of a missing key checks all of them. Compaction merges files into fewer, larger, fully sorted ones, keeping only the newest version of each key. There are two common shapes.

Layout — Level 0 holds fresh flushes that may overlap; each level above is one sorted run of non-overlapping files — Files grouped by size; similar-sized files are merged together
Level sizes — Each level about 10x the one below (RocksDB's default multiplier; LevelDB: 10 MB, 100 MB, ...) — No levels
Trigger — LevelDB and RocksDB start at four level-0 files — Enough files of about the same size
Cost — More rewriting (write amplification), less duplicate data on disk — Less rewriting, more duplicate data until merged
Used by — LevelDB; RocksDB's default; Cassandra's LCS for read-heavy tables — Cassandra's default (STCS)

Cassandra adds a third strategy, TWCS, for time-series data that expires: files are grouped by time window so old windows compact among themselves and drop cleanly. Its docs now recommend a newer strategy, UCS (Unified Compaction Strategy), for new workloads, while STCS stays the default.

Deletes are writes

A file on disk is never edited, so a delete cannot remove anything. Instead it writes a tombstone, a marker that says 'this key is gone as of now'. A read that meets a tombstone before any live value returns nothing. The tombstone can be dropped only when a compaction has merged it with every older version of the key; drop it earlier and an old copy in a deeper file comes back to life.

Cassandra adds a second reason to keep tombstones: replicas that were down must receive the delete. Its gc_grace_seconds keeps a tombstone for 864,000 seconds (10 days) by default; a node down longer than that must be repaired or it will restore the deleted data to the others.

Before the delete — b=2 in an old file
After delete(b) — b=2 in the old file, tombstone in the memtable; reads return nothing
After a flush — Tombstone in a newer file
After a compaction that includes the old file — Nothing; both are dropped
After a compaction that skips the old file — The tombstone must stay, or b=2 reappears

The three costs

Every LSM design is a trade between three amplifications. Interviewers want you to name them and say which knob moves which.

Write — Bytes written to disk per byte the user wrote — Leveled compaction, many levels — Size-tiered, larger memtable
Read — Files or blocks checked per lookup — Many level-0 files, no filters — Bloom filters, leveled layout, compaction
Space — Disk used per byte of live data — Size-tiered (old versions linger), lagging compaction — Leveled compaction

What you will be able to do

Draw the write path and the read path and say what each step costs.
Trace puts, deletes, flushes and a compaction through a tiny tree by hand.
Implement memtable, SSTable with a filter, and compaction in Python.
Explain leveled versus size-tiered compaction and the three amplifications.
Explain tombstones and when it is safe to drop one.

Interview questions

Explain the LSM tree write and read paths.
What is compaction and why is it necessary?
How are deletions handled in an LSM tree?
When would you pick an LSM tree over a B-tree?
How does a Bloom filter fit in, and what does it cost?