Cleaner Interference and Foreground Latency in Append-Only Storage

A cleaner is a second writer sharing one device with the application’s writes. Its work is not optional, since without it the log cannot reuse space, but it is deferrable, in the sense that a particular segment can be cleaned now or a second from now. The interaction between a deferrable background stream and a latency-sensitive foreground stream is where log-structured designs most often disappoint, because average throughput can be excellent while individual write latencies are unacceptable.

The mechanisms are ordinary queueing, but the parameters are unusual: the background stream’s cost per unit of progress is not fixed, and it depends on the liveness of whatever it happens to be cleaning, which is the quantity the collector’s selection rule is built around, as described in Choosing What to Clean. Writing data in segregated streams reduces the collector’s byte count and therefore the number of requests it must issue; that placement decision, covered in Data Temperature and the Cost of Cleaning Mixed Segments, is a latency decision as much as a space one.

Why the collector cannot be made free

It is tempting to assume that a background task consumes only spare capacity and therefore cannot affect the foreground. That holds only if the device has genuinely spare capacity and if the scheduler can distinguish the two streams.

Neither assumption survives contact with a real device. A device has a bounded number of outstanding requests, and every request the collector issues occupies a slot that the foreground could have used. On a solid-state device the internal parallelism is limited by the number of channels and dies, and a sequential read issued by the collector can consume the bandwidth of a channel for the duration of the transfer. On a rotating device the collector’s reads and writes are seeks, and a seek issued for cleaning displaces a seek that the foreground needed.

So the collector’s cost is not merely its byte count but its share of the device’s request slots. A collector that writes ten percent of the bytes can impose far more than ten percent of the latency if its requests are scattered and the device is queue-limited.

The second assumption fails for a subtler reason. The collector’s requests are often more expensive per byte than the foreground’s, because cleaning reads a whole segment to find the live blocks in it and then writes those blocks to a different location. The read and the write are separated in time, so they cannot be merged, and each is a separate device operation. The foreground, by contrast, writes to a contiguous region and can be merged with its neighbors. The collector therefore consumes more requests per byte of progress than the foreground does.

The shape of the latency distribution

The interference does not raise every write’s latency by a constant. It produces a bimodal distribution: most writes complete at the device’s normal latency, and a minority complete much later because they were queued behind collector requests.

The mechanism is that the collector’s activity is bursty by nature. A cleaning pass reads a segment, which is a large sequential transfer, then writes the live portion, which is another. During the read phase the collector’s requests dominate the queue; during the write phase they compete with the foreground’s writes. A foreground write that arrives at the start of a read phase waits for the whole segment to be read, which at a megabyte per pass and a few hundred megabytes per second is several milliseconds of added latency. That is small in absolute terms but enormous relative to a device whose normal write latency is tens of microseconds.

The tail is what matters for a synchronous workload, and the tail is governed by how many collector requests can be outstanding at once. A collector that issues its segment read as one large request contributes one long request; one that issues it as many small requests fills the queue and can push a foreground write behind dozens of them. The first is better for the tail even though it is worse for the scheduler’s ability to interleave.

/* Throttle the cleaner by outstanding bytes, not by a fixed sleep. */
static bool cleaner_may_issue(struct lfs *fs)
{
    /* Keep the cleaner's in-flight bytes below a fraction of the
     * device queue depth so foreground requests always find a slot. */
    uint64_t budget = fs->queue_depth * fs->max_request_bytes / 4;
    if (fs->cleaner_inflight >= budget)
        return false;
    if (fs->fg_queue_len > fs->fg_queue_target)
        return false;                 /* foreground is already backed up */
    return true;
}

Throttling against the foreground rather than against time

The naive throttle runs the collector at a fixed rate, for example one segment per second. That is wrong in both directions: too slow when the volume is filling and the collector must catch up, too fast when the foreground is idle and the collector’s work is pure interference with nothing to interfere with.

The correct signal is the foreground’s queue occupancy and its free-space trajectory. If the foreground queue is short, the device has capacity and the collector can issue freely. If the queue is long, every collector request delays a foreground request, and the collector should defer. Combined with a free-space target, cleaning aggressively when free space is below the target and lazily when above, this gives a controller that uses idle capacity and yields under load.

