Bounded Queues, Backpressure, and What to Drop Under Overload

A queue is a buffer between a producer that cannot slow down and a consumer that cannot speed up. Its depth is a design parameter with a direct latency cost, and leaving it unbounded does not make the cost disappear; it converts a capacity limit into a latency growth that continues until something else fails.

The mechanism is the identity that relates the number in a system to the time each item spends in it. Holding a queue depth of $L$ with a service rate of $\mu$ implies a waiting time of about $L/\mu$ for the request at the back, before its own service begins. A queue that grows without bound therefore has a latency that grows without bound, and every request admitted into it is a promise to the client that will be broken later rather than a rejection that could be delivered now.

Why overload without a bound is the worst outcome

Consider a service with a capacity of 1,000 requests per second whose offered load is 1,200. Each second, 200 requests’ worth of work accumulates in the queue. If the queue is unbounded, its depth grows by 200 every second, so after a minute it holds 12,000 requests and the request at the back waits twelve seconds. All 1,200 requests per second are accepted and none complete within a reasonable time.

The clients, receiving no answer, time out and retry. The retries arrive as additional load, and the effective offered rate rises above 1,200 while the completions continue at 1,000 per second, so the queue grows faster. This is the amplification described in Timeout Budgets, Deadline Propagation, and the Arithmetic of Retry Amplification, and an unbounded queue is what gives it room to happen.

A bounded queue changes the outcome. With a bound of 1,000, the service accepts the first 1,000 arrivals and refuses the rest. Refused requests fail immediately, which is a worse outcome for those clients in isolation and a much better outcome in aggregate: the accepted requests complete in about a second, at a latency the client’s timeout can accommodate, and the system stays in a regime where it can do useful work. The trade is explicit: a bounded fraction of requests fails fast so that the remainder succeeds slowly rather than everything failing after a long wait.

The distinction matters for the client’s recovery behaviour as well. A refused connection is a clear signal that the service is unavailable, and clients that treat it as such back off. An accepted request that hangs until a timeout is indistinguishable from a network problem, and clients respond to it with retries, which is the response that makes the overload worse.

Deriving the bound from a latency objective

A queue bound is not a free parameter; it follows from the waiting time that the service is willing to impose. If the service rate is $\mu$ requests per second and the objective is that a request waits at most $W_q$ seconds in the queue before being served, the implied bound is approximately

$$ L_{\max} \approx \mu \cdot W_q $$

For a service that completes 2,000 requests per second and a target queueing delay of 100 milliseconds, the bound is 200. That is the number of requests whose company a newly arriving request can tolerate given the throughput.

The formula is an approximation because it assumes the queue drains steadily and that requests are served in arrival order. Under a variable service-rate distribution the bound should be smaller, because some requests will take longer than the reciprocal of the mean. Under a discipline that serves short requests first, the bound can be larger for the short class, since they do not wait behind the long ones.

Two refinements are worth making. The bound should be expressed as a function of concurrency rather than of a rate if the service is closed-loop, since the rate is derived from concurrency and latency rather than being an independent input. And the bound should be enforced at admission rather than inferred from memory growth, because a queue implemented as an unbounded list or channel does not have a limit to enforce and will simply expand until the allocator fails.

Choosing among refusal, blocking, and dropping

When the bound is reached, three policies are available and they differ in where the pressure is applied.

Refusal at admission, returning an error immediately, applies pressure to the client. It is the policy that preserves the latency of accepted work and requires the client to have a retry policy with backoff, since an immediate error invites an immediate retry.

Blocking the producer, which is what a bounded channel with a full buffer does by default, applies pressure upstream. The producer’s thread is suspended until space is available, which propagates the overload into whatever is calling the producer. In a system with a finite thread pool this can deadlock, since the threads that would drain the queue are the ones being blocked while trying to fill it; the classic case is a bounded thread pool in which each task submits another task and waits.

Dropping from the queue, removing an already-admitted request, applies pressure to the middle of the pipeline. It is the only policy that can shed load already consuming capacity, and it requires that the work be abandonable, which rules out requests in the middle of a non-idempotent side effect.

The choice interacts with the service time distribution. Dropping the oldest request from the queue would break the arrival order and is only acceptable if the dropped request’s work can be abandoned cleanly; dropping the newest is equivalent to refusing at admission except that the request has already consumed admission resources.

