The seductive version of an LSM tree is:

writes are sequential
reads use sorted tables
background compaction cleans everything up

That is true enough to be useful and false enough to be dangerous.

The better version is:

the write path borrows sorting work from the future
compaction decides who pays it back

An LSM tree does not remove the cost of maintaining an ordered key-value index. It changes the payment schedule. New writes first land in memory. When the memory component fills, it is flushed as an immutable sorted run. Later, background merge jobs combine runs, discard overwritten versions, move tombstones, and restore a shape that reads can tolerate.

This is why LSM tuning feels like moving pressure around a sealed room. Lower write amplification and reads may touch more runs. Lower read amplification and compaction rewrites more data. Lower space amplification and deletes or overwrites must be cleaned aggressively. The three costs are not independent knobs. They are the same sorting debt accounted in different columns.

The Old Bargain Was Physical

O’Neil, Cheng, Gawlick, and O’Neil introduced the LSM-tree as a disk-based data structure for files with high rates of inserts and deletes.1 Their central move was to keep a small memory-resident component and cascade batches of changes into larger disk-resident components through merge-sort-like work.

The original motivation was physical. Random disk updates are expensive. A B-tree maintains a tidy index by updating pages in place, which can be excellent for point lookups but painful under sustained random write traffic. The LSM tree says: do not immediately force every update to find its final page. Buffer updates, sort them, and merge them in batches.

Bigtable made the pattern operational at large scale: recent updates live in a memtable, persistent state is stored in immutable SSTables, and compactions rewrite SSTables into better-organized files.2 LevelDB’s implementation notes describe the same family of mechanics in a compact form: memtables, immutable tables, levels, and compactions that pick files from one level plus overlapping files in the next.3

The important word is immutable.

An immutable sorted run is friendly to sequential writes, compression, caching, checksums, and simple crash recovery. It is also an admission that new information does not edit the old run in place. If key k is updated five times, five versions may exist across the structure until compaction proves which versions can be forgotten.

Compaction is the forgetting machine.

A Ledger for the Sorting Loan

The lab below simulates a deliberately simplified LSM tree. It is not RocksDB, LevelDB, Cassandra, Pebble, or Bigtable. It ignores block caches, file sizes, prefix filters, snapshots, range tombstones, WAL cost, compression, concurrent compactions, device bandwidth, and many production details.

What it does model is the core ledger:

  1. writes accumulate in a memtable;
  2. a full memtable flushes into an immutable sorted run;
  3. compaction policies merge runs and keep only the latest version of each key;
  4. the final physical layout is measured for write, read, and space amplification.

The three policies are:

  • none: flush only, no compaction;
  • tiered: merge several similarly aged runs into a larger run;
  • leveled: keep lower levels compact by merging them into the next level.

RocksDB’s documentation frames a similar tradeoff: universal compaction targets lower write amplification while accepting higher read and space amplification, whereas leveled compaction usually spends more write work to control read and space behavior.45

Memtable and live data Level 0 runs Leveled runs Tiered compaction Obsolete versions

Deterministic toy model. Write amplification excludes the write-ahead log and compression; point checks estimate sorted-run probes, not full device latency.

Try five moves.

First, set Policy to none. Writes look wonderfully cheap: in the default hot workload the run write amplification is only about 0.55x because repeated updates collapse in the memtable before flush. Then look at point checks and obsolete share. The system did not get free storage. It left 19 runs, about 8.04 point checks, 3.39x space amplification, and 604 obsolete entries for future reads and future compaction to deal with.

Second, switch to tiered. In this toy, the default hot workload lands at about 0.98x run write amplification, 2.99 point checks, 1.41x space amplification, and four runs. Do not read that as a universal win over leveled compaction. It is the toy workload and the toy policy telling you that update locality and whole-run merges can dominate the headline labels.

Third, switch to leveled. The lab’s leveled policy is intentionally coarse: it merges whole levels rather than doing RocksDB-style partial file picking. Even so, the shape is visible. The default run does three compactions, leaves five runs, reports about 3.62 point checks, and keeps space amplification near 1.56x. Compared with no compaction, the debt has clearly moved. Compared with tiered in this toy, the answer is more interesting than the label.

Fourth, choose append-only. Obsolete versions nearly disappear. The sorting debt becomes easier because old keys are not being rewritten. Many production engines exploit this with trivial moves or key-range-aware compactions.

Fifth, raise Delete rate under a hot workload. Tombstones are promises to forget later. Until compaction can safely drop them, they occupy space and stop reads. A delete is not merely the absence of a value; in an LSM tree it is a piece of evidence.

Every Run Is Sorted; the Database Is Not

Every immutable run is individually sorted. The whole database is not.

That sentence is the source of most LSM behavior.

If a key has been updated repeatedly, the newest version may be in the memtable, a level-0 file, or a lower-level run. Reads must find the newest visible version. Bloom filters, indexes, file metadata, and caches make this much cheaper than scanning every byte, but the number and overlap of runs still matter.

