Appendix C — Queueing and Capacity Formula Sheet

Start with the quantity you can observe and the decision you must make. If you need average in-flight work, use a conservation law. If you need waiting from an arrival model, choose a queue model and accept its assumptions. If you need a capacity ceiling, use service demand. If you need recovery time, model net drain. These formulas answer different questions; swapping one for another is the most common queueing error.

Every card in this appendix carries four items: question, equation, conditions, and failure signal. Keep the conditions beside the number when copying a result into a design record. Appendix A defines units and notation. Chapters 6, 54, and 55 provide the causal and operational treatment that this compact reference deliberately does not repeat.

Choose the law by the decision

M/M/1 means memoryless (Poisson) arrivals, memoryless (exponential) service, and one server. M/M/m keeps the first two assumptions and uses m equivalent parallel servers. The notation is an assumption register, not a decorative label.

Conservation card: Little’s Law

Question: What is the long-run average number of units inside a defined boundary?

L = λW

• L: average units in the system or queue, as a count;
• λ: long-run effective flow rate through that boundary, in units/s;
• W: average time per unit within the same boundary, in seconds.

Use admitted or completed flow consistently when work can be rejected, abandoned, duplicated, or retried. Apply the law to the whole system for average response time, or to the waiting line alone for average queue wait. Do not combine system L with queue-only W_q.

Worked check. Mercury completes 2,400 request/s, and accepted requests spend an average 0.075 s from admission to completion:

L = 2,400 request/s × 0.075 s/request = 180 requests

This estimates average in-system concurrency. It does not promise a p99, prove a queue bound, or say that exactly 180 requests are always present.

Conditions. Use compatible long-run averages over a stable observation regime with conserved flow and finite means. A finite measurement window can still use the relationship as an accounting identity if arrivals, departures, and boundary-crossing residuals are handled explicitly; a naive rate-times-latency product during a ramp or drain can be misleading.

Failure signal. If computed L disagrees with observed occupancy, first audit population and boundary: retries counted in λ but not L, censored durations, work present at the window edges, or queue depth that excludes active service.

Demand card: utilization and capacity

Question: How much of resource r does useful work consume?

U_r = X × D_r
D_r = V_r × S_r

• X: useful completion rate, completions/s;
• D_r: service demand at resource r per useful completion, resource-s/completion;
• V_r: average visits to the resource per completion;
• S_r: mean service time per visit;
• U_r: busy resource-equivalents. Divide by m_r to express average fraction across m_r equivalent servers.

If a completion visits storage 1.5 times and each visit consumes 1.2 ms of storage service, D_storage = 1.8 ms/completion. At 200 completion/s, total demand is 0.36 storage-s/s. On one equivalent server the modeled utilization is 36%; on two equivalent servers it averages 18% each, before imbalance and coordination.

The utilization must satisfy ρ < 1 for a stationary single queue. A design target well below one is not waste by definition: headroom absorbs variability, skew, failover, deployment, estimation error, and recovery work. Fleet-average ρ can hide one saturated shard.

Failure signal. If throughput rises but measured utilization does not follow X × D, test whether demand changed with workload mix, offload moved work, throttling altered clock time, the resource counter misses work, or completions include failures that consume different demand.

Exact teaching model: M/M/1

Question: Under Poisson arrivals and exponential service, how does one work-conserving server’s mean wait grow with utilization?

ρ   = λ/μ
W   = 1/(μ - λ)
W_q = ρ/(μ - λ) = W - 1/μ
L   = λW
L_q = λW_q

Here λ is arrivals/s, μ is services/s, 1/μ is mean service time, W_q is mean waiting before service, and W is mean time including service. A stationary result requires λ < μ.

With λ = 80/s and μ = 100/s:

ρ   = 0.8
W   = 1/(100 - 80) = 0.050 s = 50 ms
W_q = 50 ms - 10 ms = 40 ms
L   = 80/s × 0.050 s = 4 requests

