Queues, Backpressure, and Fair Scheduling

Queues, Backpressure, and Fair Scheduling is the set of decisions that determine what your system does in the minutes when demand exceeds what it can finish. A queue does not add capacity, it converts excess arrival rate into waiting, and a design that has not decided how much waiting is acceptable has decided to fail slowly instead of quickly.

Key takeaways

• A queue stores latency, not capacity. Chapter 1's arithmetic says so: with arrival rate above service capacity, the queue grows without bound until something rejects work.
• RFC 8289 separates a good queue, which absorbs a burst and drains within a round trip, from a bad queue, which is a standing backlog adding delay and no throughput.
• Measure sojourn time, not depth. RFC 8289 makes that case because sojourn time is independent of link rate, and its defaults are a 5 ms target over a 100 ms interval.
• Google's SRE book advises keeping queue length at or below roughly half the thread pool, since beyond that a longer queue only adds latency.
• Criticality is a property of the request that must propagate. Google's overload chapter names CRITICAL_PLUS, CRITICAL, SHEDDABLE_PLUS and SHEDDABLE, and a refusing backend should say overloaded and do not retry.

Read this after Chapter 1, whose per-class arithmetic tells you where the capacity ceiling is, and beside Chapter 8, which owns the other half of the overload story. The division is deliberate: growth, bounding, shedding and fairness belong here, while backoff, jitter, retry budgets, deadlines and idempotency belong there. Both chapters cite the same Google SRE material and take different pieces of it.

A batch import feature ships. It enqueues one job per row and the workers process them at about 300 a second, which is comfortable for the file sizes anybody has tested.

A customer uploads a file with four million rows on a Friday afternoon. The queue depth chart goes vertical.

Nothing crashes. Every unrelated job in the same queue is now four hours late, including the password reset emails, and the on-call engineer spends the evening deciding which jobs to delete.

A queue stores latency, not capacity

The single most useful reframing in this chapter is that a queue is not a buffer against overload. It is a device that converts overload into delay.

Chapter 1's arithmetic makes the reason exact. If work arrives at 500 per second and the system can finish 400 per second, the queue grows by 100 items every second, indefinitely, and the time each item waits grows with it. Adding queue capacity does not fix that. It raises the ceiling on how late things can be.

So a queue buys you exactly one thing, and it is valuable: tolerance of bursts whose mean is below capacity. A queue in front of a system whose mean arrival rate exceeds its capacity is a mechanism for turning an outage into a slow, confusing, hours-long outage.

That distinction has a name in the networking literature and it is worth borrowing.

Good queue against bad queue

RFC 8289, published by the IETF in January 2018 as the Controlled Delay active queue management specification, draws the line precisely.

A good queue absorbs a burst and drains within a round trip. It exists for a moment, it smooths arrival jitter, and it costs almost nothing in delay. A bad queue is a standing queue: it persists, it adds delay to every item passing through, and it adds no throughput whatsoever, because the server behind it was already running flat out.

That is the diagnostic to apply to your own queues. Look at whether depth returns to near zero regularly. If it does, the queue is doing its job. If there is a floor under it that never clears, you are paying latency for nothing and the fix is capacity or shedding, not a bigger queue.

The word backpressure names the correct response to a bad queue. Tell the producer to slow down or stop, rather than accepting work you cannot finish.

Sojourn time is the signal, not depth

The metric almost everybody instruments is queue depth, and RFC 8289 explains why it is the wrong one.

The specification's argument is that packet sojourn time, meaning how long an item actually spent waiting, is the signal to control on, because sojourn time is independent of link rate. Depth is not. A depth of 500 is catastrophic behind a slow consumer and trivial behind a fast one, so a depth threshold has to be retuned every time consumer performance changes. A sojourn threshold does not.

Its defaults are worth knowing as a calibration: a target of 5 milliseconds of standing queue delay, evaluated over a 100 millisecond interval. Those numbers are for network packets rather than for background jobs, so do not copy them. Copy the structure, which is a target delay plus a window over which you tolerate exceeding it.

Instrument sojourn time on every queue you own. It is the one number that tells you whether the queue is good or bad without knowing anything else about the system.

Bound the queue and reject explicitly

An unbounded queue is a decision to accept work indefinitely, and almost nobody who creates one intends that.

Google's SRE chapter on addressing cascading failures gives a concrete rule for the in-process case: keep queue length at or below roughly half the thread pool, because a long queue only adds latency once the pool is saturated. That is a strong claim and it follows from the good-queue definition. Beyond a certain depth, an item's remaining wait exceeds any latency budget the caller had, so accepting it was a lie.

The alternative to accepting is rejecting, and rejection has to be explicit. A caller that receives a clear refusal can decide what to do. A caller whose request sits in a queue for ninety seconds and then succeeds has already been failed, silently, and the user has already left.

Google's overload chapter adds the right shape for that refusal. A backend that is deliberately refusing should tell the client it is overloaded and not to retry, which is a different response from a generic error. Chapter 8 explains why that distinction bounds the damage.

One heavy tenant should not block a sparse one

Bounding a shared queue solves the total but not the distribution. The Friday afternoon import is a fairness failure, not a capacity failure.

RFC 8290, the flow queue CoDel specification also published in January 2018, describes the mechanism. Traffic is separated into per-flow queues, 1024 of them by default. The scheduler round-robins between queues that are newly active and queues that have been active for a while, so a sparse flow is not stuck behind a heavy one. The specification states the principle directly: flows that build a queue are treated differently from flows that do not.

