The LSM-Tree

The Log-Structured Merge-Tree (LSM-Tree) is a data structure designed to provide highly efficient write operations by batching modifications in memory and writing them sequentially to disk. Unlike traditional indexing structures that perform in-place updates, the LSM-Tree treats all modifications, including insertions, updates, and deletions, as append-only operations. This design aligns with the physical characteristics of modern storage hardware, transforming slow random disk writes into fast sequential disk writes.

Today, the LSM-Tree forms the foundational storage engine for many widely used distributed databases, key-value stores, and time-series databases. By deferring the cost of organizing data to background processes, it achieves write throughput that significantly exceeds that of traditional B-trees. However, this write optimization introduces complexities in the read path and requires continuous background maintenance, creating a strict theoretical tradeoff between read performance, write performance, and memory consumption.

The architecture relies on a combination of mutable in-memory buffers and immutable on-disk files. As data flows into the system, it is temporarily held in memory until a capacity threshold is reached, at which point it is flushed to persistent storage as a sorted run. Over time, background processes merge these sorted runs to reclaim space and maintain read efficiency. This continuous merging process gives the data structure its name.

The Problem of Write Amplification and Random I/O

To understand the specific problem the LSM-Tree solves, one must examine the physical limitations of storage hardware and the mechanics of traditional database indexes. For decades, the standard data structure for database storage engines was the B-tree, formalized in 1970 by Rudolf Bayer and Edward McCreight^[1], and its widely used variant, the B+ tree, detailed in 1979 by Douglas Comer^[2]. A B+ tree maintains data in a strictly sorted, hierarchical tree structure on disk, organized into fixed-size pages. When an application updates a record or inserts a new one, the database must locate the specific physical page on the disk containing that record, load it into memory, modify it, and write it back to the exact same location. This is known as an in-place update.

In-place updates generate random input and output (I/O) operations. On traditional hard disk drives (HDDs), random writes require the physical read and write head to move across the magnetic platter, incurring mechanical seek time and rotational latency. A random write on an HDD can be orders of magnitude slower than a sequential write, where the head simply lays down data continuously on a single track. Furthermore, when a B-tree page fills up, the database must allocate a new page, move half the records to the new page, and update the parent pointer. This operation, known as a page split, can cascade up the tree, generating multiple random writes and causing disk fragmentation over time.

Even on solid-state drives (SSDs), which lack moving parts, random writes remain problematic due to the underlying physics of NAND flash memory. Flash memory cannot overwrite data directly. It reads and writes data in small units called pages, but it can only erase data in much larger units called blocks. To update a single byte, the SSD controller must read the entire block into its internal memory, modify the specific page, erase the original block entirely, and then write the modified block back to the flash media. This physical constraint forces SSD controllers to perform continuous background garbage collection, moving valid pages of data to new blocks so old blocks can be erased.

When a database performs many small, random updates, it forces the storage hardware to rewrite entire blocks repeatedly. This phenomenon is known as write amplification, defined as the ratio of data written to the physical storage media compared to the logical data written by the application. High write amplification degrades performance, consumes internal bandwidth, and shortens the physical lifespan of the flash memory cells.

The LSM-Tree solves the random I/O bottleneck by abandoning in-place updates entirely. Instead of searching for the correct disk block to modify, an LSM-Tree accepts all writes into a fast in-memory buffer. When the buffer is full, the system writes the entire sorted batch to disk in one large, continuous, sequential operation. Sequential writes maximize the bandwidth of both HDDs and SSDs, bypassing mechanical seek times, avoiding B-tree page splits, and minimizing flash erase cycles.

Mechanism and Architecture

The LSM-Tree is not a single, rigid algorithm, but rather a conceptual framework consisting of several interacting components. A standard implementation relies on a MemTable, a Write-Ahead Log, Sorted String Tables, and a background compaction engine.

MemTable and Write-Ahead Log

When a write request arrives, the LSM-Tree first appends the operation to a Write-Ahead Log (WAL) on disk. The WAL is a simple, append-only file used exclusively for crash recovery. Because it only appends data, it requires minimal disk I/O. Modern implementations often use group commit techniques, batching multiple WAL appends together into a single disk synchronization call to maximize throughput. Once the WAL confirms the data is durable, the system inserts the key-value pair into the MemTable.

