LSM-trees & SSTables: the other way to store data

Every lesson in this track so far has quietly assumed one storage design: the B-tree. Rows live in pages, the index is a tree kept sorted, and an update finds the row and rewrites it in place. That design is superb for reads — a lookup is a handful of page reads down a shallow tree — but it has a cost you've already met: writes are random. Inserting a key means finding the right page (possibly anywhere on disk) and modifying it, occasionally splitting it in two. On a write-heavy workload that's a lot of scattered I/O and write amplification.

There is a completely different family of storage engine built on the opposite bet, and it's worth a lesson because it powers a huge share of modern data systems — RocksDB, LevelDB, Cassandra, ScyllaDB, HBase, and the internals of many newer databases. It's the LSM-tree: the Log-Structured Merge-tree. Its founding idea is radical in its simplicity: never write to disk randomly. Ever.

The core trick: buffer in memory, flush sequentially

If random writes are the enemy, the LSM's answer is to not do them. A write doesn't go looking for a page to modify. Instead:

1. The write lands in an in-memory sorted structure called the memtable (typically a skip list or balanced tree — something that keeps keys in order and is fast to insert into). This is just RAM, so it's instant.
2. To survive a crash, the write is also appended to a write-ahead log on disk first — the exact durability trick from the write-path lesson, a sequential append that's cheap. The WAL exists only so that if the machine dies before the memtable is flushed, the memtable can be rebuilt by replaying the log.
3. When the memtable fills up, it is flushed to disk in one sequential write as an immutable file called an SSTable — a Sorted String Table: all the keys, in sorted order, written once and never modified again.

That's the whole write path, and notice what it achieved: every byte that hits disk was written sequentially — either appended to the WAL or streamed out as a fresh SSTable. There are no in-place updates, no page splits, no random seeks. On the random-vs-sequential I/O gap from the pages lesson, the LSM lives entirely on the fast side. This is why LSM engines absorb writes so much faster than B-trees, and why they were originally designed for spinning disks (where random I/O was catastrophic) and still win on write-heavy SSD workloads.

Updates and deletes without ever modifying a file

Here's the immediate puzzle: if SSTables are immutable, how do you change a value or delete a key? You can't edit the old file. The answer is that you don't — you write the change as a new record that supersedes the old one:

• An update writes the new key/value into the memtable, which eventually lands in a newer SSTable. The old value still sits in an older SSTable, untouched. The system just has to know the newer one wins.
• A delete writes a special marker called a tombstone — a record that says "this key is deleted as of now." The actual data in the older SSTable is still there; the tombstone shadows it.

So at any moment a single key may have several records scattered across the memtable and multiple SSTables — some old values, maybe a newer value, maybe a tombstone — and the rule for resolving them is simply newest wins. This should feel familiar: it's the same "never overwrite, write a new version, resolve by recency" strategy that MVCC uses for row versions. LSM applies it to the entire storage engine, and — just like MVCC — it means dead data accumulates and something has to clean it up later.

The cost lands on reads

The bill for cheap writes arrives at read time. To read a key, the engine must find its newest record, and that could be anywhere: check the memtable first (newest), then the SSTables from newest to oldest, stopping at the first hit. A key that isn't in the memtable might force you to consult many files. This is read amplification — one logical read becomes several physical lookups — and it's the LSM's defining weakness against the B-tree's shallow, predictable descent.

Two mechanisms keep it under control:

• Each SSTable is sorted, and ships with a small sparse index (every Nth key and its file offset). So within one SSTable, finding a key is a binary search over the index plus one block read — not a scan.
• Bloom filters. This is the clever one. Each SSTable carries a Bloom filter: a compact, probabilistic bit-structure that answers one question — "could this key be in this file?" — with two possible answers: "definitely not" or "maybe." It can produce false positives (says maybe when the key is absent) but never false negatives. So before touching an SSTable, the engine checks its Bloom filter; if the filter says "definitely not," it skips that file entirely without any disk read. For the common case of looking up a key that lives in only one file, Bloom filters let the engine skip nearly every other SSTable, collapsing read amplification back toward B-tree levels. Bloom filters are the single reason LSM reads are practical at all.

Compaction: the LSM's garbage collector

If every flush creates a new SSTable and files are never modified, the file count grows without bound — more files means worse read amplification and more wasted space holding superseded values and tombstones. So a background process continuously merges SSTables together: it reads several sorted files, merges them (a merge join over sorted inputs — the same algorithm from the planner lesson), keeps only the newest record for each key, physically drops the values shadowed by newer writes and the ones marked by tombstones, and writes out fewer, larger, cleaned SSTables. This is compaction, and it is to an LSM exactly what VACUUM is to Postgres: the essential background chore that reclaims space and keeps reads fast, whose falling behind is the source of the engine's worst operational pain.

Compaction comes in strategies with different trade-offs — size-tiered (merge similarly-sized files; fewer merges, so cheaper writes, but more files to read and more space used) and leveled (keep non-overlapping files organized into size levels; more merging work, so higher write amplification, but far fewer files per read and tighter space). The choice is literally a knob for trading write cost against read cost.

Operate the engine yourself. Put a key a few times (each write is a new version), delete one to drop a tombstone, then Flush to seal each memtable into an immutable SSTable. Now Get a key and watch the search walk newest-to-oldest, skipping whole files whose bloom filter says "definitely not" — then Compact and watch the superseded versions and tombstones disappear.

The real decision: read, write, or space — pick two

Step back and the choice between B-tree and LSM is one instance of a general law of storage engines: you are trading among three amplifications, and improving one tends to worsen another.

There's no universally better engine — there's a workload, and a shape that fits it. Read-heavy transactional data with strong consistency needs and lots of range queries wants a B-tree. A firehose of writes you'll rarely read each of individually — telemetry, event logs, time series, a message store — wants an LSM. Knowing both is what lets you recognize which one a given system is, and why it behaves the way it does under load.