Compaction buys several things at once:

  1. It merges sorted runs into fewer sorted runs.
  2. It removes overwritten versions.
  3. It carries tombstones downward until old values can be hidden or discarded.
  4. It restores level invariants that make future reads predictable.
  5. It converts many small sequential writes into fewer large sequential rewrites.

The cost is also several things at once:

  1. It reads old data.
  2. It writes surviving data again.
  3. It competes with foreground reads and writes for CPU, cache, and I/O.
  4. It can create latency spikes if the debt is paid in bursts.

This is why production systems do not merely ask “is compaction enabled?” They ask which files, how much overlap, how many levels, what size ratio, how many background jobs, what tombstone rules, what snapshot horizon, and what write-stall policy.

The shape of the compaction policy is the shape of the database.

There Is No Free Corner

Tiered compaction waits until it has several comparable runs, then merges them. It tends to reduce write amplification because data is not repeatedly forced through tightly maintained levels. The price is that point lookups may need to consult more runs, and duplicate versions may persist longer.

Leveled compaction tries to maintain tighter level structure. In LevelDB, a compaction picks a file from level L and overlapping files from level L+1, then produces output files in the next level.3 This controls overlap and lookup work, but surviving data can be rewritten multiple times as it moves down the levels.

RocksDB exposes this as an explicit engineering choice. Universal compaction is documented as targeting use cases that need lower write amplification while trading off read and space amplification. Leveled compaction is the more common default when predictable reads and bounded space matter.45

There is no universally best point on this triangle, and the toy above is a useful warning against treating policy names as outcomes.

An ingest pipeline may accept high read amplification during bulk loading, then compact later. A latency-sensitive read service may spend more write bandwidth to keep the run count small. A database with large values may separate keys from values, as WiscKey does, so compaction need not repeatedly move full values while sorting keys.6

That last example is a useful reminder: “LSM tree” is not one design. It is a family of designs organized around deferred, batched merging.

Workload Shape Changes the Bill

The lab’s hot updates workload makes one important point: update locality changes the bill.

If the same small set of keys is updated many times before flush, the memtable can collapse several user operations into one flushed entry. That can make the run write amplification metric look surprisingly low. This is real in spirit, but incomplete. A real system also writes a log for durability, and snapshots may prevent old versions from being dropped immediately.

If keys are append-only, compaction has less obsolete data to remove. The system is mostly organizing new ranges. If keys are uniform and repeatedly overwritten, compaction becomes a version collector. If deletes are common, tombstones become a second workload: they must be retained long enough to hide older values, then dropped only when safe.

This is why benchmark results for LSM engines are so workload-sensitive. The same configuration can look heroic under sequential ingest and miserable under overwrite-heavy, delete-heavy, read-after-write traffic.

The data structure did not change. The debt schedule did.

Ask What Debt You Are Moving

Before touching compaction flags, ask what debt you are trying to move.

Are reads point-heavy, range-heavy, or mostly absent-key probes?
Are writes mostly inserts, overwrites, or deletes?
Do snapshots hold old versions open?
Are values large enough that moving them dominates key sorting?
Can ingest and serving happen in different phases?
Is the pain average throughput or tail latency?

The correct policy depends on those answers.

A read-heavy service cares about run count, overlap, Bloom-filter quality, cache hit rate, and how often compaction invalidates useful cached blocks. A write-heavy ingest system cares about flush rate, compaction bandwidth, write stalls, and whether a low-priority cleanup job can catch up later. A delete-heavy workload cares about tombstone horizons and when old data is provably gone.

The anti-pattern is to treat compaction as janitorial work. It is not cleaning up after the database. It is the database deciding when sorted order becomes real.

The Payment Plan

An LSM tree is not just a log, and it is not just a tree.

The log part makes new writes cheap by appending batches of sorted facts. The tree part appears gradually, as compaction merges those facts into a searchable shape. Between those moments, the database contains multiple partial truths: new values, old values, tombstones, overlapping runs, and level invariants that may or may not be paid up.

So the operational question is not:

How do I make compaction cheap?

It is:

Which bill am I willing to see, and when?

The log is a sorting debt. Compaction is the payment plan.

  1. Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil, “The Log-Structured Merge-Tree (LSM-Tree)”, Acta Informatica, 1996. A copy is also available from UMass Boston. ↩

  2. Fay Chang et al., “Bigtable: A Distributed Storage System for Structured Data”, OSDI 2006. ↩

  3. Google LevelDB, “Implementation notes”, especially the memtable, levels, and compaction sections. ↩ ↩2

  4. RocksDB Wiki, “Universal Compaction”. ↩ ↩2

  5. RocksDB Wiki, “Leveled Compaction”. ↩ ↩2

  6. Lanyue Lu et al., “WiscKey: Separating Keys from Values in SSD-Conscious Storage”, FAST 2016. ↩