Head-of-Line Blocking in a Shared Worker Pool

A pool of N workers fed by a single first-in-first-out queue is the simplest possible concurrency design, and it has a failure mode that appears as soon as the queue holds more than one kind of work. A request that takes ten times as long as its neighbours occupies one worker for ten times as long, and every request that arrived after it waits for a worker even though the work it needs is trivial. The queue is not slow; the ordering inside it is. This is head-of-line blocking, and its characteristic signature is that median latency tracks the slowest class in the mix rather than the class being measured.

The effect compounds. While the slow request runs, arrivals accumulate. When it finishes, the workers pick up the accumulated backlog, which now contains more slow requests, and the probability that all workers are simultaneously occupied by slow work rises. The pool spends increasing fractions of time with no worker free for short work, so short requests queue behind long ones repeatedly. The queue depth grows, the wait grows, and the only quantity that stays constant is the pool size.

The convoy effect and why FIFO makes it worse

The classical description of this behaviour comes from database systems, where transactions competing for locks form convoys: a transaction holding a lock is descheduled, the others queue behind it, and when it resumes it finds a long line and runs slower because of the cache and lock handoff costs. The same shape appears in worker pools without any lock. A worker holding a long request is the convoy head; the requests behind it are the convoy; the pool’s throughput is fine in aggregate while the latency of the short class is dominated by the long class’s service time.

FIFO ordering is what makes the damage systematic rather than occasional. Under FIFO, a short request cannot overtake a long one, so its expected wait includes the remaining service time of every long request ahead of it. If long requests arrive at rate λ_long and take S_long each, and the pool has N workers, the pool is saturated by long work whenever λ_long × S_long approaches N. Below that, long work occupies a fraction λ_long × S_long / N of the workers on average; the short class’s wait grows with that fraction, and its tail grows faster than its mean because the tail is generated by the moments when all long requests coincide.

A useful diagnostic is to compute, per request class, the concurrency the class demands on its own — arrival rate times service time, the Little’s law product. Two classes that individually need 0.4 of the pool need 0.8 together on average, but their peaks do not align, and the pool has to be sized for the sum of the peaks unless the classes are separated. Sizing the pool for the average is the mistake that turns a manageable mix into a queue, as the arithmetic in Little’s law and the size of a request pool makes explicit.

Separating the classes: dedicated pools and their cost

The direct fix is to stop sharing: give each class its own queue and its own workers. A pool of four workers for short requests and a pool of two for long ones cannot interfere, and each class’s latency is then a function only of its own load. Partitioning is also the cheapest fix to reason about, because the isolation is structural rather than statistical.

Its cost is idle capacity. If the short class’s peak and the long class’s peak occur at different times, dedicated pools leave workers idle during each other’s peaks, and the total worker count must exceed what a shared pool would need at the same peak load. The waste is bounded by the ratio of the peaks: with two classes whose peaks never overlap, dedicated pools need the sum of the peaks while a shared pool needs the maximum. Partitioning therefore trades utilization for tail latency, and the trade is only favourable when the latency requirement is strict or when the classes’ service times differ by an order of magnitude or more.

Partitioning also creates a new failure mode at the boundary. A class whose traffic grows beyond its share has no way to borrow capacity, so its queue grows while the neighbouring pool sits idle. The usual mitigation is to allow borrowing when the neighbour is empty, which reintroduces the coupling that partitioning was meant to remove — though in a weaker form, since borrowing happens only when there is genuinely spare capacity rather than whenever the queue is non-empty.

Priority and shortest-job-first, and why both need admission control

A single queue with a priority rule removes the convoy without splitting the pool. Requests carry a class, the scheduler picks the highest-priority waiting request, and a short request can overtake a long one. With strict priority and a continuous supply of high-priority work, low-priority work never runs; that is starvation, and it is a real outcome rather than a theoretical one when the high-priority class is latency-sensitive traffic that arrives constantly.

