LSM-Tree Storage Engines: How Compaction Works

Updated on Nov 6, 2026

9 min read

LSM-tree storage engines are used by databases that need to absorb many updates without rewriting a disk-based index for every change. They buffer writes, organize them into sorted files, and merge those files in the background. This design appears in embedded key-value stores, distributed databases, and systems built for write-heavy workloads. Understanding its moving parts helps explain why fast ingestion can come with compaction work, extra reads, and temporary storage demands.

What Is an LSM-Tree?

A log-structured merge-tree (LSM-tree) is a storage-engine design that maintains ordered key-value data across memory and disk. New changes are collected in memory and later written as sorted, usually immutable files. Background compaction merges these files into a structure that the engine can search efficiently.

Despite the name, an LSM-tree is not usually a pointer-linked tree like a binary search tree. It is better pictured as a collection of sorted runs at different ages or levels. Searches consult the newest data first, then older runs as needed. The foundational LSM-tree paper by O’Neil and colleagues describes the design as a way to defer and batch updates to disk.

RocksDB, an embedded key-value store, is a practical example. Its architecture overview describes writes entering a memtable and a write-ahead log, followed by sorted-string-table files and compaction. Many implementations share this broad pattern, but details such as level sizes, durability settings, and compaction policy vary.

Why LSM-Trees Exist

An engine organized around a B-tree may need to update pages at different locations as keys change. Caches and page batching can reduce the cost, but a write-heavy workload can still cause scattered I/O and coordination around existing pages.

An LSM engine changes the write path: it accepts changes in memory and writes data in batches, often as sequential output. This can make sustained ingestion efficient, especially when updates arrive faster than a system can conveniently rewrite its on-disk organization one record at a time. It does not make the work disappear. Compaction later reads and rewrites sorted data, and a workload with many reads or updates to existing keys can trigger substantial merge activity.

This is why LSM-tree discussions often focus on amplification and compaction. The engine is trading immediate random update work for buffered writes and later maintenance. Whether that trade is useful depends on the read/write mix, key distribution, storage device, data-retention needs, and how much background capacity is available.

How an LSM-Tree Works

When an application writes a key, the engine can append the change to a write-ahead log (WAL) for recovery and place it in an in-memory structure called a memtable. The WAL and memtable serve different purposes: the log records changes for recovery, while the memtable makes recent data available for reads and eventual sorted output. Durability depends on configuration, including whether writes are synchronized to persistent storage before success is reported.

As the active memtable fills, the engine makes it immutable and continues accepting new writes in another buffer. It flushes the immutable contents into a sorted string table (SST), also called an SSTable or sorted table file. Keys in the file are ordered, which supports binary search, range scans, block indexes, and filters. An SST is generally not edited in place; later compaction creates replacement files.

Recent SSTs may initially be placed in level zero (L0), where files can have overlapping key ranges. Compaction selects files and merges their contents into a new sorted run, often at a lower level. In leveled designs, files at deeper levels are usually range-partitioned so each file covers a distinct key range. A read checks relevant in-memory data and files, considering newer versions before older ones. Bloom filters and indexes can help skip files that cannot contain a requested key, but they do not remove all read cost.

The RocksDB compaction documentation describes several policies that produce different trade-offs:

Compaction style	How data is merged	Typical benefit	Typical cost
Leveled	Selected files are merged into a larger, range-partitioned level	Fewer runs and less redundant data to check on many reads	Existing data may be rewritten repeatedly, increasing write amplification
Tiered (often called universal in RocksDB)	Several runs are merged together, with less rewriting of older runs per merge	Lower write amplification in many workloads	More runs may need checking and more temporary space may be needed
Hybrid	Uses tiered behavior in some levels and leveled behavior in others	Balances merge work and lookup cost	More policy and configuration complexity
FIFO	Old files are dropped when a configured size limit is reached	Simple retention for cache-like or disposable data	Not a general way to preserve all database records

These are broad tendencies, not performance guarantees. Implementations add variants, and defaults can change. Benchmark the actual application and data rather than choosing a policy based only on its name.

Components and Key Concepts

Memtable: The active in-memory ordered structure that receives writes. When full, it becomes immutable and can be flushed while a new memtable accepts more changes.
Write-ahead log: A recovery record that can be replayed after a restart if recent changes have not yet reached an SST. Whether a write survives a machine or power failure depends on synchronization and storage guarantees, not simply on using an LSM-tree.
SST files and levels: Immutable sorted runs on storage. L0 files can overlap; deeper levels in leveled compaction are typically sorted by key range. File indexes and filters help avoid unnecessary reads.
Tombstones and versions: A delete is often recorded as a tombstone until compaction can safely remove it and any older value it masks. Snapshots or active readers may require an engine to retain versions longer.
Compaction debt: Pending background work accumulates when new flushes and updates arrive faster than compaction can process them. The system can then slow writes, delay space reclamation, or restrict incoming writes to regain stability.

