🌿 CuriousWinds

Lsm-trees & Write Amplification

Write amplification boundaries, multi-level merge sorting, and key-value separation on solid-state media.

Executive Summary & Key Takeaways
Foundational Synthesis for Practitioners & Research Systems

LSM-trees optimize writes via sequential I/O but inflate physical writes 10, 40x, violating NAND endurance limits. Misconceptions equate sequential writes with efficiency, empirical data shows uncontrolled amplification accelerates flash failure.

01 Merge-Sort Overhead

Compaction merges overlapping keys across levels, inflating physical writes 10, 40x via sequential reads and rewrites.

02 Amplification Stacking

Total WAF compounds LSM (15, 30x) with SSD FTL (1.2, 5x), multiplying endurance wear to 62.5x.

03 Block Erasure Penalty

Fragmented writes force FTL garbage collection, accelerating block-level erase cycles and I/O stalls.

04 Tiered Compaction Rules

Use Size-Tiered over Leveled, cap MemTable flushes at 4, 8MB, and abort compactions if WAF SSD exceeds 2.0.

01 1 · STORAGE ARCHITECTURE · FUNDAMENTAL TRADEOFFS

The Core Conflict

In-Memory Ingestion vs. NAND Endurance

Log-Structured Merge-trees (LSM-trees) represent the foundational storage architecture powering modern write-intensive distributed data systems, including RocksDB, Apache Cassandra, ScyllaDB, and ClickHouse. By buffering incoming mutations in an in-memory sorted structure (the MemTable) and sequentially appending them to an append-only Write-Ahead Log (WAL), LSM-trees convert erratic random disk writes into high-bandwidth sequential I/O.

However, this architecture incurs a severe physical cost: Write Amplification Factor (WAF).

Because immutable on-disk sorted string tables (SSTables) cannot be mutated in place, background worker threads must continuously read, merge-sort, and rewrite overlapping key ranges across cascading levels. Over the operational lifecycle of a high-throughput database, a single logical byte written by an application is rewritten to physical non-volatile NAND flash memory between 10 and 40 times.

On modern enterprise NVMe drives, uncontrolled write amplification degrades drive endurance, triggers catastrophic I/O write stalls, and burns through rated drive write limits (Drive Writes Per Day, DWPD) years ahead of schedule.

SYSTEM TOPOLOGY & ARCHITECTURE
The Cascading Write Amplification Pipeline
System Architecture
Stage 01
1. Application Write Request (1 KB)
Stage 02
2. Sequential Write to WAL (1 KB)
Stage 03
3. In-Memory MemTable (RAM)
Buffer Full →
Stage 04
4. Flush to Level 0 SSTables (1 KB on Disk)
Stage 05
5. Level 0 -> Level 1 Compaction
Read 10 KB, Merge-Sort, Write 11 KB
Stage 06
6. Level 1 -> Level 2 Compaction
Read 40 KB, Merge-Sort, Write 45 KB
Stage 07
7. Physical NVMe Flash Wear
Total Bytes Written: 28 KB (WAF = 28.0)
02 2 · MATHEMATICAL MODELING · AMPLIFICATION FACTORS

Mathematical Derivation of Write Amplification Factor

Write amplification occurs at two independent architectural layers: the Application Storage Engine Layer ($WAF_{text{LSM}}$) and the SSD Controller Firmware Layer ($WAF_{text{SSD}}$).

The system-level Write Amplification Factor is defined as the ratio of total bytes written to physical NAND flash relative to the logical bytes submitted by the user application:

text{WAF}_{text{Total}} = text{WAF}_{text{LSM}} times text{WAF}_{text{SSD}} = frac{text{Bytes Written to Storage Engine}}{text{Logical Application Writes}} times frac{text{Physical Bytes Written to NAND Flash}}{text{Host Writes Received by NVMe}}

The Physics of NAND Flash Wear

NAND flash memory cannot overwrite existing data in place. Storage is organized into:

  • Pages (typically $4text{ KB}$ to $16text{ KB}$): The smallest unit of read and program (write) operations.
  • Blocks (typically $2text{ MB}$ to $8text{ MB}$, containing $128$ to $512$ pages): The smallest unit of erase operations.

Before a page can be rewritten with new data, the entire multi-megabyte block containing it must be erased. This requires the SSD Flash Translation Layer (FTL) to read all valid pages from the block, copy them to a freshly erased block, and perform garbage collection. If an application writes small, fragmented updates, $WAF_{text{SSD}}$ escalates rapidly from $1.2$ to over $5.0$.