Shortest-job-first is the throughput-optimal ordering for a single machine when service times are known in advance: it minimizes mean residence time among all non-preemptive disciplines. Service times are not known in advance for arbitrary requests, but a proxy is often available — the endpoint, the payload size, or a class assigned at admission. Ordering by proxy converts the unknown into a prediction, and the prediction’s error rate determines how much of the theoretical gain survives.

Both priority and shortest-first need a guard against starvation, because the ordering rule alone does not bound the wait of any particular request. Aging — raising a request’s effective priority as it waits — bounds the wait by making every request eventually outrank the newcomers. A quota per class bounds it differently, by reserving a fraction of worker time. Either way, the scheduler needs a notion of fairness that the pure ordering rule lacks, and the cost is that the pure rule’s optimality no longer holds exactly.

// Weighted pick from per-class queues; each class gets a share of picks
// proportional to its weight, so no class can be starved by a busier one.
func (s *scheduler) next() *request {
    total := 0
    for _, q := range s.classes {
        total += q.weight
    }
    pick := s.rng.Intn(total)
    for _, q := range s.classes {
        if pick < q.weight {
            if r := q.pop(); r != nil {
                return r
            }
            break // chosen class empty: fall through to scanning
        }
        pick -= q.weight
    }
    for _, q := range s.classes { // fallback keeps workers busy
        if r := q.pop(); r != nil {
            return r
        }
    }
    return nil
}

The snippet above shows the essential structure of a weighted scheduler and one of its hazards: the first pass may select an empty queue, so a second pass is required to avoid leaving a worker idle when work exists. Real implementations combine the two passes more carefully, but the shape — weighted choice, empty-class handling, fallback — is the same.

Concurrency limits inside the request, not just outside

Head-of-line blocking has a second location that pool partitioning does not address: inside the request, where a handler calls several downstream services. If the handler issues those calls sequentially, its service time is the sum of the downstream latencies, and it holds a worker for that whole period. A pool that looks adequately sized when downstream calls are fast becomes badly undersized when one of them slows, because service time is the term that multiplied the concurrency requirement.

Issuing the calls concurrently reduces the service time to the maximum of the downstream latencies rather than their sum, at the cost of holding multiple downstream connections per request. That trade has to be accounted for at the downstream pool, not just at the worker pool: a handler that fans out to five connections multiplies the connection demand by five, and the downstream service’s own pool sizing must include that factor. The amplification of fan-out on tail latency is treated in fan-out and the amplification of tail latency.

A third location is the queue between the pool and the network. If requests are handed to a shared socket or a shared connection with a per-connection send queue, a large request occupying that queue delays small ones even though worker capacity is free. The general form of the problem is a single serialization point in front of a parallel resource, and the fix is the same: partition the serialization point, or make the unit of work small enough that occupying it is cheap. In HTTP terms this is why multiplexed streams over one connection replaced the practice of opening several connections to work around per-connection head-of-line blocking.

What the pool’s own metrics hide

A shared pool reports one latency distribution, and that distribution is a mixture. Its median may describe the short class and its 99th percentile the long class, so a single percentile cannot be compared against a per-class objective. The correct instrumentation keeps arrival and residence histograms per class and reports them separately, along with the queue depth at admission. Without per-class histograms, a service that meets its median objective and misses its tail objective looks like a mystery rather than a mixture.

Two further measurements are needed to confirm that head-of-line blocking is the cause rather than a symptom of something else. Queue wait, separated from service time, shows whether requests are waiting for a worker at all; if wait is small and service time is large, the pool is not the problem. Worker occupancy broken down by class shows whether the slow class is monopolizing capacity; if long requests occupy a fraction of workers far above their share of arrivals, the mix is the problem. Both measurements are cheap, and both are usually absent, which is why pools get resized repeatedly without the latency changing.

There is a boundary case worth naming: a pool with exactly one worker has no head-of-line problem distinct from its own scheduling, because every request waits for every other by construction. The interesting regime begins at two workers, where the scheduler can choose, and the choice is where the entire effect lives. Adding a worker to a convoyed pool does help, but sublinearly: the probability that all workers are occupied by slow work falls, so the short class’s wait falls, yet the mechanism that produced the convoy remains and returns as soon as load rises.