Garbage Collection Under Space Pressure: When Cleaning Cannot Outrun Writes

A log-structured filesystem with adequate free space cleans in the background: the collector picks segments at leisure, and the foreground never waits for it. As the volume fills, the two activities become coupled. The foreground cannot write without free segments, the collector cannot produce free segments without writing, and the rate at which the collector produces them depends on how live the candidate segments are. Near full, that dependency turns into a feedback loop whose steady state is a write rate far below the device’s capability.

Understanding the loop requires distinguishing two regimes that behave qualitatively differently, and then computing the capacity reserve that keeps the filesystem in the benign one.

Background cleaning and its slack

In the benign regime, the collector runs ahead of the write head by a comfortable margin. It cleans segments whose live fraction is low, because it can afford to wait for low-liveness candidates to appear. The cost per byte freed is therefore near the theoretical minimum for the workload’s data distribution.

The important property of this regime is that the collector’s throughput requirement is less than the foreground’s. If the collector frees space at rate F and the foreground consumes at rate W, the requirement is F ≥ W in steady state, but the collector’s device cost is not F: it is F plus the copies it writes. In the benign regime the copies are a small fraction of F because the candidate segments are mostly dead. So the collector consumes perhaps 1.1 to 1.3 times the free-space rate in device bandwidth, and the foreground consumes W, and the device has enough left over.

Slack is what makes this work. Slack is the accumulated dead space in segments that have not been cleaned. It exists because the collector is not required to clean immediately; it can leave a segment full of dead blocks sitting in the queue until it is a good candidate. The larger the volume and the lower the fill level, the more slack is available, and the lower the live fraction of the segments the collector eventually chooses.

The feedback loop near full

As the volume approaches full, slack disappears. The collector can no longer choose the emptiest segment in the volume, because the volume contains few segments at all; it must clean whatever is available, and the available segments are the ones that have been written recently, which are the ones with the highest live fraction.

Raising the live fraction u raises the copy cost per byte freed, u/(1−u). It also raises the total device bandwidth the collector needs, since it must write both the freed space and the copies. Let B be the device’s sustained write bandwidth. The collector’s requirement is

W * (1 + u/(1-u)) = W / (1-u)  <=  B

so the maximum sustainable foreground write rate is

W_max = B * (1 - u)

This is the collapse. At u = 0.5, the filesystem can sustain half the device’s bandwidth. At u = 0.8, a fifth. At u = 0.95, a twentieth. And u is not independent of the fill level: the fuller the volume, the higher the live fraction of the segments the collector is forced to touch, because the dead space has already been squeezed out of the segments that were cleanable.

The loop closes because a lower W_max does not reduce u. The data that is live stays live; the foreground simply runs slower while the collector churns through the same segments. The system settles at the intersection of the two curves, which is a low write rate and a nearly full volume. This is the state in which a filesystem appears to “get slow when it fills up”, and it is not a bug in any one component: it is the arithmetic of copying live data with no slack to amortize it.

/* Admission control: block foreground writes unless reclaim can keep up. */
static int admit_write(struct lfs *fs, size_t nbytes)
{
    double u = fs->reclaim_live_ratio;      /* mean liveness of cleanable segs */
    double w_max = fs->dev_write_bw * (1.0 - u);

    if (fs->fg_rate > w_max && gap(fs) < fs->reserve_segs)
        return -EAGAIN;                     /* caller must wait, not spin */
    return 0;
}

Why the reserve is not optional

The natural response is to keep more space free, and that is correct, but the amount matters. The reserve has to cover two things that are easy to conflate.

It must cover the collector’s staging requirement: freeing one segment requires writing its live contents somewhere, so at least one free segment must exist before cleaning can begin. As established in The Circular Log, the worst case needs a full segment of staging.

