LSM trees and compaction

In a typical RocksDB path, a write is recorded in a WAL when enabled and inserted into a memory structure called a memtable. A full memtable becomes immutable and is flushed to a sorted table file. A newer value for the same key may coexist with older values in other runs. A point lookup must find the visible newest version while respecting sequence numbers, snapshots, and deletions; reading the first physical occurrence without that ordering would be incorrect.

Sorted runs support sequential construction and range scans, but several runs can overlap in key space. Bloom filters can reject many files that definitely do not contain a queried key, with possible false positives. They do not normally prove presence or return the current value. Cache and file counts change read cost. A filter tuned for point lookups may not address a workload dominated by long scans.

Leveled compaction organizes increasingly large levels and merges overlapping ranges; within ordinary nonzero leveled levels, sorted files are nonoverlapping in key range. Level zero can contain overlapping flush files. Other policies keep different numbers of sorted runs, changing read, write, and space amplification. There is no universal best policy independent of update rate, read mix, storage capacity, and latency objectives. Measure steady-state behavior after the dataset reaches its realistic size.

Deleting a key usually writes a tombstone rather than instantly finding and removing every old value. Compaction can discard obsolete versions only when snapshots and deeper data no longer require them. Dropping a tombstone prematurely can expose an older value that still survives in another run. Long-lived snapshots therefore affect retained history, while compaction filters and retention features require explicit application semantics. Reclaiming bytes and preserving historical reads are competing obligations, not merely cleanup preferences.

Incoming writes create future merge work. If the storage device spends all its bandwidth accepting flushes, debt can accumulate until file counts, read work, or space consumption force stalls. Reserve headroom for compaction and observe pending bytes, level-zero files, write stalls, and foreground latency together. Rate limiting background I/O can protect readers temporarily, but a permanently insufficient merge budget cannot be repaired by throttling alone. Compression also trades CPU time against stored bytes and bandwidth.

A fluid debt model helps separate a temporary burst from an unstable workload. Let the arrival rate mean generated compaction work, not user-request bytes, and estimate it from the chosen policy under representative updates. Completion capacity depends on the same CPU and disk resources used by queries, so it need not remain constant. Validate recovery after a write burst, and test disk space during overlapping old and new runs; the final compacted size can substantially understate the peak space requirement.