Admission Control for Background Work: Keeping Scans Off the Critical Path

Every system that runs background work against a live dataset faces the same question: how much of the shared resource may the background job take. The answer cannot be a fixed number, because the foreground load is not fixed. A backfill sized to run comfortably at the morning’s traffic level will saturate the storage during the evening peak and, if it is throttled to be safe at peak, will waste the quiet hours running far below the capacity available. A rate limit that does not respond to the measured state of the resource is a guess that is wrong most of the time.

The resource being rationed is not throughput

The intuitive formulation is to cap the background job’s operations per second. That cap protects the wrong quantity. What the foreground cares about is latency, and latency is a function of queue depth at the bottleneck, not of the total rate. A background job issuing 200 small reads per second against an SSD that is 5 percent utilised costs the foreground nothing; the same 200 reads per second against a disk whose queue is already eight deep adds a full queueing delay to every foreground request.

So the controlled variable should be the signal that predicts foreground latency (queue depth, utilisation, or a latency percentile of the foreground path itself), and the manipulated variable is the background rate. This is a feedback loop, and it has the properties of one: it needs a setpoint, a measurement, and a gain, and it can oscillate if the gain is wrong.

The queueing relationship behind the choice of setpoint is Little’s law: for a stable system, the average number of items in the queue equals the arrival rate times the average time each spends there. A device serving μ operations per second with a total arrival rate λ has utilisation ρ = λ/μ, and the average queueing delay grows roughly as 1/(1-ρ). At ρ = 0.5 the delay is about twice the service time; at ρ = 0.9 it is about ten times; at ρ = 0.99 it is about a hundred. The practical consequence is that the useful operating range for a shared resource ends well below saturation, and a controller that targets 100 percent utilisation is targeting unbounded latency.

Three signals, three failure modes

Utilisation is the easiest to obtain and the coarsest. It is a fraction over an interval, so it lags: a controller sampling utilisation once per second learns about a burst after the burst has already filled the queue. It also saturates at 100 percent, which means a device that is overloaded and a device that is exactly at capacity report the same value, and the controller cannot tell how far past the limit it has gone. On a device with a large internal queue, utilisation can read 100 percent while latency is still acceptable, and on one with a small queue it can read 60 percent while requests are already waiting.

Queue depth is finer and more direct: the number of outstanding operations is proportional to the delay under a work-conserving server. It is available on block devices that expose it and inside database engines as the count of waiting sessions. The difficulty is that it is per-device, and a job whose I/O is spread across several devices, or which is limited by a network link rather than a disk, will be controlled by a signal that does not represent its actual bottleneck.

Foreground latency is the signal that matters, and the one most directly measured: the p99 of the requests the system exists to serve. Using it closes the loop on the actual objective rather than on a proxy. The cost is that it is noisy and it is the quantity being harmed: a controller reacting to a latency spike has already allowed the spike to happen, so it must be tuned to act early, on a trend rather than on an absolute breach.

// Controller adjusts a background work rate to hold a latency SLO.
// err is measured/target - 1, so positive means too slow.
type Controller struct {
    rate, min, max float64
    gain           float64 // fraction of rate change per unit of error
}

func (c *Controller) Observe(p99, target time.Duration) {
    err := float64(p99)/float64(target) - 1
    // Multiplicative adjustment: rate scales with the error, so the
    // response is proportional at any operating point.
    c.rate *= 1 - c.gain*err
    if c.rate < c.min {
        c.rate = c.min
    }
    if c.rate > c.max {
        c.rate = c.max
    }
}

The multiplicative form matters. An additive adjustment such as subtracting 50 operations per second when latency is high behaves differently at 100 operations per second than at 10,000, so a gain tuned at one operating point is wrong at another. Scaling the rate by a factor proportional to the error gives a response whose magnitude tracks the current rate, which is the property that makes a single gain usable across a range of loads.

Why the loop oscillates

A feedback loop with delay oscillates. The background job’s effect on the resource is not visible immediately: an operation issued now consumes the device now, but the latency it causes may only appear in the measurement window a second later, and the controller’s response takes another window to take effect. With a high gain and a long delay, the controller overshoots, backs off too far, overshoots in the other direction, and the background rate swings between its floor and its ceiling while the foreground latency oscillates with it.