When paired with an LSM-tree running default Leveled Compaction ($WAF_{text{LSM}} approx 15$ to $30$), the cumulative wear factor reaches:

text{WAF}_{text{Total}} = 25 times 2.5 = 62.5

At this rate, an ingestion pipeline processing $200text{ MB/s}$ of incoming client writes subjects the physical drive to $12.5text{ GB/s}$ of internal NAND writes, exhausting a standard 3-DWPD enterprise drive within months.

03 3 · EXPERIMENTAL TELEMETRY · COMPACTION STRATEGIES

Empirical Telemetry

Leveled vs. Size-Tiered Compaction

The choice of compaction strategy determines the fundamental trade-off between write amplification, space amplification, and read latency.

SYSTEM TOPOLOGY & ARCHITECTURE
System Architecture & Operational Pipeline
System Architecture
Stage 01
Leveled Compaction (LCS)
• Strict non-overlapping key ranges per level
• WAF: 15x – 35x (High)
• Space Amp: 1.1x – 1.2x (Low)
• Read Latency: Fast (1 SSTable per level)
Stage 02
Size-Tiered Compaction (STCS)
• Accumulates SSTables of similar size
• WAF: 2x – 8x (Low)
• Space Amp: 1.5x – 2.0x (Very High)
• Read Latency: High (Probes multiple SSTables)

Empirical Storage Telemetry Comparison

Architectural DimensionLeveled Compaction (RocksDB Default)Size-Tiered Compaction (Cassandra Default)FIFO Compaction (Time-Series Only)
Typical Write Amplification (WAF)15.0x, 30.0x2.5x, 6.0x1.0x, 1.1x
Typical Space Amplification (SAF)1.10x, 1.25x1.60x, 2.00x1.00x, 1.05x
Read Amplification (Point Lookups)$mathcal{O}(L)$ (Worst-case 1 read/level)$mathcal{O}(N)$ (Must probe all run files)High (Requires full scans)
P99 Read Latency ImpactLow ($< 2.5text{ ms}$)High ($12text{ ms} – 45text{ ms}$)Very High
NVMe Drive Wear Rate (3 DWPD)High (Depletes drive in ~18 months)Low (Preserves drive for 5+ years)Minimal (Line-rate wear)
I/O Write Stall SusceptibilityHigh (When L0 $rightarrow$ L1 falls behind)Low (Periodic heavy batch stalls)None (Drops old files)

Leveled Compaction maintains strict non-overlapping key ranges across all levels from $L_1$ to $L_{max}$. When level $L_i$ reaches capacity, one SSTable is selected and merge-sorted with all overlapping SSTables in level $L_{i+1}$. Because the amplification factor between levels is typically set to $T = 10$, every byte in level $L_i$ is rewritten alongside approximately 10 bytes in $L_{i+1}$, generating an unavoidable theoretical WAF of $mathcal{O}(T cdot L)$.

For related analysis on low-level memory allocation and CPU cache line behavior, explore our study on Fast Compilers & Data-Oriented Arenas.

04 4 · NVME PERFORMANCE · SATURATION MECHANICS

Compaction Bandwidth Scheduling & NVMe Saturation Mechanics

(Integrated from absorbed monograph: LSM Compaction Overhead: NVMe Saturation Mechanics)

The most dangerous failure mode in high-throughput LSM deployments is the Compaction Write Stall. When background compaction workers cannot merge-sort SSTables as fast as the application fills the MemTable, Level 0 accumulates un-compacted files. Because Level 0 files have overlapping key ranges, read performance collapses exponentially. To protect database stability, RocksDB and Cassandra intentionally throttle or freeze client writes until background threads catch up.

SYSTEM TOPOLOGY & ARCHITECTURE
System Architecture & Operational Pipeline
System Architecture
Stage 01
Client Writes Fill MemTable at 400 MB/s
Stage 02
Level 0 File Count Hits Threshold (e.g. 20 files)
Stage 03
Storage Engine Triggers Write Stall
Client latency spikes from 0.5ms to 2,000ms
Stage 04
Compaction Threads Awaken Simultaneously
Drive saturated at 3,500 MB/s bus bandwidth
Stage 05
PCIe Controller Submission Queue Saturates
Tail latency degrades across all collocated services
Stage 06
Stall Released; Buffer Resumes

The Physics of PCIe Queue Saturation

