LSM-tree compaction works by replacing selected sorted files with a new representation that is better organised while preserving the read results the storage engine still promises to support. It can reduce overlapping search work and reclaim obsolete versions, but it must not discard a value or deletion marker that another valid read still needs.
The difficult word is obsolete. A value hidden from the latest reader may still be needed by an older snapshot. A deletion marker may still be suppressing a value in a file that this compaction is not reading. A replacement output may be complete but not yet safely installed. Compaction is therefore a correctness problem before it is a space-saving operation.
This guide explains file selection, sorted merging, leveled and tiered layouts, snapshot retention, tombstone safety, publication, resource budgets and practical verification. It continues How LSM Trees Work, How Memtables Work and How SSTables Work.
The Direct Answer: Reorganise Files Without Rewriting History
Several SSTables can contain overlapping keys and different versions of the same key. A compaction selects a set of inputs, reads them in order, decides which entries must survive, builds new table outputs and installs a new file-set version.
The logical catalogue need not change at all. If camera-2 was reserved before ordinary compaction, it remains reserved afterward for the same read view. If an active older snapshot saw available, that snapshot must still see available. Maintenance changes representation, not the meaning of a previously committed operation.
RocksDB’s Compaction documentation describes multiple policies rather than one universal algorithm. The explanation here starts from a common versioned key-value model. Product-specific expiry filters, merge operators and distributed repair semantics need their own contracts and must not be smuggled into the basic preservation rule.
Why Compaction Exists Even When Every File Is Already Sorted
Sorting is local to each file or run. Ten individually sorted files can all contain camera-2. A point lookup may need to inspect several of them, and a range scan may need to merge their results.
Old values and deletion markers also consume space. Some remain essential; others become removable once visibility and coverage conditions allow it. Without maintenance, the engine can accumulate more physical history and overlapping sources than the workload needs.
Compaction addresses this organisation cost. However, “sorted plus sorted” does not automatically mean “one latest value per key.” The merge must preserve all supported read views. The distinction between ordering and retention explains why an ordinary merge-sort exercise is only part of the algorithm.
Separate Policy From Mechanism
The policy decides which files to process, when to run, how much work to permit and where outputs belong. The mechanism reads entries, merges ordered streams, applies retention rules, builds output files and publishes the replacement.
This separation is useful for debugging. If the outputs contain the wrong visible versions, the correctness mechanism is suspect. If outputs are correct but the backlog grows indefinitely, selection or resource allocation may be inadequate. If foreground reads become slow during maintenance, the job may be consuming shared resources too aggressively.
A large number of configuration options can obscure these two layers. Start with the actual job: what inputs did it choose, what property justified discarding each record, and what resources did it consume? Those questions are more informative than assuming a policy name guarantees good behaviour.
A Sorted Run Can Contain More Than One File
A run is an ordered collection that can be searched as one sorted sequence. It may be stored in a single file or divided into non-overlapping key-range files. A run count and a file count are therefore different metrics.
This matters when reading descriptions of tiered or universal compaction. Merging several runs does not necessarily create one enormous output file. The result can be a run split into manageable file ranges.
RocksDB’s Universal Compaction guide explicitly describes runs that can be represented by an L0 file or a range-partitioned level. Avoid equating every box in a conceptual diagram with exactly one physical file. The abstraction represents ordering and overlap; the file boundaries represent storage granularity.
Leveled Compaction Controls Overlap Within Deeper Levels
In RocksDB’s documented leveled layout, level zero can contain overlapping files from flushes. Each deeper level is organised as one sorted run, partitioned into files with non-overlapping key ranges. A selected file range is merged with the relevant overlapping range in a destination level.
This organisation helps bound file candidates within a level. It does not mean a key has only one version across the entire database. The key can still occur in memory and other levels, subject to the engine’s version rules.
Use the official leveled-compaction description for that concrete policy. Its layout should not be presented as the definition of every LSM engine. Other policies deliberately permit more overlapping runs, and the trade-offs change accordingly.
Tiered Policies Combine Runs at Selected Size or Count Thresholds
A tiered approach can allow several runs to accumulate before combining them. Grouping similarly sized inputs is one way to avoid repeatedly rewriting a much larger run for every small arrival.
The cost is that reads may face more overlapping candidates and merges can require substantial temporary space. The exact balance depends on run selection, size ratios, workload and retention. Cassandra’s Size-Tiered Compaction Strategy and RocksDB’s universal policy are related examples, not interchangeable specifications.
The useful question is how long the system tolerates multiple runs before paying to combine them. Delaying consolidation can reduce immediate rewrite work. Delaying forever leaves readers and storage to absorb an expanding organisation cost. A policy schedules that trade rather than abolishing it.
Worked File Selection: Why Key-Range Overlap Matters
Consider a teaching layout with a recent file covering keys 20 through 70. A destination level has files covering 0–29, 30–59 and 60–89. All three destination files overlap the recent file’s range.
A leveled merge that incorporates the recent range must account for those overlaps under its layout rules. Looking only at the destination file containing key 20 would miss existing versions and boundaries farther through the range.
File boundaries affect how much surrounding data is read and rewritten. Even if the recent changes touch only a few keys, their range can overlap substantial existing files. This is one reason compaction cost cannot be estimated solely from the number of newly written records. The physical layout determines the amount of neighbouring data involved in the job.
Merging Sorted Streams Is the Easy Part to See
Each input supplies entries in its internal order. A merge iterator repeatedly selects the next key/version from the candidate streams. Entries for one user key can then be considered together before output moves to the next key.
A priority queue is one possible implementation for choosing among r streams. In a simplified model, processing E physical entries costs on the order of E log r selection comparisons, plus decoding, visibility checks and output work. This is not a universal performance formula for production engines.
The harder decision comes after gathering versions: which ones can be discarded? Sorting gives the algorithm an efficient encounter order. It does not supply the authority to forget history. That authority comes from snapshot, deletion, transaction and coverage rules.
The Central Invariant: Preserve Every Required Read View
For ordinary representation-preserving compaction, compare the database before and after at every snapshot the engine is still required to support. Point reads and range scans should return equivalent logical results.
RocksDB’s Snapshot documentation states that compaction preserves data visible to snapshots. That requirement explains why an old value can survive even after a newer value has been written.
The invariant is stronger than “latest lookup works after the merge.” It also covers old snapshots, logical absence, complete range results and version ordering. A compaction that returns the right latest value for one sampled key can still be wrong elsewhere. Good tests compare independently computed views, not just file size or the presence of a few newest entries.
Worked Version History: Four Different Correct Answers
Use a fictional key camera-2. Sequence 26 writes available. Sequence 36 writes reserved. Sequence 46 deletes it. Sequence 51 writes repaired. Assume a read at S sees the newest operation with sequence no greater than S.
At S=32, the answer is available. At S=40, it is reserved. At S=49, the key is absent. At S=55, it is repaired. These are four correct results for the same user key at four different views.
If all four views remain required, retaining only sequence 51 destroys three of them. Keeping 26, 36 and 51 but dropping the deletion at 46 also fails: the read at 49 can return reserved instead of absence. A deletion marker can be required even when a newer value exists. The example makes retention a visible correctness question rather than an aesthetic preference for fewer records.
When Can an Older Value Be Removed?
An older version can be removed only when the engine can prove that no supported read or recovery obligation requires it. In a simple complete-history teaching model, one can identify which version answers each retained snapshot and the latest view, then retain the necessary representatives.
That model is not a complete production compaction algorithm. Real jobs may see only a subset of files, handle merge records, process range deletions or coordinate with transactions. The set of required readers can also change while the job runs, so the engine needs a well-defined snapshot of its own retention obligations.
The safe principle is narrower and more durable: absence of demand from the latest reader is not proof of global obsolescence. Every deletion of physical history needs a justified visibility argument. When the proof is incomplete, retaining the record is conservative; silently discarding it is not.
Why a Tombstone Cannot Always Be Removed With Its Matching Value
Suppose the selected inputs contain camera-2 reserved at 36 and a deletion at 46. A deeper, unselected file still contains available at 26. Removing both selected entries can expose 26 to a latest read.
The merger has removed one old value and its deletion marker, but it has not removed every older value the marker was suppressing. A local pairwise cancellation is therefore unsafe.
LevelDB’s implementation notes describe tombstone dropping in relation to possible overlapping data in higher-numbered levels. The general obligation is to rule out resurrection from surviving sources and satisfy snapshot requirements. A tombstone is removable when its suppressing role is no longer needed, not merely when it happens to meet one previous value during a merge.
Deleting Data and Erasing Every Physical Copy Are Different Jobs
A visible deletion can take effect before compaction reclaims old bytes. Even after active files are replaced, older copies can remain in snapshots, backups, replicas or storage-level remnants governed by other mechanisms.
Compaction should therefore not be advertised as universal secure erasure. Its immediate purpose is to maintain the engine’s logical and physical representation under its documented rules. A requirement to remove every recoverable copy needs a broader, explicitly defined lifecycle.
For our catalogue, latest lookup returning absent proves only the query result. It does not prove that a backup no longer contains the item or that a disconnected replica has learned the deletion. Keeping those claims separate prevents a storage-maintenance operation from being credited with guarantees it was never designed to provide.
Distributed Tombstone Retention Adds Repair Obligations
In a replicated database, an unavailable node may still hold an older value. Deletion information may need to survive long enough for that node to reconcile correctly rather than reintroduce the value later.
Apache Cassandra documents grace periods, overlap conditions and repaired-data considerations in its Tombstones guide. These are Cassandra-specific rules, not universal LSM settings.
The transferable lesson is that safe forgetting depends on every place older information can return from. A local compaction may have complete coverage of local files and still need a distributed retention policy. Never lower a retention setting merely because deletion markers occupy space without understanding the failure and repair assumptions that made the setting necessary.
Time-Based Expiry Is Not Automatically a File-Deletion Permission
An application may assign a time to live to records. Their expiry can make them logically invisible, but the engine still needs to handle any versions or tombstones required by its read and replication rules.
Time-window compaction can group compatible time-oriented data so that whole expired runs become easier to reclaim. Cassandra’s Time Window Compaction Strategy describes one such policy.
Late-arriving records and mixed lifetimes complicate the clean picture. A file containing mostly expired data can still contain a live entry or a marker suppressing an older value elsewhere. Treat time windows as a workload and layout strategy, not a universal shortcut around correctness checks.
Output Boundaries Shape Future Work
A compaction may emit several files rather than one. Target sizes and key-range boundaries influence later overlap, read candidates, caching and the granularity of future maintenance.
Suppose one huge output spans both a frequently updated key range and a rarely changed range. Later merges touching the hot range may involve unrelated cold bytes depending on the engine’s file-selection granularity. Smaller or differently partitioned outputs can change that cost, though they add files and metadata.
This is why file-count minimisation is not the sole objective. One enormous sorted file can be easy to describe and expensive to maintain. The policy should optimise useful read and write behaviour over time, not merely make the directory look tidy after one job finishes.
Publishing Outputs Safely
A typical correctness model is to complete replacement outputs, make their contents durable as required, install the new file set through durable metadata and retain old inputs until no relevant reader or recovery path needs them.
The exact sequence of file operations is engine-specific. RocksDB’s MANIFEST documentation describes persistent file-set changes. The invariant is that a crash must not leave the system believing incomplete outputs are the only authoritative state.
Test before output completion, after output completion but before installation, after installation and before input cleanup. The old or new recognised view must remain recoverable according to the protocol. A file existing on disk is not enough evidence to retire every input that contributed to it.
Old Readers Can Delay Physical Reclamation
A read that began before file-set replacement may still reference the old inputs. New readers can use the outputs while old readers finish on a consistent earlier representation.
The engine needs a lifetime mechanism so obsolete files are not removed while they are still in use. Logical obsolescence for future reads and physical reclaimability are different states.
This distinction helps explain why disk usage does not always fall immediately after a successful compaction. The job may have installed outputs correctly while readers, backup operations or other retention obligations keep inputs alive. Investigate those dependencies before repeatedly forcing more compactions, which can add work without releasing the files that remain pinned.
Temporary Disk Headroom Is Part of the Algorithm
Replacement files often coexist with their inputs during construction and publication. A job intended to reduce long-run storage use can therefore require additional free space before it can finish.
RocksDB’s disk-space management documentation describes reserving headroom and checking whether compaction outputs can fit. It also identifies what its accounting includes, which is important when comparing table bytes with total filesystem usage.
In an illustrative job with 60 GB of inputs and a predicted 40 GB output, the final replacement may save 20 GB. But while the output is being built, those 40 GB need somewhere to go before the inputs can be safely reclaimed. The prediction is not a guarantee; retained versions and compression can change output size. Plan for the transition, not just the hoped-for final state.
Write Amplification: Label the Numerator
Suppose an illustrative interval accepts 100 MB of logical application updates, writes 100 MB through flush and writes 500 MB through compaction. Counting only table output gives 600/100 = 6 times write amplification.
If the measurement also includes 100 MB of recovery-log writes, the ratio becomes 7. If replication or the storage device’s internal rewriting is included, the accounting changes again. Those are different scopes, not necessarily contradictory measurements.
State whether compression, headers, failed jobs and repeated output are counted. Also state the time window. Measuring logical writes during one interval and delayed compaction writes during another can produce misleading ratios. The useful metric compares related work under a transparent definition, not an unlabeled number presented as an inherent property of all LSM trees.
Read and Space Amplification Need Their Own Definitions
Read amplification may count candidate files, blocks read, bytes fetched or physical I/O operations. These measures differ when caches and filters avoid storage work. Space amplification may compare current physical table bytes with live logical data, but compression and retained snapshots complicate that denominator.
A policy that reduces file candidates can still increase bytes rewritten. A policy that minimises writes can retain more overlapping runs. A policy that compresses strongly can reduce disk space while using more CPU.
A fair comparison therefore uses a small scorecard rather than one winning number: read latency distribution, sustainable write throughput, space and headroom, maintenance traffic, memory use and recovery behaviour. Choose based on the workload’s requirements, not on the claim that one compaction policy dominates every dimension.
A Backlog Model Explains Why More Buffering Is Not Enough
Let the estimated unfinished maintenance work be Q. In a simple model, Q grows when new work enters faster than the system completes it. Over an interval, the change is incoming maintenance work minus completed maintenance work.
If a fictional workload creates 30 MB per second of maintenance work and the available resources complete only 24 MB per second, the backlog grows by 6 MB per second. A larger queue delays the limit; it does not change the sign of that growth.
Real work estimates are imperfect and costs vary by key overlap, compression and file size. Still, the model clarifies the decision. Increase sustainable service, reduce admitted work, reduce work per admitted byte or change the workload. Merely allowing Q to become larger is a burst-management choice, not a long-run capacity solution.
Rate Limiting and Parallelism Solve Different Problems
A rate limiter constrains resource consumption so maintenance does not overwhelm other work. More workers or subcompactions can improve utilisation when there is spare parallel capacity. Neither setting creates unlimited storage or CPU bandwidth.
RocksDB documents a Rate Limiter and Subcompaction mechanisms. Their effects depend on job structure and hardware. Increasing concurrency can help a parallelisable bottleneck or worsen contention and cache pressure.
Measure whether completed useful work rises while foreground latency remains acceptable. A busier machine is not necessarily a more productive one. Also protect flush progress: compaction throughput is not sufficient if recent memory buffers cannot obtain the resources needed to reach storage.
Write Stalls Are an Admission-Control Boundary
When file counts or estimated pending work exceed limits, an engine may slow or stop new writes. This prevents unbounded growth in overlapping files, memory or disk use.
The RocksDB Write Stalls guide distinguishes several triggers. Diagnose the actual cause rather than treating every stall as proof that the memtable is too small.
For a benchmark, include the period after ingestion when maintenance catches up. Otherwise a test can advertise rapid admission while hiding the time and resources required to reach a stable layout. For an application, define retry behaviour and handle ambiguous outcomes carefully. A timeout or throttle response is part of the system contract, not an invitation to flood the engine with unlimited immediate retries.
Not Every Compaction Has to Rewrite Every Byte
Some layouts permit a file to move logically between levels without rebuilding it when the required non-overlap and compatibility conditions hold. RocksDB calls this a trivial move.
This is another reason to distinguish the maintenance policy from one physical implementation. Reorganising file membership can sometimes satisfy the layout invariant without a full merge. In other situations, changing compression, removing obsolete records or resolving overlap requires rewriting.
Do not assume that a reported compaction count directly equals a fixed quantity of I/O. Inspect bytes read, bytes written, input overlap and output installation. The same high-level event name can represent very different amounts of work.
Compaction Filters Can Intentionally Change Application Data
An application may configure maintenance-time transformations such as removing expired values. Those operations are not merely physical representation changes; they apply an additional semantic policy.
RocksDB’s Compaction Filter documentation describes this extension. Its interaction with snapshots and application semantics must be reviewed explicitly. Do not assume that the ordinary compaction preservation argument automatically covers a custom function that deletes or rewrites values.
For testing, separate two oracles. One checks that structural maintenance preserves data under the engine rules. The other checks that the configured transformation changes exactly the records it is authorised to change. Combining them into a vague “compaction cleaned things up” assertion makes unintended data loss difficult to detect.
A Small Compaction Laboratory
Make four camera-2 cards for sequences 26, 36, 46 and 51 using the values and deletion described earlier. Add lamp-9 ready at 31 and tripod-4 ready at 39. Divide the cards among three sorted input piles.
Record complete expected maps at snapshots 32, 40, 49 and 55. Then merge the piles into a new sorted pile without removing any version. Verify every map. Next remove versions only when they are unnecessary for the retained views under the complete-history model.
Finally move sequence 26 into an unselected fourth pile and attempt to discard the deletion at 46 together with sequence 36. At snapshot 49, the old available value can reappear. This counterexample demonstrates that correctness depends on the unselected world as well as the input files visible to the job.
A Production-Oriented Verification Plan
Use an independent history model to compute expected reads. Generate puts, deletes and supported snapshots across a small key universe. Force flushes and partial compactions with different file boundaries. Compare both point lookups and full range results after every transformation.
Exercise incomplete coverage deliberately. Keep an older value outside the selected inputs. Retain a snapshot that needs a superseded version. Hold an iterator across file-set replacement. Inject failure during output construction and metadata publication, then recover under the documented protocol.
For resource testing, include limited disk headroom, slow storage, CPU pressure and sustained ingestion long enough to expose a backlog. A compaction implementation needs both semantic correctness and operational progress. Passing one does not establish the other.
How to Read the Symptoms
A rising L0 count with stable memtable memory suggests that flush may be working while consolidation lags. High physical writes with little overlap reduction suggest poor job economics or a workload that repeatedly revisits the same ranges. Disk use that stays high after successful jobs may reflect pinned inputs, retained history or output coexistence.
A deleted key returning after compaction points toward a semantic failure: tombstone coverage, version ordering or installation logic. A crash that loses acknowledged data points toward the durability and publication contract. A slow scan over few live results can indicate many examined versions or tombstones.
Do not start by forcing the largest possible merge. First identify which obligation is failing: preserve answers, reduce overlap, reclaim eligible bytes, maintain headroom or complete work at a sustainable rate. Different obligations require different evidence and different remedies.
Frequently Asked Questions
Is compaction the same as compression?
No. Compression encodes bytes more compactly. Compaction reorganises records and files, potentially merging sources and removing provably unnecessary history. It can also use compression when writing outputs, but that is a separate mechanism.
Does compaction always make one large file?
No. A result can be one sorted run divided into several files. File boundaries are chosen according to layout and size policies, and some eligible operations can move files logically without rewriting them.
Why keep old values after a newer write?
An older snapshot or another engine obligation may still need the previous version. The latest value is not a complete substitute for every supported historical read view.
Why not remove tombstones as soon as they are old?
Age alone does not prove safety. A marker may still suppress older values in unselected files or be required by distributed repair rules. The engine must establish that removing it cannot resurrect deleted data or invalidate supported reads.
Is leveled compaction always better than tiered compaction?
No. They distribute read, write and space costs differently. Compare the actual workload, implementation, resource limits and retention requirements rather than treating either policy name as a universal recommendation.
Why can compaction need free disk space to remove old data?
Replacement outputs must often be built and installed while inputs remain available. Peak usage during that transition can exceed the final compacted size. Space planning must include the handoff, not only the expected savings.
Sources, Scope and Related Mechanisms
The linked RocksDB references document leveled and universal policies, snapshot preservation, manifests, headroom, rate limiting, subcompaction, write stalls, trivial moves and custom compaction filters. Apache Cassandra’s references establish that distributed tombstone retention and time-window policies have additional engine-specific conditions.
The equipment histories and byte calculations are teaching examples. For document-search index segments rather than key-value LSM storage, use How Index Segments and Merges Work. Return to the LSM master guide or the How X Works library for the broader learning route.
Final Synthesis: Compaction Is Controlled Forgetting
Compaction collects scattered ordered evidence into a more useful physical arrangement. It can forget some old versions, but only after proving that their work is finished. It can retire old files, but only after publishing replacements and satisfying reader and recovery obligations.
The deepest questions are therefore not “How do we merge two sorted files?” but “Which history may be removed, which sources remain outside this job, and when is the replacement authoritative?” Answer those precisely, then budget enough resources to keep the maintenance queue stable. That is how an LSM tree turns deferred organisation into sustainable storage rather than accumulating uncertainty and unfinished work.