Elijah's Notes

Little's Law and Bottleneck Analysis

4 min read

Purpose

This note is the first scheduling note to memorize. Most system arguments about “too much load”, “not enough headroom”, or “wrong place to optimize” reduce to a handful of algebraic identities:

  • utilization law
  • Little’s Law
  • bottleneck law

They are not queueing-model assumptions. They are bookkeeping identities for stable systems.

Model

Take one service stage with:

  • arrival rate requests/second
  • throughput completions/second
  • service time seconds/request
  • response time seconds/request
  • average number in service
  • average number in the whole system

For a stable stage, long-run throughput equals long-run arrival rate:

If the stage is unstable, the queue is growing and the averages are not stationary enough to be useful.

Utilization Law

Apply Little’s Law only to the server itself, not the queue. The average number of jobs “inside the server” is the utilization:

For a single server, is the busy fraction, so .

With service rate :

This is the cleanest way to check whether a plan is impossible. If a stage needs 3 ms of CPU per request and you want 500 requests/second from one core:

That is impossible on one core before queueing is even discussed.

Little’s Law

For any stable subsystem:

Average concurrency equals throughput times average time spent inside.

This identity is more useful than it first looks because the subsystem can be chosen freely:

  • the whole service
  • one queue
  • one RPC stage
  • one disk
  • the decode queue of a model server

If a service does 20,000 requests/second and p50 end-to-end time is 50 ms, the average concurrent requests implied by the mean relation is on the order of

That does not say the distribution is narrow. It says any steady-state design claiming 20k QPS with only a handful of in-flight requests is wrong.

Bottleneck Law

Suppose request visits stage an average of times and each visit costs service time . The total demand per request at stage is

Then stage cannot sustain throughput above

for one server, or

for identical servers.

The system throughput limit is the minimum across stages:

This is the operational form of “the bottleneck wins.”

Worked Example

Suppose one request does:

  • 2 ms of CPU
  • 6 ms of network-bound downstream wait on a pool of 4 workers, each spending 6 ms of service
  • 1 ms of local serialization

The demands are:

and

with , so

and

The CPU side is the bottleneck. Speeding up the RPC pool changes little until CPU demand drops.

flowchart LR
    IN[Arriving requests] --> CPU[CPU stage: demand 3 ms, max 333 req/s]
    CPU --> RPC[RPC pool: 4 workers at 6 ms each, max 667 req/s]
    RPC --> OUT[Complete]
    style IN fill:#e3f2fd
    style CPU fill:#f9d0d0,stroke:#c00
    style RPC fill:#e8f5e9

Why Queueing Starts Late and Then Gets Ugly Fast

Operational laws tell you where the cliff is. Queueing models tell you how the cliff looks. In many systems the shape is:

  • low utilization:
  • moderate utilization: queueing appears but is tolerable
  • high utilization: tail latency explodes

That last step is why a bottleneck running at 95% can dominate the whole service even if all other stages are comfortable.

Tiny Python Helper

from dataclasses import dataclass
 
@dataclass
class Stage:
    name: str
    visits: float
    service_s: float
    servers: int = 1
 
    @property
    def demand_s(self) -> float:
        return self.visits * self.service_s
 
    @property
    def max_throughput(self) -> float:
        return self.servers / self.demand_s
 
 
stages = [
    Stage("cpu", visits=1, service_s=0.003, servers=1),
    Stage("rpc_pool", visits=1, service_s=0.006, servers=4),
]
 
for stage in stages:
    print(stage.name, stage.max_throughput)
 
print("system_limit", min(stage.max_throughput for stage in stages))

What This Note Does Not Do

This note does not predict the full latency distribution. It only tells you:

  • whether capacity math is even plausible
  • how much concurrency a measured throughput implies
  • which stage is limiting throughput

That is enough to rule out many bad explanations quickly.

Graph View