Sven Erik Matzen

Software Architect | Cloud & Security Expert | AI-enabled Solutions

Write First, Sort Later – Log-Structured Merge-Trees and the Inversion of the Database

🎧 Listen to this article

Software Architecture · 2026-07-22

EU label: fully AI-generated content Fully AI-generated article (no prior review).

The Hook

Picture a librarian who is handed a new book every second. He is supposed to shelve each one immediately, in correct alphabetical order. For the first book he walks to the shelf, pushes neighbors aside, makes room, slots it in. For the second, the same, but in a different aisle. For the third, somewhere else again. After ten minutes the librarian is out of breath and the stack of books on his counter is taller than before. He spends nearly all his time walking, not shelving.

Now a second librarian faces the same flood. He shelves not a single book right away. He simply drops each arriving book on top of a pile on his counter—arrival order, no sorting, no walking. When the pile reaches a certain height, he sorts it once, calmly, and slides it into the shelf as a single, already-sorted block. Every so often he takes several such blocks and merges them into one larger, still-sorted block. In the same span of time, this second librarian accepts many times as many books. The price: whoever looks for a particular book may have to check several sorted blocks, not just one place.

This difference is not an anecdote but the core of one of the most consequential design decisions in building databases. The first librarian is the classic B-tree, the indexing method that has dominated since the 1970s, writing every change straight to its final place. The second is the Log-Structured Merge-Tree, or LSM-tree—the storage architecture that today sits under Cassandra, RocksDB, LevelDB, HBase, ScyllaDB, and, by way of detours, under a large share of modern cloud databases.

This article explains why sequential writing is so much cheaper than random writing, what idea the LSM-tree makes of that fact, how its parts—memtable, SSTable, write-ahead log, Bloom filter, and compaction—work together, which three costs you are trading off against one another, and why there can be no universally best storage method. By the end, you should stop judging a database only by its query language and start asking how it writes.

The Core Problem: Why Random Writing Hurts

To understand why the LSM-tree exists, you have to glance briefly at the physics of storage media. Databases do not live in a vacuum; their designs are answers to the quirks of the hardware they run on.

On a classic magnetic hard disk (HDD), an access consists of two parts: the seek (moving the read/write heads to the correct track, then waiting for the right sector to rotate under the head) and the actual transfer of the data. Seeking is mechanical and takes milliseconds; transferring is fast. The decisive point: sequential writing—one large, contiguous block—costs one seek and then only transfer. Random writing—many small changes at scattered locations—pays the expensive seek again for every change. On rotating disks the difference quickly reaches two or three orders of magnitude.

Now the B-tree. A B-tree keeps its keys sorted in nodes scattered across the disk. Insert a new record and it must be written to exactly the place where it belongs—somewhere in the middle of the tree. At a high insert rate this means precisely the scattered, random writes the disk hates. Worse still: to persist a single changed row, an entire page (typically 4 to 16 KB) often has to be rewritten, even if the change touched only a few bytes. This mismatch between logical change and physically written bytes is called write amplification—a term we will meet several more times.

You might think SSDs solve the problem, since they have no moving parts. They soften it, but they do not abolish it. Flash memory cannot simply be overwritten; it must be erased in large blocks before it can be rewritten. Many small, scattered writes therefore lead to internal copying (the Flash Translation Layer shuffles valid data around to free up blocks)—write amplification again, this time hidden in the firmware—and, on top of that, wear, because flash cells survive only a limited number of erase cycles. So even on modern hardware: large, sequential writes are the friend, many small, random ones the foe.

The question that follows is easy to pose and hard to answer: Can you build a database that writes almost only sequentially—and can still search efficiently for individual keys?

The Idea: Write First, Sort Later

The conceptual root lies in a paper that at first had nothing to do with databases. In 1991, Mendel Rosenblum and John Ousterhout described, in The Design and Implementation of a Log-Structured File System (SOSP 1991), a file system that writes each change not to its assigned place but buffers it in memory and then streams all buffered changes together as a single, long sequential write—a "log"—to the disk. The idea: treat the medium as an endless running journal; you only ever append at the end.

