Storage Engines
Every database is a bet about where to pay for writes. B-trees pay up front by updating pages in place; LSM-trees pay later by merging immutable files in the background. Here's how each works, and how each fails.
The whole idea
The simplest database
A storage engine is the part of a database that decides how bytes sit on disk. Its job sounds simple: store a value under a key, and give it back later. Doing both quickly, durably and at scale is where every interesting design comes from.
Start with the smallest thing that works. A set appends key,value to the end of a file; a get reads the
file and returns the last value it saw for that key. Appending is the cheapest write any disk can do, and
many real databases keep exactly this kind of append-only log at their core.
Fast writes, slow reads
The log is fast to write and hopeless to read: every get scans the whole file. The fix is an index, an
extra structure derived from the data that tells you where to look. An in-memory hash map from each key to its
byte offset is enough to make reads one seek; Riak’s Bitcask engine works roughly like this. But it has two hard
limits. Every key must fit in RAM, and a hash map can’t answer range questions like “all keys between
user:100 and user:200”.
So real engines keep data sorted by key, which makes ranges cheap and lets an index be sparse. There are two families of answer to “how do you keep data sorted while writes arrive in random order?”, and they run almost every database you use:
- Update in place. Keep a sorted tree of fixed-size pages on disk and overwrite the right page on every write. That’s the B-tree: Postgres, MySQL’s InnoDB, SQLite, SQL Server, Oracle.
- Append, then merge. Buffer writes in memory, write them out as sorted immutable files, and merge those files in the background. That’s the LSM-tree: RocksDB, Cassandra, ScyllaDB, HBase, and the engines under CockroachDB and TiKV.
The write-ahead log
Both families share one rule: every change is first written down in an append-only log, and that log record must reach disk before the changed data does. A transaction counts as committed once its log records are on stable storage. That’s the write-ahead log (WAL). If the machine dies mid-change, the log is the record of truth, and recovery replays it.
Durability, then speed
The WAL turns many scattered random writes into one sequential append per transaction, and lets the database keep its real data structures in memory, flushing them whenever it’s convenient. Two details make it work in practice:
- fsync is the commit point. A
write()only reaches the operating system’s page cache. Untilfsyncreturns, a power cut can still lose it. Because fsync waits for the device, it’s the slowest step in a commit, so databases use group commit: many concurrent transactions share one fsync. - Pages can tear. A database page (8 KB in Postgres, 16 KB in InnoDB) is bigger than the unit a disk writes
atomically, so a crash can leave half an old page and half a new one. Postgres guards against this by logging
a full image of each page the first time it changes after a checkpoint (
full_page_writes); InnoDB writes pages to a doublewrite buffer first.
LSM-trees
The log-structured merge-tree was described by Patrick O’Neil and colleagues in 1996, and Google’s Bigtable (2006) gave its parts the names everyone still uses. It never modifies a file once written. Writes go to two places:
- The WAL, in arrival order, for durability.
- The memtable, an in-memory sorted structure (RocksDB’s default is a skip list), which is where writes are actually read from until they reach disk.
When the memtable reaches its size limit (64 MB by default in RocksDB), it becomes immutable and is flushed to disk as an SSTable, a sorted string table: key-value pairs in key order, split into small blocks, with an index of where each block starts. Because the file is sorted, an in-memory index of one key per block is enough to find any key with a single block read. After the flush, the log records that covered that memtable are no longer needed; RocksDB deletes a WAL file once everything in it has been flushed.
Inside an LSM-tree
Three consequences fall out of “files are immutable”:
- Updates and deletes are just more writes. Overwriting
catleaves the old value in an older file; the newer file shadows it. A delete writes a tombstone, a marker that says “this key is gone”, which also shadows older values until compaction removes both. - Reads check newest to oldest: memtable, then each file in turn, stopping at the first hit. A read for a key that lives in an old file, or doesn’t exist at all, may have to look in many places. That’s read amplification.
- Writes are always sequential. Flushes and merges write big sorted files from start to finish, which is what lets an LSM-tree absorb very high write rates.
Compaction
Left alone, files pile up, reads get slower and dead values waste disk. Compaction is the background process that merge-sorts several SSTables into new ones, keeping only the newest version of each key and dropping tombstones once nothing older could still hold the key. Merging sorted files is cheap and sequential, like the merge step of merge sort. The interesting question is which files to merge, and when. Two strategies dominate.
Leveled compaction (RocksDB’s default; LevelDB’s only mode) arranges files in levels. L0 holds fresh flushes, which may overlap. Every level below is a single sorted run of non-overlapping files, each level about 10× larger than the one above. When a level grows past its target, one of its files is merged into the overlapping files of the next level down. A read checks at most one file per level below L0, and with dynamic level sizing (RocksDB’s default since version 8.4) about 90% of the data sits in the last level, so space overhead is small. The price is that each byte gets rewritten once per level it passes through.
Size-tiered compaction (Cassandra’s default; RocksDB calls its variant universal) waits until there are several files of similar size and merges them into one bigger file. Each byte is rewritten far fewer times, so writes are cheaper. But a key can now live in many overlapping files, so reads check more of them, and a big merge needs room for the inputs and the output at once, so RocksDB’s docs warn it can temporarily double the space used.Cassandra 5.0 added a Unified Compaction Strategy, now the one its docs recommend, that can behave like either, tuned per table, rather than forcing an up-front choice.
| Leveled | Size-tiered / universal | |
|---|---|---|
| Write amplification | high (often over 10×) | low |
| Read amplification | low: about one file per level | higher: many overlapping files |
| Space amplification | low (≈ 10–14% extra) | high, up to 2× during big merges |
| Good for | read-heavy, space-constrained | write-heavy, append-mostly, time-series |
Bloom filters
A read for a key that’s absent, or old, would touch every file on its way down. LSM engines avoid most of that with a Bloom filter per SSTable: a compact, in-memory summary that answers “is this key in the file?” with either definitely not or maybe.
How a Bloom filter answers
It’s a bit array of m bits and k hash functions. Adding a key sets the k bits it hashes to. Checking a key looks at the same k bits: if any is 0, the key was never added. If all are 1, it probably was, but other keys may have set those bits: a false positive. There are no false negatives. With n keys, the false-positive rate is about (1 − e−kn/m)k, minimised at k ≈ 0.69 · m/n.
Skipping files
Filters only help point lookups. A range scan has no single key to hash, so it still has to visit every file whose key range overlaps; RocksDB’s prefix Bloom filters exist to win some of that back when queries share a known key prefix.
B-trees
The B-tree is older than most programmers: Rudolf Bayer and Edward McCreight described it in 1970, and by the end of that decade it was already the standard database index. It’s still the default almost everywhere.
A B-tree breaks the data into fixed-size pages and arranges them as a tree. Interior pages hold separator keys and pointers to children; leaf pages hold the entries themselves (most databases use the B+tree variant, where only leaves hold data and leaves link to their neighbours for fast range scans). A lookup starts at the root and follows one pointer per level down to the right leaf.
What keeps the tree shallow is fanout. A page holds hundreds of keys, so each level multiplies the reach by hundreds. Ben Dicken’s estimate for a 16 KB page (InnoDB’s default) holding 8-byte keys, values and child pointers is about 682 entries per page, which puts roughly 317 million rows within three levels. Add a fourth and you’re into the hundreds of billions. The top levels are tiny and stay cached, so a lookup costs about one disk read.
Lookup and split
Writes are where the B-tree earns its complexity. A new key goes into the leaf that covers it. If that page is full, it splits into two half-full pages, and a new separator is inserted into the parent, which may split in turn. If the root splits, the tree gains a level at the top, so every leaf is always at the same depth.
A split rewrites several pages as one logical change, and a crash between them would corrupt the tree. That’s why B-trees lean on the WAL so heavily: the split is logged first, so recovery can finish or undo it. It’s also why concurrent B-trees need careful latching on pages: two writers splitting neighbouring pages must not see each other’s half-finished work.Some engines avoid in-place overwrites entirely. LMDB uses a copy-on-write B-tree: a write copies the changed pages and the path above them, then atomically switches to a new root, which also gives readers consistent snapshots for free.
Write amplification
Write amplification is the ratio of bytes the engine writes to disk to bytes you asked it to write. It’s the number that decides how much disk bandwidth your writes really cost, and how fast you wear out an SSD.
Both families amplify, for different reasons:
- A B-tree rewrites a whole page to change a few bytes in it, and writes the change to the WAL as well, plus a full page image the first time a page changes after each checkpoint. Small random updates spread across many pages are its worst case.
- An LSM-tree writes each byte to the WAL, then to L0, then again every time compaction pushes it down a level.
Where 33× comes from
For leveled compaction the arithmetic is simple: roughly one rewrite per level, times the size ratio between levels. RocksDB’s tuning guide works through exactly this example and lands at about 33×. Size-tiered compaction cuts this a lot, at the cost of read and space amplification. That three-way tension between write, read and space amplification is the core of LSM tuning: you can improve any two at the expense of the third.
B-trees vs LSM-trees
There’s no winner, only workloads.
| B-tree | LSM-tree | |
|---|---|---|
| Write path | find the page, overwrite it in place | append to memtable, flush and merge later |
| Write throughput | good; random page writes | very high; sequential writes |
| Point reads | one root-to-leaf path, predictable | memtable, every L0 file, then at most one file per lower level; Bloom filters help |
| Range scans | excellent: leaves are sorted and linked | good, but must merge several sorted files |
| Space | pages are often partly empty after splits | compact once compacted; tombstones linger until then |
| Latency | steady | background compaction can cause spikes and stalls |
| Each key lives… | in exactly one place, handy for locking | in several files until compaction catches up |
Rules of thumb that hold up:
- Write-heavy, append-mostly or huge data sets (event logs, time series, message stores, metrics) favour LSM-trees.
- Read-heavy OLTP with in-place updates and range scans favours B-trees, which also give the most predictable latency.
- Measure in steady state. An LSM benchmark run before compaction has caught up flatters it badly.
In the real world
RocksDB is the reference LSM engine. Facebook forked it from Google’s LevelDB, and today it’s embedded almost everywhere: Kafka Streams state stores, Apache Flink’s large-state backend, TiKV, and many more. Its defaults tell you what it’s tuned for: leveled compaction, 64 MB memtables, 4 KB blocks, and the advice to use ~10-bit Bloom filters per key.
- Facebook’s user database (UDB), which stores the social graph, was space-bound on flash even with InnoDB compression. Its team built MyRocks, MySQL on top of RocksDB, and finished migrating UDB in August 2017. It cut storage usage in half. Part of the win is structural: B-tree pages are left partly empty by splits, while LSM files are written densely and compressed block by block.
- Instagram found that much of its Cassandra tail latency came from JVM garbage-collection pauses in the storage engine itself. Its 2018 Rocksandra project replaced that engine with RocksDB; on one production cluster P99 reads fell from 60 ms to 20 ms and GC stalls from 2.5% to 0.3% of the time.
- CockroachDB ran on RocksDB from its first release until Pebble, a RocksDB-inspired LSM engine written in Go, became its default storage engine in v20.2 (November 2020).
- Postgres stays firmly in the B-tree camp, with 8 KB pages, a WAL with full-page images, and a separate heap for table rows (more on that in the next lesson). Postgres 18 (September 2025) added an asynchronous I/O subsystem with up to 3× faster reads from storage in benchmarks.
- Filters keep improving. RocksDB added the Ribbon filter (experimental in 6.15 in 2020, production-ready in 6.22), which matches a Bloom filter’s 1% false-positive rate in about 7 bits per key instead of 10, trading construction CPU for roughly 30% less memory.
Pitfalls
- Trusting that
write()means durable. Only a successful fsync (orO_DSYNC) does, and even then every layer below, down to the drive’s own write cache, must honour the flush. And a failed fsync must be treated as fatal, not retried. - Compaction debt. If writes outpace compaction, L0 fills up and reads slow down; RocksDB then stalls writes on purpose until compaction catches up. Watch pending-compaction bytes, not just disk usage.
- Tombstone trouble. In an LSM, deleting a million rows adds a million records. Scans over deleted ranges
wade through tombstones, and in a replicated store like Cassandra, if a replica that missed the delete isn’t repaired within
gc_grace_seconds(10 days by default), the tombstone can be purged and that replica brings the row back to life. - Random keys in a B-tree. UUIDv4 primary keys scatter inserts across every leaf, causing more page splits, more cache misses and half-empty pages. Time-ordered keys like UUIDv7 append at the right edge instead.
- Expecting Bloom filters to speed up range scans. They only answer “is this exact key here?”
- Benchmarking a fresh LSM. Its first hour, before compaction reaches steady state, is not the workload you will run in production.
Recall
Go deeper
- O’Neil, Cheng, Gawlick & O’Neil, “The Log-Structured Merge-Tree” (1996): the original LSM paper, with the cost model that explains why merging beats updating in place.
- Chang et al., “Bigtable: A Distributed Storage System for Structured Data” (OSDI 2006): where memtables, SSTables and compactions got their names, with a Bloom filter per SSTable.
- RocksDB wiki: Leveled Compaction and Tuning Guide: the clearest practical treatment of write, read and space amplification.
- RocksDB wiki: Bloom Filter: bits-per-key tables, prefix filters and the Ribbon filter.
- Ben Dicken, “B-trees and database indexes” (PlanetScale, 2024): interactive B+trees, and why sequential keys beat random ones.
- Matsunobu, Dong & Lee, “MyRocks: LSM-Tree Database Storage Engine Serving Facebook’s Social Graph” (VLDB 2020): what it takes to move a giant B-tree workload onto an LSM.
- PostgreSQL wiki: Fsync Errors: how a durability assumption failed across kernels, and what Postgres changed.
- Sam Rose, “Bloom Filters” (samwho.dev): a playable explanation of false-positive rates.
Keep going
The atomic notes for this lesson live in the knowledge graph:
Next on the map: Indexes & Search (secondary, clustered, inverted and vector indexes) and Analytics & Columnar Storage (laying data out by column instead of by row).