Bounded Queues and Load Shedding at the Admission Boundary

When arrivals exceed service capacity, the difference has to go somewhere. There are exactly three destinations: a queue, a rejection, or a degradation of the service itself. An unbounded queue is the choice to absorb the difference in memory and in latency, and it is the choice that turns a temporary overload into a failure that outlasts the overload by the entire depth of the queue.

The depth is the design decision. Everything else follows from it.

What an unbounded queue actually does

Take a server that can complete 1000 requests per second and receives 1100. The excess is 100 requests per second, and if nothing rejects them they accumulate. After ten seconds the queue holds 1000 items and the newest arrival waits one second. After a hundred seconds it waits ten seconds, and by then every one of those queued requests has almost certainly been abandoned by its client, because the deadlines described in Deadline Propagation and the Shared Request Time Budget were set for a healthy system.

The server is now doing work whose results are discarded. It has not gained throughput; throughput is still 1000 per second. It has gained a growing memory footprint, a growing latency for every arrival, and a growing set of abandoned requests that will still be processed. When the arrival rate finally drops below capacity, the queue drains at 100 requests per second of excess capacity, so a hundred-second overload takes a hundred seconds to clear even after the cause is gone.

This is the mechanism behind the observation that a system stays broken after the trigger is removed. The queue is a memory of the overload, and it keeps the system at saturation for as long as it takes to forget.

Choosing a depth from a latency target

A queue depth is a latency budget expressed in requests. If the target is that no accepted request waits more than W seconds, and the service rate is C requests per second, then a depth of W × C holds exactly one target’s worth of waiting.

A server at 1000 requests per second with a 250-millisecond queueing allowance therefore wants a depth near 250. Beyond that, the marginal request cannot complete within the allowance and accepting it only displaces a request that could have. That is the argument for a small queue: past the latency target, a queued request has negative value, and the correct action is to reject it immediately so the client can make its own decision, which may include trying a different replica.

The counter-argument is absorption of bursts. Traffic is not smooth, and a queue smooths short spikes that would otherwise produce rejections. A depth that covers the burst duration at the excess rate is defensible: a spike of 200 requests per second above capacity lasting half a second needs 100 slots. The two arguments produce very different numbers, and which applies depends on whether the burst is shorter than the latency target.

The kernel’s accept queue has its own depth, set by the backlog argument to listen(). On Linux, the effective limit is min(backlog, somaxconn), and the default value of somaxconn has changed across kernel versions, so the configured backlog is often not the binding constraint. When the queue is full, the kernel drops the incoming SYN by default, so the client retransmits after its initial retransmission timeout and the connection eventually succeeds or fails at the client’s own connection timeout. The observable effect is a slow connection establishment rather than an error, which is a form of implicit shedding with a delay attached.

The three shedding points

Rejection can happen at several places, and they are not equivalent.

At connection accept, the cost of shedding is one handshake. The server closes the connection immediately, and the client learns of the rejection without a request being parsed. This is the cheapest point, and it requires that the accept loop itself not be the bottleneck.

At request parse, the server has read the headers and can make a decision based on the method, the path, or a priority header. Shedding here costs a round trip plus a header parse, which is small relative to any real handler.

At dequeue, after the request has been admitted and queued, shedding is expensive in a specific way: the request consumed a queue slot that a better request could have used, and the server has already done the admission work. Dequeue-time checking is still worth doing for the deadline case, where a request that is already out of time should be discarded rather than executed, but it is a correction rather than a control.

The design consequence is that admission decisions belong before the queue, not after it. A server that accepts everything and then decides what to drop has already spent the resource it was trying to protect.

Priorities and the cost of being fair

Uniform shedding treats all requests as equivalent, which is rarely what the caller wants. A health check, a metadata read, and a report generation all occupy the same queue slot under a first-in-first-out policy, and the report generation may hold its slot for orders of magnitude longer.