At λ = 90/s with unchanged service, utilization rises only from 80% to 90%, but W doubles to 100 ms. The denominator μ - λ is the remaining service margin; shrinking it creates the nonlinear knee.

What the model assumes. Poisson independent arrivals, independent exponential service times, one stable equivalent server, no finite queue limit, no abandonment, no priorities, and steady state. The mean response formula is insensitive to a work-conserving discipline in some special single-server settings, but tail, fairness, and class behavior are not.

Failure file: bounded concurrency. A worker pool with rejections at 64 in-flight requests cannot have the unbounded M/M/1 stationary distribution. Use the formula only as a diagnostic comparison below the bound; model admission, rejected work, and client retry behavior explicitly.

Equivalent parallel servers: M/M/m and Erlang C

Question: What mean queue wait is predicted for m equivalent first-come first-served servers under Poisson arrivals and exponential service?

Let offered traffic a = λ/μ in erlangs and ρ = a/m < 1. The probability an arrival must wait is:

P(wait) = [a^m / (m! (1-ρ))]
          -----------------------------------------
          [Σ from k=0 to m-1 of a^k/k!] + [a^m / (m! (1-ρ))]

W_q = P(wait) / (mμ - λ)
W   = W_q + 1/μ

For λ = 240/s, μ = 50/s per server, and m = 6, offered traffic is 4.8, utilization is 80%, P(wait) ≈ 0.517772, and modeled W_q ≈ 8.630 ms. Mean service is 20 ms, so W ≈ 28.630 ms.

Do not replace this with an M/M/1 queue whose service rate is mμ. Six simultaneous jobs can receive service in M/M/6; a single pooled super-server processes only one job at a time. They have different waiting behavior.

Escalate instead of trusting Erlang C when servers differ, requests pin to shards, work stealing is delayed, service depends on class, arrivals abandon, jobs require multiple resources simultaneously, or scaling changes cache locality. Simulation, trace replay, or a measured queue curve may be a better decision aid.

Variability card: Kingman-style G/G/1 approximation

Question: How do arrival and service variability change mean one-server waiting when memoryless assumptions are weak?

W_q ≈ ((c_a² + c_s²) / 2) × (ρ / (1 - ρ)) × E[S]

• c_a² = Var(A)/E[A]²: squared coefficient of variation (SCV) of inter-arrival times;
• c_s² = Var(S)/E[S]²: SCV of service times;
• ρ = λE[S] < 1;
• E[S]: mean service time.

This is commonly remembered as variability × utilization × time. For Poisson arrivals and exponential service, both SCVs are 1 and the expression reduces to the M/M/1 mean wait.

With λ = 80/s, E[S] = 10 ms, c_a² = 1.5, and c_s² = 2.0:

ρ = 80/s × 0.010 s = 0.8
W_q ≈ ((1.5 + 2.0)/2) × (0.8/0.2) × 0.010 s
    = 0.070 s = 70 ms

The corresponding M/M/1 wait at the same mean rate and service time is 40 ms. Variability—not extra mean work—accounts for the modeled difference.

Kingman’s heavy-traffic reasoning is an approximation for a stable single-server queue. Independence, representative moments, and operating regime matter. Batching can make inter-arrivals bursty; cache misses can make service multimodal; retries can correlate arrivals with slow service. SCVs estimated over a mixed or drifting window can therefore summarize the wrong process.

Failure signal. If the observed curve bends earlier than the approximation, inspect hidden serialization, priority inversion, synchronized arrivals, per-class demand, downstream blocking, and service-time/load correlation before fitting a larger “variability factor.”

Bottleneck laws and capacity ceilings

Question: Which resource sets the highest possible useful throughput under the measured demand vector?

For resource demands D_1 ... D_K per useful completion:

D_max = max(D_k)
X_max ≤ 1 / D_max                 one equivalent unit at each resource
X_max ≤ m_k / D_k                 m_k equivalent units at resource k

