How LSM Trees Turn a Million Random Writes into One Calm, Sequential Stream

01 / 07

The disk arm problem nobody sees

A traditional B-tree database updates records in place. Your row lives at byte offset 48,201 on a spinning platter, so the drive seeks to 48,201, writes, then seeks to wherever the next update needs to go. With ten users that is fine. With ten thousand users updating per second, the arm spends more time travelling than writing.

Sequential writes avoid this entirely. Instead of jumping to ten thousand spots, the disk writes one long stream from wherever the head already sits. On a mechanical drive, sequential throughput can be a hundred times faster than random. Even on an SSD, where there is no physical arm, sequential writes still win because the flash translation layer can batch and align them. The gap is smaller (roughly two to five times), but it never disappears.

So the question becomes: can you take thousands of updates aimed at random locations and somehow rearrange them into a single sequential stream? That is the entire premise of the Log-Structured Merge-Tree.

02 / 07

One rule: never overwrite, only append

Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O'Neil published the LSM-Tree paper in Acta Informatica in 1996. The core idea fits in one sentence: instead of updating a record where it lives, write every change to the end of a list.

That list is the memtable, a sorted data structure sitting in RAM (often a red-black tree or a skip list). Every write, update, or delete goes here first. Because it lives in memory, insertions take microseconds. There is no disk seek, no waiting for a platter to spin around.

Once the memtable fills a configured threshold (typically a few megabytes), the database freezes it, sorts the contents by key, and flushes the whole thing to disk as a single file called an SSTable (Sorted String Table). One file, one straight write. The disk arm never has to jump.

03 / 07

What happens when the same key appears twice

Follow a user named Sam through the system. At 9:01 Sam sets status to away. That goes into memtable A. At 9:04 Sam changes to busy. Same memtable. At 9:07 the memtable fills and flushes to SSTable-1 on disk, carrying both versions of Sam.

An hour later Sam sets status to offline. This lands in a new memtable, which eventually flushes as SSTable-2. Now Sam's data exists in two files. Which value is real?

The answer is simple: the newest file wins. A read for Sam checks the memtable first (in case the latest write hasn't flushed yet), then SSTable-2, then SSTable-1, stopping as soon as it finds a match. The first hit is by definition the freshest, because SSTables are numbered in creation order.

04 / 07

Compaction: cleaning up without stopping the show

Left alone, the system would accumulate hundreds of small SSTables, and reads would slow to a crawl because every lookup would have to check file after file. So the database runs a background process called compaction.

Compaction picks two or more SSTables, merges them into one larger, sorted file, and throws out every outdated copy of a key. If Sam appeared in three files with three different statuses, only offline (the latest) survives the merge. Deleted records get cleaned up too: a special marker called a tombstone tells the merge process to discard the key entirely.

The clever part is that compaction never blocks the writers. New updates keep flowing into the memtable while old files merge in the background. The writers stay fast; the cleanup happens at its own pace.

05 / 07

The read tax and how Bloom filters pay it

Writes got faster. Reads got harder. That is the fundamental tradeoff of an LSM tree, and the Short did not have time to say it.

A B-tree can answer a point lookup in one or two disk reads because the data lives in exactly one place. An LSM tree might have to check several SSTables before it finds (or doesn't find) the key. Database engineers call this read amplification: the ratio of actual disk reads to logical reads.

The standard fix is a Bloom filter, a compact probabilistic data structure that sits in memory alongside each SSTable. Before opening a file to search for a key, the database asks the Bloom filter: "Could this key be here?" If the filter says no, the file is skipped entirely. A Bloom filter using roughly ten bits per key can reduce false positives to under one percent, which means nearly all wasted reads disappear.

RocksDB, LevelDB, Cassandra, HBase: every major LSM-based engine ships with Bloom filters enabled by default for exactly this reason.

06 / 07

Write amplification: the cost you pay later

There is a second cost the Short skipped. Every piece of data that enters the system will eventually be rewritten during compaction, possibly several times as it moves through levels. If a ten-byte key-value pair gets compacted through four levels, the database wrote forty bytes to disk for one ten-byte update. That ratio is write amplification.

Leveled compaction (used by LevelDB and RocksDB's default) keeps read amplification low but pushes write amplification higher, sometimes ten to thirty times the original write volume. Size-tiered compaction (used by Cassandra's default strategy) writes less but accumulates more temporary space on disk.

Neither strategy is wrong. The choice depends on whether your workload cares more about read latency or write throughput, and how much spare disk space you can tolerate. The point is that LSM trees did not eliminate the cost of random I/O. They moved it: from the write path, where users wait, to the background, where they do not.

07 / 07

Why this matters beyond the paper

Google's Bigtable paper in 2006 brought LSM trees into the mainstream by using them as the storage layer for a system handling petabytes of data across thousands of machines. That paper led directly to open-source implementations: HBase in the Hadoop ecosystem, LevelDB as a standalone library, and RocksDB (originally a Facebook fork of LevelDB) which now powers storage in MySQL (via MyRocks), CockroachDB, and TiKV.

If you have used a messaging app, a time-series database, or a key-value store in the last decade, an LSM tree was probably writing your data. The pattern that O'Neil and colleagues described in 1996 turned out to be one of the most widely deployed ideas in database engineering.