Five years later, Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O'Neil carried this principle over to the problem of indexing. Their paper The Log-Structured Merge-Tree (LSM-Tree) appeared in 1996 in Acta Informatica (volume 33, issue 4, pp. 351–385). Their starting scenario was very concrete: files with a very high rate of insertions over a long time—history tables or transaction logs, say—where a conventional B-tree index chokes on the random writes. Their solution was a multi-level construct: a small, sorted component in memory (called C0 in the original paper) and one or more larger, sorted components on disk (C1, C2, …). New entries land first in C0; when it fills up, its contents are merged into C1 in a sequential pass—a process the authors called the rolling merge.

The core thought that emerges from all this fits in one sentence: replace many expensive, random writes with a few cheap, sequential ones—by gathering changes in memory, streaming them sorted to disk, and catching up on sorting the whole dataset later in orderly merges. The database is turned inside out, as it were: instead of sorting on write and profiting on read, it writes raw and reconciles the order in the background.

The Blueprint of a Modern LSM-Tree

The form built today into RocksDB, LevelDB, or Cassandra differs in detail from the original paper but follows the same spirit. Five parts form the scaffold.

The write-ahead log (WAL). Before anything else happens, every write operation is appended to the end of a log file on disk—purely sequential, and therefore cheap. This journal serves durability alone: if the process crashes before the data has reached anywhere else, the state can be reconstructed from the WAL. It is the same principle of the immutable event log that underlies Event Sourcing.

The memtable. At the same time, the entry is written into a sorted data structure in memory—the memtable, usually a skip list or a balanced tree. Because it lives in RAM, insertion and sorting are cheap here. All recent writes live first only here (and, for safety, in the WAL).

The SSTable. When the memtable reaches a threshold size, it is "frozen" and its sorted contents are written to disk in a single sequential sweep—as a Sorted String Table (SSTable): an immutable file containing key-value pairs in key order, usually accompanied by a small index over the key ranges it holds. "Immutable" is the decisive word: once written, an SSTable is never again modified in place. A fresh, empty memtable is then opened and the corresponding WAL segment may be discarded.

The levels and compaction. Over time this produces more and more SSTables. If they simply piled up, every search would have to comb through more and more files. That is why compaction runs in the background: a process takes several SSTables, merges their sorted contents into a new, larger, still-sorted SSTable, and throws the input files away. Because all inputs are sorted, this is a classic merge as in mergesort—sequential reading, sequential writing. Usually the SSTables are organized in levels, where each deeper level is larger than the one above it by a fixed factor.

The Bloom filter. To avoid having a search touch every SSTable, each SSTable carries a Bloom filter—a small, probabilistic data structure that answers the question "is key k possibly in this file?" very quickly and with little memory. A Bloom filter can be wrong, but only in one direction: it never falsely reports "not present" (no false negatives), though it does occasionally report "maybe present" falsely (a false positive). For the LSM-tree, precisely this asymmetry is worth gold: if the filter says "no," the whole file can be skipped without a disk access.

Reading, Deleting, Updating: The Other Side of the Coin

As elegant as the write path is, the cost migrates to the read path. A point lookup for a key proceeds like this: first the database checks the memtable. If it does not find the key there, it goes through the SSTables from newest to oldest—because a key can live in several SSTables with different versions, and the newest one wins. For each candidate SSTable it first consults the Bloom filter; only if that says "maybe" does it actually read into the file. The first hit (from new to old) is the valid answer.

Here the price of the method shows itself: while the B-tree resolves a point lookup in a fixed, small number of accesses (the tree height), the LSM-tree may have to consult several levels in the unfavorable case. This is called read amplification—one logical read triggers several physical ones. Bloom filters drive these costs down dramatically but do not eliminate them entirely.

Particularly instructive is the handling of deletion. Because SSTables are immutable, you cannot simply strike out a record—the file it sits in must not be touched. Instead, the LSM-tree writes a special marker entry, a tombstone: "key k is deleted from now on." On lookup the most recent entry wins; if you hit the tombstone first, the answer is "not present," even if deeper levels still hold the old value. Only in a later compaction, which gathers up both the tombstone and the old value, is the space actually reclaimed. Exactly the same logic applies to updating: an update is nothing but writing a new version of the same key; the old one lives on until compaction overwrites it. The LSM-tree fundamentally knows only one operation—appending—and deletion and update are special cases of it. Anyone who has read the vault article on Event Sourcing will recognize the same philosophy here: state is the result of a sequence of immutable events, not a value you overwrite.