Three remedies exist and they are usually combined. Lowering the gain reduces oscillation amplitude at the cost of slower response. Adding a derivative term, which reacts to the rate of change of the error rather than to its magnitude, damps the response, since a controller that sees latency rising fast backs off before the threshold is crossed. Adding a dead band around the setpoint, within which no adjustment is made, prevents the controller from chasing measurement noise.

A subtler instability comes from the measurement itself. If the controller samples latency over a window that includes its own previous action, it is controlling a system whose response depends on its own history. Sampling at a period shorter than the resource’s response time makes the loop read its own transient as new information. The sampling period should be at least as long as the time for the controlled resource to reach a new steady state, which for a storage device with a deep queue is on the order of seconds, not milliseconds.

Where the cap belongs

A controller that can reduce the background rate to zero is not safe: it can starve the job indefinitely under sustained foreground load, and a backfill that never progresses is a change that never completes, which is its own kind of failure. The floor should be a rate that guarantees forward progress (one batch per interval, however small), so that the job finishes eventually even if the completion time is unbounded.

The ceiling matters for a different reason. When the foreground is idle, an unconstrained controller will drive the background job to consume the entire resource, which is correct for throughput but produces two problems: the resource’s own internal behaviour degrades at full utilisation, and the transition when foreground load returns is abrupt. A ceiling at some fraction below saturation, commonly around 80 percent of measured capacity, leaves headroom for the return of foreground traffic and for the resource’s own maintenance work.

Where the controller lives is a design choice with real consequences. In-process control, inside the job, is simple and has low latency, but it only sees the job’s own view of the resource. Control at the resource, whether through a database’s own cost-based delay mechanism or a storage layer’s I/O priority, sees all clients and can allocate proportionally, at the cost of needing the resource to support it. The two are complementary: the resource enforces a share, the job adapts its request rate within that share.

The interaction with batching

The controller sets a rate, but the job executes batches. A reconciliation loop repairing state against the same store competes for the same resource, so the rate a backfill is permitted is not the rate it can assume. A batch of 1,000 records takes some time T and consumes some resource; the achievable rate is 1000/T, and a rate limit below that is enforced by sleeping between batches. This couples the controller’s resolution to the batch size: with batches of 1,000, the minimum nonzero rate is one batch per interval, and the granularity of control is coarse. Reducing the batch size gives finer control at the cost of more per-batch overhead: a transaction per batch, a position update per batch, a round trip per batch.

The compromise that works in practice is a batch size small enough for control (a few hundred records or a few megabytes) combined with a sleep computed from the measured time of the previous batch: if the target rate is R records per second and the last batch of B records took T seconds, the sleep is B/R - T, floored at zero. This is self-correcting in the useful sense: it accounts for the batch’s actual cost rather than for a nominal cost, and it degrades gracefully when the batch takes longer than its budget, since the sleep simply becomes zero and the job runs at whatever rate the resource permits.

The sleep calculation also explains why a controller must not act on a single batch’s latency. One slow batch produces a large T, and a controller that responds to it by halving the rate will then run at half speed for many batches. The measurement window for the control decision should span enough batches to average out individual variance, which is a few tens of batches for a job whose per-batch time varies by a factor of two.

What the controller cannot fix

Rate control protects a shared resource from a background job’s volume. It does not protect against the job’s access pattern. A backfill that holds a row lock while waiting on a network call blocks foreground writes for the duration of the call regardless of how few rows it touches per second; a job that scans in key order concentrates its writes on one region and contends there even at a low total rate. Those are shape problems, and the remedy is a different chunking strategy rather than a lower rate, as the batching discussion in resumable backfills sets out.

Nor does it protect the resource from the job’s own failures. A job that retries a failing batch aggressively consumes the resource while making no progress, and the controller sees only a high demand. Retry policy belongs above the rate limiter, with a cap and a backoff, so that a failing job reduces its own demand rather than being throttled into a slower failure.