On this page

Queueing Theory

Queueing theory is the mathematics of waiting. Every time a request hits your load balancer, enters a thread pool, joins a Kafka partition, or waits for a database connection — it enters a queue. Understanding queueing theory lets you predict when systems will break before they actually break, and explains why your p99 latency is 50x your median.

This is not abstract math. If you have ever asked "why does latency spike at 70% CPU?" or "how many instances do I need to keep p99 under 200ms?" — the answer comes from queueing theory.

Little's Law

Little's Law is the most useful result in queueing theory. It requires almost no assumptions and applies to virtually any stable system:

Where:

  • = average number of items in the system (queue + being served)
  • = average arrival rate (items per unit time)
  • = average time an item spends in the system (wait time + service time)

Intuition

If a coffee shop serves 60 customers per hour () and each customer spends an average of 5 minutes in the shop (), then at any given moment there are on average:

Application: Sizing a Connection Pool

Your service handles 1,000 requests/second. Each request holds a database connection for an average of 10ms.

You need at least 10 connections in your pool to sustain this throughput. In practice, add headroom for variance — 2-3x is common, so 20-30 connections.

Little's Law Is Model-Free

Little's Law holds for any stable system regardless of arrival distribution, service distribution, number of servers, or queueing discipline. The only requirement is that the system is in steady state (arrival rate equals departure rate over time). This makes it extraordinarily useful for quick capacity estimates.

Application: Throughput from Latency

You observe that your API has 200ms average latency () and your load balancer shows 50 concurrent requests on average (). Your throughput is:

Why Little's Law Holds

The proof idea fits in one picture. Draw, for each request, a horizontal bar from its arrival time to its departure time. Now measure the total area of all bars over a long period in two ways:

  • Row by row: each bar has length equal to that request's time in the system, and there are about requests, so the area is about .
  • Column by column: at each instant, the height of the stack of bars is the number of requests in the system, so the area is the time integral of that count, which is .

The two must be equal, so . Nothing in the argument mentions distributions, the number of servers, or the order of service. That is why the law is so general, and why it applies to any boundary you draw: one thread pool, one service, a whole data centre, or the queue alone (giving ).

Little's Law Pitfalls

MistakeWhy it is wrongCorrect use
Plugging in p99 latencyThe law relates averagesUse mean time in system. For tail sizing use a model or the distribution
Mixing boundariesMeasuring at the client but at the serverAll three quantities must describe the same box
Applying it during overloadThe law needs a stable system, where arrivals equal departures over the window. In overload, grows without bound.Check that the queue is not trending upward over the window
Ignoring retries and timeoutsA request that times out and retries counts as two arrivals to the serverCount what the box actually sees

One very practical use is as a sanity check on dashboards. If a service reports 2,000 rps, 30 ms mean latency, and an average of 400 concurrent requests, something is wrong: , not 400. Either latency is measured at a different point (excluding queueing time), or the concurrency metric counts something else, such as idle keep-alive connections.

The M/M/1 Queue

The M/M/1 queue is the simplest analytically tractable queueing model:

  • M — Arrivals follow a Poisson process (memoryless, exponentially distributed inter-arrival times)
  • M — Service times are exponentially distributed
  • 1 — One server

Despite its simplicity, M/M/1 captures the essential behavior of many real systems and explains the nonlinear relationship between utilization and latency.

Key Parameters

  • = arrival rate (requests/second)
  • = service rate (requests/second one server can process)
  • = utilization (fraction of time the server is busy)

For stability, we require (the server must be faster than the arrival rate on average).

M/M/1 Results

Average number in system:

Average time in system (wait + service):

Average time waiting in queue (before service begins):

Average number waiting in queue:

Where the Formulas Come From

Because arrivals and service are both memoryless, the state of an M/M/1 queue is just the number of requests in it. Requests arrive at rate , moving the state from to , and while the server is busy they leave at rate , moving it from to .

flowchart LR
    S0(("0")) -->|"λ"| S1(("1"))
    S1 -->|"μ"| S0
    S1 -->|"λ"| S2(("2"))
    S2 -->|"μ"| S1
    S2 -->|"λ"| S3(("3"))
    S3 -->|"μ"| S2
    S3 -->|"λ"| SN(("..."))
    SN -->|"μ"| S3

In steady state, the flow across any cut between neighbouring states must balance: . So , which gives . The probabilities must sum to 1, so and