The MemTable is an in-memory data structure that keeps keys in sorted order. Implementations typically use a Skip List, a probabilistic data structure invented by William Pugh in 1990^[3], or a Red-Black Tree.^[29] Skip lists are particularly favored because they allow for efficient, lock-free concurrent access by multiple threads. Because the MemTable resides entirely in random access memory (RAM), write operations are extremely fast. The time complexity for an insertion is $O(\log M)$, where $M$ is the number of elements currently in the MemTable. From the perspective of the disk, the write is amortized to $O(1)$ because the actual disk write only happens later in large batches.

Sorted String Tables (SSTables)

When the MemTable reaches a predefined size limit, often ranging from a few megabytes to a few gigabytes, it becomes immutable. A new, empty MemTable is created to accept incoming writes. Meanwhile, a background thread flushes the immutable MemTable to disk as a Sorted String Table (SSTable).

An SSTable is a highly optimized, immutable file format that stores a sequence of key-value pairs sorted by key. Because the data is already sorted in the MemTable, the flush operation is a pure sequential disk write. Internally, an SSTable is typically divided into fixed-size data blocks, often 4 kilobytes or 16 kilobytes in size. At the end of the file, the SSTable stores an index block containing the starting key of each data block, along with a pointer to its byte offset. This block-based organization allows the database to compress individual blocks using algorithms like Snappy or LZ4, saving disk space without requiring the entire file to be decompressed during a read.

Once an SSTable is written to disk, it is never modified. If a user deletes a key, the system does not locate the key in the old SSTable to remove it. Instead, it inserts a special marker called a tombstone into the active MemTable. The tombstone acts as a logical delete, shadowing older values of the key during future read operations.

Compaction

Because data is continually flushed into new SSTables, the number of files on disk grows over time. A single logical key might exist in multiple SSTables, with the most recent file containing the current value and older files containing obsolete values. To prevent the disk from filling up with obsolete data, and to keep read performance from degrading, the LSM-Tree relies on a background process called compaction.

Compaction reads multiple existing SSTables, merges them together in sorted order, discards deleted or overwritten keys, and writes the result to a new, larger SSTable. The old SSTables are then deleted. This process is functionally identical to the merge phase of the merge-sort algorithm. There are several primary strategies for organizing compaction.^[30]

Size-Tiered Compaction waits until a certain number of similar-sized SSTables accumulate, then merges them into a single, larger SSTable. This approach prioritizes write throughput because it minimizes the number of times a record is rewritten. However, it results in high space amplification, requiring significant free disk space during a major merge, and high read amplification, as a read query might need to check multiple overlapping SSTables within the same tier.

Leveled Compaction organizes SSTables into hierarchical levels, typically labeled Level 0, Level 1, Level 2, and so on. Level 0 contains files flushed directly from the MemTable, which may have overlapping key ranges. From Level 1 downwards, the system enforces strict, non-overlapping key ranges within each level. Each level is typically ten times larger than the previous one. When a level fills up, one of its SSTables is selected and merged with all overlapping SSTables in the next level down. This reduces space amplification to a strict bound but increases write amplification, as a single piece of data might be merged multiple times as it cascades down the levels.

Universal Compaction is a hybrid approach that attempts to balance read and write amplification by dynamically switching between size-tiered and leveled behaviors based on current disk usage. Alternatively, FIFO Compaction is a specialized strategy for time-series data where the oldest SSTables are simply dropped when the database reaches a certain size limit, completely eliminating write amplification for workloads that only require recent data.

The Read Path and Bloom Filters

While the LSM-Tree offers exceptional write performance, its read path is inherently more complex than that of a B-tree. To find a specific key, the system must search through the components from newest to oldest.

function get(key):
    # 1. Check the active in-memory MemTable
    value = active_memtable.search(key)
    if value is not null:
        return value
        
    # 2. Check the immutable in-memory MemTable (currently flushing)
    value = immutable_memtable.search(key)
    if value is not null:
        return value
        
    # 3. Check on-disk SSTables from newest to oldest
    for level in range(0, max_levels):
        for sstable in get_sstables_for_level(level):
            # Use Bloom filter to avoid unnecessary disk reads
            if sstable.bloom_filter.might_contain(key):
                value = sstable.search(key)
                if value is not null:
                    # Return value unless it is a tombstone
                    return value if not is_tombstone(value) else null
                    
    return null