The bottleneck is the resource with the largest demand relative to its effective parallel capacity. Suppose CPU, store, and network demands are 3.2 ms, 1.8 ms, and 0.7 ms per completion. CPU is the modeled bottleneck and its one-core ceiling is:

1 / 0.0032 CPU-s/completion = 312.5 completion/s per equivalent core

This is an upper bound, not a safe operating rate. Queueing, imbalance, coordination, background work, failure headroom, and changing mix reduce safe goodput. Adding CPU can move the bottleneck to storage; recompute the whole demand vector after each material design change.

For operation classes j, construct a workload-weighted demand:

D_r = Σ mix_j × D_(r,j)

Average mix can hide a hot tenant or shard. Capacity review should include peak class mixes and degraded/recovery states, not only the nominal blend.

Closed workloads and the interactive-response law

Question: For a fixed population that alternates between thinking and requesting, how are population, throughput, and response related?

N = X(R + Z)
R = N/X - Z
X = N/(R + Z)

• N: fixed circulating users or jobs;
• Z: mean think or delay time outside the measured system;
• R: mean response time inside it;
• X: completion rate.

This is Little’s Law applied to the closed cycle. It describes interactive users, terminal workloads, or a fixed worker population. It does not describe an open external arrival stream that continues regardless of response time.

If the no-queue service demands sum to 5.7 ms, N = 120, and Z = 2.0 s, the response-free upper line is:

X ≤ N/(Z + ΣD_k) = 120/(2.0 + 0.0057) ≈ 59.8 completion/s

The bottleneck ceiling from the preceding CPU demand is 312.5/s, so at this population and think time the interactive bound is lower. As population grows, the bottleneck ceiling eventually dominates and response time grows approximately as N/X_max - Z.

Measurement trap. A closed load generator self-throttles when the service slows: offered rate falls because virtual users wait for responses. It can produce deceptively bounded queues. Use a closed model when it represents user behavior; use an open schedule when production demand does not wait.

Queue age, depth, and deadline value

Depth is a count; age is elapsed time. Measure age directly from enqueue timestamps:

age_i(t) = t - enqueue_time_i
oldest_age(t) = max age among queued units

For first-come first-served work with roughly stable arrivals, Q/λ can be a rough average waiting-scale estimate through Little’s Law. It is not the oldest age, a tail bound, or valid during an arbitrary burst. Priority queues can have low overall depth while one class starves. Retries can inflate depth without increasing useful demand.

Compare age with remaining value:

remaining_slack = deadline - now - estimated_remaining_service

When remaining slack is negative and completion has no independent value, early cancellation or admission rejection protects goodput. Preserve operations whose effects must complete for correctness, and design compensation or idempotency instead of discarding them blindly.

Queue telemetry should include depth, oldest or selected age, arrival and completion rates, wait distribution, service distribution, rejections, abandonment, priority class, and deadline success. A bound needs a defined action: reject, shed, expire, spill, persist, degrade, or block upstream.

Backlog drain and recovery

Question: How long will a backlog take to drain while new work continues arriving?

For constant rates and μ_drain > λ_new:

net drain rate = μ_drain - λ_new
T_drain = B_0 / (μ_drain - λ_new)

With B_0 = 180,000 jobs, new arrivals 1,200 job/s, and completions 1,500 job/s:

T_drain = 180,000 jobs / 300 job/s = 600 s = 10 min

If arrivals equal completions, the backlog never drains. If arrivals exceed completions, it grows. If jobs expire or are deduplicated, count valuable remaining work rather than raw records.

Constant rates are rarely adequate for recovery. Completion demand may rise because caches are cold, replicas rebuild, messages replay, and dependencies throttle. A piecewise model is safer:

B_(t+Δ) = max(0, B_t + arrivals_t - completions_t - expirations_t)

Recalculate each interval with observed class mix and protected foreground capacity. Do not assign every spare worker to drain if that steals capacity from new deadline-bound work and triggers a second collapse.