That is a geometric distribution, and its mean is , which is the formula for . Little's Law then gives . Note two useful facts that come out for free: the server is idle a fraction of the time (as it should be), and the chance of finding at least requests in the system is . At 90% utilization, an arriving request finds 10 or more ahead of it about 35% of the time ().

The Whole Distribution, Not Just the Mean

For M/M/1 with first-come-first-served order, the time in system is itself exponentially distributed with rate . That gives percentiles directly:

So the median is the mean, p90 is , p99 is and p99.9 is the mean. With a 10 ms mean service time at 80% utilization (mean time in system 50 ms):

PercentileTime in system
p5035 ms
p90115 ms
p99230 ms
p99.9345 ms

Two lessons. First, even the friendliest textbook queue has a p99 that is many times its service time, purely because of queueing. Second, every percentile scales with , so the utilization cliff hits the tail exactly as hard as the mean, starting from a higher point.

The Utilization Cliff

This is the most important insight from queueing theory. Plot against :

Utilization Avg Queue Length Avg Wait Time Multiple
0.1 (10%)0.111.1x service time
0.3 (30%)0.431.4x
0.5 (50%)1.02.0x
0.7 (70%)2.33.3x
0.8 (80%)4.05.0x
0.9 (90%)9.010.0x
0.95 (95%)19.020.0x
0.99 (99%)99.0100.0x
graph LR
    subgraph "The Utilization Cliff"
        direction TB
        A["At 50% util:<br/>latency = 2x service time<br/>Comfortable"] --> B["At 80% util:<br/>latency = 5x service time<br/>Noticeable"]
        B --> C["At 95% util:<br/>latency = 20x service time<br/>System melting"]
    end

The 80% Rule

Never plan to run a system above 70-80% utilization in production. The relationship between utilization and latency is not linear — it is a hyperbola (). Going from 70% to 90% utilization does not increase latency by 28% — it increases it by 3x (from to the service time). This is why systems seem "fine" until they suddenly are not.

Correction: this box previously said 3.3x. The table above gives and service times, a ratio of exactly 3.

Where Is the Knee?

People talk about "the knee" of the latency curve as if it were a fixed point, so it helps to be precise. The slope of the M/M/1 curve is

At 50% utilization, one extra percentage point of load adds 4% of a service time to the mean latency. At 90% it adds a full service time, and at 95% it adds four. There is no sharp corner. The curve bends continuously, and "the knee" is wherever the slope becomes larger than your latency budget can absorb from a normal traffic fluctuation. For a latency-sensitive service with spiky traffic, that may be 60%. For a batch system that only cares about throughput, 95% may be fine.

The knee also moves with the number of servers, which is the subject of the M/M/c section below: a pool of 64 workers can run at 90% with almost no queueing, where a single server at 90% is deep in the cliff.

Practical Example: Thread Pool Sizing

Your API server has a thread pool of 100 threads (, but treating as M/M/1 for each thread). Each request takes an average of 50ms to process ( req/s per thread). Total capacity is req/s.

At 1400 req/s ():

At 1800 req/s ():

At 1960 req/s ():

At 1990 req/s ():

The system went from 52ms to 250ms by adding 42% more traffic.

Correction: model 100 threads as M/M/100, not M/M/1

The calculation above treats the pool as one server that is 100 times faster (). In that model, is already the total time in system, including a 0.5 ms service time, so adding a separate 50 ms of service mixes two models. A pool of 100 threads, each taking 50 ms per request, is an M/M/100 queue, and the Erlang C formula below gives:

LoadP(wait)Mean queue waitMean total
1,400 req/s0.700.05%about 0 ms50 ms
1,800 req/s0.9022%1.1 ms51 ms
1,960 req/s0.9878%19 ms69 ms
1,990 req/s0.99594%94 ms144 ms

The qualitative lesson survives: latency is flat for a long time and then shoots up close to saturation. But a large pool stays flat much longer than a single server would, and the cliff is steeper when it arrives. The original numbers have the right shape but overstate the delay, most of all close to saturation.

The M/M/c Queue (Multi-Server)

Real systems have multiple servers (threads, instances, workers). The M/M/c queue models identical parallel servers with a single shared queue.

Parameters

  • = arrival rate
  • = per-server service rate
  • = number of servers
  • = per-server utilization (must be < 1 for stability)

Erlang-C Formula

