LSM trees and the write amplification you signed up for

A B-tree updates a record by finding its page and rewriting it. If your working set doesn't fit in memory, that's a random read followed by a random write, per update. An LSM tree refuses to do that. It buffers writes in memory, flushes them sequentially, and defers all the sorting to a background process.

That deferral is the entire design, and everything interesting about LSM trees follows from what happens when the deferred work comes due.

#The write path

Writes touch exactly two things, both cheap.

async function put(key: Key, value: Value): Promise<void> {
  // 1. Append to the write-ahead log — sequential, durable, ~free
  await wal.append({ key, value, seq: nextSeq() });
 
  // 2. Insert into the in-memory table — a skiplist or B-tree
  memtable.insert(key, value);
 
  if (memtable.sizeBytes >= FLUSH_THRESHOLD) {
    // Swap in a fresh memtable; the old one flushes in the background
    const frozen = rotateMemtable();
    void flushToLevel0(frozen);
  }
}

No read is required to write. There is no read-modify-write cycle, no page to locate, no in-place mutation. A delete is just another write — a tombstone marking the key as removed.

#Everything is immutable once written

An SSTable on disk is never modified. It is sorted, it has a block index, and it is either alive or superseded. This is what makes concurrent reads lock-free and snapshots nearly free: a snapshot is just a set of file handles plus a sequence number.

#The read path pays for it

A read has to look in every place a key might live, newest first:

1. The active memtable
2. Any frozen memtables still flushing
3. Level 0 SSTables — which overlap, so all of them
4. Levels 1..N — which don't overlap, so one file per level, found by binary search

async function get(key: Key): Promise<Value | undefined> {
  const hit = memtable.get(key) ?? frozenMemtables.get(key);
  if (hit) return hit.tombstone ? undefined : hit.value;
 
  for (const level of levels) {
    for (const table of level.candidatesFor(key)) {
      // A Bloom filter turns "probably not here" into zero I/O.
      // False positives cost one wasted block read; false
      // negatives can't happen, which is what makes it safe.
      if (!table.bloom.mightContain(key)) continue;
 
      const found = await table.lookup(key);
      if (found) return found.tombstone ? undefined : found.value;
    }
  }
 
  return undefined;
}

Without Bloom filters this design would be unusable — a miss would touch every level on disk. With them, a negative lookup usually costs no I/O at all, and the read amplification collapses to roughly one block read per query.

#Compaction: where the cost actually lands

Flushed tables accumulate. Compaction merges them, drops superseded versions, and discards tombstones once nothing below can contain the key. The strategy you choose sets the trade-off.

#Leveled compaction

Each level is ~10× the size of the one above, and files within a level don't overlap. Merging one file into the level below rewrites roughly 10 files' worth of data.

• Write amplification: high — around 10 per level, so 30–40× overall is normal
• Read amplification: low — at most one file per level
• Space amplification: low — usually under 1.1×

#Size-tiered compaction

Tables of similar size are merged together into one bigger table. Levels contain multiple overlapping tables.

• Write amplification: low — each byte is rewritten a handful of times
• Read amplification: high — many overlapping tables to check
• Space amplification: high — up to 2× during a large merge, since both inputs and output exist at once

You cannot minimise read amplification, write amplification, and space amplification simultaneously. Every storage engine picks two and negotiates the third. Choosing a compaction strategy is making that choice explicitly.

#The failure modes worth knowing

Write stalls. If flushes and compaction can't keep up with ingest, level 0 grows, read amplification climbs, and the engine eventually throttles writers on purpose. A stall is the system defending its read latency — the fix is more compaction throughput, not a bigger memtable.

Tombstone accumulation. A deleted key isn't gone until its tombstone has been compacted past every table that could contain the old value. Delete-heavy workloads on wide key ranges can leave millions of tombstones that make range scans crawl while returning nothing.

Range scans over level 0. Because level 0 files overlap, a scan there merges across all of them. A long-running scan issued while level 0 is backed up will be dramatically slower than the same scan a minute later.

#Why this shape keeps winning

The hardware argument has held for two decades and still holds on NVMe: sequential writes are cheaper than random ones, and a background process with a full view of the data can compact more efficiently than a foreground process reacting one update at a time.

An LSM tree doesn't remove work. It moves work off the critical path, batches it, and gives you a dial that says how much of it to do. That's a better default than a B-tree's insistence on paying in full, immediately, for every write.