LSM Trees and Write Amplification

An LSM tree improves throughput with sequential writes, but rewriting data during compaction causes write amplification.

Choosing sequential writes

For the same volume of data, storage devices handle sequential writes more efficiently than random writes. Hard disks avoid seek costs, while SSDs can reduce internal writes and garbage collection work. That physical property splits storage engine write strategies.

A B+Tree does update-in-place. Changing one row rewrites the page that holds the key. Reads are fast because a key lives in exactly one place, but writes touch scattered pages at random.

A Log-Structured Merge-Tree (LSM tree) accumulates writes in memory and writes them sequentially in batches. A background process performs cleanup later. RocksDB, Cassandra, and LevelDB use this structure.

The LSM tree write path

Writes begin in memory and flow in one direction, downward toward disk. The stages connect as follows.

flowchart LR
  w[Write request<br/>one key-value pair] --> wal[Write-Ahead Log<br/>sequential log for crash recovery]
  w --> mem[MemTable<br/>sorted in-memory structure]
  mem -->|full| imm[Immutable MemTable<br/>switched to read-only]
  imm -->|flush| l0[SSTable L0<br/>immutable sorted file]
  l0 -->|compaction| l1[SSTable L1 and below<br/>merged and compacted levels]

• MemTable: a sorted in-memory structure, usually implemented as a skip list, where new writes land first.
• Write-Ahead Log (WAL): because the MemTable is volatile, the same content is appended sequentially to disk as the basis for crash recovery.
• When the MemTable fills up, it is switched to immutable and a new MemTable is opened. The immutable MemTable is flushed to an SSTable.
• Sorted String Table (SSTable): an immutable sorted file. It carries a Bloom filter and an index so reads can skip keys it does not contain.

Reads walk down from the MemTable through L0, L1, and so on looking for the key. The Bloom filter screens out SSTables that lack the key, cutting disk access.

At this stage, writes are sequential. SSTables are immutable, so updates and deletions add new records. Older key versions and deletion markers (tombstones) therefore accumulate across files.

Where write amplification comes from

Compaction removes old versions and tombstones. It reads SSTables, merges records for the same key, and writes new SSTables without the obsolete records. This necessary cleanup reads and rewrites data that was already stored.

Write amplification puts a number on that cost. The Write Amplification Factor (WAF) is bytes actually written to storage divided by bytes the application asked to write. A single key gets rewritten at several levels on its way to the bottom. Under typical leveled compaction, WAF rises with the number of levels and the size ratio between adjacent levels.

The official RocksDB tuning guide calculates WAF for an example 500 GB database with a size ratio of 10. Summing bytes rewritten at each populated level gives a WAF of about 33. This is a calculation example, not a guaranteed default or a measured range for every workload. Actual WAF depends on key distribution, update patterns, compression, and populated levels.

Example WAF = initial L0 write 1 + L0→L1 merge 2 + lower-level merges 10 + 10 + 10 = 33

Compaction strategy trade-offs

Compaction strategy determines how SSTables are grouped and how amplification costs are distributed. Leveled compaction keeps key ranges within a level non-overlapping. Tiered compaction merges similar-size files when N files have accumulated.

This comparison summarizes the structural properties in the RocksDB compaction documentation. Leveled rewrites overlapping files in the next level, trading higher WAF for tighter space use. Tiered rewrites existing runs less often but retains more runs and temporary space.

Tiered compaction merges files of the same size and rewrites less data in each pass. Older key versions remain in multiple files, increasing space and read amplification. Lower write amplification therefore comes with other costs.

The RUM Conjecture states that read, update, and memory costs cannot all be minimized together. Write, read, and space amplification are related costs. Reducing one can increase another.

Under leveled compaction, if L0 accumulates too quickly, RocksDB applies a write stall to deliberately slow ingestion. It is a signal that compaction cannot keep up with the incoming rate. This is the point where write amplification turns directly into a throughput drop.

Reducing amplification

Much of the write amplification comes from compaction moving keys and values together. Large values inflate the rewrite cost proportionally, so pulling large values out of the compaction path is effective.

Key-value separation stores large values in a blob area and leaves keys and pointers in the LSM tree. The WiscKey paper assumes a 16-byte key, a 1 KB value, and a key-side WAF of 10. It calculates an overall WAF of 1.14 under those assumptions. The actual reduction depends on key/value sizes and garbage collection cost.

The diagram below shows the layout: keys and pointers stay in the LSM tree while values live in a separate blob store.

flowchart LR
  subgraph lsm["LSM tree (keys and pointers)"]
    k1["k1 → 0x10"]
    k2["k2 → 0x20"]
  end
  subgraph blob["Blob store (value bodies)"]
    v1["0x10: large-value-A"]
  end
  k1 -->|pointer reference| v1

SSTable compaction does not automatically clean the blob store. A separate garbage collection (GC) process must identify live keys. Reducing write amplification therefore adds GC and space management costs.

RocksDB parameters control amplification during operation. The following official options are frequently adjusted.

The workload determines which parameter to adjust first. If SSD endurance is limited, prioritize write amplification. For read-heavy search or online analytical processing (OLAP), prioritize read amplification. If storage cost is the limit, prioritize space amplification.

Summary

An LSM tree converts random writes into sequential writes and then rewrites data during compaction. WAF depends on the level configuration and workload, so one range cannot describe a default RocksDB deployment. Production systems should measure it from RocksDB statistics or disk write volume.

A compaction strategy distributes cost across writes, reads, and space. Key-value separation removes large values from compaction but requires separate garbage collection. Measure the active bottleneck and all three forms of amplification before changing parameters.