Failure file: the recovery estimate that doubles work. A team observes 300 job/s spare capacity and announces a ten-minute drain. Consumers then read cold data, retries double attempts, and the downstream store limits completion to 1,250/s. Net drain falls to 50/s; the same useful backlog needs an hour. The original arithmetic was correct for the wrong recovery demand.

Formula failure patterns

Applied checks with answers

Foundation — conservation audit. A queue reports average depth 90, throughput 600 job/s, and mean wait 100 ms. Queue-only Little’s Law predicts L_q = 600 × 0.1 = 60, not 90. Do not “correct” the formula. Check whether depth includes 30 active jobs, throughput excludes retries, wait excludes time before persistence, or the window is draining. The discrepancy is an instrumentation and boundary question.

Field — variability decision. Two single-server designs both average 10 ms service at 80% utilization. Design A has c_a² = c_s² = 1; Design B has c_a² = 1.5, c_s² = 2.0. Kingman’s approximation predicts waits of 40 ms and 70 ms. A viable response may smooth arrivals, split variable classes, reduce service variance, or lower utilization. Adding mean capacity without inspecting the variability mechanism is not the only option.

Principal — recovery control. A 180,000-job backlog has a ten-minute constant-rate estimate. Require a piecewise plan with foreground reservations, cold-cache and rebuild demand, retry suppression, expiration policy, downstream limit, abort threshold, and measured net useful drain. If the net drain becomes nonpositive for two intervals, stop increasing replay and protect new goodput. Alternative policies are valid if they preserve invariants and state their recovery objective.

Field card

Before using a queueing or capacity result, ask:

• Is the workload open, closed, or a mixture of both?
• Are λ, L, and W defined on exactly the same population and boundary?
• Does utilization describe the actual constraint, server count, shard, and interval?
• Are service demand and visit count normalized per correct useful completion?
• Which arrival, service, scheduling, independence, and steady-state assumptions does the queue model require?
• Are variability, skew, priority, abandonment, retries, batching, and blocking material?
• Is the result an average, upper bound, approximation, or direct observation?
• What evidence would show the model has stopped transferring?
• Does capacity include failure, deployment, recovery, and workload-mix headroom?
• Is queue age measured directly and connected to deadlines or freshness?
• Is backlog recovery based on net useful drain after new arrivals and recovery amplification?
• What operational action follows when the bound is crossed?

Use conservation laws broadly, stochastic queue formulas narrowly, and measurements continuously. The best model is the smallest one that disqualifies a bad design or names the next decisive observation.

A law still needs credible inputs. When target measurements do not yet exist, begin with a dated range whose boundary and transfer limit are visible; then replace that range as soon as it crosses a decision threshold or failure state changes the mechanism.

Sources and evidence scope

• John D. C. Little, “A Proof for the Queuing Formula: L = λW,” Operations Research 9(3), 1961 establishes the long-run mean relationship under stated stochastic conditions. This appendix applies it to explicitly bounded engineering populations.
• J. F. C. Kingman, “On Queues in Heavy Traffic,” Journal of the Royal Statistical Society: Series B 24(2), 1962 establishes the heavy-traffic foundation behind the single-server variability approximation. The field formula is an approximation, not a tail guarantee.
• Peter J. Denning and Jeffrey P. Buzen, “The Operational Analysis of Queueing Network Models,” ACM Computing Surveys 10(3), 1978 develops operational relationships including utilization, bottleneck, and interactive response-time laws from observable quantities.
• M. Reiser and S. S. Lavenberg, “Mean-Value Analysis of Closed Multichain Queuing Networks,” Journal of the ACM 27(2), 1980 provides the recursive product-form closed-network method. This appendix uses only the simpler interactive relationship and does not claim product-form behavior for arbitrary services.
• The Little, M/M/1, Erlang C, Kingman, bottleneck, interactive, and backlog examples are illustrative models verified by examples/performance-engineering-system-design-handbook/appendices/statistics-and-queueing/verify.mjs. The fixture checks arithmetic only; it cannot verify stationarity, distributional form, independence, equivalence of servers, representativeness, or production transfer.