Queue amplification and unbounded buffering

How big should a queue be, and why does queue discipline matter more than size under overload?

A queue does not add capacity. Draining L items at rate λ takes L/λ, whatever the reason they are there, so a buffer is a pure latency device: its only defensible size is the service rate times the latency you will accept (admission and queuing). Every slot beyond that stores work that will be stale before anyone serves it. Making buffers cheap and large does not help either: it removes the loss signal a control loop depends on (bufferbloat).

Two consequences

1. A bounded queue is a feature. It converts a latency failure into an error, and an error is a better failure: it is fast, the client can understand it, and it does not consume downstream capacity. This is "fail fast" over "fail degraded".
2. Queue discipline matters more than queue size under overload. If the delay exceeds the timeout, a FIFO queue serves only abandoned requests: exactly 0% goodput, the worst possible policy at the worst possible moment.
   • LIFO serves the newest arrivals, which are the only ones still being waited on, and gives degraded but nonzero goodput.
   • Discard at dequeue is better still: check the deadline when an item leaves the queue, and drop it for free if it has expired.

The general principle: a queue must have a discard policy. If it does not, the discarding still happens, but the client does it, through timeout and retry, which is the most expensive mechanism available. LIFO has a cost: unfairness, and possible starvation of the oldest requests. That is why it is an overload mode, not a default.

# Discard at dequeue: never spend work on a request nobody is waiting for.
def worker(queue):
    while True:
        req = queue.pop_newest()          # LIFO end, used only while overloaded
        if now() > req.deadline:
            continue                      # expired: drop it for free
        handle(req)