There is an old post office in the town, a single counter.

Letters and parcels arrive all day. The post office has a peculiar system: behind the counter sits a young clerk with a wide desk. When a letter arrives, the clerk does not carry it to the back room right away. Instead, she slides it into the sorted stack on her desk — filed by the sender’s surname, always in order. Anyone who comes to look for a letter checks the desk first; it takes only seconds.

But the desk is finite. When the stack grows to roughly two hundred letters, the clerk ties it with twine, writes a serial number on the bundle, and hands it to an assistant behind her. The assistant places the bundle on the “recent shelf” — a row of wooden racks against the wall. The recent shelf can hold several bundles. Each bundle is internally sorted, but the bundles themselves are not sorted relative to one another.

After a while, the recent shelf fills up too. That is when the old archivist steps in. He pulls every bundle off the recent shelf, spreads them on a long table, and merges them the way you merge runs of playing cards — for any sender that appears more than once, only the newest letter is kept; the rest go into the wastepaper basket. The merged super-bundle is carried to the storeroom at the end of the corridor. Storeroom bundles are larger, older, and slower to search, but the letters inside each one are still in strict order.

If the storeroom fills up? There is a cellar with an even deeper set of racks. The archivist merges storeroom bundles once more and moves them down. The cellar bundles are the biggest, the oldest, and the slowest to search — but as long as you know which level you are on, you can flip through the sorted letters quickly enough.

A townsperson looking for a letter knows none of this. She simply tells the clerk “I need the letter from Wang’s Ironworks,” and the clerk searches in order: desk first (fastest), then each bundle on the recent shelf, then the storeroom, then the cellar. Most of the time, the desk or the recent shelf is enough.

The assistant eventually came up with a shortcut: before sealing each bundle, he jots down on a small card which surnames are definitely not inside. When searching, a glance at the card — “no Wang here” — and the bundle is skipped without being untied. The time saved is considerable.

Townspeople sometimes wonder: writes are so fast, but reads might have to dig through several levels — won’t that be slow? The old archivist smiles and says the trick is that writes only ever add to the desk; they never go back and amend an old bundle. Untying a bundle, pulling a letter out, re-sorting, re-tying — that is what’s slow. As long as you merge regularly, the dead letters in old bundles get cleaned out naturally.

— By now you’ve probably recognized it: this is the LSM tree (Log-Structured Merge-tree).

What it is

The LSM tree is a data structure designed for write-heavy workloads. New writes land first in an in-memory sorted buffer called the memtable. When the memtable fills, it is flushed as a whole into an immutable sorted file on disk called an SSTable (Sorted String Table). Multiple SSTables accumulate on disk in layers (Level 0, Level 1, …), each layer holding progressively more data. A background compaction process merges SSTables from one level into larger SSTables at the next level, discarding stale or overwritten records along the way.

Reads start at the memtable and work downward through the levels until the target key is found. Each SSTable can carry a Bloom filter — a probabilistic data structure that can quickly say whether a key is definitely not in that file, allowing the reader to skip irrelevant files entirely.

Why it matters

RocksDB, LevelDB, Cassandra, HBase, CockroachDB — nearly every modern write-heavy storage engine is built around LSM trees. The structure turns random writes into sequential writes (only appends and merges), pushing write throughput close to the disk’s sequential I/O ceiling. The tradeoff is that reads may need to probe multiple levels, and compaction consumes CPU and I/O bandwidth. Tuning an LSM engine is fundamentally about balancing write amplification, read amplification, and space amplification — Leveled compaction, Tiered compaction, and FIFO compaction each make different bets. Kubernetes’ etcd uses BoltDB (a B+ tree), not an LSM; but if you run Cassandra or CockroachDB workloads, understanding LSM compaction behavior is what lets you diagnose write-latency spikes and I/O storms.

Metaphor mapping

• the clerk’s desk, letters sorted by surname → the in-memory memtable, a sorted buffer
• tying the full stack and handing it back → flush, memtable written to an SSTable
• bundles on the recent shelf → multiple SSTables at Level 0
• the archivist merging bundles into a super-bundle → compaction, merging SSTables
• discarding duplicate old letters during merge → compaction dropping stale/overwritten records
• the storeroom and cellar → deeper levels (Level 1, Level 2, …)
• searching desk first, then each deeper level → read path from memtable through L0, L1, …
• the card listing which surnames are “definitely not here” → Bloom filter, skipping irrelevant SSTables
• writes only add to the desk, never amend old bundles → append-only writes, no random updates
• regular merging clears dead letters → compaction reclaims space and reduces read amplification