LSM Trees and Compaction

Every time you post a message, swipe a payment, or update a profile, a database has to write something to disk. Disk writes are slow — especially random ones that scatter data across a spinning platter or wear-level flash cells unevenly.

In 1996, Patrick O'Neil and colleagues described a structure that sidesteps the problem entirely: the Log-Structured Merge-tree (LSM-tree). Instead of finding the right spot on disk and overwriting it, every write is an append — the fastest thing a storage device can do.

The catch is that appending forever creates clutter. So a background process called compaction periodically merges the accumulated sorted files, throwing away stale versions and keeping the layout tidy enough for reads.

The result is one of the most important engineering trade-offs in modern systems: write performance is near-optimal, but reads and space must be actively managed. RocksDB, LevelDB, Apache Cassandra, ScyllaDB, and HBase all live on this foundation.

Click Write key to send entries into the in-memory buffer (MemTable). When the MemTable fills up it is flushed to a new immutable sorted file on disk (an SSTable). Once several SSTables pile up, click Compact to merge them — duplicates are removed and only the freshest value for each key survives.

<p class="hint">{{hint}}</p>
<div class="lsm-wrap">
  <div class="panel" id="panel-mem">
    <div class="panel-title">{{panel_mem_title}} <span class="badge" id="mem-badge">0/4</span></div>
    <div class="entries" id="mem-entries"></div>
  </div>
  <div class="panel" id="panel-disk">
    <div class="panel-title">{{panel_disk_title}}</div>
    <div id="sstables"></div>
  </div>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="btn-write" type="button">{{btn_write}}</button>
  <button id="btn-compact" type="button" disabled>{{btn_compact}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.5; }
.lsm-wrap { display: flex; gap: 10px; margin-bottom: .6rem; }
.panel { flex: 1; border: 1.5px solid #cdd9e3; border-radius: 10px; padding: 8px 10px; min-height: 120px; background: #f5f8fb; }
#panel-disk { flex: 2; }
.panel-title { font-weight: 700; font-size: .82rem; color: #1d3557; margin-bottom: 6px; display: flex; align-items: center; gap: 6px; }
.badge { background: #1d3557; color: #fff; border-radius: 20px; font-size: .7rem; padding: 1px 6px; font-weight: 600; }
.entries { display: flex; flex-direction: column; gap: 3px; }
.entry { display: flex; gap: 4px; align-items: center; }
.key { background: #1d3557; color: #fff; border-radius: 5px; padding: 2px 7px; font: 600 12px ui-monospace, monospace; }
.val { font: 400 12px ui-monospace, monospace; color: #444; }
.arrow { color: #888; font-size: 11px; }
#sstables { display: flex; flex-wrap: wrap; gap: 6px; }
.sst { border: 1.5px solid #adb1b8; border-radius: 8px; padding: 5px 8px; background: #fff; min-width: 80px; }
.sst-title { font-size: .72rem; font-weight: 700; color: #888; margin-bottom: 4px; }
.sst.compacted { border-color: #0a7d33; background: #f0fff4; }
.sst.compacted .sst-title { color: #0a7d33; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; color: #333; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button:disabled { opacity: .4; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }
@keyframes pop { 0%{transform:scale(1.18)} 100%{transform:scale(1)} }
.pop { animation: pop .2s ease-out; }

// Code not found

Notice the asymmetry: every write is $O(1)$ — just append to the MemTable. Compaction is $O(n \log n)$ but runs in the background and amortizes over many writes. A read may have to check the MemTable and every SSTable level, which is why real systems use Bloom filters to skip files that cannot contain a key.

LSM trees do not eliminate cost — they redirect it.

• Write path is $O(1)$ amortized. Every incoming write goes to the in-memory MemTable, which is just a sorted structure (often a skip-list or red-black tree). Flushing a full MemTable to disk is a single large sequential write — the cheapest disk operation possible.
• Compaction is $O(n \log n)$ but amortized. When K sorted runs of total size N are merged, each key is touched at most $O(\log N)$ times across all compaction rounds. This is the price paid for making writes fast.
• Write amplification (WA). Each byte written by the application can be physically written to disk several times — once on flush, then once per compaction level it passes through. Tiered strategies (like RocksDB's universal compaction) keep WA low; leveled strategies (like LevelDB's default) trade higher WA for lower read amplification.
• Read amplification (RA). A point lookup may scan the MemTable, the immutable MemTable, and every SSTable level from newest to oldest. Without Bloom filters, RA grows with the number of levels. With Bloom filters (invented by Burton Bloom in 1970), most negative lookups skip all disk I/O.
• Space amplification (SA). Until compaction runs, multiple versions of the same key exist on disk simultaneously. In the worst case, space usage can double. This is why compaction is not optional — it is a correctness and efficiency requirement.

The RUM conjecture (Idreos et al., 2016) formalizes the tension: any data structure pays in at least two of read overhead, update overhead, and memory/space overhead. LSM trees minimize update overhead at the expense of the other two, controlled by careful compaction policy.

See also sorting lower bounds for why merge-sort's $O(n \log n)$ is the best any comparison-based merger can do — the same bound that limits compaction speed.

The LSM write-optimized design shows up wherever the write rate is high and data is mostly appended rather than updated in place:

• RocksDB (Meta/Facebook, 2012): a heavily tuned fork of LevelDB, now the storage engine behind MySQL (MyRocks), MongoWiredTiger-competitor configurations, and countless internal Meta services processing petabytes of social-graph data daily.
• Apache Cassandra and ScyllaDB: distributed wide-column stores built entirely on the LSM model. Every write is appended to a commit log and a MemTable; SSTables are flushed and compacted in the background. These systems handle hundreds of thousands of writes per second per node.
• Apache HBase (Hadoop): Google Bigtable's open-source counterpart. Bigtable itself — described in Google's 2006 paper — was one of the first production systems built on the LSM idea.
• Time-series databases (InfluxDB, Prometheus TSDB): sensor readings, metrics, and logs are almost pure appends; LSM trees map perfectly onto this access pattern.
• SSD firmware: many NVMe drives internally use log-structured layouts for wear-leveling, mirroring the same compaction logic at the hardware layer.

Understanding LSM trees also illuminates the design of SQL optimization — query planners account for the read-amplification cost of LSM-backed tables and choose scan strategies accordingly.

The LSM tree is a lesson in deliberate trade-offs. Writing fast means never overwriting; never overwriting means accumulating sorted runs; accumulating sorted runs means paying a compaction tax. The art of tuning a system like RocksDB is deciding exactly how much read amplification and space amplification you will tolerate to keep writes at peak speed.

Every time you see a write throughput benchmark in the millions of operations per second, an LSM tree is almost certainly behind it — quietly merging layers in the background so that the next write can land in memory without touching disk at all.