The probability that an arriving customer must wait (all servers busy):

Average wait time in queue:

Average time in system:

Why Multi-Server Is Better Than Multiple Single-Server

A single queue feeding multiple servers (M/M/c) always outperforms multiple separate queues (c independent M/M/1 systems). This is because a shared queue eliminates the problem of one server sitting idle while another has a backlog.

ConfigurationArrival RateServersUtilizationAvg Wait
1 queue, 4 servers (M/M/4)300 req/s4 at 100 req/s each75%Low
4 queues, 1 server each (4x M/M/1)75 req/s each4 at 100 req/s each75%Higher

This is why supermarkets with a single serpentine line are more efficient than per-register lines, and why a shared thread pool outperforms per-client worker threads.

Putting numbers on that table, with 10 ms mean service time: each of the four separate M/M/1 queues has a mean wait of ms. The shared M/M/4 queue has , so the mean wait is ms. Same hardware, same load, about six times less waiting.

Practical Implication

Always prefer a single shared queue feeding multiple workers over separate per-worker queues. This applies to:

  • Thread pools (shared work queue, not per-thread queues)
  • Load balancers (least-connections, not round-robin which approximates separate queues)
  • Kafka consumers (more partitions per consumer group, not separate consumer groups)

Correction on the Kafka bullet: in a classic Kafka consumer group, each partition is consumed by exactly one consumer, so partitions behave like separate queues: a slow partition cannot be helped by an idle consumer. Kafka is closer to the "4 queues, 1 server each" row than to M/M/c. Separate consumer groups are not an alternative at all, since each group receives every message. The practical advice is to use more partitions than consumers (so rebalancing can spread hot partitions), keep per-message processing time even, or hand messages from a partition to a shared worker pool inside the consumer. Newer Kafka releases also add "share groups" (KIP-932), which let several consumers take records from the same partition, queue-style.

Erlang C in Code

Computing Erlang C directly from the formula overflows quickly, because of the factorials. The standard trick is to compute Erlang B with a stable recurrence and convert:

def erlang_c(servers: int, offered_load: float) -> float:
    """Probability an arrival must wait in M/M/c.
    offered_load = lambda / mu (in Erlangs). Requires offered_load < servers."""
    b = 1.0
    for k in range(1, servers + 1):           # Erlang B recurrence
        b = offered_load * b / (k + offered_load * b)
    rho = offered_load / servers
    return b / (1 - rho * (1 - b))

def mmc(arrival_rate: float, service_rate: float, servers: int):
    a = arrival_rate / service_rate
    if a >= servers:
        return None                          # unstable: queue grows forever
    pw = erlang_c(servers, a)
    wq = pw / (servers * service_rate - arrival_rate)
    return {"p_wait": pw, "wait": wq, "total": wq + 1 / service_rate}

# 100 threads, 50 ms per request, 1,960 req/s (the corrected table above)
r = mmc(1960, 20, 100)
assert abs(r["p_wait"] - 0.775) < 0.01 and abs(r["wait"] - 0.0194) < 0.001
print(r)

Economies of Scale and the Moving Knee

The same per-server utilization means very different waiting depending on how many servers share the queue. Mean queue wait in units of the service time:

Utilization1 server8 servers64 servers
50%1.000.01~0
70%2.330.11~0
80%4.000.29~0
90%9.000.880.05
95%19.02.110.18

This is why large pools can safely run hot and small ones cannot. A rule like "keep utilization under 70%" is about right for a handful of servers and wasteful for a pool of hundreds.

The telephone-network version of this insight is the square-root staffing rule. If the offered load is (the number of servers that would be busy on average), then to keep the probability of waiting roughly constant you need

servers, where is a quality-of-service constant (around 1 to 2 for typical targets). The spare capacity grows like , not like . Doubling traffic from to with takes you from 115 to 221 servers, so the headroom fraction falls from 15% to 10.5%. Bigger systems are more efficient, purely because of pooling.

Why p99 >> p50: Heavy-Tailed Distributions

In production systems, the p99 latency is often 10-100x the p50. This is not a bug — it is a fundamental property of queueing systems with variable service times.

The Exponential vs. Heavy-Tailed Service Times

The M/M/1 model assumes exponential service times, which are well-behaved. Real systems have heavy-tailed service times due to:

  • Garbage collection pauses
  • Cache misses (L1 cache hit: 1ns, disk read: 10ms — a 10,000,000x difference)
  • Lock contention
  • Network retries
  • Database query plan regressions
  • Background compaction in LSM-tree databases

