LSM-tree: never update in place, write a new sorted file and merge in the background

What it is for. Absorbing heavy random-write workloads without paying a random write per write. A B-tree updates in place: find the page, insert, split when full, update parents. LSM refinances that bill: turn random structural writes into sequential appends, and pay for it with more expensive reads.

The whole picture first. Writes land in memory, flush to disk as new tables, reads walk the tables newest first, and compaction merges in the background:

Write path. Every write goes to the write-ahead log first (durability), then into the memtable, an in-memory sorted structure (usually a skip list) where an insert only rewires pointers and moves no bulk data. When the memtable fills, it is traversed in key order and written out sequentially as one brand-new immutable SSTable: sorted, with an index block and a Bloom filter. Old SSTables are never touched, never modified.

Why insertion never shifts anything. Inserting into a sorted array moves every element after the gap; inserting into a skip list only rewires pointers:

Read path. Check the memtable first, then SSTables newest to oldest, and stop at the first hit: the newest version wins. Inside one table, the Bloom filter goes first: it answers "is this key in this table at all" without reading any data block. "No" means definitely absent, and the whole table is skipped with zero disk I/O. "Maybe" means: binary search the index block for the block's byte offset, seek straight there, and binary search inside the block. So the Bloom filter decides which table, and binary search decides where inside the table. The index alone cannot do the filter's job: it can only say which block would hold the key if the key were in the table, not whether it is there at all.

Worked example: one read, two maybes, one miss, one hit. Three tables on disk, newest first: T3 holds grape, lemon, peach; T2 holds apple, mango, sun; T1 holds book, dog, kite. Read the key sun. The memtable does not have it. T3's Bloom filter says maybe: say sun hashes to bits 3 and 7, and grape set bit 3 while lemon set bit 7, so the filter is fooled. Binary search of T3's index, seek, binary search inside the block: sun is not there. That is a false positive, and its whole cost is one wasted block read; nothing is missed. T2's filter also says maybe, and this time binary search finds sun. Return it and stop. T1 is never touched. If any table's filter had said no, that table would have been skipped without a single disk read. In a real system, the filter block, index block, and data block are each checked against the shared block cache first; the walk above is the cache-miss path, drawn for simplicity.

Updates and deletes are writes too. A new version of a key is just an entry in a newer table, and it shadows every older version. A delete is a tombstone entry: reads stop at the tombstone and report absent. Tombstones are dropped by compaction once they cover all older versions beneath them.

Tombstone lifecycle. A delete is a write, and the old version is only reclaimed by a later merge:

Compaction: where the single sorted order finally appears. Each SSTable is sorted inside itself, but across tables there is no global order at all: tables relate only by age, newest to oldest. The global order is reconstructed at read time (newest-first merge) and physically produced only by background compaction, which reads several tables, merge-sorts by key, writes new tables, and deletes the old ones. Insertion never rewrites an old file; only compaction writes new ones. Two strategies: leveling keeps one sorted run per level (cheap reads, high write amplification), tiering keeps several runs per level (low write amplification, high read amplification).

The three amplifications. Write amplification: compaction recopies data. Read amplification: one key may need the memtable plus several tables. Space amplification: old versions and tombstones sit until a merge drops them.

L0 and write stalls. The write path has a speed limit, and it lives in L0. Flushes land in L0, the one level whose files overlap, because flushed tables never went through a merge. From L1 down, compaction guarantees files do not overlap, so a read checks at most one file per level; in L0 a read may have to check every file. When writes arrive faster than compaction drains L0, backpressure kicks in, in two stages: first writes are deliberately delayed to buy time, then, if L0 keeps growing, writes stop outright until compaction catches up. Think of it as a rate-limited queue: writes are inflow, compaction is the drain, memtables plus L0 are the bucket; when inflow beats the drain and the bucket fills, the intake throttles. So LSM writes are not free: their cost is background merge work plus occasional stalls. Below compaction throughput they feel free; above it, they stall.

Sequence numbers and snapshots. Tables are immutable and old versions pile up, so a read needs to know which version is its version. Every write carries a monotonically increasing sequence number, and a read first takes a snapshot: the newest sequence number at read start. The read only considers versions with sequence numbers at or below its snapshot, newest first wins among those. So "newest wins" means newest visible to your snapshot, not newest globally. And compaction may only drop a version once no live snapshot can still see it: a version shadowed by a newer one still stays while an older snapshot lives. This is MVCC in LSM clothing: sequence numbers are transaction timestamps, snapshots are MVCC snapshots, old versions stay for unfinished reads.

