Choosing What to Clean: Greedy, Cost-Benefit, and Age-Ordered Segment Policies

A cleaner has a queue of candidate segments and must pick one. The choice determines how much data must be copied to free a given amount of space, and that ratio is the collector’s efficiency. Three selection rules have been standard since the original design: clean the emptiest segment, clean the segment with the best ratio of benefit to cost, or clean the oldest segment. They are not variations on a theme; they optimize different quantities, and the difference between them is measurable in copies per byte freed.

The setup: what a cleaning pass costs and yields

Every policy is choosing among segments with different live fractions. Let a segment hold U bytes in total and L bytes that are still live. Cleaning it means reading all L live bytes and writing them to the head of the log, then marking the segment free. The yield is U bytes of free space. The cost is L bytes of write traffic plus whatever read traffic is needed to find the live bytes.

Define the utilization u = L / U, the fraction of the segment that is live. The write cost per byte of free space produced is u / (1 − u): the bytes written divided by the bytes actually reclaimed. At u = 0.25 the collector writes one byte for every three it frees; at u = 0.75 it writes three bytes for every one it frees, and the net free-space production is a quarter of the write bandwidth it consumes.

That ratio is the quantity every policy is trying to minimize, and it explodes as u approaches one. A segment at u = 0.9 costs nine bytes of copy per byte freed, which is worse than simply not writing the data in the first place. A segment at u = 1.0 cannot be cleaned at all: copying it consumes exactly as much space as it frees.

Greedy: always the emptiest

The simplest rule sorts segments by live byte count and cleans the minimum. It minimizes the copy cost of the current pass, which is a genuine advantage: each individual cleaning operation is as cheap as it can be.

The rule’s weakness is that it ignores how the segment’s liveness will evolve. A segment that is empty right now may be one that was just written and then partially superseded, and the blocks that survive in it may be the ones that will never be rewritten. Cleaning it copies exactly the immovable data, and that data lands in a new segment which will become a cleaning candidate again later, at a similarly high live fraction. The collector ends up repeatedly relocating the same handful of long-lived blocks, each pass freeing the segment around them but writing them once more.

This is the cold data migration problem, and it is not hypothetical: a segment that contains a single never-modified file and a great deal of churn will always look attractive to a greedy policy, and cleaning it always moves the file. The garbage collected is real, but the cost is paid on the same bytes every time.

A second weakness is that greedy selection is unstable under load. A burst of writes creates many fresh segments with high live fractions, so the minimum-live segment may be relatively old and expensive; a lull lets those segments age, so the same policy picks cheap ones. The number of bytes copied per cleaning pass therefore tracks the write rate rather than the amount of garbage available.

Cost-benefit: space reclaimed multiplied by the age of the data

The cost-benefit policy replaces the instantaneous cost with an expected yield over time. For a segment i, define

• benefit(i) = the free space that cleaning it would produce, U − L, multiplied by the age of the segment’s data, meaning the elapsed time since its most recent write;
• cost(i) = 1 + u, one unit of cost to read the segment and u units to write its live bytes back into the log, measured per segment of data moved.

The score is benefit / cost, and the segment with the highest score is cleaned. The age factor is the essential addition, and it is not the reciprocal of the segment’s liveness: the benefit is a space-time product. Freeing a segment yields U − L bytes of free space, but it yields them only for as long as the data left in that region is not superseded and written back into it. A segment that has not been written for a long time holds data whose owners have moved on, so the space recovered from it is more likely to stay free. Multiplying the free space by the age of the data is the cheapest available estimate of that duration, and it is what lets an old segment with a moderate live fraction outrank a young one that is nearly empty.

On uniform media the ordering reduces to (U − L) · age / (1 + u), so segments with different ages and different live fractions can be ranked on one scale. Some formulations weight the cost term by the transfer cost of the medium, so that a segment on a slower region is penalized for the same work; on uniform media that weight is a constant and cancels out of the ordering.

