Admission control and queuing

Why is the queue the control surface, and why should deadlines be checked at dequeue?

With N requests in flight against a fixed capacity, each gets about 1/N of the resource. So per-request latency grows linearly with N while the completion rate stays flat.

Little's Law (L = λW) then gives you the only two knobs there are:

• hold N constant: a concurrency limit; or
• hold W constant: a deadline or timeout.

You cannot hold both while the arrival rate λ is chosen by someone else.

The queue is the control surface

So the queue in front is not a buffer. It is the control surface, and its depth is a latency budget in disguise:

An unbounded queue is a declaration that you would rather be infinitely late than ever refuse. That is how you get requests whose client gave up before the work started. The key distinction:

• Throughput counts work completed.
• Goodput counts work whose result is still wanted.

Past the knee the two diverge, and a system optimizing throughput will happily spend 100% of its capacity on abandoned requests. That is Lena's problem 2.

Forms of admission

Admission takes several forms, and most systems already have some of them without noticing:

• Concurrency limiting. At most N requests in flight; queue or reject the rest. Little's Law makes this a latency guarantee: bounded concurrency plus a known service time gives a bounded queueing delay. This is the most reliable form of overload protection, because it limits the very thing that causes collapse.
• Connection and pool limits. A bounded connection pool is admission control, and most systems already have one without noticing. What happens when the pool is exhausted (block forever, block with a timeout, or reject) is a load-shedding policy hidden in a configuration file. Go and check that setting. It is very often "block forever".
• Resource reservation. The request declares what it needs, and you admit it only if that is available. Warehouse-style query admission and YARN or Kubernetes scheduling work this way.
• Priority admission. Reserve a fraction of capacity for high-priority work so that it can always get in. This prevents priority inversion (low-priority work holding the resources high-priority work needs) under sustained load.
• Cost-based admission. Estimate the cost before admitting, and reject or queue the expensive queries. Every serious analytical warehouse does this, and it is why a warehouse degrades gracefully where a naive query service falls over.

Admission and shedding act at different times

Load shedding drops work already accepted. Admission control declines it before any resources are committed. Why it beats shedding where it is available. Rejecting at time 0 costs one cheap decision. Shedding at 500 ms costs 500 ms of work across several systems, all wasted. Admission control is fail-fast in its cleanest form, and the earlier a failure happens, the cheaper it is.

Why you still need shedding. Admission decisions are based on estimates. Some admitted work turns out to be much more expensive than predicted. Some capacity disappears after admission (a dependency slows down, a node dies). Shedding corrects the cases where admission control was wrong. You want both: they act at different times with different information.

The cheap fix: check the deadline at dequeue

The fix is cheap and rarely implemented: check the deadline at dequeue, not at completion. If the remaining deadline is less than the expected service time, discard the request now. It is going to fail anyway, and failing before spending the resource is free capacity.

def worker_loop(queue):
    while True:
        req = queue.pop()
        remaining = req.deadline - now()
        if remaining < expected_service_time(req):
            req.reject("deadline would be missed")   # costs almost nothing
            continue
        run(req)

This is where rejecting is a service, not a failure. A fast "no" lets the client retry elsewhere or tell the user, and it keeps the capacity for requests that can still succeed.

A bounded queue is admission control. Its depth is the latency you have agreed to tolerate.