These tombstones have an unpleasant side effect that regularly causes surprises in practice: if you delete very many records, the database first fills up with tombstones and thereby grows larger, not smaller, and range queries over deleted regions can become slower because they must work through masses of tombstones. I am of the opinion that this counterintuitive behavior—deletion at first costs space and read performance—is one of the most common stumbling blocks in the production operation of Cassandra and similar systems.

The Three Costs: Writing, Reading, Space

At this point it is worth naming the trade-off cleanly. Every storage engine juggles three kinds of amplification:

  • Write amplification: how many bytes are physically written per byte of logical payload? Every compaction rewrites data; a record that travels through several levels is copied multiple times.
  • Read amplification: how many physical accesses does a logical lookup cost? The more SSTables and levels, the more expensive in the unfavorable case.
  • Space amplification: how much more space does the database occupy than the raw payload would need? Old versions and tombstones not yet compacted away cost storage.

The catch is that you cannot minimize these three simultaneously. This is precisely what the choice of compaction strategy holds in its hands, and here two schools part ways.

Size-Tiered Compaction (STCS) waits until several SSTables of similar size have accumulated on a level, and then merges them at once into a larger one. This keeps write amplification low—each record is copied only about once per level—but pays for it with high read and space amplification: a key can lie in many equally sized SSTables, and during a merge the input and output files exist briefly at the same time, which can temporarily nearly double the space requirement. This strategy is the friend of write-heavy, space-tolerant workloads—the default, for instance, in Cassandra's classic operation.

Leveled Compaction (LCS) instead keeps each level as a set of non-overlapping SSTables, so that a key lies in at most one file per level. This strongly drives down read and space amplification: a point lookup has to check only one file per level, and there are hardly any superfluous copies. The price is a considerably higher write amplification, because slotting new data into a level forces the rewriting of overlapping files of the next level. As a rule of thumb, a factor of roughly 10 per level applies here; over a multi-level tree the write amplification easily sums up to ten to thirty times. LCS is the friend of read-heavy, space-sensitive workloads—the default, for instance, in RocksDB.

You can see: there is no "better," only a "different." Whoever lowers read and space costs pays on writing; whoever saves on writing pays on reading and on space. This symmetry is no accident of implementation but has a deeper, almost law-like reason.

The RUM Conjecture: Why There Is No Best Method

In 2016, Manos Athanassoulis, Stratos Idreos, and colleagues gave this observation a name and a form. In Designing Access Methods: The RUM Conjecture (EDBT 2016) they formulated it thus: every access method must trade off three quantities against one another—the cost of reading (Read), the cost of updating (Update), and the memory overhead (Memory). The conjecture holds that you cannot be optimal in all three at once: if you optimize two of these quantities sharply, the third inevitably worsens. You can imagine the design space as a triangle in which every real method occupies a point—and the three corners are unreachable ideals.

This lens orders the whole landscape. The B-tree sits near the read corner: it is optimized for fast point and range lookups and pays for it on updates (random writes, page rewriting). The LSM-tree sits near the update corner: it is optimized for cheap, sequential writing and pays for it on reads (several levels) and, depending on compaction, on space. Bloom filters, in turn, are a deliberate trade: they give up a little memory (M) to lower read costs (R)—a move toward one corner, paid for with another.

The RUM conjecture is deliberately a conjecture, not a proven theorem; it is a framework for thinking, not a formal impossibility proof like, say, the FLP result for distributed consensus. But as a compass it is extraordinarily useful. It explains why the database world is not converging on one winning architecture but diverging into a spectrum of specialized engines. And it supplies the right question to ask of every new storage engine: which corner of the triangle has this design moved toward, and what did it give up in the opposite corner to get there?

Where the Research Keeps Tuning

The LSM-tree is not a closed chapter but an active research field—and interestingly, it is almost always about placing the RUM compromise more cleverly rather than abolishing it.