The worst-case time complexity for a read is $O(L \log N)$, where $L$ is the number of levels and $N$ is the total number of elements.^[31] Searching every file on disk would be prohibitively slow. To mitigate this, LSM-Trees employ Bloom filters, a space-efficient probabilistic data structure invented by Burton Howard Bloom in 1970^[4].

A Bloom filter is attached to each SSTable and kept in memory. Before performing a costly disk read, the system queries the Bloom filter. If the filter returns a definitive negative, the system skips the SSTable entirely. If it returns a possible positive, the system performs the disk read. While false positives occur, Bloom filters successfully eliminate the vast majority of unnecessary disk accesses.^[32] To further accelerate reads, implementations maintain in-memory block caches to hold frequently accessed uncompressed data blocks, and table caches to hold open file descriptors and index blocks.

Concurrency and Multi-Version Concurrency Control

The append-only nature of the LSM-Tree makes it highly suitable for Multi-Version Concurrency Control (MVCC), a method used by databases to provide concurrent access to data without locking. In an LSM-Tree, updates do not overwrite existing data. Instead, every write operation is tagged with a monotonically increasing sequence number.

When a transaction reads from the database, it is assigned a read sequence number. The read operation then ignores any key-value pairs with a sequence number higher than its assigned number. This guarantees that the transaction sees a consistent snapshot of the database at a specific point in time, entirely unaffected by concurrent writes. The older versions of the keys remain in the SSTables until they are no longer needed by any active transaction, at which point the background compaction process safely discards them.

Discovery and History

The theoretical foundation of the LSM-Tree was formalized in a 1996 paper titled "The Log-Structured Merge-Tree (LSM-Tree)," published in the journal Acta Informatica by Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O'Neil^[5].^[33] At the time of publication, O'Neil was a professor at the University of Massachusetts Boston, Cheng was at Digital Equipment Corporation, Gawlick was at Oracle, and Elizabeth O'Neil was at UMass Boston.

The authors developed the structure to address a specific bottleneck in high-performance transaction systems. Applications often needed to insert rows into a history table to provide an activity trace, while simultaneously generating log records for system recovery.^[34] Traditional B-trees could not sustain the required insertion rates because the random I/O saturated the disk controllers. O'Neil and his co-authors proposed a structure that deferred index changes, cascading them from a memory-based component through one or more disk components in a manner reminiscent of merge sort.

The LSM-Tree did not emerge in a vacuum. It drew heavy inspiration from prior art in file system design, specifically the Log-Structured File System (LFS) introduced by Mendel Rosenblum and John Ousterhout in 1992^[6]. LFS treated the entire disk as an append-only log, optimizing for write performance at the operating system level. The 1996 LSM-Tree paper adapted this append-only philosophy specifically for database indexing.

Despite its formalization in 1996, the LSM-Tree remained a niche academic concept for a decade. Its widespread adoption began in 2006 with the publication of the Bigtable paper by Fay Chang and other researchers at Google^[7]. Bigtable was a distributed storage system designed to manage petabytes of data across thousands of commodity servers. To handle the massive write volume of Google's web indexing pipeline, the engineers implemented a storage engine based on MemTables and SSTables. The success of Bigtable proved that the LSM-Tree architecture was highly scalable, sparking a renaissance in database design.

Key Refinements and Variants

As the LSM-Tree became the standard for modern storage engines, researchers and engineers identified specific inefficiencies and developed numerous variants to address them. A comprehensive survey of these techniques was published in the VLDB Journal in 2019 by Chen Luo and Michael J. Carey^[8].

bLSM and SILK

