Deadline-Derived Queue Depth

Most frameworks ship with an unbounded request queue, and most teams that bound one pick a round number from memory pressure. Both are wrong for the same reason: the only thing a queue should hold is work that will still be wanted when it reaches the front.

The depth that satisfies that is arithmetic. Completion rate is the concurrency limit divided by mean service time. A request entering at depth N waits roughly N divided by the completion rate. Set the depth so that wait stays inside the latency objective, and the queue is self-limiting without any shedding policy.

Why it matters

With 60 concurrent slots and a 50 ms service time the service completes 1,200 requests per second. A 2-second client deadline gives a hard ceiling of about 2,400 — and at that depth a request arrives at the front with its entire budget spent and no time left for the work. Size from the objective instead: 1,200 × 0.4 s ≈ 480 slots for a 400 ms p99 target.

Beyond that depth every extra slot stores a request that will expire before it is served. The service continues at 1,200 per second with CPU fully busy while the share of completions anyone still wants falls — throughput holds and goodput collapses, and a CPU or throughput graph cannot show it.

Implementation patterns

• Derive the number, record the derivation. Put concurrency limit, measured service time, completion rate and objective in the comment next to the constant, so the next person can recompute it when service time changes.
• Check the deadline at dequeue and drop expired entries unserved. Served-but-expired work is the purest waste a system produces.
• Serve newest-first under overload. FIFO hands the server the oldest and most likely expired request; LIFO or deadline ordering keeps some requests inside budget instead of failing all of them equally.
• One queue and limit per service class where service times differ by orders of magnitude, because a single depth cannot be correct for 2 ms and 4 s work at once.
• Recompute after any change to concurrency or service time, and treat a drifting service time as a reason to move to an adaptive limit rather than to raise the depth.

Industry example

A search platform of Baidu's shape makes the rule unavoidable. A query is useless after a few hundred milliseconds — the user has retyped or left — and the front end fans out to many shards, so every shard's queue must be short enough that a queued sub-request still fits inside the page's budget. The tail-at-scale literature (CACM 2013) states the resulting design directly: queue almost nothing, shed early, and return partial results on time rather than complete results late. Overload then shows up as a thinner result set instead of a slow page.

Failure scenarios

• An unbounded queue, which converts an overload that would have been visible as rejections into unbounded latency and eventual memory exhaustion, with every response produced after its deadline.
• A depth chosen from memory, typically far beyond the deadline bound, which looks like resilience and is a guarantee of timeouts.
• FIFO under sustained overload, where the server works continuously and every request it completes has already expired.
• One shared queue for mixed service times, where slow requests occupy the depth and fast ones queue behind them.

Trade-offs

A bounded queue rejects requests the system might eventually have served, so the visible error rate rises while what users receive improves. That exchange must be agreed before an incident.

The depth also needs maintenance. Service time changes with every release and every dependency, so a fixed depth decays; keeping it correct costs either a recurring measurement or a move to an adaptive limiter, which is more machinery to operate. The simplest defensible position is a conservative depth plus deadline dropping, since dropping makes an over-large depth harmless.

When not to use it

If there is no client deadline, there is no derivation. Durable background work — a job queue, an ingestion buffer, an outbox — should be bounded by storage and retention, not by latency, because late is not failure there. A pure proxy with no per-request work is the other exception: the scarce resource is sockets, and connection limits plus the accept backlog are the right instruments.

Interview question

Q: "Our request queue is set to 10,000 and under load we see timeouts with healthy CPU. Someone proposes raising the queue to 50,000 so we stop dropping work. Respond, and give me the number you would use instead."

What a strong answer covers: completion rate from concurrency over service time; the deadline ceiling and the objective-derived depth; why depth beyond the bound stores doomed work and collapses goodput while throughput holds; deadline checks at dequeue and newest-first ordering; and the conditions under which an unbounded queue is actually right.

Quick check

Quiz: 60 slots, 50 ms service time, 400 ms p99 objective. What queue depth? About 480 — 60 ÷ 0.05 = 1,200 completions per second, times 0.4 s.

Flashcard: What happens to a service whose queue is deeper than its deadline allows? — It stays fully busy while the share of completions anyone still wants falls, so throughput holds and goodput collapses.