Queueing, Little's Law & Scalability

The BoxOffice inventory database is at 70% CPU during a normal on-sale and holds take about 75 ms at p99. The team decides it has "30% to spare". At the next, bigger on-sale the CPU reaches 92% — only 22 points more — and the p99 jumps to almost 300 ms, four times worse and right at the 300 ms hold target. Timeouts fire, clients retry, and the extra load pushes the database to 100%. Nothing was "broken"; the team simply did not know the shape of the curve that relates load to latency. This page derives that curve from a few simple laws, and then uses the same laws to answer the questions that every capacity decision asks: how many requests are in flight? how big must this pool be? how full can this component run? will adding nodes help?

The vocabulary of a queue

Every component that serves requests — a CPU core, a thread pool, a database connection, a payment API — can be seen as a queue in front of one or more servers (in queueing theory, a "server" is anything that serves a request):

flowchart LR
    arrivals(["Arrivals<br/>λ requests/s"]) --> queue["Queue<br/>(waiting: Wq)"]
    queue --> s1["Server 1<br/>(service: S)"]
    queue --> s2["Server 2"]
    queue --> s3["Server c"]
    s1 --> out(["Completions<br/>X requests/s"])
    s2 --> out
    s3 --> out

Little's Law

The most useful formula in capacity planning is also the simplest¹:

The average number of requests in a system equals the average arrival rate times the average time each request spends in the system. It holds for any stable system (arrivals do not exceed capacity in the long run), regardless of the distribution of arrivals or service times, the number of servers, or the scheduling order. You can apply it to a thread pool, a whole service, a queue, a database — or a coffee shop: if 2 customers arrive per minute and each stays 15 minutes, there are on average 30 customers inside.

Its three forms answer three different questions:

Little's Law as a lie detector for load tests

A load-testing tool with a fixed number of virtual users (VUs) that each send a request, wait for the response, "think" for Z seconds and repeat is a closed system. Little's Law applied to it says:

With 100 VUs, no think time (Z = 0) and R = 50 ms, the test cannot produce more than 100 / 0.05 = 2,000 req/s, whatever the server could take. If the server slows down to R = 500 ms, the test generates only 200 req/s — the load drops exactly when the system struggles, hiding the problem. Check every load-test result with this formula; lab 2 does it, and class 15 discusses open vs closed workload models.

The utilization law

A second, equally simple law connects throughput and utilization:

The utilization of a resource equals its throughput times the service time per request. A database that serves 1,000 holds/s at 5 ms of CPU each needs 5 CPU-seconds per second: 5 cores at 100%, or 62.5% of 8 cores. Turned around, it gives the capacity of a resource: utilization cannot exceed 100% per server, so

That is the "parallel slots divided by service time" rule used in the overview. The resource with the highest utilization (the largest ratio of demand to capacity) is the bottleneck: it saturates first and caps the throughput of the whole system.

Why latency explodes before 100%: the knee

If requests arrived at perfectly regular intervals and each took exactly S, a server could run at 99% utilization with no waiting at all. Real traffic is random: requests arrive in bursts, and some take longer than others. During a burst, requests queue; the queue drains during quiet moments. The busier the server, the fewer quiet moments it has to catch up — and the longer the queues grow.

The simplest model of this is the M/M/1 queue: random (Poisson) arrivals, random (exponential) service times, one server. Its mean response time is²:

(In M/M/1 the response time is exponentially distributed, so its p99 is ln(100) ≈ 4.6 times its mean.) Going from 50% to 90% utilization — less than double the load — makes the response time 5× worse; from 90% to 99% — 10% more load — another 10× worse. That is exactly the story of the BoxOffice inventory at the top of this page.

The plot shows R / S as a function of utilization for one server (M/M/1, mean and p99), and for 4 and 16 servers sharing one queue (M/M/c, computed with the Erlang C formula):

Three lessons from the curves:

1. The knee. Latency is almost flat at low utilization, then bends sharply. For a single server the bend is around 70–80%; past it, small increases in load cause huge increases in latency, and the tail (p99) explodes first.
2. Pooling helps. With 16 servers sharing one queue, the knee moves far to the right: a request only waits if all servers are busy. That is one reason why one big pool behind a load balancer behaves better than many small, separate queues (for example, sticky routing of users to specific servers).
3. Variability is the enemy. The M/M/1 model assumes very random arrivals and service times. More regular traffic queues less; burstier traffic (an on-sale!) queues more. Kingman's approximation for a single server makes this explicit³:

where \(C_a\) and \(C_s\) are the coefficients of variation (standard deviation / mean) of the inter-arrival and service times. The first factor is the utilization effect; the second is the variability effect. A waiting room that admits fans at a steady rate lowers \(C_a\); cutting slow outliers (a heavy query that takes 50× the normal time) lowers \(C_s\). Both reduce queueing without adding a single server.

What utilization should you run at?

Redundancy pushes in the same direction: with 4 replicas at 60%, losing one moves the other three to 80% — still serviceable. With 4 replicas at 80%, losing one asks for 107%: the remaining replicas collapse. Headroom is what makes failover work.

Try it: run the breakpoint profile, then double the database's capacity (or add app replicas) and run again. Does the knee move? By how much? If adding app replicas does not move it, which component is the bottleneck?

#!/usr/bin/env bash
# Lab 2: run load.js once per arrival rate and save one k6 summary per run.
#   bash scripts/sweep.sh 25 50 100 150 200 300 400
# Then:  uv run scripts/summarize.py results/lab2/rate-*.json
set -euo pipefail
OUT=${OUT:-results/lab2}
DURATION=${DURATION:-1m}
mkdir -p "$OUT"
echo ">>> warm-up: 30 s at RATE=$1 (not recorded)"
k6 run -q -e RATE="$1" -e DURATION=30s load/load.js > /dev/null || true
for rate in "$@"; do
  echo ">>> RATE=$rate req/s for $DURATION"
  # || true: a run that crosses a threshold still produces a summary; keep sweeping
  k6 run -q -e RATE="$rate" -e DURATION="$DURATION" \
     --summary-export "$OUT/rate-$rate.json" load/load.js > /dev/null || true
  sleep 10   # let queues drain before the next step
done

When more servers stop helping

Little's Law and the utilization law suggest that capacity grows linearly with the number of servers: X_max = c / S. In practice it does not, because servers coordinate. Two classic models describe how scaling bends.

Amdahl's law

If a fraction σ of the work is inherently serial (cannot be parallelized — a global lock, a single primary, a sequential step), then with N parallel workers the speedup is bounded⁴:

With 5% serial work, no number of nodes gives more than 20× speedup; with 1%, 100×. For BoxOffice: if every hold must pass through the same lock on the same "section counter" row for even 5% of its time, adding inventory replicas stops paying off long before 20 replicas.

The Universal Scalability Law

Neil Gunther's Universal Scalability Law (USL) adds a second term, κ (coherency), for the cost of keeping nodes consistent with each other — cache invalidation messages, distributed locks, cluster membership chatter, replication — which grows with the number of pairs of nodes, roughly N²⁵:

With κ > 0, throughput does not just flatten — it reaches a peak at \(N^* = \sqrt{(1 - \sigma)/\kappa}\) and then decreases: adding nodes makes the system slower.

The practical use of the USL is to fit σ and κ to a few load-test measurements (throughput at N = 1, 2, 4, 8…) and predict where scaling stops before buying the hardware (class 15). The design lesson is broader: shared-nothing designs scale. Partition the work so that nodes do not need to talk to each other — BoxOffice partitions inventory by event, so that holds for different events never contend — and both σ and κ shrink.

How it connects

flowchart LR
    LL["Little's Law<br/>L = λ × W"] --> POOL["thread and connection pools<br/>→ Compute, Databases"]
    LL --> WR["waiting-room wait<br/>W = L / λ → Messaging"]
    LL --> LT["load-test lie detector<br/>→ Performance"]
    UL["utilization law<br/>U = X × S"] --> CAP["capacity ≈ c / S"]
    CAP --> KNEE["the knee<br/>R = S / (1 − ρ)"]
    KNEE --> TARGET["run at 50–70%<br/>autoscaling targets → Compute"]
    KNEE --> SHED["load shedding, backpressure<br/>→ Reliability"]
    AMD["Amdahl σ<br/>hot rows, global locks"] --> PART["shared-nothing partitioning<br/>→ Databases"]
    USL["USL κ<br/>coherency cost"] --> PART

Palette components: app (worker threads = λ × W per replica) · sql (the connection pool, the primary that is "only" at 70%, row-lock contention) · queue (the waiting room: how long the last fan waits) · worker (batch workers can run at 80–90%) · payment (a slow provider multiplies the calls in flight) · nosql (shared-nothing partitions scale where the USL says a shared primary cannot). Scenarios: monolith (with the breakpoint profile), flash-sale, async-queue. Continues in: Percentiles, Compute — autoscaling lag, Reliability — load shedding, Databases — contention, Performance — capacity planning, Hands-on 2.

Key takeaways