LSM Tree¶

The idea in one sentence¶

A log-structured merge tree never updates data in place: it buffers writes in memory, writes them out as immutable sorted files, and continuously merges those files in the background so reads stay fast. It trades extra background work for writes that are always large and sequential. It was introduced by O'Neil et al. in 1996 and popularized by Google's Bigtable (2006) and LevelDB (2011).

The write path¶

1. The write is appended to the write-ahead log so it survives a crash. (See WAL.)
2. It is inserted into the memtable, an in-memory sorted structure (usually a skip list). The write is now complete — no disk read, no random disk write.
3. When the memtable reaches its size limit, it is frozen as an immutable memtable and a fresh memtable (with a fresh WAL file) takes new writes.
4. A background thread writes the immutable memtable to disk as a Sorted String Table (SSTable): a file of key-value pairs sorted by key, with an index and a Bloom filter. The old WAL file can then be deleted.
5. Background compaction merges SSTables into larger ones at deeper levels.

Updates and deletes are just writes: an update writes a newer version of the key; a delete writes a tombstone — a marker meaning "this key is deleted as of this sequence number." Old versions and tombstones are physically removed only during compaction.

Sequence numbers and internal keys¶

Every write gets a monotonically increasing sequence number. The engine actually stores internal keys:

internal key = user_key + sequence_number + type (PUT or DELETE)
sort order   = user_key ascending, then sequence_number DESCENDING

So for one user key, the newest version sorts first. Example contents of a memtable after Put(a,1) Put(b,2) Put(a,3) Delete(b):

A lookup for a seeks to the first entry with user key a and finds seq 3 — the newest value. A lookup for b finds the tombstone at seq 4 and answers "not found" without looking further. Sequence numbers are also what make snapshots cheap: a snapshot is just a sequence number, and a read at snapshot 2 ignores every entry with seq > 2.

The read path¶

The first version found wins, because everything above it is newer. For each candidate SSTable, the engine:

1. Checks the file's key range (kept in memory) — skip if k is outside it.
2. Checks the Bloom filter — a compact bit array answering "is k possibly in this file?" with no false negatives and a tunable false positive rate (~1% at 10 bits per key). Most files are skipped without any I/O.
3. Binary-searches the in-memory index block to find the one data block that could hold k.
4. Reads that block (from the block cache or disk), verifies its checksum, and searches it.

With Bloom filters, a point lookup for an existing key typically costs about one disk read (the data block of the file that holds it); for a missing key, usually zero.

Range scans cannot use Bloom filters: they open an iterator on every memtable and every relevant SSTable and merge them, returning the newest version of each key and hiding tombstones.

Compaction¶

Without compaction, the number of SSTables grows forever, reads check more and more files, and deleted data is never reclaimed. Compaction reads several SSTables, merge-sorts them, keeps only the newest version of each key (that no snapshot still needs), drops tombstones that no longer hide anything, and writes new SSTables.

Leveled compaction (LevelDB, RocksDB default)¶

• Each level beyond L0 is a sorted run of non-overlapping files, so a point lookup checks at most one file per level.
• Each level is ~10x larger than the previous one (the fan-out).
• When a level exceeds its target size, one file is picked and merged with the overlapping files in the next level (about 10 of them, given the 10x ratio).

Worked example of the cost: moving one 64 MB file from L1 to L2 reads it plus ~10 overlapping L2 files (~640 MB) and writes ~700 MB. Each byte is rewritten roughly 10 times per level it passes through; across 4 levels that is the source of the ~10–30x write amplification. The payoff: about 90% of data lives in the last level, so space amplification is only ~1.1x, and reads touch one file per level.

Tiered / size-tiered compaction (Cassandra default, RocksDB "universal")¶

Wait until there are several SSTables of similar size, then merge them into one larger file. Each byte is rewritten only about once per tier, so write amplification is much lower — but a key can exist in many overlapping files (more read amplification), and merging requires free space equal to the inputs (space amplification up to ~2x).

Write stalls¶

Compaction is background work, but it is not optional. If writes arrive faster than compaction can merge, L0 files pile up and every read must check them all. Engines protect themselves by slowing down and then stopping writes when L0 reaches thresholds (RocksDB's level0_slowdown_writes_trigger and level0_stop_writes_trigger). These stalls are the most common LSM production incident.

Deletes are expensive in an LSM¶

A delete adds data (a tombstone) instead of removing it. The tombstone must survive until compaction has merged it into the bottom level — past every older version it hides. Workloads that delete large ranges (for example, a queue that deletes consumed messages) accumulate tombstones that scans must skip one by one, causing slow range reads. RocksDB adds range tombstones (DeleteRange) and options to compact files with many tombstones sooner.

Common pitfall¶

Treating "LSM tree" as one fixed design. Its behavior is dominated by tuning: memtable size, level size ratio, compaction style, Bloom filter bits per key, block cache size, and the number of compaction threads. The same RocksDB build can have write amplification of 5x or 40x depending on options. When comparing an LSM store with a B+Tree store, or diagnosing a slow one, check these settings first — most "LSM is slow at X" conclusions are really "this configuration was not tuned for X." Hands-on implementation details are in the storage engine series.