The free-space target itself must have hysteresis. A collector that starts when free space falls below a threshold and stops when it rises above the same threshold will oscillate, issuing bursts of cleaning that coincide with the foreground’s own bursts. Two thresholds, with a wide band between them, produce a collector that runs in long stretches rather than in short bursts, which is better for the device’s ability to amortize seeks and for the foreground’s ability to predict when it will be interrupted.

Priority inversion through the page cache

A log-structured filesystem that is also the page cache’s backing store has a second interference path that is easy to miss. Dirty pages accumulate until memory pressure or a writeback timer forces them out. The writeback then issues a burst of writes to the log, advancing the head rapidly. If free space is near its target, the collector must clean to make room for that burst, and the collector’s requests interleave with the writeback’s. The foreground application, which caused the dirty pages in the first place, sees its next write blocked behind both.

The effect is that a memory-pressure event in one part of the system manifests as a latency spike in another. The writeback burst is not caused by the application’s current activity but by pages it dirtied earlier, and the collector’s response is caused by the writeback. Untangling the two requires either reserving space for writeback bursts or rate-limiting writeback so that it does not outrun the collector.

A related inversion occurs with synchronous writes. A synchronous write must wait for its segment to reach the device, which means it waits for the segment to be closed and written. If the segment is partially filled and the filesystem waits for more data to fill it, the synchronous write waits for unrelated writes to arrive. The standard fix is to close and write a partial segment when a synchronous write is pending, accepting the wasted space in exchange for bounded latency. That trade, space for latency, is the same one that appears at every level of the design.

Read interference and the two-sided cost

The collector reads as well as writes, and its reads compete with the foreground’s reads. On a device where reads are cheaper than writes this is less severe, but on a device with a single queue it is the same competition.

The read side has one advantage: reads can often be scheduled at lower priority without affecting correctness, since the collector’s read has no deadline. A read that is deferred only delays the cleaning, and cleaning has slack as long as free space is above its target. Writes have less freedom, because a cleaning write that is deferred holds a segment in the cleaning state and prevents that segment from being freed or rewritten.

The asymmetry suggests splitting the collector into a read phase and a write phase that are throttled independently: read ahead when the device is idle, and write the copies when the write queue has room. This decouples the collector’s progress from the instantaneous state of a single queue and lets each phase run when its own resource is available.

What the foreground can do about it

The application-side mitigations are limited but real.

Batching writes so that each one is larger reduces the number of requests the foreground issues, which reduces the number of opportunities for a collector request to be interleaved ahead of one. A workload issuing 4 KiB writes is far more sensitive to queue interference than one issuing megabyte writes, because the latter’s requests are large enough that the device processes them as single units.

Issuing writes with an explicit priority hint, where the platform supports it, lets the scheduler distinguish the streams. The effect is bounded by the device’s willingness to honor the hint, and many devices reorder internally regardless, so the benefit is smaller than the interface suggests.

The most effective mitigation is capacity. A volume with generous free space gives the collector slack, and a collector with slack runs during idle periods instead of competing. The interference problem is therefore partly a provisioning problem: the same workload that produces unacceptable tail latency at ninety percent full may be entirely smooth at seventy percent, because the collector’s work is spread over idle time rather than concentrated where it collides with the foreground.

The residual cost

No throttling scheme removes the collector’s work. It can only move it in time, and moving it in time is worthwhile exactly to the extent that the device has idle periods. A workload that saturates the device continuously has no idle periods to move the work into, and the collector’s cost then appears as a direct reduction in foreground throughput, the W_max = B·(1−u) bound from Garbage Collection Under Space Pressure applies regardless of how the work is scheduled.

What scheduling can do is make the cost predictable. A collector that runs in long, well-separated passes produces occasional long delays; one that runs continuously at low rate produces a uniformly slightly-worse latency. Neither is universally better, and the choice depends on whether the workload’s latency budget is expressed as an average or as a tail. For interactive workloads the tail dominates, which is why collectors are usually tuned for large throttled passes over continuous low-level activity, and why the free-space target is usually set well above the minimum the arithmetic requires.