Papers
The Log-Structured Merge-Tree (LSM-Tree)
Patrick O'Neil, Edward Cheng, Dieter Gawlick, Elizabeth O'Neil · Acta Informatica 33(4), 1996, 1996
The problem: indexing a table with constant inserts is expensive in disk I/O
The paper's starting point is high-performance transactional systems that insert records all the time into files that grow over long periods. The authors' example is a history table, which records account activity and is indexed by account. Traditional on-disk index structures, such as the B-tree, require several disk interactions for each insertion, because each new record may land on a different index page, and this causes a lot of disk arm movement. The abstract states that, in this scenario, maintaining a B-tree index in real time can roughly double the I/O cost of each transaction, which would raise the system's total cost by up to fifty percent. The question that motivates the work is therefore how to offer a low-cost index for files with a very high rate of insertions and deletions, without paying a random disk access per operation. The paper also makes the scope clear: the structure makes sense when the write rate is high relative to the read rate, but queries are still frequent enough that scanning the whole table is infeasible and an index is needed.
The core idea: components C0 and C1 and the rolling merge
The LSM-tree splits the index into two or more components, with two being the basic case. Component C0 is small, lives entirely in memory, and can use any tree structure, since inserting into it generates no disk I/O. Component C1 lives on disk and has a shape similar to a B-tree, but optimized for sequential access: the nodes are fully packed and neighboring nodes are stored in contiguous multi-page blocks. New entries always go to C0 first. When C0 approaches a size limit, a background process, the rolling merge, takes a contiguous range of entries out of C0 and merges it into C1, working one block at a time: it reads a multi-page block, merges the entries into the leaves, and writes the resulting nodes to new locations on disk. The effect is to trade many small random writes for a few large sequential writes, in the spirit of a merge sort. Meanwhile, the index values remain queryable, since each entry is in C0 or in C1, except for very short locking periods. A search looks first in C0 and then in C1.
More components, deletions, and recovery
The paper generalizes the two-component design to a series C0, C1, ..., CK, of increasing sizes: C0 in memory and the others on disk. Between each adjacent pair there is an asynchronous rolling merge, triggered when the smaller component exceeds its threshold. The cost analysis, which uses the Five-Minute Rule to identify the points where the dominant cost factor changes, concludes that the total I/O rate of the merges is minimal (for a fixed C0) when the sizes form a geometric progression, with a fixed ratio r between neighboring components. The total cost depends on r, the size of C0, and the number of components. More components reduce the write cost but increase the CPU cost of the merges, the memory for merge buffers, and the number of places a search must look. A deletion of an entry that is already on disk is recorded as a deletion entry in C0, which removes the corresponding entry from C1 during a merge; the cost is an extra filter on searches. For crash recovery, whatever was only in C0 must be rebuilt, and since merged blocks are written to new locations, the old blocks remain available for recovery. The full concurrency and recovery details of the paper were not verified in this write-up.
The trade-off: cheap writes, costlier reads
The LSM-tree's central guarantee is a large reduction in disk arm movement compared to B-trees, which matters when that movement dominates the storage cost. The price shows up on reads. A lookup has to consult more than one component and filter the results, for example discarding entries that a delete entry invalidates. Because of this, lookup performance is similar to that of a B-tree, but with some overhead, and the LSM-tree brings no advantage when lookups are very frequent. The best use case is workloads with many inserts and little later reading, such as log records or activity histories, where the data is usually time series, although that is not a requirement. The design decision is also economic: memory is expensive per unit, which limits the size of C0, and the paper sizes the system by comparing the cost of storage with the cost of I/O capacity. In short, the LSM-tree shifts work from the write path to background merges and to the read path.
Legacy: the foundation of modern write-intensive storage
The idea of absorbing writes in memory and merging them in batches into sorted structures on disk became the basis of many current storage engines. Secondary technical sources consulted state that Bigtable, LevelDB, RocksDB, Cassandra, and HBase use LSM-trees, generally with the same shape of write path: the write is first recorded in a write-ahead log for durability, enters a sorted in-memory buffer (memtable), and when that fills up it is written to disk as an immutable sorted file (SSTable). In the background, compaction merges these files and discards overwritten or deleted keys. Reads check the memtable and then the files, from newest to oldest, and Bloom filters help skip files that cannot contain the key. These terms and optimizations come from later systems, not from the 1996 paper, which talks about C0, C1, and rolling merge. The variants diverge mainly in compaction strategy: LevelDB and RocksDB use leveled compaction, and HBase uses the strategy of grouping files by size. The general trade-off holds: high write throughput in exchange for reads that may touch several files and extra compaction I/O.
See the ideas at work
Practice the designs that use this paper in the System Design school.