Modern enterprise NVMe SSDs employ the NVMe protocol over PCIe lanes (Gen 4/5), supporting up to $64,000$ submission queues with $64,000$ commands per queue. However, when background compaction threads saturate sequential write bandwidth, two hardware bottlenecks emerge:

  1. Flash Controller Channel Contention: The SSD internal multi-channel controller spends $100%$ of its duty cycle executing page program and block erase operations, delaying flash read commands initiated by concurrent client read transactions.
  2. Read Latency Tail Inversion: While average read latency remains low, 99.9th percentile read latency jumps from $150 mutext{s}$ to over $50text{ ms}$ due to queuing behind multi-megabyte compaction write bursts.

Algorithmic Mitigation: Token Bucket Rate Limiting

To eliminate write stalls and protect read latency SLAs, storage engineers must decouple compaction execution from unconstrained I/O. RocksDB provides a dedicated `RateLimiter` component implementing a token bucket algorithm to enforce hard bandwidth ceilings on compaction:

================================================================================
 ROCKSDB COMPACTION RATE LIMITER ARCHITECTURE
================================================================================
Target Ingestion Bandwidth: 150 MB/s
Available NVMe Write Bandwidth: 3,200 MB/s
Enforced Compaction Rate Limit: 600 MB/s (Cap background I/O)

Token Bucket Refill Interval: 100 microseconds
Burst Allowance: 10 MB max burst

Result:
- Flushes (MemTable -> L0) prioritized with infinite rate limit tokens.
- Compaction (L0 -> Lmax) capped at 600 MB/s.
- 2,600 MB/s remaining NVMe bandwidth reserved for client read transactions.
- Zero write stalls; P99 read latency stabilized at 1.2 ms.
================================================================================

By capping background compaction bandwidth to an empirical multiple of the steady-state ingestion rate (typically $3times$ to $4times$ the application write rate), the NVMe controller is never saturated, eliminating write stalls while extending drive operational life. For architectural comparisons with relational concurrency models, examine our analysis of Database Isolation Levels & Concurrency.

05 5 · SYSTEMS ENGINEERING · PHYSICAL INVARIANTS

Five Governing Invariants for High-Throughput LSM Storage

To optimize LSM performance while protecting hardware endurance, systems engineers must enforce five physical invariants:

================================================================================
 THE FIVE GOVERNING LAWS OF LSM NVME STORAGE
================================================================================
1. THE BANDWIDTH PARTITIONING INVARIANT
 Never allow background compaction threads to consume more than 50%
 of maximum sustained sequential device write bandwidth.

2. LEVEL 0 INLINE FLUSH SOVEREIGNTY
 MemTable flushes to Level 0 must be prioritized above all cascading
 compactions. Never rate-limit L0 flushes.

3. DYNAMIC LEVEL BASE SIZING
 Set Level 1 target size equal to the maximum aggregate size of Level 0
 to minimize the number of merge-sort passes during initial ingestion.

4. PREFIX BLOOM FILTER DOMINANCE
 Equip all SSTables with 10-bit-per-key Bloom filters to eliminate 99%
 of unnecessary disk reads during point lookups.

5. SEPARATION OF COLD HISTORICAL DATA
 Partition time-series data using FIFO or tiered storage so historical
 data is never repeatedly re-compacted alongside active mutable keys.
================================================================================
06 6 · OPERATIONAL PRAGMATISM · ENDURANCE-OPTIMIZED DESIGN

Synthesis

Engineering at the Boundary of Hardware Limits

The beauty of Log-Structured Merge-trees lies in their profound mathematical pragmatism: they trade disk space and future background compute to provide unmatched in-memory write speed. But that trade is not free. When an engineering team ignores Write Amplification Factor, they convert an algorithmic optimization into a physical hardware liability.

True software architecture does not treat the underlying physical medium as an infinite abstract buffer. It respects the physical realities of NAND gate oxide breakdown, Flash Translation Layer garbage collection, and PCIe controller queue dynamics. By pairing disciplined compaction scheduling with precise rate-limiting invariants, distributed systems achieve the holy grail of high-throughput data engineering: blistering ingestion velocity, deterministic read latency, and multi-year hardware resilience.

Governing Empirical Axiom

The performance of an LSM-tree is not defined by how fast it writes data into RAM; it is defined by how intelligently it organizes data before the physical silicon wears out.

Curated Inquiry Series • 10 Investigations

Memory Arena Allocation

An empirical exploration through compiler performance engineering, monotonic memory arenas, cache line data locality, and fast toolchain architecture.

Primary Scholarly Provenance & Empirical Attribution
Card, S. K., Moran, T. P., & Newell, A. (1983). The Psychology of Human-Computer Interaction. Lawrence Erlbaum Associates; ACM SIGCHI Model of Human Processor & Saccadic Latency Foundations.
DOI: 10.1145/358896.358899