Inside a block: prefix compression and restart points. Keys in a block are sorted, so neighbors usually share a prefix: user:1001, user:1002, user:1003 share user:10. A block stores the shared prefix length and only the differing suffix, which saves a lot of space when keys share prefixes. But then binary search cannot work directly, because reconstructing a key means walking forward from the start. So every N entries (16, typically) stores a full key, a restart point: binary search over restart points, then scan forward reconstructing within the small group. Blocks themselves may also be compressed whole (Snappy, LZ4, Zstd): CPU traded for disk I/O.

How compaction picks its files. Compaction never rewrites a whole level; that would explode write amplification. It is triggered by one of three conditions: L0 file count over its limit, a level's size over its limit, or pending compaction bytes over their limit. Each round picks one file plus every file in the next level whose key range overlaps it, merge-sorts them, and writes new files to the next level. L0 to L1 is special: because L0 files overlap, one round must bring every L1 file overlapping the picked range. In leveled compaction each level is roughly 10 times the previous one, so the number of levels grows with the logarithm of the data size, which bounds read amplification. Compaction also does the cleanup: tombstones once they cover older versions and no live snapshot needs them, versions invisible to all live snapshots, and TTL-expired records, which nobody deletes proactively.

The MANIFEST: the ledger of the file set. The WAL protects the data, but the file set itself needs a ledger: the MANIFEST. When a flush or compaction finishes, the database first writes an edit to the MANIFEST (new files in, old files out), and only then deletes the old files. Crash ordering is the whole trick: if the crash lands before the edit is written, the old file set is still valid and the new files are orphans cleaned on recovery; if the edit is written, the new file set is live. Atomic switchover comes from edit-first ordering.

Range scans. A point lookup finds one key; a range scan merges every lane in the range. One iterator per lane (memtable plus each table), all yielding keys in order, feeds a k-way merge heap: the heap top is always the smallest key's newest visible version. Emitting one key advances that lane. Snapshot rules are the same as point reads: only versions at or below the snapshot number, newest visible version per key only, tombstones suppress older versions behind them.

Where it is used, and where it is not. Cassandra, HBase, and ScyllaDB are all LSM; LevelDB and RocksDB are LSM storage engines underneath systems like CockroachDB and TiKV; InfluxDB is LSM too. Same family, different name: Lucene segments and ClickHouse MergeTree parts are immutable pieces plus background merge. Not LSM: PostgreSQL and MySQL/InnoDB, which are B-tree. The selection rule: write-heavy goes LSM, point-lookup-heavy with transactions goes B-tree.

The Bloom filter, in one paragraph. A bit array plus hash functions: it stores traces of keys, not keys. Joining a key sets a few bits; querying checks them. If any bit is 0, the key definitely never joined: no false negatives. If all bits are 1, the key may have joined, or other keys' traces may happen to cover those bits: false positives are possible, about 1% at roughly 10 bits per key. Each table's filter lives on disk with its table and is loaded into the database's one shared block cache, not one cache per table. The classic filter cannot delete, because one bit may serve several keys, but that is no problem here: tables are immutable, and a deleted table's filter is discarded with it. A semantic cousin exists, the distance-sensitive Bloom filter (LSH hashes plus Bloom bits), which promises "definitely nothing similar in the set"; in practice false negatives do appear, and the variant without them costs storage exponential in the radius, so it is rarely used. Exact membership goes to the classical Bloom filter, semantic neighbors go to vector indexes.

Transfer. The same arbitrage as wal: sequential beats random, and the counterpart to b-tree, whose in-place bill LSM refinances. nosql wide-column stores are the flagship users, and columnar-storage shares the immutable-pieces-plus-merge philosophy.

Kin. b-tree, wal, nosql, columnar-storage

Agent audit checklist: read this node, then check a storage system against every line, and report each item with evidence.

1. Write path order: WAL first, then memtable, then flush as a new file; old files untouched by any write.
2. Read order: memtable, then SSTables newest to oldest, stop at first hit; Bloom filter before any data block read.
3. Bloom semantics: says absent means absent, says present means maybe; false-positive rate and bits per key stated.
4. Deletes: tombstone present, read stops at it, compaction drops it only once it covers older versions.
5. Compaction strategy named (leveling or tiering) and which amplification it buys down.
6. Selection rule applied: write-heavy versus point-lookup-heavy, with the workload's numbers.
7. Stall limits: L0 file count and pending compaction bytes limits stated, with slow-then-stop behavior.
8. Snapshot gating: no version dropped while a live snapshot can see it.
9. MANIFEST order: edit written before old files deleted; crash before the edit leaves the old set valid.