It must also cover the burst absorption requirement: the foreground can advance the head faster than the collector advances the tail for a period, and the gap is what absorbs that period. A workload that writes a gigabyte in a second on a device whose collector sustains a few hundred megabytes per second needs the gap to hold the difference, or the writes stall.

The two requirements are different in kind. The staging requirement is a hard floor: below it, the filesystem deadlocks. The burst requirement is a performance target: below it, latency spikes. Systems that conflate them end up with a reserve sized for staging and then discover that every burst stalls.

A useful rule of thumb follows from the arithmetic above: the reserve should be large enough that the collector’s required bandwidth stays below the device’s sustained bandwidth with margin. If the collector must sustain W/(1−u) and the device delivers B, the margin is the headroom that lets the collector catch up after a burst rather than merely keep pace during one. Operating at W_max exactly leaves no capacity to recover, so any disturbance, whether a burst, a slow region on the medium, or a competing I/O stream, moves the system into the collapsed regime and it stays there.

Reclaiming when there is nothing to reclaim

A distinct pathology appears when the live fraction is high not because the volume is full but because the data is genuinely long-lived. A volume holding a large immutable data set and a small amount of churn has a u floor equal to the immutable fraction, and no policy can lower it. Cleaning a segment in such a volume copies almost all of it, freeing almost nothing.

The only remedies are structural. One is to stop copying the immutable data at all, by giving it a region that is never cleaned: a segment written once and marked as permanently allocated, exempt from the collector’s candidate set. This is a form of segregation by temperature, and it works because the immutable data never needs to move. The cost is that the region’s space is unavailable for anything else, which is acceptable if the data set really is immutable.

The other is to recognize the state and refuse writes rather than thrash. A filesystem that has determined its reclaimable live fraction exceeds a threshold cannot serve a sustained write stream, and the honest response is to report the volume as full at a lower apparent capacity rather than to accept writes and slow to a crawl. Reporting an ENOSPC earlier than the physical capacity is a design decision, and it is the one that keeps the write path predictable.

Interaction with the write path

Space pressure changes the write path’s behavior in ways that are not obvious from the collector’s side.

Buffered writes that would normally be acknowledged immediately must be held until space is available, which means the buffer cannot be recycled and the filesystem’s dirty-page footprint grows. If the filesystem is also the page cache’s backing store, the pressure propagates into memory reclaim, and the kernel begins writing back pages it would otherwise have kept. The resulting behavior, a burst of writeback under memory pressure followed by a stall on segment allocation, is a compounding effect that neither subsystem would exhibit alone.

Synchronous writes become disproportionately expensive, because each one must wait not only for its own segment to reach the device but, under pressure, for the collector to produce the space that segment occupies. A workload that issues one synchronous write per transaction at a high rate degrades much faster near full than a streaming workload, even at the same average byte rate, because each write pays a fixed share of the reclaim latency.

The mitigation is to decouple the two: acknowledge a write once its bytes are in the segment buffer, and make the segment’s durability a separate, batched event. That preserves the throughput of the write path under pressure, at the cost of a durability window, which is the standard trade discussed in Checkpoint Regions and Tail Recovery.

Measuring how close to the edge a volume is

The fill level alone is a poor predictor, because two volumes at 85 percent can behave very differently depending on the liveness distribution. The quantity that predicts behavior is the mean live fraction of the segments the collector would actually choose, which is available from the segment usage table without any additional I/O.

A volume whose chosen candidates have a mean live fraction below about 0.5 has headroom; one whose candidates average above 0.8 is in the collapsed regime regardless of how much space it reports. The distinction matters because a monitoring system watching only free space will report the second volume as healthy right up until the write rate falls, and will not explain why.

The other predictive quantity is the gap between head and tail, measured in segments. A gap that stays near its reserve under load means the collector is the binding constraint; a gap that oscillates widely means the foreground is bursty and the collector is keeping up on average. Both are visible from the same counters the collector uses for its own decisions, which is the argument for exposing them rather than hiding them behind an aggregate “space used” figure.