/* Cost-benefit score; higher is better. Sizes in bytes, time in seconds. */
static double cb_score(struct segusage *s, uint64_t now, uint32_t segsize)
{
    double live  = s->live_bytes;
    double freeb = (double)segsize - live;            /* space reclaimed */
    double u     = live / (double)segsize;            /* segment utilization */
    double age   = (double)(now - s->mtime) + 1.0;    /* never zero */

    if (live <= 0.0)
        return 1e18;                  /* empty: free it at once, no copy */
    return (freeb * age) / (1.0 + u); /* space-time product over cleaning cost */
}

The age term has its own failure direction. Age measures when the segment was last written, not what its remaining contents will do next, and it discounts the cost of delay entirely. When the volume is nearly full, deferring a young but sparsely live segment in the hope that it ages is the wrong decision: the space is needed now, and the cost of waiting is a stall rather than a smaller copy.

Cost-benefit ordering is not optimal either. It uses age as a proxy for future coldness, and the proxy fails when a workload rewrites an old file: the segment holding it looks cold, is cleaned, and the file is rewritten immediately afterward, making the freshly copied block dead again. Repeated cleaning of such a segment is the hot-cold misclassification failure, and no selection rule can fix it, because the information needed, which blocks will be rewritten, is not available at selection time. The mitigation is at write time, not clean time: segregating writes by expected lifetime keeps hot blocks out of segments that look cold.

Age-ordered: clean in creation order

The third rule ignores liveness entirely and cleans segments in the order they were written, oldest first. It is the rule several log-structured designs have adopted, and it has a specific virtue: it produces sequential cleaning. Reading segment n and writing its live contents to the head produces two sequential streams that the device can schedule efficiently, and the write pattern of the collector matches the write pattern of the filesystem, so the cleaner does not introduce seek patterns that the foreground did not already have.

Its weakness is that it can be arbitrarily inefficient on liveness. If the oldest segment happens to be fully live, because it holds a large file written once at filesystem creation, cleaning it copies the entire segment to free nothing at all, and the net effect is that the file moves and the free space is unchanged. Age ordering relies on the workload’s tendency to rewrite data in roughly the order it was created, which holds for append-heavy workloads and fails for update-heavy ones.

The advantage appears under a different constraint: predictability. Because cleaning order is independent of the liveness distribution, the collector’s cost per pass is a function of the workload’s age profile rather than of a fluctuating score, and the volume’s free-space trajectory is easier to reason about. For a filesystem that must guarantee a minimum free-space level, an unpredictable collector is harder to bound.

Comparing the three on one workload

Take a volume where half the writes are to a small set of files rewritten constantly and half are to large files written once. Segregation at write time puts the churn in one stream and the bulk data in another. Then:

Greedy cleans the churn segments first, which is correct because they are nearly dead, and leaves the bulk segments alone until they age. The bulk segments eventually reach low liveness only when their files are deleted, at which point they become fully dead and greedy cleans them for free. Greedy performs well here, and its earlier weakness does not appear because the immovable data was never mixed with churn.

Cost-benefit produces a similar ordering but delays the churn cleaning slightly, since young segments score low. That delay is beneficial if the churn is bursty, since waiting lets more of the segment die, and harmful if the volume is near full and space is needed now.

Age ordering cleans the bulk segments as soon as they are oldest, copying data that is entirely live and freeing nothing. That is the pathological case, and it is why age ordering is paired in practice with a liveness floor: a segment whose live fraction exceeds some threshold is skipped regardless of age, and the policy degrades to greedy-with-a-cutoff.

What the policies cannot do

None of the three can beat the fundamental relation between cleaning cost and the distribution of liveness. If the steady-state live fraction across all reclaimable segments is u, every policy pays at least u / (1 − u) bytes of copy per byte freed, and the best policy merely approaches that bound rather than exceeding it. Selection is about approaching the bound; the bound itself is set by how writes were placed, which is the subject of Decomposing Write Amplification and the reason segregation by temperature, covered in Data Temperature and the Cost of Cleaning Mixed Segments, matters more than the choice of scoring function.

There is also a scheduling dimension the three rules ignore. A cleaner competes with foreground writes for the same device, so the best policy in isolation can be the worst in practice if it issues its reads and writes at moments when the device is saturated. Collectors therefore commonly throttle themselves against a free-space target and an observed foreground rate rather than running at full speed whenever garbage exists, which is the interference problem examined in Cleaner Interference and Foreground Latency.