Lesson 09 · Storage engines · Module 1
Writing Fast and Reading Slow
A B-tree pays for its fast reads on every write, and the bill is a random write to a page somewhere in a file the size of your data. Rewrite that bargain the other way round — never update anything in place, always append — and you get the LSM-tree. Which does not make the work disappear. It moves the work to a background thread, and the name of that thread is compaction.
The win in this lesson: you will be able to say why an LSM-tree makes writes cheap, exactly what it defers, and what compaction is paying off — and to argue the choice against Lesson 08's B-tree rather than reciting that one is "for writes".
1. The problem the B-tree hands you
Lesson 08 ended on the bill. An insert into a B-tree-indexed table is a write to the table, plus a write to every index, plus — when the leaf will not fit the new entry — a page split that rewrites two pages and inserts a downlink into the parent, cascading upwards. Every one of those writes lands at whatever offset the key happens to sort to. A thousand inserts with scattered keys are a thousand scattered writes.
That is fine when reads dominate. It stops being fine when the workload is a firehose of writes — metrics, events, message history, a write-ahead stream of user actions — and it was exactly the workload RocksDB was built for. RocksDB is the storage engine underneath a long list of write-heavy systems; it began as a fork of LevelDB, and Cassandra, HBase and ScyllaDB all use the same family of structure.
"The primary design point for RocksDB is that it should be performant for fast storage and for server workloads. It should support efficient point lookups as well as range scans. It should be configurable to support high random-read workloads, high update workloads or a combination of both."
RocksDB wiki, RocksDB Overview · Assumptions and Goals · Performance
2. The shape chosen: never write over anything
The whole structure follows from one refusal. A B-tree finds the page a key belongs to and modifies it. An LSM-tree never does. A write goes into memory and into a sequentially-appended log, and that is the entire write path the caller waits for:
"The three basic constructs of RocksDB are memtable, sstfile and logfile. The memtable is an in-memory data structure - new writes are inserted into the memtable and are optionally written to the logfile (aka. Write Ahead Log(WAL)). The logfile is a sequentially-written file on storage. When the memtable fills up, it is flushed to a sstfile on storage and the corresponding logfile can be safely deleted. The data in an sstfile is sorted to facilitate easy lookup of keys."
RocksDB Overview, §3 High Level Architecture
Read that against the B-tree. There is no search for the right page, because there is no right page. There is no split, because nothing is full except memory, and when memory is full the answer is to write a new file rather than to rearrange an old one. The only disk write on the critical path is an append to the end of a log — one sequential write, at a location the disk head or the flash translation layer is already sitting on.
The sorting still happens; it just happens in RAM. The default memtable is a skiplist, "a sorted set, which is a necessary construct when the workload interleaves writes with range-scans". So the file that eventually lands on disk is sorted — but it was sorted for free, in memory, in a structure that never touched storage while it was being built.
3. What that defers: the read gets harder
Nothing was free. The cost moved. A B-tree has exactly one place a key can be. An LSM-tree has many, because every flush produces another sorted file, and the newest version of a key is in the newest file that contains it. A read must ask them in order, newest first, until it finds an answer.
"Most LSM-tree engines cannot support an efficient range scan API because it needs to look into multiple data files."
RocksDB Overview, §4 Features · Prefix Iterators
Left alone, this degrades without limit: a million flushes means a million files to consult for a key that does not exist. So the files cannot be left alone. Something has to merge them, and that something is compaction — which is the actual subject of this lesson, because everything difficult about operating an LSM-tree is a fact about compaction.
"In the presence of ongoing writes, compactions are needed for space efficiency, read (query) efficiency, and timely data deletion. Compaction removes key-value bindings that have been deleted or overwritten, and re-organizes data for query efficiency."
RocksDB Overview, §4 Features · Multi-Threaded Compactions
Three jobs in one sentence, and they are worth separating, because they are the three things the fast write deferred:
| What compaction does | Which deferred bill it settles |
|---|---|
| Merges overlapping sorted files into fewer | Read amplification — how many files a lookup must consult |
| Drops overwritten values and deleted keys | Space amplification — bytes on disk per byte of live data |
| Applies TTLs and compaction filters | Timely deletion — data you told it to forget is still there until a merge rewrites past it |
An LSM-tree does not make writing cheaper. It makes the foreground write cheap by promising to do the real work later, in bulk, sequentially, on a background thread. Compaction is that promise being kept. If the background cannot keep up with the foreground, the promise is broken, and the system stops accepting writes — which is section 6.
4. The alternatives, and what each one costs
"Merge the files" is not one algorithm. It is a dial, and where you set it decides which of the three amplifications you are willing to pay. RocksDB ships several settings of the dial and is blunt about the trade:
"Classic Leveled compaction, introduced by LSM-tree paper by O'Neil et al, minimizes space amplification at the cost of read and write amplification."
"Tiered compaction minimizes write amplification at the cost of read and space amplification."
RocksDB wiki, Compaction · Overview of Compaction algorithms
Those two sentences are the same sentence twice, with the terms permuted. There is no setting that minimises all three; you choose which two to spend. RocksDB restates it in product terms, where "Universal" is its name for tiered:
"Level Style Compaction (default) typically optimizes disk footprint vs. logical database size (space amplification) by minimizing the files involved in each compaction step: merging one file in Ln with all its overlapping files in Ln+1 and replacing them with new files in Ln+1."
"Universal Style Compaction typically optimizes total bytes written to disk vs. logical database size (write amplification) by merging potentially many files and levels at once, requiring more temporary space. Universal typically results in lower write-amplification but higher space- and read-amplification than Level Style Compaction."
RocksDB Overview, §4 Features · Compaction Styles
The mechanism behind the difference is one line in the taxonomy. In tiered compaction, merging into a level does not rewrite what is already there — "The per-level write amplification is 1 which is much less than for leveled where it was fanout." You write each byte into each level once. The price is that a level now holds several sorted runs instead of one, so a read must check all of them, and an old copy of a key survives in every run that ever held it.
| Write amp | Read amp | Space amp | Chosen when | |
|---|---|---|---|---|
| B-tree (Lesson 08) | Random writes, splits cascade | Lowest — one place per key | Low, minus fragmentation | Read-dominated, range scans, transactional |
| Levelled LSM | High — "often larger than 10" | Moderate — one file per level | Lowest of the LSM options | Write-heavy but disk-constrained; RocksDB's default |
| Tiered / Universal LSM | Lowest — ~1 per level | Highest — many runs per level | High; needs temporary space | Ingest-dominated, disk is cheap |
| FIFO | Effectively none | All files in L0 | Bounded by a size cap | "cache-like data" you are happy to drop |
FIFO is worth noticing precisely because it is degenerate: "In FIFO compaction, all files are in level 0. When total size of the data exceeds configured size… we delete the oldest table file." That is what the structure looks like when you decline to pay any of the three — you keep the cheap write and throw the data away instead.
5. The mechanism: levelled compaction
Take RocksDB's default and follow a byte through it. Files live in numbered levels, and the levels are not equals:
"Files on disk are organized in multiple levels. We call them level-1, level-2, etc, or L1, L2, etc, for short. A special level-0 (or L0 for short) contains files just flushed from in-memory write buffer (memtable). Each level (except level 0) is one data sorted run"
RocksDB wiki, Leveled Compaction · Structure of the files
Why a level is a sorted run, and what that buys the reader
"The level is a sorted run because keys in each SST file are sorted… To identify a position for a key, we first binary search the start/end key of all files to identify which file possibly contains the key, and then binary search inside the file to locate the exact position. In all, it is a full binary search across all the keys in the level."
Leveled Compaction, Structure of the files
That is the read amplification being held down. Below L0, a level is exactly as searchable as one enormous sorted file: no key appears twice in it, so one file per level is the most a lookup can be asked to open. L0 is the exception — its files came straight from separate memtables, so their key ranges overlap and all of them must be checked, which is why the number of L0 files is the single knob that most visibly moves read latency.
What triggers a merge
"All non-0 levels have target sizes. Compaction's goal will be to restrict data size of those levels to be under the target. The size targets are usually exponentially increasing"
"Compaction triggers when number of L0 files reaches
Leveled Compaction, Structure of the files · Compactionslevel0_file_num_compaction_trigger, files of L0 will be merged into L1. Normally we have to pick up all the L0 files because they usually are overlapping"
Then it cascades, and the cascade is the mirror image of Lesson 08's page split. A split propagates upward — a full leaf pushes a downlink into its parent, which may push into its parent, all the way to the root, and it happens synchronously inside your insert. An LSM cascade propagates downward — L1 exceeding its target pushes a file into L2, which may push into L3 — and it happens on a background thread, after your write already returned. Same cascade, opposite direction, different thread. That single contrast is most of what separates the two structures.
The choice of how much to merge at once is where levelled buys back its read and space amplification:
"Compaction in the original LSM paper was all-to-all -- all data from Ln-1 is merged with all data from Ln. It is some-to-some for LevelDB and RocksDB -- some data from Ln-1 is merged with some (the overlapping) data in Ln."
Compaction, Overview of Compaction algorithms · Classic Leveled
Some-to-some is why a 300 GB database does not have to rewrite 300 GB to absorb a few megabytes. Pick one file from L1, find the slice of L2 whose key ranges it overlaps, merge just those, write the result back into L2. The write amplification you pay is the fanout, per level — not the size of the level.
6. Residual risk: compaction debt and the write stall
Now the failure mode, which is the part you actually get paged for. Compaction is the promise to do the work later. Your write rate decides how fast the debt accrues; your disk and CPU decide how fast it can be paid. When the second is slower than the first, the debt does not stabilise — it grows.
"The overall write throughput of an LSM database directly depends on the speed at which compactions can occur, especially when the data is stored in fast storage like SSD or RAM."
RocksDB Overview, §4 Features · Multi-Threaded Compactions
Read that as an operational claim, not an implementation note. Your sustained write ceiling is not the speed of an append. It is the speed of compaction. The append is what you measure in a benchmark that runs for thirty seconds; compaction is what you measure in production at 3 a.m. on day forty.
"If all background compaction threads are busy doing long-running compactions, then a sudden burst of writes can fill up the memtable(s) quickly, thus stalling new writes."
RocksDB Overview, §4 Features · Avoiding Stalls
That is the mechanism of a write stall in one line. Memtables fill; the flush queue is behind the compaction queue; there is nowhere to put the next write; the engine applies back-pressure and your p99 goes vertical. Note the shape of the failure — it is not gradual degradation, it is a cliff, and the cliff arrives after a period in which everything looked fine because the debt was still being absorbed.
The wiki does not oversell the fix:
"Note that leveled compaction still cannot efficiently handle write rate that is too much higher than capacity based on the configuration. Works on going to further improve it."
Leveled Compaction, More Adaptive Compaction To Write Traffic
Two more residual risks worth naming, because they surprise people who only learned the happy path:
- A delete is a write. Deleting a key appends a tombstone; the old value is still on disk,
in every older file that holds it, until a compaction merges past it. Space does not come back at
DELETEtime — it comes back at compaction time, possibly much later. RocksDB added attloption precisely because a cold key range "could exist in the LSM tree without going through the compaction process for a really long time", leaving "wasted space". - Compaction competes with your reads. It is a large sequential rewrite running against the same disk and the same page cache your queries use. This is why RocksDB has rate limiters and reserved flush threads at all — the background work has to be deliberately starved so the foreground survives.
Not "B-trees are for reads, LSM-trees are for writes". Say instead: a B-tree pays its cost synchronously and predictably, in random I/O, at write time; an LSM-tree pays a larger total cost asynchronously, in sequential I/O, on a background thread — and converts a throughput problem into a latency cliff if that thread cannot keep up. The follow-up question is then the right one: what is our sustained write rate, and what is compaction's capacity at that rate?
7. Check yourself
8. Back to your world
Most systems at your scale run Postgres, which is a B-tree engine, and the honest answer is that you should not swap it for an LSM-tree. But the shape shows up anyway, and recognising it is the point:
- You already run one. Postgres' own WAL is the append-then-reorganise trick, and
VACUUMis its compaction — background work that reclaims space from rows made dead by updates and deletes, competing with your queries for the same disk. Lesson 07's hard stop on transaction-id wraparound is a compaction-debt failure wearing a different hat. - The diagnostic question is the same in both worlds. Not "is it slow" but "is the background reclaimer keeping up with the foreground writer, and what happens on the day it does not". Write a monitor for the gap, not for the symptom.
- Where an LSM does belong is the shape of table that is append-mostly and read by recent range: events, metrics, audit logs, message history. If one table in your system is that and the rest are not, the answer is usually to move that table somewhere else, not to move the database.