Too Much Traffic? Decide Who Waits.

In October 1986, the link between Lawrence Berkeley Lab and UC Berkeley fell over. The two sites are 400 yards apart. Throughput went from 32 kbit/s to 40 bit/s.

Not 32 down to 20. Down by a factor of a thousand, over a link that had been managing the full 32 a short while earlier, between two buildings you could shout between. Van Jacobson and Michael Karels went and found out why, and the seven algorithms they added to Berkeley UNIX as a result are the ancestors of the congestion control in every TCP stack running today (Jacobson and Karels).

The thing I want you to hold onto is the shape of it, because it is not the shape people expect. The network didn’t get slower by degrees as load rose. It got slower by degrees, and then it fell off a cliff, and on the other side of the cliff it was doing effectively no useful work while running absolutely flat out.

Your service has that cliff too. A queue is not storage. A queue is a statement about time: when this component is slower than its caller, here is where the difference accumulates. Systems that treat queues as buffers to be sized get overload behaviour by accident. Systems that treat them as a language get to choose it.

The policy nobody chose

The default configuration of most services encodes a policy nobody wrote down: unbounded acceptance until memory runs out. Under normal load it’s invisible. Under overload it produces a specific and very bad shape: latency climbs, every request eventually times out at the client, and the server keeps working on requests whose callers stopped caring several seconds ago.

That last part is the expensive bit. A server at 100% CPU doing work for departed clients is not degraded; it is doing nothing at all, at full power.

An unbounded queue does not absorb overload. It converts it into wasted work and hides the conversion from you.

Which would be a manageable problem if you could just take the extra load away again. You can’t, and the reason is the least intuitive thing in this post.

Taking the extra load away doesn’t fix it

Here is the arithmetic, from Google’s SRE book, and I’d encourage you to guess the answer before reading it (Google SRE).

A service is healthy at 10,000 requests per second. At 11,000 it starts crashing, and a cascading failure begins. Traffic then drops back to 9,000, comfortably under the level it was happily serving twenty minutes ago.

It does not recover. It stays down.

The reason is that you’re no longer asking the question you think you’re asking. You are not asking a healthy service to handle 9,000 QPS. You are asking a service with most of its capacity dead to handle 9,000 QPS, while each freshly restarted task gets buried before it can warm up and start serving. If 10% of your fleet is healthy enough to answer at any moment, the load has to fall to around 1,000 requests per second before the thing stabilises.

Ten percent of the traffic. Not ninety.

This is why backpressure is not a nice-to-have that you retrofit after the first outage. Once you are over the cliff, the cheap interventions have all stopped working. The decisions have to be made on the way in, while the queue is still filling, and there are only a few of them to make.

Three things a queue can say

Once you accept that overload is a design surface, there are only a few sentences a queue can utter, and picking one is the whole job.

Wait

The caller blocks until there is room. Correct when the caller is a pipeline stage that has nowhere else to be, and disastrous when the caller is a request thread holding a connection. Blocking propagates backwards, and that’s the point: it is how the pressure reaches whoever can actually slow down.

Say no

The request is rejected immediately with a signal the caller understands. This is the right default for anything user-facing, because a fast failure is composable and a slow success is not. The critical detail is which request you drop:

// Shedding the newest arrival is the obvious instinct and it is not
// quite right. Under sustained overload the item at the head of the
// queue is the one most likely to have already lost its caller, so
// evicting it reclaims capacity that was about to be wasted anyway.
func (q *Queue) Push(req *Request) error {
    if q.Len() < q.cap {
        q.items = append(q.items, req)
        return nil
    }
    if oldest := q.items[0]; time.Since(oldest.Enqueued) > oldest.Deadline {
        q.items = append(q.items[1:], req)   // drop the corpse, admit the live one
        metrics.ExpiredDrop.Inc()
        return nil
    }
    return ErrOverloaded                      // genuinely full of live work
}

Note the condition on that eviction: it only drops the head when the head has already blown its deadline. Blind head-dropping is not a free win, and the queueing literature is careful not to claim it is.¹¹Facebook’s Ben Maurer makes the underlying observation in Fail at Scale: under heavy queueing the first-in request has often been waiting so long that the user has already abandoned whatever generated it. Their fix is adaptive LIFO, which changes the order work is served in rather than which item gets dropped. The version above is the narrower, safer claim: evict what has provably expired.

Google’s version of the same observation is the one I find easiest to repeat. If a search has been queued for ten seconds, the user has almost certainly hit refresh, which means you now have two copies of that request and nobody waiting for either.

Slow down

The queue reports its depth upstream and the producer reduces its rate. This is the only one of the three that actually solves anything, and it’s the one that requires the producer to have been designed for it. Retrofitting rate control onto a client fleet you don’t own is not engineering; it’s diplomacy.

All three, though, depend on something the queue does not have by default, and cannot work out for itself.

A queue can’t shed what it can’t date

Every policy above turns on one question: has this request’s caller given up? A queue can’t answer that unless the caller said so on the way in, and by default, it didn’t.

gRPC is the clearest case, because its own documentation admits the problem in the first line of the section. By default gRPC sets no deadline at all, which means a client can wait for a response effectively forever, and the advice is to always set one explicitly (gRPC). Not “tune it”. Set one at all.