A first approach optimizes the Bloom filters. In the naive implementation, every SSTable gets the same number of filter bits per element. Niv Dayan, Manos Athanassoulis, and Stratos Idreos showed with Monkey (SIGMOD 2017) that this is wasteful: because the total read cost is proportional to the sum of the false-positive rates across all levels, it pays to distribute the scarce memory unevenly—smaller, denser filters for the deeper, larger levels. At the same memory budget, read costs drop noticeably, purely through a smarter allocation of the same bits.

A second approach files at the compaction logic itself. With Dostoevsky (SIGMOD 2018) the same authors identified superfluous merge work and proposed a "lazy leveling" that keeps leveling-style behavior for the largest level but a tiering-style one for the smaller levels—a hybrid method that deliberately hits better points in the design space than pure tiering or pure leveling can reach.

A third, very effective approach attacks write amplification at the root. WiscKey (FAST 2016) rests on the observation that only the keys are needed for sorting, not the often much larger values. So WiscKey separates the two: keys stay in the LSM-tree, the values move into a separate, sequential value log. Because compaction now copies only keys and metadata and no longer the large values, write amplification for large values drops drastically—in the paper, by up to two orders of magnitude. The price is additional complexity in the garbage collection of the value log; here too the RUM logic applies.

This line—Monkey, Dostoevsky, and relatives from Idreos's Harvard group—pursues a larger goal: to make the LSM design space navigable, that is, to turn a fixed architecture into a continuous surface of configurations from which, for a given workload, one can automatically choose the optimal point. I am of the opinion that precisely here lies the real future: not in yet another "best" engine, but in systems that adjust their own position in the RUM triangle to the observed load.

Who Uses the LSM-Tree—and Why

The reach of this method is easy to underestimate, because it usually sits invisibly in the lowest layer. Google's BigTable (2006) made the approach popular for distributed systems. From the same school of thought comes LevelDB by Sanjay Ghemawat and Jeff Dean, a compact embedded library that became the blueprint for much that followed. Facebook (Meta) forked LevelDB into RocksDB, which today serves as the storage engine in an astonishing range of systems. Apache Cassandra and HBase, the great column-oriented stores, rest on the LSM principle just as much as ScyllaDB, tuned for Cassandra compatibility. Time-series databases such as InfluxDB and distributed SQL systems such as CockroachDB or TiKV rely on LSM-based engines (RocksDB or its successors), because their workload—high, continuous write rates—hits exactly the method's strength.

The pattern is everywhere the same: as soon as an application writes more than it reads pointwise, as soon as data streams rather than being queried individually—sensor measurements, logs, metrics, chat messages, event streams—the LSM-tree is the natural choice. Conversely, the B-tree remains superior where reads dominate, where individual rows are frequently updated in place, and where low, predictable read latency matters more than maximum write throughput—which is why classic relational systems such as PostgreSQL, MySQL/InnoDB, or Oracle continue to build on B-trees. Both live side by side, not because one world is backward, but because they are at home in different corners of the RUM triangle.

The Central Takeaway

The real lesson of the LSM-tree reaches beyond databases. It is this: you can turn an expensive, immediately-due piece of work into a cheap, deferred one—if you are willing to catch up on the deferred work later, in bundled form and in a shape favorable to the medium. The LSM-tree does not sort on write but on merge; it does not delete immediately but marks; it does not tidy up constantly but in large, rare passes. Each time, an immediate, fine-grained, expensive operation is replaced by a later, coarse-grained, cheap one.

In practice this means: the next time you face a system component suffering under a flood of small, expensive changes—a search index, a cache, an audit trail, an analytics pipeline—ask yourself whether you can follow the LSM pattern: append changes at first, gather them in a cheap buffer, and defer the expensive ordering work in bundled form to the background. And when you choose a database, stop looking only at the query language and the feature list. Ask instead: how does this system write, how does it read, how much space does it waste in the process—and which corner of the RUM triangle does that put it in relative to my workload? This one question often says more about a system's suitability than any datasheet.

Reflection Question

Where in your own systems are you paying the price of the first librarian today—many small, expensive "straight-to-the-right-place" operations—even though the workload would actually tolerate an "append first, bundle later"; and where, conversely, would the deferred cleanup burden of an LSM-style approach be more dangerous than the problem it solves?

Cross-References in the Vault

Sources

← All articles