Which requests to shed

Once the decision to shed is made, the selection is a scheduling problem with a latency objective. Three criteria are common, and they are not mutually exclusive.

The deadline criterion refuses requests whose remaining time budget cannot be met even at the current queue depth. A request that carries a deadline has a computable answer: the estimated completion time is the current queue drain time plus the service time, and if that exceeds the deadline, serving the request produces a result nobody will use. Refusing it releases capacity for requests that can still be satisfied. This is the extreme case of the reducing-priority idea, and it strictly dominates shedding at random when the deadline is meaningful.

The priority criterion refuses the least valuable class first. Priority classes are effective when the classes have different service-time distributions or different arrival rates, and they are ineffective when they do not; assigning priority to traffic that is already the bulk of the load simply relabels the queue.

The work-size criterion refuses the largest remaining work, since a request that occupies a worker for a long time blocks more subsequent requests. This is the same reasoning that makes shortest-remaining-processing-time optimal for mean response time in a single-server queue, and its cost is fairness: large requests are starved whenever load is sufficient to keep the queue non-empty.

# Proportional refusal: shed before the queue fills, not after it overflows.
class Gate:
    def __init__(self, limit, target_util=0.9):
        self.limit = limit
        self.target = target_util
        self.in_flight = 0

    def admit(self, deadline_slack):
        # Expected drain time if this request were admitted behind the queue.
        predicted_wait = self.in_flight / self.limit
        if predicted_wait > deadline_slack:
            return False              # deadline already unreachable
        if self.in_flight >= self.target * self.limit:
            return False              # keep a slice of capacity free
        self.in_flight += 1
        return True

The target factor keeps room for the requests that have already been admitted to complete, which is the reason a limit set exactly at the sustainable concurrency still produces long waits: the limit describes the capacity, while the target describes the operating point below it that leaves room for the queue to drain.

Queue delay as the signal to control

Measuring queue depth directly is often impractical, because the queue may be a kernel structure, a channel, or a thread pool’s internal list. Measuring the time a request spends waiting is usually easier and is the quantity that matters, and this is the insight behind controlling a queue by its delay rather than by its length.

The delay signal has an advantage over a length signal in that it is measured in the same units as the objective, so no conversion through the service rate is needed. It also automatically reflects changes in service time: if the service becomes slower, the measured wait grows without any change in depth, and the control responds.

Applying control to the measured delay rather than to the depth requires a filter, because instantaneous delay is noisy. A common approach watches the minimum delay over an interval, on the argument that the minimum is the closest available estimate of the queue’s drained state; when the minimum itself rises, the queue has stopped draining and the signal is a persistent backlog rather than a burst. A burst passes and the minimum returns to its floor; a backlog does not.

Failure modes of shedding

Shedding fails in three characteristic ways.

The shed load returns. A refused request is retried by the client unless the refusal is paired with a backoff instruction and the client honours it. A protocol that carries a retry-after signal lets the server state how long to wait, and a client that ignores it will reproduce the shed load as fast as the server refuses it. The load remains on the network and on the server’s admission path even though the work is not done.

The bound is enforced in the wrong place. A limit on the number of workers does not bound the queue in front of them if the queue is separate, and a limit on the queue does not bound the connections in the kernel’s accept queue. Each boundary has its own limit, and each has to be set for the system’s total in-flight count to be bounded. A backlog limit that is unreachable because an earlier limit is always hit first is a limit that does nothing.

The measurement itself adds load. Per-request queue depth sampling with a lock, or a shared counter updated on every admission, becomes a contention point at exactly the load levels where the control matters. The counter has to be cheap, which usually means approximate or per-shard, and per-shard counters make the global limit approximate, which is acceptable as long as the approximation is understood.

A queue bound also interacts with the fleet. A bounded queue in each of twenty instances bounds the total in-flight requests at twenty times the bound, and a load balancer that distributes evenly keeps each near its bound. A load balancer that retries a refused request against another instance transfers the pressure without resolving it, which is why the refusal path and the load balancer’s retry policy have to be designed together. The relationship between the queue at each instance and the aggregate behaviour of the fleet is the same question as Aggregating Percentiles Across a Fleet Without Losing the Tail, applied to capacity rather than to latency.