Percentile Amplification in Queues

When requests with variable service times queue behind each other, slow requests delay fast ones. A single 100ms garbage collection pause at the head of the queue delays every request behind it.

If service time has a coefficient of variation (standard deviation divided by mean), then wait times scale with . For exponential distributions, . For heavy-tailed distributions, , and wait times explode.

Real-World Percentile Example

Consider an API with these service time percentiles:

PercentileService TimeExplanation
p505msTypical request — cache hit, fast query
p9020msModerate — larger payload, index scan
p99150msSlow — cache miss, GC pause, cold start
p99.9800msVery slow — timeout + retry, compaction

After queueing (at 70% utilization), the latency distribution widens further:

PercentileService TimeAfter QueueingAmplification
p505ms12ms2.4x
p9020ms65ms3.3x
p99150ms890ms5.9x
p99.9800ms4200ms5.3x

These "after queueing" figures are illustrative, chosen to show the shape of the effect rather than computed from a specific model. Real amplification depends on the server count, the scheduling order and how correlated the slow requests are.

Averages Lie

Never use average latency to assess system health. A system with 5ms average latency might have a p99 of 2 seconds. The average is dominated by the fast majority, completely hiding the slow tail that real users experience. Always monitor p50, p90, p99, and p99.9.

Fan-Out Amplifies Tail Latency

When a single user request fans out to N backend services (common in microservices), the overall latency is the maximum of all N calls. The probability that at least one call hits the tail increases rapidly:

For a p99 of 100ms across each of parallel calls:

39.5% of user requests will experience a slow backend call. Your user-facing p99 is driven by the backend's p99, amplified by fan-out. This is why Jeff Dean's "tail at scale" paper is essential reading.

Kingman's Formula

Kingman's formula (also called the VUT formula) estimates average wait time for a G/G/1 queue (general arrival and service distributions, single server):

Where:

  • = utilization
  • = coefficient of variation of inter-arrival times ()
  • = coefficient of variation of service times ()
  • = mean service time

The VUT Decomposition

The formula has three intuitive factors:

FactorSymbolMeaning
V (Variability)How variable are arrivals and service times?
U (Utilization)How busy is the server?
T (Time)How long does service take?

This decomposition is powerful because it tells you the three levers you have to reduce wait times:

  1. Reduce variability — More consistent request handling (eliminate GC pauses, use connection pools, avoid cold starts)
  2. Reduce utilization — Add more servers (horizontal scaling)
  3. Reduce service time — Make each request faster (optimize code, add caching)

Example: Impact of Service Time Variability

Two systems with the same average service time (10ms) and utilization (80%):

System A: Consistent service times ()

System B: Highly variable service times ()

System B has 10x the wait time despite identical average throughput and utilization. This is why reducing variance (eliminating outlier requests) is often more impactful than reducing average latency.

An Exact Special Case: Pollaczek–Khinchine

For Poisson arrivals () and any service distribution (the M/G/1 queue), the mean wait is known exactly:

This is the Pollaczek–Khinchine formula, and Kingman's approximation reduces to it when . Two special cases are worth remembering:

  • Exponential service (): the factor is 1, giving the M/M/1 result.
  • Constant service (, the M/D/1 queue): the factor is . Perfectly consistent service halves the queueing delay compared with exponential service at the same utilization.

Halving is the most that reducing service variability can do when arrivals are random. The remaining half comes from the randomness of arrivals, which only smoothing the arrival process (batching, admission control, pacing) can remove.

Why Variance Hurts: the Inspection Paradox

Why does service variance matter so much? A request that arrives at a random moment is more likely to land during a long service than a short one, simply because long services cover more of the timeline. The expected remaining work of the request in service, as seen by a random arrival, is , not . With , , so a random arrival waits on average 5 service times just for the current job to finish. A rare 2-second request in a stream of 10 ms requests is not a rare problem: it delays everyone who arrives while it runs.

Applying Queueing Theory to Capacity Planning

Step 1: Measure Your Parameters

# Measure arrival rate (requests per second)
# From your load balancer metrics or application metrics

# Measure service time distribution
# p50, p90, p99, mean, standard deviation
# From your APM tool (Datadog, Grafana, etc.)