One of the primary drawbacks of the standard LSM-Tree is unpredictable latency. When background compaction processes consume too much disk bandwidth, foreground write operations stall, causing severe latency spikes. In 2012, Russell Sears and Raghu Ramakrishnan published bLSM at the ACM SIGMOD conference^[9], introducing a spring-and-gear compaction scheduler to bound worst-case write latency. Building on this problem, researchers from the University of Sydney and Nutanix introduced SILK in 2019 at the USENIX Annual Technical Conference^[10]. SILK implements an advanced I/O scheduler that preempts background compactions during heavy client load and opportunistically allocates bandwidth during idle periods, significantly reducing tail latency spikes.

WiscKey

In 2016, researchers at the University of Wisconsin-Madison (Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau) introduced WiscKey at the USENIX FAST conference^[11]. WiscKey addresses the high write amplification caused by leveled compaction. In a standard LSM-Tree, both the key and the value are moved during every compaction step. If values are large, moving them repeatedly wastes massive amounts of SSD bandwidth. WiscKey separates keys from values. The keys, along with pointers to the values, are stored in a standard LSM-Tree. The actual values are appended to a separate, unstructured file called a value log. This significantly reduces the size of the LSM-Tree, making compactions much faster and reducing write amplification, at the cost of requiring an extra disk seek to retrieve the value during a read.

Monkey and Dostoevsky

Another major area of refinement involves the mathematical optimization of Bloom filters and compaction policies. In 2017, researchers at Harvard University (Niv Dayan, Manos Athanassoulis, and Stratos Idreos) published Monkey at the ACM SIGMOD conference^[12]. Standard LSM-Trees allocate an equal number of bits per key to the Bloom filters at every level. Monkey proved this is mathematically suboptimal. Because the lowest levels contain exponentially more data, they generate the most false positives. Monkey allocates memory dynamically, assigning more bits-per-key to the lower levels and fewer to the upper levels, mathematically minimizing the overall false positive rate without using additional RAM.

The same research group followed up in 2018 with Dostoevsky, published in the ACM SIGMOD conference^[13]. Monkey was expanded in ACM TODS, not Dostoevsky^[14]. Dostoevsky introduced lazy leveling, a hybrid compaction strategy that removes superfluous merging operations, dynamically balancing the tradeoffs between read performance, write performance, and space amplification based on the specific workload.

PebblesDB and Fragmented LSM-Trees

In 2017, researchers at the University of Texas at Austin (Pandian Raju, Rohan Kadekodi, Vijay Chidambaram, and Ittai Abraham) introduced PebblesDB at the ACM SOSP conference^[15]. PebblesDB modifies the standard architecture into a Fragmented Log-Structured Merge-Tree. It uses guard pages inspired by skip lists to partition the key space at each level. Instead of rewriting data to enforce strict non-overlapping boundaries during compaction, PebblesDB simply appends new SSTables into the appropriate guarded fragments. This drastically reduces write amplification, though it slightly increases the time required for range queries.

Hardware Synergy and Zoned Namespaces

As storage hardware evolves, the relationship between the LSM-Tree and the physical storage medium continues to develop. A notable inefficiency in modern systems is the double garbage collection problem. The LSM-Tree performs compaction to manage obsolete data at the software level, while the SSD controller simultaneously performs garbage collection at the hardware level to manage flash erase blocks. This duplication wastes processing power and increases write amplification.

To resolve this, the storage industry developed Zoned Namespaces (ZNS), a new interface standard for NVMe SSDs. ZNS exposes the physical boundaries of the flash erase blocks to the host operating system, requiring the software to write sequentially into designated zones. Because the LSM-Tree is inherently append-only, it maps perfectly to the ZNS interface. By placing each SSTable into its own zone, the database can simply reset the entire zone when the SSTable is deleted by a compaction process. In 2021, researchers from Western Digital and Carnegie Mellon University published a study at the USENIX Annual Technical Conference^[16] demonstrating that running an LSM-Tree on a ZNS SSD eliminates hardware-level garbage collection entirely, resulting in higher throughput and significantly lower tail latency.

Real-World Applications

The theoretical advantages of the LSM-Tree have translated into massive commercial and open-source adoption. The architecture is central to the infrastructure of nearly every major technology company.

LevelDB: In 2011, Google engineers Jeff Dean and Sanjay Ghemawat extracted the single-node storage engine from Bigtable and open-sourced it as LevelDB. Written in C++, LevelDB provided a fast, embedded key-value store that implemented the classic MemTable and Leveled Compaction architecture. Google announced the release on their open-source blog^[17], and the codebase remains available on GitHub^[18].

