How LSM Tree Leveled Compaction Internals Actually Work
A deep technical guide to LSM tree leveled compaction internals, scoring algorithms, K-way merge iterators, tombstone GC, and amplification tradeoffs.
Introduction
Modern storage engines rely on Log-Structured Merge (LSM) trees to transform random application writes into sequential disk I/O. However, unconstrained writes quickly degrade read latency and bloat storage utilization through superseded key versions and orphaned deletion markers. To maintain bounded read latency and reclaim space, storage engines enforce periodic background data reorganizations.
Among data organization strategies, LSM tree leveled compaction stands as the industry standard for read-heavy and balanced key-value workloads. By enforcing strict, non-overlapping key ranges across hierarchical levels, leveled compaction bounds read amplification and minimizes storage overhead, albeit at the cost of elevated write amplification.
Understanding how leveled compaction operates at the byte, file, and iterator levels is essential for diagnosing write stalls, tail latencies, and storage amplification in production systems. This article dissects the algorithmic foundations, execution pipelines, scoring heuristics, and synchronization mechanisms governing modern leveled compaction implementations.
Anatomy of LSM Tree Leveled Compaction
An LSM storage engine decouples foreground writes from disk persistence using an in-memory buffer (MemTable) paired with a Write-Ahead Log (WAL). When the MemTable reaches capacity (typically 64 MB to 256 MB), it becomes immutable and flushes to disk as a Sorted String Table (SSTable) file at Level 0 ($L_0$).
+-------------------------------------------------------------+
| MemTable (Active) |
+-------------------------------------------------------------+
| (Flush)
v
+-------------------------------------------------------------+
| Level 0 |
| [File 1: A - M] [File 2: D - Z] [File 3: B - P] | <-- Overlapping Key Ranges
+-------------------------------------------------------------+
|
| (L0 -> L1 Compaction)
v
+-------------------------------------------------------------+
| Level 1 |
| [File 10: A - C] [File 11: D - H] [File 12: I - Z] | <-- Partitioned, Non-Overlapping
+-------------------------------------------------------------+
|
| (L1 -> L2 Compaction, 10x Capacity)
v
+-------------------------------------------------------------+
| Level 2 |
| [File 20: A - B] [File 21: C - E] ... [File 29: W - Z] | <-- Partitioned, Non-Overlapping
+-------------------------------------------------------------+
The structural contrast between Level 0 and deeper levels forms the core design principle of LSM tree leveled compaction:
- Level 0 (Unpartitioned / Overlapping): Because each $L_0$ file represents a direct point-in-time flush of an entire
MemTable, key ranges across $L_0$ files inevitably overlap. Reading a key from $L_0$ requires probing every $L_0$ file whose range covers the requested key—an $O(N)$ operation relative to the number of $L_0$ files. - Levels $L_1$ to $L_{max}$ (Partitioned / Disjoint): Every level $L_i$ where $i \ge 1$ guarantees that files have mutually exclusive, sorted key ranges. SSTable boundaries are strictly non-overlapping:
$$\forall j < k \implies \max(\text{KeyRange}(F_{i,j})) < \min(\text{KeyRange}(F_{i,k}))$$
This invariant simplifies point lookups. To locate a key at level $L_i$ ($i \ge 1$), the engine performs an in-memory binary search across the level's file metadata array to identify the exact SSTable containing the key range. It then evaluates that single SSTable via Bloom filters and index blocks.
Compaction Trigger Mechanics and Level Scoring
Leveled compaction executes as an asynchronous control loop driven by a priority score. Storage engines evaluate compaction candidates by computing a normalized compaction score $S_i$ for every level:
+-------------------------------+
| Compute Scores Across Levels |
+-------------------------------+
|
v
+-------------------------------+
| Find Level with Max Score |
+-------------------------------+
|
Score > 1.0? / \ No
/ \
Yes / \
v v
+----------------+ +-------------------+
| Trigger Worker | | Yield / Sleep |
+----------------+ +-------------------+
Level 0 Trigger Score
Because $L_0$ lookups scale with file count rather than raw byte volume, $L_0$ is evaluated by file count:
$$S_0 = \frac{N_{L0}}{\text{level0_file_num_compaction_trigger}}$$
If level0_file_num_compaction_trigger is set to 4, an $L_0$ count of 8 yields $S_0 = 2.0$, immediately queueing an $L_0 \to L_1$ compaction. If writes continue faster than the compaction thread can process them, $L_0$ reaches a hard ceiling (e.g., 20 files or 32 files), triggering a write stall that throttles client write operations to prevent unbounded read latency degradation.
Deeper Levels ($L_i \ge 1$) Capacity Sizing
For levels $L_1$ through $L_{max}$, scores depend on aggregate byte capacity:
$$S_i = \frac{\sum_{f \in L_i} \text{SizeBytes}(f)}{\text{TargetBytes}(L_i)}$$
Target capacities follow an exponential geometric progression governed by the level amplification factor $T$ (typically set to 8 or 10):
$$\text{TargetBytes}(L_i) = \text{TargetBytes}(L_1) \times T^{i-1}$$
Assuming $\text{TargetBytes}(L_1) = 256\text{ MB}$ and $T = 10$:
- $L_1 = 256\text{ MB}$
- $L_2 = 2.56\text{ GB}$
- $L_3 = 25.6\text{ GB}$
- $L_4 = 256\text{ GB}$
- $L_5 = 2.56\text{ TB}$
Modern engines optimize this calculation through dynamic level base sizing. If the actual payload on disk only populates up to 30 GB (fitting inside $L_3$), enforcing a fixed 256 MB $L_1$ causes unnecessary rewrites through empty intermediate levels. Instead, the engine dynamically anchors the largest level ($L_{max}$) to the total user data size, working backward by factor $T$ to establish base capacities.
Storage engines manage these operations with minimal foreground impact by using asynchronous I/O architectures. Analyzing How io_uring Submission Queue Polling Actually Works illustrates how modern storage backends dispatch high-throughput block reads and writes while preventing thread-pool context thrashing.
The K-Way Merge Pipeline and Tombstone GC
Once a level qualifies for compaction ($S_i > 1.0$), the compaction scheduler selects one or more files from $L_i$ and identifies all overlapping files in $L_{i+1}$.
Level i Input: [ File A: [100 - 250] ]
|
(Find Overlapping Key Ranges)
v
Level i+1 Inputs: [File B: [80 - 150]] [File C: [151 - 300]]
|
v
+----------------------------------+
| K-Way Merge Sort Engine |
| (Min-Heap / Priority Queue) |
+----------------------------------+
|
+------------------+------------------+
| |
v v
MVCC Version Deduplication Tombstone Purging
(Drop versions older than (Verify absence of key
oldest active snapshot) in Levels i+2 to L_max)
| |
+------------------+------------------+
|
v
+----------------------------------+
| Output Chunks to Level i+1 |
| [New File 1] [New File 2] |
+----------------------------------+
1. Range Expansion
If file $F \in L_i$ spans keys [100, 250], the scheduler searches $L_{i+1}$ for files whose ranges intersect [100, 250]. If $L_{i+1}$ contains File B [80, 150] and File C [151, 300], both become inputs to the compaction task.
The expanded input boundary now covers [80, 300]. If this occurs during an $L_0 \to L_1$ compaction, the scheduler re-scans $L_0$ to gather any other files intersecting [80, 300], preventing range-inversion bugs during manifest commit.
2. Multi-Way Merge Sort
The compaction job initializes a min-heap iterator over the selected input SSTables. Each entry in the iterator is an internal key structured as:
$$\text{InternalKey} = \langle \text{UserKey}, \text{SequenceNumber}, \text{OpType} \rangle$$
Where:
UserKey: Raw application key bytes.SequenceNumber: Monotonically increasing 64-bit integer representing logical commit order.OpType: Value type flag (TypePut,TypeDelete,TypeMerge, etc.).
The comparison comparator orders internal keys using:
UserKeyascending.SequenceNumberdescending.
This sorting ensures that for any unique UserKey, the iterator encounters its most recent update first.
3. MVCC Snapshot Retention
If an application executes with active read snapshots, obsolete key versions cannot simply be discarded. The merge pipeline compares the internal key's SequenceNumber against a sorted array of active snapshot identifiers.
If multiple versions of UserKey exist between two snapshot identifiers, only the highest sequence number in that snapshot bracket is preserved. All older versions preceding the lowest snapshot boundary are discarded.
4. Tombstone Garbage Collection Rules
Deletions in an LSM tree do not erase data in place; they append a tombstone (TypeDelete). Dropping a tombstone prematurely causes resurrected data:
> Data Resurrection Invariant: A tombstone at level $L_i$ can be eliminated if and only if no level $L_k$ (where $k > i+1$) contains an earlier version of that UserKey.
If the tombstone compaction spans up to $L_{i+1}$, and the engine verifies that the key range [k_min, k_max] does not appear in $L_{i+2} \dots L_{max}$, the tombstone marker can be safely deleted. If an older version might exist in deeper levels, the tombstone must be written to the output files at $L_{i+1}$ to ensure it continues shadowing older records during lookups.
To coordinate concurrent foreground writers with background manifest updates without race conditions, engines rely on lightweight coordination mechanisms. For low-overhead concurrency models, review Designing Lock-Free Shared-Memory Ring Buffers: Cache-Coherence, Memory Barriers, and Kernel-Bypass IPC and High-Throughput Deterministic Actor Runtimes: Cache-Conscious Architectures, Lock-Free Rings, and Kernel-Bypass I/O.
Algorithmic Implementation: C++20 Compaction Iterator
The following C++20 implementation demonstrates the core merge-processing logic executed within an LSM compaction task. It tracks active snapshots, filters superseded sequence numbers, and evaluates tombstone eligibility across level boundaries.
#include
#include
#include
#include
#include
#include
#include
enum class ValueType : uint8_t {
kTypeValue = 1,
kTypeDeletion = 2
};
struct InternalKey {
std::string user_key;
uint64_t sequence_number;
ValueType type;
// Sort order: UserKey ascending, SequenceNumber descending
bool operator>(const InternalKey& other) const {
if (user_key != other.user_key) {
return user_key > other.user_key;
}
return sequence_number < other.sequence_number; // Descending seqno
}
};
struct ParsedEntry {
InternalKey key;
std::string value;
size_t source_input_index;
};
class SSTableIterator {
public:
virtual ~SSTableIterator() = default;
virtual bool Valid() const = 0;
virtual void Next() = 0;
virtual ParsedEntry Current() const = 0;
};
class CompactionMergeIterator {
public:
CompactionMergeIterator(
std::vector> iterators,
std::vector active_snapshots,
uint64_t earliest_snapshot,
bool at_bottom_level
) : active_snapshots_(std::move(active_snapshots)),
earliest_snapshot_(earliest_snapshot),
at_bottom_level_(at_bottom_level) {
std::sort(active_snapshots_.begin(), active_snapshots_.end());
for (size_t i = 0; i < iterators.size(); ++i) {
if (iterators[i]->Valid()) {
heap_.push({iterators[i]->Current(), i});
}
iters_ = std::move(iterators);
}
}
struct OutputRecord {
InternalKey key;
std::string value;
};
std::optional NextKey() {
while (!heap_.empty()) {
HeapElement top = heap_.top();
heap_.pop();
ParsedEntry current = top.entry;
size_t input_idx = top.source_index;
// Advance the iterator that provided this element
iters_[input_idx]->Next();
if (iters_[input_idx]->Valid()) {
heap_.push({iters_[input_idx]->Current(), input_idx});
}
bool is_new_user_key = !has_last_key_ || last_user_key_ != current.key.user_key;
if (is_new_user_key) {
last_user_key_ = current.key.user_key;
has_last_key_ = true;
last_retained_seq_ = UINT64_MAX;
}
// Determine if this entry is visible to any active snapshot
uint64_t seq = current.key.sequence_number;
auto snap_it = std::lower_bound(active_snapshots_.begin(), active_snapshots_.end(), seq);
uint64_t snapshot_boundary = (snap_it != active_snapshots_.end()) ? *snap_it : UINT64_MAX;
// Drop version if obscured by a newer record in the same snapshot bracket
if (!is_new_user_key && snapshot_boundary == last_retained_seq_) {
continue; // Suppressed: Obsolete MVCC version
}
// Evaluate deletion tombstone garbage collection
if (current.key.type == ValueType::kTypeDeletion) {
// If this is the oldest version visible to the earliest snapshot,
// and we are at the bottom-most level where this key exists, GC it.
if (seq <= earliest_snapshot_ && at_bottom_level_) {
continue; // Dropped: Tombstone will not expose older records
}
}
last_retained_seq_ = snapshot_boundary;
return OutputRecord{current.key, current.value};
}
return std::nullopt;
}
private:
struct HeapElement {
ParsedEntry entry;
size_t source_index;
bool operator>(const HeapElement& other) const {
return entry.key > other.entry.key;
}
};
std::priority_queue, std::greater> heap_;
std::vector> iters_;
std::vector active_snapshots_;
uint64_t earliest_snapshot_;
bool at_bottom_level_;
bool has_last_key_ = false;
std::string last_user_key_;
uint64_t last_retained_seq_ = UINT64_MAX;
};
Amplification Tradeoffs: Write, Read, and Space Bounds
LSM tree leveled compaction navigates trade-offs governed by the RUM Conjecture (Read, Update, Memory/Space). Balancing these metrics requires tuning structural parameters to match system hardware profiles.
Write Amplification Factor (WAF)
/\
/ \
/ \ <--- Leveled Compaction Design Point
/ \ (Low RAF, Low SAF, High WAF)
/________\
Read Amplification Space Amplification
Factor (RAF) Factor (SAF)
1. Write Amplification Factor (WAF)
Write Amplification measures the bytes written to non-volatile storage relative to bytes ingested by client operations:
$$\text{WAF} = \frac{\text{Bytes Written to Storage}}{\text{Bytes Written by Application}}$$
In leveled compaction, when a file moves from $L_i$ to $L_{i+1}$, its key range intersects an average of $T$ files in $L_{i+1}$ (where $T \approx 10$). The compaction task reads these intersecting files, merges them, and rewrites the data into $L_{i+1}$.
As a result, each byte is rewritten approximately $T$ times per level jump:
$$\text{WAF}_{\text{leveled}} \approx 1 + T \times L$$
For a 6-level database with $T = 10$, empirical WAF often hovers between 20 and 40. This is significantly higher than Size-Tiered Compaction Strategy (STCS), where $\text{WAF}_{\text{tiered}} \approx O(L)$. The elevated write rate accelerates flash cell wear and consumes significant storage controller bandwidth.
2. Space Amplification Factor (SAF)
Space Amplification captures storage overhead caused by redundant versions and deletion tombstones:
$$\text{SAF} = \frac{\text{Total Database Size on Disk}}{\text{Uncompressed Size of Live Data}}$$
Leveled compaction excels at space reclamation. Because levels expand geometrically ($L_i = T \times L_{i-1}$), the bottom level ($L_{max}$) holds roughly $90%$ of all data, while $L_{max-1}$ holds $9%$, and all preceding levels combined constitute less than $1%$.
Even if levels $L_0$ through $L_{max-1}$ contain entirely duplicate versions of keys in $L_{max}$, the maximum space amplification remains bounded:
$$\text{SAF}_{\text{leveled}} \approx 1 + \frac{1}{T} \approx 1.11 \quad (\text{for } T = 10)$$
This bounded overhead contrasts with Size-Tiered Compaction, which can require up to $100%$ spare capacity ($\text{SAF} \approx 2.0$) to accommodate side-by-side rewriting of full tiers during major compactions.
3. Read Amplification Factor (RAF)
Read Amplification is measured as the number of storage reads (or logical block scans) required to service a single point or range query:
$$\text{RAF} = \frac{\text{Bytes Read from Storage}}{\text{Bytes Returned to Application}}$$
By enforcing disjoint key intervals, leveled compaction simplifies point queries. For any read operation:
- The engine checks $L_0$, which may require querying up to $N_{L0}$ files (mitigated by Bloom filters).
- At each deeper level ($L_1 \dots L_{max}$), the key can reside in at most one SSTable.
With an optimized Bloom filter allocated at 10 bits per key, the false positive rate (FPR) is:
$$p \approx 0.6185^{\frac{m}{n}} \approx 0.01 \quad (1%)$$
The expected number of disk reads for a non-existent key across $L$ levels is bounded by:
$$\mathbb{E}[\text{Disk Probes}] \le p \times N_{L0} + \sum_{i=1}^{L} p \approx 0.01 \times 4 + 6 \times 0.01 = 0.10$$
This deterministic bound prevents read thrashing during random point lookup workloads.
Commit Phase: The Atomic VersionEdit Protocol
Generating new SSTables on disk does not instantly change visible database state. A compaction task must register the new files and retire superseded files atomically. LSM engines manage this transition using a VersionSet coordination model.
Active Version: V_curr
- L1 Files: {F1, F2}
- L2 Files: {F10, F11, F12}
|
| Compaction completes:
| Deleted: L1 {F1}, L2 {F10, F11}
| Added: L2 {F20, F21}
v
VersionEdit Record:
- Drop: (L1, F1), (L2, F10), (L2, F11)
- Add: (L2, F20), (L2, F21)
|
v
+---------------------------------------------+
| Write VersionEdit to MANIFEST File (fsync) |
+---------------------------------------------+
|
v
Install New Version: V_next
- Retain V_curr while active iterators read it
- Unlink deleted files once V_curr refcount drops to 0
The commit pipeline executes the following sequence:
- Construct
VersionEditDelta: The compaction thread builds a changeset object detailing the input files marked for unlinking and newly written SSTable paths, checksums, and boundaries. - Log to Manifest: The engine appends the
VersionEditrecord to the persistentMANIFESTlog file and invokesfsync(). This disk write serves as the atomic commit barrier. If the machine crashes prior to this log write, the newly generated SSTables are cleaned up as orphaned files on reboot. - Advance Pointer to
VersionSet: Upon disk sync, the engine registers a new internal state object (Version(n+1)) and increments its reference count. - Asynchronous Garbage Collection: Older SSTables marked for deletion cannot be unlinked immediately if concurrent read queries hold references to
Version(n). When those reader references release, the parentVersiondecrements to zero, safe-deleting the underlying physical files without read-path locks.
Conclusion
LSM tree leveled compaction provides a predictable structural framework for data storage by trading elevated write amplification for bounded space usage and predictable read latencies. Its core design rules—non-overlapping boundaries across levels $L_1 \dots L_{max}$, geometric capacity scaling, deterministic merge loops, and coordinated manifest delta commits—ensure reliable database behavior across sustained workloads.
As high-capacity NVMe drives, Zoned Namespaces (ZNS), and kernel-bypass I/O architectures become standard infrastructure, the implementation details of compaction continue to evolve. Modern storage engines frequently decouple key-value payloads to minimize compaction write overhead, implement tiered hybrid storage, or adaptively dynamically re-tune $T$ under write pressure. Nevertheless, the algorithmic foundations of leveled compaction remain central to the architecture of high-performance persistent systems.
References
- RocksDB Leveled Compaction Architecture: https://github.com/facebook/rocksdb/wiki/Leveled-Compaction
- LevelDB Implementation Notes: https://github.com/google/leveldb/blob/main/doc/impl.md
- WiscKey: Separating Keys from Values in SSD-conscious Storage: https://www.usenix.org/conference/fast16/technical-sessions/presentation/lu