# Calculate utilization
# CPU utilization, thread pool utilization, connection pool utilization
MetricHow to Get ItWhat It Tells You
(arrival rate)Load balancer RPSDemand on the system
(mean service time)APM p50 or mean latencyHow fast the system processes
(service time CoV) from latency histogramHow variable processing is
(utilization)CPU usage, thread pool active/totalHow close to saturation

Step 2: Model Your System

For a web service with instances, each handling requests/second:

Step 3: Predict Latency at Target Load

Use Kingman's formula to estimate wait times at your target utilization:

import math

def kingman_wait(arrival_rate, service_rate, ca, cs):
    """Estimate average wait time using Kingman's formula."""
    rho = arrival_rate / service_rate
    if rho >= 1.0:
        return float('inf')  # System is unstable

    mean_service = 1.0 / service_rate
    variability = (ca**2 + cs**2) / 2.0
    utilization = rho / (1.0 - rho)

    return utilization * variability * mean_service

def capacity_plan(peak_rps, service_time_ms, service_time_std_ms,
                  target_util=0.7, target_wait_ms=50):
    """Calculate required instances for a capacity target."""
    mu = 1000.0 / service_time_ms  # per-instance throughput (req/s)
    cs = service_time_std_ms / service_time_ms

    # Instances needed for utilization target
    instances_util = math.ceil(peak_rps / (target_util * mu))

    # Check if wait time meets target
    total_mu = instances_util * mu
    rho = peak_rps / total_mu
    ca = 1.0  # Assume Poisson arrivals
    wait = kingman_wait(peak_rps, total_mu, ca, cs) * 1000  # ms

    print(f"Peak RPS: {peak_rps}")
    print(f"Per-instance throughput: {mu:.0f} req/s")
    print(f"Instances needed (utilization): {instances_util}")
    print(f"Actual utilization: {rho:.2%}")
    print(f"Estimated avg wait: {wait:.1f} ms")
    print(f"Estimated avg total: {wait + service_time_ms:.1f} ms")

    if wait > target_wait_ms:
        # Need more instances
        # Iterate to find the right number
        for c in range(instances_util, instances_util * 3):
            total_mu = c * mu
            rho = peak_rps / total_mu
            if rho >= 1.0:
                continue
            wait = kingman_wait(peak_rps, total_mu, ca, cs) * 1000
            if wait <= target_wait_ms:
                print(f"\nTo meet {target_wait_ms}ms wait target: {c} instances "
                      f"(util={rho:.2%}, wait={wait:.1f}ms)")
                break

# Example: API doing 5000 RPS, 20ms avg service, 15ms std dev
capacity_plan(
    peak_rps=5000,
    service_time_ms=20,
    service_time_std_ms=15,
    target_util=0.7,
    target_wait_ms=10
)

Correction: the planner above models the fleet as one fast server

capacity_plan passes instances * mu to Kingman's single-server formula, so it treats a fleet of instances as one server times faster. That also shrinks the mean service time to , so the estimated wait is too small by a large factor and does not reflect pooling correctly. For servers, a standard approximation (Allen–Cunneen) scales the M/M/c wait by the same variability factor that Kingman uses:

The function below uses it, with the erlang_c helper from the M/M/c section.

def multi_server_wait(arrival_rate, per_server_rate, servers, ca=1.0, cs=1.0):
    """Allen-Cunneen approximation for G/G/c mean queue wait (seconds)."""
    a = arrival_rate / per_server_rate
    if a >= servers:
        return float("inf")
    rho = a / servers
    pw = erlang_c(servers, a)
    return pw / (servers * per_server_rate * (1 - rho)) * (ca**2 + cs**2) / 2

def instances_for(peak_rps, service_ms, service_std_ms, workers_per_instance,
                  max_wait_ms, max_util=0.85):
    mu = 1000.0 / service_ms                     # per worker
    cs = service_std_ms / service_ms
    c = workers_per_instance
    while True:
        servers = c
        rho = peak_rps / (servers * mu)
        wait_ms = multi_server_wait(peak_rps, mu, servers, 1.0, cs) * 1000
        if rho <= max_util and wait_ms <= max_wait_ms:
            return servers // workers_per_instance, rho, wait_ms
        c += workers_per_instance

# 5,000 rps, 20 ms +/- 15 ms, 8 workers per instance, wait budget 2 ms
print(instances_for(5000, 20, 15, 8, max_wait_ms=2))