RocksDB: In 2012, engineers at Facebook, led by Dhruba Borthakur, forked LevelDB to create RocksDB. While LevelDB was designed for general use, Facebook needed an engine optimized for multi-core servers and fast SSDs. They introduced highly configurable compaction styles, multithreaded background operations, and advanced metrics. Facebook detailed the creation of RocksDB in a 2013 engineering blog post^[19], and published a retrospective on its evolution at the USENIX FAST 2021 conference^[20]. Today, RocksDB is hosted on GitHub^[21] and serves as the underlying storage engine for countless other databases, including Apache Kafka Streams and MySQL.

Apache Cassandra: Developed initially at Facebook and open-sourced in 2008, Cassandra is a distributed NoSQL database designed for high availability and massive write scalability. Its architecture relies heavily on the LSM-Tree. As detailed in the Apache Cassandra documentation, every node uses MemTables and SSTables to process writes without requiring distributed locks or in-place disk seeks.

Apache HBase: Modeled directly after Google's Bigtable, HBase is a distributed, scalable, big data store built on top of the Hadoop Distributed File System. The HBase architecture^[22] uses an LSM-Tree structure to provide real-time read and write access to massive datasets.

CockroachDB and Pebble: CockroachDB is a distributed SQL database that originally used RocksDB as its underlying storage engine. In 2020, Cockroach Labs replaced RocksDB with a custom LSM-Tree implementation written entirely in Go, named Pebble. This transition allowed them to avoid the performance overhead of crossing the C-to-Go language boundary. The Pebble source code is maintained on GitHub^[23].

Other Implementations: The LSM-Tree concept has been adapted for various specialized workloads. InfluxDB, a time-series database, uses a variant called the Time-Structured Merge Tree to handle high-volume metric ingestion, as described in their internal documentation^[24]. MongoDB's WiredTiger storage engine includes an LSM implementation^[25] for write-heavy workloads. SQLite4 experimented with an LSM extension. Academic systems like AsterixDB use LSM-based B-trees and R-trees to manage big data, as detailed in a 2014 VLDB paper^[26].

Significance and the RUM Tradeoff

The widespread adoption of the LSM-Tree has fundamentally altered how database engineers approach storage design. However, the architecture is not a universal solution. Its significance is best understood through the lens of the RUM Conjecture, formalized in 2016 by Manos Athanassoulis and colleagues at Harvard University.

The RUM Conjecture posits that database access methods face a strict, three-way tradeoff between Read overhead, Update overhead, and Memory overhead. According to the conjecture, a data structure can optimize at most two of these parameters, strictly at the expense of the third.

Traditional B-trees optimize for Read overhead and Memory overhead. They provide fast, predictable read times and require minimal auxiliary memory, but they suffer from high Update overhead due to random I/O and page splits.

The LSM-Tree occupies a different point in the RUM space. It optimizes for Update overhead and Memory overhead. By batching writes and flushing them sequentially, it achieves unmatched write throughput. By compressing immutable SSTables, it maintains a small physical footprint. However, it sacrifices Read overhead. A single logical read may require searching the MemTable, checking multiple Bloom filters, and reading from several overlapping SSTables on disk. Furthermore, the continuous background compaction consumes CPU cycles and disk bandwidth, which can occasionally cause latency spikes in the foreground application.

Recent research continues to explore this design space. A 2021 paper by researchers at Boston University^[27] analyzed the vast configuration space of LSM compactions, while a 2022 paper by Niv Dayan and colleagues^[28] proposed granulating compactions to minimize latency spikes.

Because of these inherent tradeoffs, the LSM-Tree is highly effective for specific workloads. It excels in environments managing time-series data, event logging, messaging systems, and distributed key-value stores where write volume is massive and read patterns are predictable. It is less suited for traditional relational workloads that require heavy secondary indexing, complex multi-table joins, or strict latency guarantees on highly random read queries. By accepting slower reads and background maintenance overhead, the LSM-Tree successfully bypasses the physical limitations of storage hardware, enabling the scale of modern data infrastructure.