In Log-Structured Merge-tree (LSM-tree) storage engines, data is initially buffered in an in-memory structure (the memtable) and then flushed to disk as immutable Sorted String Tables (SSTables). Over time, these SSTables accumulate across multiple levels, and the storage engine must periodically merge them to reclaim space, remove deleted or overwritten entries, and maintain efficient read performance. This process is called compaction.
Linear merge compaction is the foundational mechanism underlying all LSM-tree compaction strategies. It exploits the fact that SSTables are individually sorted — meaning that merging multiple sorted files into a single sorted output can be accomplished with a simple linear scan through each file simultaneously, identical to the merge step in merge sort. This is an O(N) operation where N is the total number of entries across all input SSTables.
Understanding compaction is essential for AI engineers because vector databases like Weaviate and Milvus, as well as key-value stores like RocksDB and Pebble that back many AI infrastructure systems, all rely on LSM-tree compaction to maintain performance under heavy write workloads typical of embedding ingestion pipelines.
Each SSTable on disk is already sorted by key. When the storage engine needs to combine multiple SSTables, it opens all input files simultaneously and maintains a pointer (or iterator) at the beginning of each file. At every step, it compares the current key at each pointer, selects the smallest (or largest, depending on sort order), writes it to the output SSTable, and advances that pointer. This is exactly the merge phase of the classic merge sort algorithm.
Given k sorted SSTables with a combined total of N entries, the merge operation runs in O(N log k) time using a min-heap to efficiently select the next smallest key across all k inputs. When k is small (e.g., 2–4 SSTables), the overhead is effectively linear in N.
During the merge, when the same key appears in multiple input SSTables, the engine keeps only the most recent version (determined by a sequence number or timestamp). Deleted keys are represented by special markers called tombstones. During compaction, if a tombstone exists and no older version of that key survives in deeper levels, the key and its tombstone are both dropped from the output — reclaiming disk space.
While the linear merge operation itself is constant, LSM-tree engines differ in when and which SSTables they choose to merge. The two classical strategies are:
SSTables of similar size are grouped into tiers. When enough SSTables of a given size accumulate (typically 4), they are merged together into a single larger SSTable. This minimizes write amplification — each byte is rewritten approximately O(log N) times over its lifetime — but increases read amplification because multiple overlapping SSTables at each tier must be checked during reads.
SSTables are organized into levels with exponentially increasing capacity (e.g., Level 1 holds 10 SSTables, Level 2 holds 100). Within each level, SSTables have non-overlapping key ranges. When a level overflows, one SSTable is selected and merged with the ~10 overlapping SSTables in the next level. This produces excellent read performance (typically only one SSTable per level needs to be checked) but increases write amplification to approximately O(10 × levels).
Every compaction strategy navigates a three-way tradeoff: write amplification (how many times each byte is rewritten), read amplification (how many SSTables must be consulted per read), and space amplification (how much temporary disk overhead compaction requires). No strategy can minimize all three simultaneously — this is known as the RUM conjecture.
Consider a leveled compaction where an SSTable at Level 1 overlaps with 10 SSTables at Level 2. The engine performs the following steps:
// Pseudocode: k-way merge of sorted SSTables
func mergeCompact(inputs []SSTableIterator) []SSTable {
heap := NewMinHeap()
for i, iter := range inputs {
if iter.Valid() {
heap.Push(HeapEntry{key: iter.Key(), seq: iter.Seq(), source: i})
}
}
writer := NewSSTableWriter()
var lastKey []byte
for heap.Len() > 0 {
entry := heap.Pop()
// Skip older versions of the same key
if !bytes.Equal(entry.key, lastKey) {
if !entry.isTombstone() {
writer.Add(entry.key, entry.value)
}
lastKey = entry.key
}
// Advance the source iterator
inputs[entry.source].Next()
if inputs[entry.source].Valid() {
heap.Push(HeapEntry{
key: inputs[entry.source].Key(),
seq: inputs[entry.source].Seq(),
source: entry.source,
})
}
}
return writer.Finish()
}Modern engines like RocksDB and Pebble don’t compact entire levels at once. Instead, they use file-level granularity — selecting individual SSTable files for compaction based on heuristics such as:
Compaction runs in background threads with rate limiting to prevent I/O starvation of foreground read and write operations. Pebble, for example, uses a concurrency-controlled compaction scheduler that can run multiple compactions simultaneously across different level pairs.
When ingesting millions of document embeddings into an AI system backed by a key-value store (like Weaviate’s use of LSM-based storage), the write-heavy workload produces many SSTables rapidly. Without well-tuned compaction, read latency degrades because the engine must search through an ever-growing number of files. Size-tiered compaction suits the initial bulk load, while leveled compaction is preferred for the steady-state query serving phase.
RocksDB is the storage engine behind many AI infrastructure components, from feature stores to metadata indexes. Its default leveled compaction uses the linear merge operation thousands of times per day in a busy system. Engineers tune parameters like max_bytes_for_level_base (size of Level 1, typically 256 MB), max_bytes_for_level_multiplier (growth factor, typically 10), and target_file_size_base (individual SSTable size, typically 64 MB) to balance write throughput and read latency.
In a leveled compaction scheme with a multiplier of 10, the worst-case write amplification is approximately 10 × number_of_levels. For a database storing 1 TB of data with 64 MB SSTables and a 256 MB Level 1, you get roughly 5 levels, yielding a worst-case write amplification of ~50×. This means each byte of user data may be written to disk up to 50 times over its lifetime — a critical consideration for SSD endurance and I/O budgeting in AI infrastructure.
If compaction cannot keep up with the write rate, the system enters a compaction stall — writes are throttled or blocked entirely while the engine catches up. This manifests as tail latency spikes in embedding pipelines and must be monitored via metrics like rocksdb.compaction.pending and rocksdb.stall.micros.
O(N log k) merge of k sorted SSTables — the fundamental building block of all LSM-tree compaction strategies.