Step 4: Plan for Spikes

Traffic is not constant. Use a multiplier based on your traffic pattern:

Traffic PatternSpike MultiplierExample
Steady SaaS B2B1.5-2x averageBusiness hours traffic
Consumer web2-3x averageEvening peak
E-commerce5-10x averageFlash sales, Black Friday
Gaming3-5x averageNew content release
Event-driven10-100x averageSuper Bowl, election night

Autoscaling Is Not Instant

Cloud autoscaling takes 2-10 minutes to add new instances (boot, health check, warm up). During that window, your existing fleet must absorb the spike. Size your base fleet for the traffic level you must sustain during the scaling lag.

instances_for (above) prints (15, 0.83, 0.03): 15 instances, 83% utilization, a mean queue wait well under a millisecond. It treats the fleet's 120 workers as one shared queue, which is only true if the load balancer sends each request to a free worker (least-outstanding-requests or similar). With random or round-robin balancing the fleet behaves more like separate queues, and you need noticeably more headroom.

Worked Capacity Examples

Example 1: database connection pool

A service makes 1,000 queries per second, and each holds a connection for 10 ms on average. Little's Law says 10 connections are busy on average. How many should the pool have? Model it as M/M/c with , :

Pool sizeUtilizationP(wait for a connection)Mean wait
1191%68%6.8 ms
1283%45%2.2 ms
1471%17%0.4 ms
1663%5.7%0.1 ms
2050%0.4%under 0.01 ms

A pool of 16 makes waiting rare. The "2–3× headroom" rule from the Little's Law section (20–30 connections) is safe but generous. The interesting part is the top of the table: with 11 connections the pool is stable, but two-thirds of queries wait.

The other side of this sum is the database. If 40 application instances each have a pool of 16, the database may see 640 connections, and most databases degrade well before that (PostgreSQL in particular, with its process per connection). That is a queueing argument for a central pooler such as PgBouncer: it turns 640 client-side queues into one shared queue in front of a small number of real connections.

Example 2: how many Kafka consumers?

A topic receives 12,000 messages per second at peak. Each message takes 4 ms of processing, with high variability () because some trigger extra lookups. Messages should be processed within 1 second of arrival on average.

  • Offered load: busy consumers on average.
  • Each partition is a separate queue (see the correction above), so model one partition as M/G/1. With 64 partitions and one consumer thread each, per partition, , .
  • Pollaczek–Khinchine: ms. Fine.
  • But if one partition is hot and gets twice its share, there: that partition's lag grows without bound while the others are idle. Partition skew, not average load, is what usually sinks a consumer group. Plan the partition count for the hottest key, not the mean.

Example 3: instances for a p99 target

An API must keep p99 under 200 ms. Service time is 40 ms on average, and each instance runs requests on 4 CPU-bound workers. Peak traffic is 2,000 rps.

  • Offered load: workers, so 20 instances at 100% utilization, which is impossible.
  • At 25 instances (100 workers, ), M/M/c gives a 2% chance of waiting and a p99 queue wait of about 1.4 ms. The p99 is dominated by the service-time tail. If the service p99 is 150 ms, the queue costs almost nothing.
  • At 22 instances (88 workers, ), 28% of requests wait, and the p99 queue wait is about 17 ms. Tolerable.
  • At 21 instances (84 workers, ), 56% wait and the p99 queue wait is about 40 ms, which, added to a 150 ms service tail, breaks the 200 ms budget.

With 80-odd pooled workers, queueing barely matters until about 90% utilization, and then it matters very quickly. A sensible answer is about 25 instances before adding headroom for the autoscaling lag and for losing an availability zone. If a zone loss must be absorbed, size so that the surviving two-thirds of the fleet still meets the target: about 33 instances.

How Queueing Theory Guides Design

Thread pools

For CPU-bound work, more threads than cores only adds context switching: the "servers" are the cores, and extra threads just form a queue inside the scheduler. For work that blocks on I/O, a thread is a server only while it computes, so you need more of them. Brian Goetz's rule from Java Concurrency in Practice captures it:

where is the ratio of time spent waiting to time spent computing. With 8 cores, a 90% CPU target, and requests that wait 9 ms for every 1 ms of compute, that is threads.

Little's Law gives the same answer from the other side. If you want to sustain requests per second and each holds a thread for seconds, you need threads busy on average, plus headroom from an M/M/c table. And a thread pool must have a bounded queue. An unbounded queue in front of a saturated pool does not prevent overload. It only converts it into unbounded latency and memory use.

