Introduction

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.

Watch It Live

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">Each <b>Write</b> appends a key→value pair to the in-memory MemTable.
    When it fills up it <b>flushes</b> to a new immutable SSTable on disk. Hit <b>Compact</b>
    to merge all SSTables — only the latest value for each key survives.</p>
<div class="lsm-wrap">
  <div class="panel" id="panel-mem">
    <div class="panel-title">MemTable <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">SSTables on Disk</div>
    <div id="sstables"></div>
  </div>
</div>
<div class="status" id="status">Write some keys to get started.</div>
<div class="btns">
  <button id="btn-write" type="button">Write key</button>
  <button id="btn-compact" type="button" disabled>Compact</button>
  <button id="btn-reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// LSM-tree demo: MemTable → flush → SSTable → compact
// Keys cycle through a small alphabet so duplicates appear naturally.
const KEYS = ['A','B','C','D','E','F','G','H'];
const MEM_CAPACITY = 4; // entries before flush
let memTable = [];   // [{key,val,ts}]  most-recent first
let ssTables = [];   // [{id, entries:[{key,val,ts}]}]  newest first
let ts = 0;          // logical timestamp
let sstId = 0;

function nextKey() {
  // weighted random: keys A-D appear more often to create duplicates
  const pool = ['A','A','B','B','C','C','D','E','F','G','H'];
  return pool[Math.floor(Math.random() * pool.length)];
}
function nextVal() { return 'v' + (++ts); }

function write() {
  const key = nextKey(), val = nextVal();
  // Insert or update in memTable (keep all — flush will deduplicate via timestamp)
  memTable.unshift({key, val, ts});
  setStatus(fmt('Wrote %key% → %val% (ts=%ts%)', { key: key, val: val, ts: ts }), 'info');
  if (memTable.length >= MEM_CAPACITY) flush();
  render();
}

function flush() {
  // Sort by key asc, then ts desc (newest per key first)
  const sorted = [...memTable].sort((a,b) => a.key < b.key ? -1 : a.key > b.key ? 1 : b.ts - a.ts);
  ssTables.unshift({id: ++sstId, entries: sorted});
  memTable = [];
  setStatus(fmt('Flushed MemTable → SSTable-%sstId%', { sstId: sstId }), 'info');
  document.getElementById('btn-compact').disabled = ssTables.length < 2;
}

function compact() {
  // Merge all SSTables: for each key keep only the entry with highest ts
  const map = new Map();
  // Iterate newest SSTable first so the first occurrence wins (highest ts)
  for (const sst of ssTables) {
    for (const e of sst.entries) {
      if (!map.has(e.key)) map.set(e.key, e);
    }
  }
  const merged = [...map.values()].sort((a,b) => a.key < b.key ? -1 : 1);
  ssTables = [{id: ++sstId, entries: merged, compacted: true}];
  setStatus(fmt('Compacted %v% SSTables → SSTable-%sstId% (%length% unique keys)', { v: ssTables.length === 1 ? 'all' : '', sstId: sstId, length: merged.length }), 'ok');
  document.getElementById('btn-compact').disabled = true;
  render();
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t; s.className = 'status ' + (cls || '');
}

function renderEntry(e) {
  const div = document.createElement('div'); div.className = 'entry';
  div.innerHTML = '<span class="key">' + e.key + '</span>' +
    '<span class="arrow">→</span><span class="val">' + e.val + '</span>';
  return div;
}

function render() {
  // MemTable
  const me = document.getElementById('mem-entries'); me.innerHTML = '';
  memTable.forEach(e => me.appendChild(renderEntry(e)));
  document.getElementById('mem-badge').textContent = memTable.length + '/' + MEM_CAPACITY;
  if (memTable.length >= MEM_CAPACITY - 1) {
    document.getElementById('mem-badge').style.background = '#e63946';
  } else {
    document.getElementById('mem-badge').style.background = '#1d3557';
  }

  // SSTables
  const sc = document.getElementById('sstables'); sc.innerHTML = '';
  ssTables.forEach(sst => {
    const div = document.createElement('div');
    div.className = 'sst' + (sst.compacted ? ' compacted' : '');
    div.innerHTML = '<div class="sst-title">SSTable-' + sst.id + (sst.compacted ? ' ✓' : '') + '</div>';
    const entries = document.createElement('div'); entries.className = 'entries';
    sst.entries.forEach(e => entries.appendChild(renderEntry(e)));
    div.appendChild(entries); sc.appendChild(div);
  });

  document.getElementById('btn-compact').disabled = ssTables.length < 2;
}

// Verify: compact merges correctly — most recent ts per key wins
(function selfTest() {
  const a = {key:'A', val:'v1', ts:1};
  const b = {key:'A', val:'v3', ts:3};
  const c = {key:'B', val:'v2', ts:2};
  const testSSTs = [{id:1,entries:[a,c]},{id:2,entries:[b]}]; // newest first
  const map = new Map();
  for (const sst of testSSTs) for (const e of sst.entries) if (!map.has(e.key)) map.set(e.key, e);
  const merged = [...map.values()].sort((x,y) => x.key < y.key ? -1 : 1);
  console.assert(merged.length === 2, 'compact: 2 unique keys');
  console.assert(merged[0].key === 'A' && merged[0].ts === 3, 'compact: A→v3 wins');
  console.assert(merged[1].key === 'B' && merged[1].ts === 2, 'compact: B→v2 present');
  console.log('LSM demo self-test: PASS');
})();

document.getElementById('btn-write').addEventListener('click', write);
document.getElementById('btn-compact').addEventListener('click', compact);
document.getElementById('btn-reset').addEventListener('click', () => {
  memTable = []; ssTables = []; ts = 0; sstId = 0;
  document.getElementById('btn-compact').disabled = true;
  setStatus('Write some keys to get started.', '');
  render();
});
render();
Result
Console

Notice the asymmetry: every write is O(1)O(1) — just append to the MemTable. Compaction is O(nlog⁡n)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.

The Real Complexity

LSM trees do not eliminate cost — they redirect it.

  • Write path is O(1)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(nlog⁡n)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)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(nlog⁡n)O(n \log n) is the best any comparison-based merger can do — the same bound that limits compaction speed.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/log-structured-merge-compaction/Content licensed under CC BY-NC 4.0.