Three amplification measures help explain the trade-offs. Write amplification compares bytes written by the storage engine to the logical bytes written by the application; compaction can make the physical total much larger. Read amplification describes how many files, blocks, or bytes a read must examine to find its result. Space amplification compares storage occupied by the engine with the live logical data, including obsolete versions and temporary files during compaction. Exact measurement conventions differ, so use the database’s own metrics and state how the measurement is calculated.

Real-World Use Cases

An LSM design can suit systems that ingest many events, updates, or key-value records, particularly when data is appended in batches and point or range reads can tolerate checking multiple structures. Examples include embedded storage engines, distributed key-value databases, write-heavy event pipelines, and some time-series workloads. Retention and deletion patterns matter: if old records expire in large groups, the storage system may be able to reclaim them efficiently.

It is not a universal fit. A workload dominated by latency-sensitive reads, frequent updates to a narrow set of keys, or storage with limited background bandwidth may spend too much time on lookups and compaction. Some databases use B-tree structures, LSM-trees, or multiple structures for different tables and indexes. The application interface alone may not reveal the underlying storage model.

Getting Started with RocksDB

RocksDB is an embedded library, so this small C++ program writes and reads a key in a local database directory. On Ubuntu, install the compiler and development package:

sudo apt-get update
sudo apt-get install g++ librocksdb-dev

On macOS, install the library with brew install rocksdb. For other platforms and source builds, follow the RocksDB installation instructions.

Save this as lsm-demo.cpp:

#include <iostream>
#include <memory>
#include <string>

#include "rocksdb/db.h"

int main() {
  rocksdb::DB* raw_db = nullptr;
  rocksdb::Options options;
  options.create_if_missing = true;

  rocksdb::Status status =
      rocksdb::DB::Open(options, "./lsm-demo-db", &raw_db);
  if (!status.ok()) {
    std::cerr << "Open failed: " << status.ToString() << '\n';
    return 1;
  }
  std::unique_ptr<rocksdb::DB> db(raw_db);

  rocksdb::WriteOptions write_options;
  write_options.sync = true;
  status = db->Put(write_options, "user:42", "active");
  if (!status.ok()) {
    std::cerr << "Write failed: " << status.ToString() << '\n';
    return 1;
  }

  rocksdb::FlushOptions flush_options;
  flush_options.wait = true;
  status = db->Flush(flush_options);
  if (!status.ok()) {
    std::cerr << "Flush failed: " << status.ToString() << '\n';
    return 1;
  }

  std::string value;
  status = db->Get(rocksdb::ReadOptions(), "user:42", &value);
  if (!status.ok()) {
    std::cerr << "Read failed: " << status.ToString() << '\n';
    return 1;
  }
  std::cout << value << '\n';
  return 0;
}

Compile and run it on Ubuntu:

g++ -std=c++17 lsm-demo.cpp -lrocksdb -o lsm-demo
./lsm-demo

The expected output is active. The explicit flush makes the small memtable eligible to appear as an SST in the demo database directory; it does not run a full compaction. sync = true asks RocksDB to synchronize this write before returning, which can add latency. Choose durability settings based on the application’s failure model rather than copying demo settings into production. Keep the sample directory disposable, and do not point experiments at a database containing data you need.

For a real workload, measure sustained writes after the initial buffers fill, not just a short burst. Watch write stalls, pending compaction bytes, read latency, disk usage, and device write volume. If writes slow over time, check whether compaction is falling behind before increasing buffer sizes; larger buffers can delay work while increasing memory or recovery costs. Use the engine’s supported statistics and logs, and compare results with representative keys, values, and read patterns.

Common Misconceptions

“An LSM-tree writes every update only once.”

The application update may first be logged and buffered, then flushed and rewritten through one or more compactions. Sequential batching can make this efficient, but physical storage writes can exceed the logical input.

“Compaction is just cleanup that can be disabled.”

Compaction also shapes files for reads and may remove obsolete versions or tombstones. Disabling automatic compaction can cause files and pending work to accumulate; it is a specialized operational choice, not a free performance setting.

“LSM-trees are always faster for writes.”

They can handle write-heavy workloads well, but performance depends on whether compaction keeps pace and whether storage can supply the needed background I/O. A workload that saturates the device or reads across many runs may not benefit.

For the device interface that can complement sequential storage engines, see NVMe Zoned Namespace storage.
Compare LSM behavior with other index structures in database indexing strategies.
See why append-oriented workloads are common in time-series databases.
For a storage-layer view of write costs, read block storage performance optimization.
For row-version cleanup in a specific relational database, see PostgreSQL MVCC, VACUUM, and table bloat.

Changelog

Initial publication; reviewed against the LSM-tree paper and RocksDB documentation.