LSM Trees and Write Amplification
Why LSM trees, which buy throughput with sequential writes, pay for it in write amplification, traced from the structure through compaction.
Write amplification is the point where compaction charges back the throughput that sequential writes earned.
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.
The Log-Structured Merge-Tree (LSM tree) takes the opposite approach. Incoming writes accumulate in memory, get written out sequentially in bulk, and cleanup is deferred to a background process. RocksDB, Cassandra, and LevelDB all 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.
- 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.
Up to this point every write is sequential. The trouble starts with SSTable immutability. Updates and deletes are also appended as new records, so older versions of the same key and deletion markers (tombstones) pile up across files.
Where write amplification comes from
Cleaning up those stale versions and tombstones is the job of compaction. Compaction reads several SSTables, merges identical keys, and writes out new SSTables with the old versions and tombstones dropped. The cleanup is necessary, but it means reading and rewriting data that was already written once.
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 a WAF of about 33 for an example 500 GB database with a size ratio of 10. This is a worked example that sums bytes rewritten at each populated level, not a guaranteed default or a measured range for every workload. The actual value depends on key distribution, update patterns, compression, and the populated level count.
Example WAF = initial L0 write 1 + L0→L1 merge 2 + lower-level merges 10 + 10 + 10 = 33Compaction strategy trade-offs
Even within compaction, how SSTables are grouped for merging decides how the amplification is distributed. There are two broad families, leveled and tiered. Leveled keeps key ranges non-overlapping within each level; tiered merges files of similar size once N of them accumulate.
| Strategy | Write amplification | Space amplification | Reads | Suited to |
|---|---|---|---|---|
| Tiered (STCS, Cassandra) | Lower | Higher | Consults several runs | Bulk sequential inserts |
| Leveled (LCS) | Higher | Lower | One run per level | Read-heavy, evenly distributed updates |
| Universal | Lower | Can grow temporarily | Consults several files | Time series and log ingestion |
| FIFO | Deletes old files without rewriting | Uses the configured limit | Consults L0 files | Expiry-based ephemeral data |
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 merges only same-size files, so the amount rewritten in one pass is smaller. In exchange, old versions of the same key stay scattered across multiple files, which raises space and read amplification. Whatever write amplification is saved comes back as cost on another axis.
That tension is not accidental. The RUM Conjecture, which holds that read, update, and memory costs cannot all be minimized at once, summarizes the limit. The three amplifications - write, read, and space - trade off, so pressing one down inflates 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 separate blob area and keeps only keys and pointers in the LSM tree. The WiscKey paper calculates an overall WAF of 1.14 when it assumes a 16-byte key, a 1 KB value, and a key-side WAF of 10. This is a result for those assumptions; the actual reduction depends on key and 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.
Blobs, however, are not cleaned up automatically the way compaction cleans SSTables. A separate garbage collection (GC) pass has to trace back which keys are still live, and its cost returns as space amplification. The space freed on the write amplification axis is refilled by GC overhead.
In operation, RocksDB parameters control where the amplification lands. These are the official options adjusted most often.
| Parameter | Effect |
|---|---|
| level_compaction_dynamic_level_bytes | Auto-adjusts level sizes, slightly lowering write amplification |
| Raising target_file_size_base | Fewer files, which reduces unnecessary compaction triggers |
| min_blob_size | Applies key-value separation only above the given value size |
Which parameter to touch first is decided by the workload. If SSD endurance budget is tight, press write amplification down first. If reads matter, as in search or online analytical processing (OLAP), prioritize read amplification. If storage cost is the constraint, 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.