Part 1 · 2 chapters · ~12 min

LSM Trees

Why LSM trees (sequential writes versus B-tree page updates), memtables and the commit log, SSTables with block indexes and Bloom filters, the read path, compaction strategies (size-tiered, leveled, time-window, incremental), tombstones, amplification and the RUM conjecture, caches, and RocksDB as the reference implementation.

3

Writes in memory, merges in the background

B-trees (MySQL and Postgres courses) update pages in place: a write may touch a random page. LSM trees turn every write into an append, then pay the cost later in compaction. Fast writes now, merge work later.

AN LSM TREE
writes go to memory and a log; sorted files are merged in the background
writecommit logappend, durablememtablesorted, in memorySSTable L0flushed, immutablecompactionmerge, drop tombstonesSSTables L1..Lnlarger, sorted runs
swipe the figure sideways, or tap expand for full screen
1/5
write path
A write is appended to the commit log (for durability) and inserted into the in-memory memtable (a sorted structure). That is all: sequential IO and memory, no in-place page updates. This is why LSM stores take writes so fast.
append to a log, insert in memoryno random writes on the write path
4

Compaction strategies and tombstones

strategyhowgood forcost
size-tiered (STCS)merge SSTables of similar sizewrite-heavy workloadsreads touch more files; temporary 2× disk space
leveled (LCS)levels of non-overlapping runs, each 10× largerread-heavy, updatesmore write amplification
time-window (TWCS)compact within time buckets; drop whole old bucketstime series with TTLsout-of-order writes break the buckets
unified / incremental (newer)adapts between tiered and leveledmixed workloadsnewer, fewer operational war stories

Tombstones: a delete writes a marker that hides older values until compaction removes both. Many deletes (queue-like workloads) leave tombstones that every read must skip; reads scanning thousands of them become slow and Cassandra warns or fails (tombstone_failure_threshold). RocksDB, Facebook's embeddable LSM engine, is the reference implementation and powers many databases (CockroachDB's Pebble is a Go descendant, MyRocks, Kafka Streams state stores).