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.
Contents
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 faster than random ones. Hard disks are commonly cited as roughly 100 times faster on sequential access than on random access, and SSDs also favor sequential writes in both endurance and throughput. That physical property is what splits storage engine write strategies.
A B+Tree does update-in-place. Changing one row rewrites the entire page that holds the key, typically 8-16KB. 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 every level on its way to the bottom. Write amplification therefore grows in proportion to the number of levels L and the per-level fanout T, up to O(L·T).
RocksDB defaults to six levels with a fanout of about 10 per level. Measured write amplification in that configuration is commonly reported in the range of 10-30x (workload dependent, approximate). In other words, one byte written by the user can mean 10-30 bytes written to disk.
Compaction 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 amp (approx.) | Space amp (worst) | Reads | Suited to |
|---|---|---|---|---|
| Tiered (STCS, Cassandra) | About 5x | About 9x | Weak | Bulk sequential inserts |
| Leveled (LCS) | About 13x | About 1.1-2x | Good | Read-heavy, evenly distributed updates |
| Universal | About 2-5x | Medium | Medium | Time series and log ingestion |
| FIFO | About 1x | High | Weak | Expiry-based ephemeral data |
These figures are approximations from public measurements and documentation. By ScyllaDB's measurements, leveled is about 5 times more space efficient than tiered but has roughly 2 times the write amplification. The reason is that compacting a single SSTable under leveled pulls in up to a dozen or so overlapping files from the next level.
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. WiscKey (FAST 2016) proposed it, and RocksDB's BlobDB and TiKV's Titan implement it. For values of 4KB and above, write amplification reportedly drops by roughly 50-80% (as reported for the WiscKey line of work).
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 to gain write throughput. It pays for that with compaction repeatedly rewriting the same data, which is write amplification. That amplification grows with level count and fanout, up to O(L·T), and is commonly reported around 10-30x in a default RocksDB configuration.
Choosing a compaction strategy is a decision about how to distribute the amplification across write, read, and space. As the RUM Conjecture states, the three cannot be minimized simultaneously. Key-value separation and RocksDB parameter tuning genuinely reduce write amplification, but the saved cost tends to return as GC work or as amplification on another axis.