Two separations are worth the complexity. The first is by cost: cheap requests go to a small fast queue and expensive ones to a separate bounded pool, so a backlog of expensive work cannot delay cheap work. The second is by criticality: a small reserved capacity for requests that must not be dropped, with the remainder shared. The reserved fraction has to be small, on the order of a few percent of capacity, because reserved capacity is capacity that the general pool cannot use, and the reserve is idle whenever the critical traffic is below its reservation.

Weighted fair queueing generalises both. Each class gets a weight, and the scheduler serves classes in proportion to their weights among those with pending work, so an idle class does not waste its share and a busy class cannot exceed it. The implementation cost is a scheduler with per-class accounting; the operational cost is that a misconfigured weight silently starves a class, and the starvation is only visible in that class’s latency.

Priority inversion is the trap. If a high-priority request depends on a low-priority one, dropping the low-priority request fails the high-priority one. Priority schemes work when the dependency graph follows the priority order, which is true for read paths and often false for anything involving background computation.

Shedding as a response, not an error

The distinction between a rejection that the client can act on and one it cannot is carried in the response. A 503 with Retry-After tells the client to wait a specific interval, and a client that honours it stops contributing to the load. A 429 does the same for rate limits specifically. A connection reset tells the client nothing except that something failed, and a client that treats it as a transient network error will retry immediately, which is the worst response.

The server also has to avoid the pattern where a shed request is retried by an intermediary that does not understand the response. A load balancer that retries a 503 on the client’s behalf converts a shedding decision into additional load, and it does so at the moment the server has declared it cannot handle more. Retry policy on the intermediary has to be aware that 503 is an instruction rather than a failure.

// shed at the admission boundary, before the request occupies a slot
select {
case sem <- struct{}{}:
    defer func() { <-sem }()
    serve(w, r)
default:
    w.Header().Set("Retry-After", "1")
    http.Error(w, "overloaded", http.StatusServiceUnavailable)
}

A non-blocking send on a semaphore channel is the smallest form of admission control: the semaphore’s capacity is the concurrency limit, and a full channel is a rejection rather than a wait. The variant that waits with a timeout is a bounded queue in disguise, and the timeout is its depth in time rather than in items.

When the shed requests are the wrong ones

Shedding protects the server and can still harm the system. Three cases.

Dropping requests at the edge of a fan-out means the aggregator loses an entire response because one of twenty shards was shed, and the retry it issues is a full fan-out rather than a single request. The amplification is the fan-out width, so shedding at a leaf is far more expensive than the leaf’s own load suggests. Per-shard partial results, where the aggregator can return a degraded response, change the calculus entirely.

Dropping requests that carry an expensive side effect wastes work already committed. A payment authorization that is shed after the authorization succeeded at the provider leaves the client with an ambiguous state and no idempotency key to resolve it. Shedding is safe at the front of an operation and unsafe after a non-idempotent effect.

Dropping the slowest requests preferentially is a policy that selects against exactly the requests that need the most capacity, and it interacts badly with queue time. A server that sheds whatever has been waiting longest is really shedding whatever arrived during the previous spike, which may be ordinary traffic that happened to arrive at a bad moment.

Interaction with the circuit breaker

Shedding and circuit breaking act at different layers and are frequently confused. Shedding is a decision about a request the server has received and cannot serve. A circuit breaker is a decision about a dependency the server calls and which is failing. The first protects capacity, the second avoids spending time on calls that will fail.

The two combine in the obvious order: shed at admission, then call dependencies through breakers, then apply a deadline to whatever remains. Circuit Breaker State Machines and Half-Open Probing describes the second layer. What matters at this layer is that a breaker opening must not convert into a shedding decision that drops requests which never needed the broken dependency, and that a dependency’s recovery is not delayed by the server’s own queue backlog.

The residual limitation is that none of these mechanisms create capacity. They decide who receives the shortfall. A system that sheds correctly fails a small number of requests quickly and keeps the rest fast; a system that queues correctly fails everyone slowly. Between those, the bounded queue is not a refinement of the unbounded one but a different answer to the same question.