Translate flow into tenant, or customer, or job class, and the design writes itself. One queue per tenant with round-robin service means a four-million-row import consumes its own share and nobody else's. Head-of-line blocking disappears, because there is no single line to be at the head of.

Ordering is the cost. Amazon's SQS documentation notes that standard queues provide best-effort ordering, and messages may occasionally arrive out of order, so if your consumer depends on strict order per entity you need a partition key rather than a global queue. That is the trade, and it is usually worth taking.

Criticality is a property of the request

Shedding is only defensible if you can shed the right work, which requires knowing what each request is worth before you need to drop it.

Google's overload chapter describes the mechanism in production terms. It names four criticality classes: CRITICAL_PLUS, CRITICAL, SHEDDABLE_PLUS and SHEDDABLE. The important property is that criticality propagates through the call tree. A backend three hops down therefore knows whether its work supports a user-facing request or a background refresh. The chapter also describes per-customer limits and utilisation signals rather than raw request counts.

Its client-side adaptive throttling is the part most worth copying. The client tracks requests and accepts, and rejects locally with probability max(0, (requests minus K times accepts) divided by requests), where K is typically 2. That means a client whose calls are being refused starts refusing its own calls before they leave, which removes load from the network as well as from the server.

Assign criticality at the edge, propagate it on every hop, and write the shedding order down. Two lines in a design document. It is the difference between shedding background reindexing and shedding checkouts.

Shedding and autoscaling must be designed together

The last decision is the one most often made by two different teams who never spoke, and the SRE Workbook documents what that produces.

Its Managing Load chapter reports a case study with a clean shape. Load shedding reduced CPU utilisation in a region. The load balancer read the lower utilisation as spare capacity and sent more traffic there, and the service degraded further. The feedback loop came from two individually sensible mechanisms reading the same signal differently. Its guidance is to design load balancing, load shedding and autoscaling as one system, and to configure autoscaling to act before shedding does.

The practical form is an ordering. Autoscaling first, because adding capacity is the correct response to sustained demand. Shedding second, because it is the correct response to demand that has already exceeded what capacity can reach in time. And the signal each one reads must be chosen so that the action of one does not look like good news to the other.

Write the order down. Name the signal each mechanism uses. That is the whole control.

A worked example, composited and labelled

The details here are composited from ordinary production shapes rather than one system, and the shape is exact.

A document processing service runs 40 workers, each handling one job at a time, with a mean service time of 50 milliseconds. Capacity is therefore 800 jobs per second. The request it serves has a p99 budget of 300 milliseconds.

Two bounds now compete, and both are informative. The latency budget allows 250 milliseconds of queueing, which at 800 per second is 200 queued items. The SRE guidance says half the pool, which is 20 items, draining in 25 milliseconds. The gap between 20 and 200 is the design conversation, and the resolution is that 20 is the steady-state target and 200 is the hard ceiling above which every accepted item is already outside its budget.

So the configuration is a bound of 200, an alert on sustained sojourn time above 25 milliseconds, and per-tenant sub-queues served round-robin. The recorded constraint is that jobs are rejected rather than delayed past 250 milliseconds of queueing. The reversal signal is sustained rejection of CRITICAL work, which means the answer is capacity rather than scheduling.

The objection: we will just autoscale

Autoscaling is real and it works, and the objection fails on timing rather than on principle.

Scaling out takes time: instance start, application warm-up, connection pool establishment, cache fill. Call it two minutes on a good day. A burst that arrives in ten seconds is therefore handled entirely by your queue and your shedding policy, and autoscaling arrives afterwards to help with the next ten minutes.

There is a second limit that money does not move. Downstream dependencies have their own capacity, so scaling the tier that queues frequently just moves the standing queue one hop deeper, into a database connection pool that cannot be scaled in two minutes.

And there is the failure mode the Workbook documented, where the two mechanisms interfere. Autoscaling is the answer to sustained load. Shedding is the answer to the first two minutes. A design needs both and needs them ordered.

Chapter summary

A queue converts excess arrival rate into delay rather than into capacity, so with arrivals above service capacity the backlog and the wait both grow without bound, and adding queue space only raises the ceiling on lateness. RFC 8289 separates a good queue, which absorbs a burst and drains within a round trip, from a bad queue, which is a standing backlog that adds delay and no throughput, and it argues for controlling on sojourn time rather than depth because sojourn time is independent of link rate. Bounding follows from that, and Google's cascading failure chapter gives the concrete rule of holding queue length at or below roughly half the thread pool, with explicit rejection rather than silent lateness, and a refusal that says overloaded and do not retry. Fairness is a separate axis: RFC 8290 separates traffic into per-flow queues, 1024 by default, so sparse flows are not blocked behind heavy ones, and the translation to per-tenant queues removes head-of-line blocking at the cost of global ordering, which Amazon's SQS documentation confirms is best-effort on standard queues anyway. Criticality has to be assigned at the edge and propagated, using the four classes Google names, with client-side adaptive throttling that rejects locally at probability max(0, (requests minus K times accepts) over requests) and K typically 2. The SRE Workbook's Managing Load case study shows why shedding and autoscaling must be one design, and the chapter's decision is a bound, a sojourn alert and a written shedding order.

Overload is what happens when too much work arrives. Partial failure is what happens when one call inside a request does not come back, and the three settings that govern it decide whether a retry is a recovery or a corruption. Chapter 8 is Timeouts, Retries, Idempotency.