Without that, a server cannot distinguish live work from dead work, and every shedding policy above degenerates into guessing. Google’s SRE book puts the cost plainly: servers spend resources on requests that have already exceeded their deadline at the client, and you get no credit for late work.

There’s a lovely detail in how gRPC passes the deadline down the chain, and it’s worth knowing because it tells you what the protocol designers were afraid of. When your server calls another server, it does not forward the deadline as a point in time. It converts it to a timeout, subtracting the time already spent, and sends that instead. The reason is that the two machines’ clocks might not agree, and a deadline is worthless if the recipient reads it against a different clock.

So a system with working backpressure is one where every request carries a countdown that was started once, by the only participant who knows what it’s for, and decremented honestly at every hop. That’s a real design commitment and it is usually made late, badly, or never.

Once each request carries its own clock, the metric you should have been watching all along becomes computable.

Measure queues in seconds, not items

The most useful reframing I know: queue depth in items is nearly meaningless, and queue depth in time is nearly always the right metric.

                items                      seconds
   depth = ─────────────────   →   delay = ───────────
             (a number)                     depth / rate

Ten thousand items is alarming or fine depending entirely on the service rate. On a session cache turning over 50,000 a second it’s 200 milliseconds and nobody should be woken up. On a report builder managing four a second it’s forty-two minutes, and every caller left hours ago.

Same alert. Same dashboard. Same max_queue_size in the same config file, copied from one service to the other by someone being consistent.

Three seconds of backlog, on the other hand, is three seconds of backlog on every service in the world, and it compares directly against the deadline the caller gave you. Alert on the seconds. Autoscale on the seconds. Shed on the seconds.

Here are those three services with the same number of things queued up. Slide the depth and watch how little the item count tells you:

The relationship underneath that conversion is Little’s Law, which is the reason it’s a single division rather than a model.

And it isn’t a new idea. The networking people got there first, and their version is more disciplined than anything I’ve seen in a service codebase. CoDel, the algorithm that fixed bufferbloat, controls sojourn time rather than buffer occupancy, so it tracks how long each packet sat rather than how many packets there were (Nichols and Jacobson, later RFC 8289).

The thing worth stealing is how small it is. CoDel’s entire configuration is two numbers: a target of 5 milliseconds and an interval of 100. The interval is the only setting it genuinely requires, and the 5 isn’t a magic constant either, it’s derived, at 5 to 10% of a typical 100 millisecond round trip.

An algorithm that fixed a decade-long problem across the entire internet has one required knob, and it is measured in milliseconds. Meanwhile your service has max_queue_size: 10000, which is not measured in anything.

Which leaves the obvious question. If your queue policy were wrong, how would you find out?

The one test worth running

Reliability work has a bad habit of testing the happy path harder. The property that actually matters here is monotonic:

As offered load increases past capacity, goodput must not decrease.

A system that peaks at 12k requests per second and delivers 11k at 30k offered load is healthy. One that peaks at 14k and collapses to 900 is not, no matter how much better its benchmark number looked. Plot goodput against offered load and push it well past the knee. That curve is the single most informative graph you can produce about a service, and almost nobody produces it.

So here it is. Drag the load past capacity and watch the three policies from earlier separate. They’re identical below the knee, which is the whole problem: the region where they differ is the region nobody load-tests.

Run the load test past the point where it stops being flattering. That is where the design language is either present or absent.

The failure mode you’re looking for on the right-hand side has a name, and it’s nearly as old as the internet. Nagle described it in 1984 as congestion collapse, where throughput drops to a small fraction of normal because everything is being sent several times (RFC 896). Sally Floyd’s later restatement is the one to quote at a design review, because it’s exactly the curve above: congestion collapse is when an increase in load produces a decrease in useful work done (RFC 2914).

Which brings us back to 400 yards. That link in 1986 wasn’t short of bandwidth and the machines at each end weren’t broken. Every part of the system was working exactly as written, and the emergent behaviour of all of them together was to do a thousandth of the useful work they were capable of.

Forty years later, the fix is still the same fix: decide, in advance and on purpose, who waits.

Sources

Standards and documentation

• Nagle, J. Congestion Control in IP/TCP Internetworks, RFC 896, 1984.
• Floyd, S. Congestion Control Principles, RFC 2914 / BCP 41, 2000.
• Nichols, K., Jacobson, V., McGregor, A. and Iyengar, J. Controlled Delay Active Queue Management, RFC 8289, 2018.
• Beyer, B. and others. Addressing Cascading Failures, Site Reliability Engineering, chapter 22, Google, 2016.
• gRPC. Deadlines, gRPC documentation.

Papers and articles

• Little, J. D. C. A Proof for the Queuing Formula: L = λW, Operations Research 9(3), 1961.
• Jacobson, V. and Karels, M. J. Congestion Avoidance and Control, SIGCOMM, 1988.
• Nichols, K. and Jacobson, V. Controlling Queue Delay, ACM Queue 10(5), 2012.
• Maurer, B. Fail at Scale, ACM Queue 13(8), 2015.