Autoscaling

Queueing theory tells you three things about autoscaling:

  1. Scale on a signal that leads latency. CPU utilization is fine for CPU-bound services. For I/O-bound ones, in-flight requests per instance (concurrency, which is in Little's Law) or queue length rises before latency does and is a better trigger. Knative, for example, scales on concurrency per pod.
  2. Choose the target from the knee and the lag. If scale-out takes 4 minutes and traffic can rise 30% in 4 minutes, the target must leave room for 30% growth before reaching the knee. If the knee is at 85% for your pool size, the target is about .
  3. Larger instances are a form of pooling. One instance with 32 workers behind a least-loaded balancer queues less than four instances with 8 workers each behind a random one, at the same total capacity.

Backpressure and bounded queues

A queue is useful when it absorbs short bursts. It is harmful when it absorbs sustained overload, because every queued request ages, and by the time it is served, its client may have given up. The useful bound on a queue comes from the latency budget:

A service that handles 500 rps with a 200 ms budget for queueing should hold at most about 100 waiting requests. Anything beyond that will finish too late to matter, so rejecting it at once (an HTTP 503 or 429, or a gRPC RESOURCE_EXHAUSTED) is kinder to everyone. That is backpressure, and it pairs with rate limiting at the edge and circuit breakers at the client.

For a bounded M/M/1 queue that holds at most requests (the M/M/1/K model), the fraction of arrivals rejected is

With , about 5% of arrivals are rejected at . At (20% overload) about 19% are rejected, and, crucially, the 81% that are accepted still see bounded latency. An unbounded queue at serves everyone late.

Two scheduling tricks for overload come from Facebook's experience, described in "Fail at Scale" (Ben Maurer, ACM Queue, 2015):

  • Adaptive LIFO. Under normal load, serve the queue first-in-first-out. When it builds up, switch to last-in-first-out: the newest requests are the ones whose users are still waiting, and the oldest have probably timed out already.
  • Controlled delay (CoDel). Borrowed from network queue management: if the queue has not been empty at any point in a recent interval, apply a short timeout to queued requests, so that a standing queue is drained by shedding instead of growing.

Cutting tail latency

Since tail latency comes from queueing and service variance, the remedies attack one or the other:

TechniqueMechanismCost
Hedged requests (from "The Tail at Scale")Send a second copy to another replica if the first has not answered by, say, the p95A few percent more load
Tied requestsSend to two replicas, and the first to start cancels the otherMore complex, little extra load
Least-outstanding-requests balancingTurns separate queues into something closer to M/M/cNeeds per-backend state
Isolating slow request classesSeparate pools for heavy and light requests, so heavy ones do not block light onesLower pooling efficiency
Removing variance sourcesGC tuning, pre-warming, avoiding cold caches, splitting huge requestsEngineering time

Dean and Barroso report in "The Tail at Scale" that in one Google benchmark, hedging after 10 ms reduced the 99.9th percentile latency of a read from 1,800 ms to 74 ms while sending only about 2% more requests.

Open vs Closed Systems, and Load Testing

The formulas on this page assume an open system: requests arrive from an outside population at rate , regardless of how the system is doing. Public web traffic is roughly open. A closed system has a fixed number of clients, each of which sends a request, waits for the reply, thinks, and sends the next. Many load-testing tools are closed by default: "100 virtual users in a loop".

The difference matters. In a closed system, if the server slows down, clients send less, so the queue cannot grow beyond the number of clients. A closed load test of a service that is about to fall over shows latency rising gently and throughput flattening, which looks healthy. The same service under real open traffic hits the cliff. Schroeder, Wierman and Harchol-Balter's paper "Open Versus Closed: A Cautionary Tale" (NSDI 2006) shows how different the two can be for the same server.

A related trap is coordinated omission, a term popularised by Gil Tene. If a load generator waits for each response before sending the next request, then during a 2-second stall it simply does not send the requests that would have queued, and those missing samples are exactly the slow ones. The recorded p99 looks fine. Tools that schedule requests at a fixed rate and measure latency from the intended send time (wrk2, and HdrHistogram's correction mode) avoid this.

War Story (illustrative)

A team load-tested a new checkout service with 200 virtual users in a closed loop and recorded p99 of 180 ms at 1,800 rps, with CPU at 85%. They launched with a fleet sized for exactly that. On the first sale day traffic reached 2,000 rps, which is only 11% above the test. In an open system at that utilization the service was close to saturation, and the queue grew faster than it drained. p99 went to 9 seconds and clients started timing out and retrying, which raised the arrival rate further. The closed test had hidden the cliff, because its 200 users could never put more than 200 requests in the queue. The fix was to rerun the test with an open-loop, constant-rate generator, which showed the knee at about 1,500 rps for that fleet size. They added 40% more instances, a bounded request queue sized from the latency budget, and a retry budget on clients.

Interview Questions

1. State Little's Law and use it to size a connection pool.

. At 1,000 queries per second holding a connection for 10 ms each, 10 connections are busy on average. Add headroom from an M/M/c calculation: about 16 makes waiting rare.

2. Why does latency explode as utilization approaches 100%?

In M/M/1, mean time in system is . As the denominator goes to zero. Intuitively, the server has no spare capacity to drain the backlog left by random bursts, so bursts accumulate.

3. Why can a pool of 64 workers safely run at 90% when a single server cannot?

Pooling. With many servers, the chance that all are busy at once is small even at high utilization. Mean waiting is about 0.05 service times for 64 servers at 90% against 9 for one server.

4. What does Kingman's formula tell you to do about long queues?

Wait scales with utilization (), variability () and service time. Reduce any of them: add capacity, make service times consistent, smooth arrivals, or make each request cheaper.

5. A backend's p99 is 100 ms and a page fans out to 50 backends in parallel. What fraction of pages see at least one slow call?

. Fixes: hedged or tied requests, fewer fan-out calls, and reducing the backend's tail.

6. How do you choose the bound for a request queue?

From the latency budget: max queue length is roughly the time you can afford to wait times the throughput. Requests beyond that will finish too late, so reject them immediately.

7. Why might a load test show healthy latency for a service that falls over in production?

A closed-loop test caps the number of outstanding requests at the number of virtual users, which hides the cliff, and coordinated omission drops the slow samples. Use constant-rate open-loop generators and measure from intended send time.

8. Why does a Kafka consumer group not behave like an M/M/c queue?

Each partition is consumed by one consumer, so partitions are separate queues. A hot partition backs up while other consumers are idle. Plan for the hottest partition, keep processing times consistent, or use a worker pool inside the consumer.

9. How many threads for an I/O-heavy service on 8 cores?

. At 90% target and 9 ms waiting per 1 ms computing, about 72. Check with Little's Law against the request rate.

10. Your autoscaler targets 80% CPU and still lets latency spike during traffic ramps. Why?

Scale-out lag. Traffic keeps rising while new instances boot, so the fleet passes the knee before help arrives. Lower the target to leave room for the growth that can happen during the lag, scale on a leading signal such as concurrency, and keep a bounded queue so overload turns into fast rejections rather than long waits.

Key Takeaways

PrincipleFormulaPractical Implication
Little's LawRelate concurrency, throughput, and latency
Utilization cliffNever run above 70-80% utilization
Shared queues winM/M/c > c x M/M/1Use shared work queues, not per-worker queues
Variance killsReducing variance > reducing mean
Tail amplificationFan-out amplifies tail latency
Kingman's formulaThree levers: variability, utilization, service time

Further Reading

  • Consistent Hashing — Load distribution across nodes
  • Rate Limiting — Controlling arrival rate
  • Load Balancing Algorithms — Queue assignment strategies
  • Caching Strategies — Reducing service time
  • Backpressure Patterns — What to do when queues fill up
  • Performance Modeling and Design of Computer Systems by Mor Harchol-Balter — The definitive textbook
  • Jeff Dean, "The Tail at Scale" (2013) — Fan-out and tail latency in large-scale systems
  • Giovanni Giambene, Queuing Theory and Telecommunications: Networks and Applications (Springer) — Applied queueing for network engineers. (Correction: this entry was previously attributed to an author name that does not match the book.)
  • Ben Maurer, "Fail at Scale" (ACM Queue, 2015) — Adaptive LIFO, CoDel and overload handling at Facebook
  • Bianca Schroeder, Adam Wierman, Mor Harchol-Balter, "Open Versus Closed: A Cautionary Tale" (NSDI 2006)
  • Timeouts, Retries and Backoff — How retries change the arrival rate