Unit 6.4 · about 4 h
277 / 324Little's Law, capacity and queueing approximations
Admission bounds and queue sizes from the Programming backpressure-graceful-shutdown unit, taken as assumed background, need numbers. This unit derives them: arrival rate times time in system is the queue you must bound.
- derive
You can now
- State Little's Law with units and its stability assumption, and solve for any one of arrival rate, concurrency and time in system.
- Derive capacity, utilization and headroom for requests, bytes, storage, memory and bandwidth from a stated workload.
- Apply an M/M/1 or M/D/1 approximation with its assumptions written down, and report the uncertainty range.
Covers
- Arrival rate, service time, concurrency and Little's Law
- Capacity for requests, bytes, storage, memory and bandwidth
- Basic queueing-model approximations and uncertainty ranges
Study, in this order
3 steps
- M/M/1 stability and closed formsM/M/1 queue - model definition and stationary analysis
Model definition (Poisson arrivals, exponential service, single server, infinite buffer, FIFO); Stationary analysis (stability \(\lambda < \mu\), \(\rho = \lambda/\mu\)); Average number of customers in the system (\(L = \rho/(1 - \rho)\)); Response time (\(W = 1/(\mu - \lambda)\) via Little's Law)
Depth · Use the closed forms as approximations only. Your service is not proven Poisson or exponential; the simulation in Reproduce is the check.
- Capacity in resources, not queriesGoogle Site Reliability Engineering - selected core chapters
The Pitfalls of 'Queries per Second' (cost per request varies; model capacity directly in CPU time and memory)
- Conservative capacity and scaling boundsGoogle SRE Workbook - SLO, load, incident and canary exercises
Autoscaling (Configuring Conservatively: stay far from bottlenecks, spare capacity for overload and redundancy; Setting Constraints: minimum and maximum bounds); Avoiding Overloading Backends
Focus on
- \(L = \lambda W\) needs matching units: \((\text{requests}/\text{s}) \times \text{s} = \text{requests}\). It holds for long-run averages in a stable system; it predicts nothing about tails.
- Utilization \(\rho = \lambda/\mu\) governs the wait. At \(\rho\) 0.5, 0.8 and 0.95 the M/D/1 mean wait is 0.5x, 2x and 9.5x the service time; a seeded 60 s simulation at 10 ms service measured 4.86, 19.97 and 80.87 ms against theory 5, 20 and 95 ms.
- Capacity is per resource. The bottleneck is the smallest capacity-over-work ratio: \(12000/1\), \(5000/2\) and \(20000/0.5\) give 2500 rps at the database.
- Approximations carry ranges. M/M/1 assumes Poisson arrivals and exponential service; burstier arrivals or heavier-tailed service widen the real wait. Report the assumption beside the number.
Reproduce closed-book
random.seed(11), Poisson arrivals at 80/s from random.expovariate for 60 s, deterministic 10 ms service. The mean queue wait should be 20.475 ms against M/D/1 theory \(\rho \times S / (2 \times (1 - \rho)) = 20.000\) ms, so the mean time in system is 30.475 ms and Little's Law gives \(L = 80 \times 0.030475 = 2.44\). Check the law directly: the time-average number in system over 5 to 55 s is 2.52, against \(\lambda W\) 2.49 for the arrivals in that window. Then size servers: 0.8 average busy, so one server runs at \(\rho\) 0.8 and two at 0.4.Traps
- Applying \(L = \lambda W\) to percentiles or to a draining queue. It relates long-run averages in a stable system only.
- Quoting \(\lambda\) without a window. Poisson bursts exceed the average; size the bound for the peak window, not the daily mean.
- Treating the M/M/1 number as measured. It is a prediction under strong assumptions; the simulation or load run is the check.
Practice
AlgoMaster: Solve Little's Law
LittlesLawCalculator.solve: detect the -1 argument and rearrange \(L = \lambda W\), rounded to 5 places (examples: \(100 \text{ rps} \times 0.05 \text{ s} = 5\); \(5/0.05 = 100\) rps)
Attempt only after your own three-way derivations. Keep units attached: throughput in requests/s, latency in seconds.
AlgoMaster: Analyze Capacity Bottlenecks
maxThroughput (minimum of capacity/work ratios) and bottleneck (name of the smallest ratio; alphabetical on ties)
Attempt only after your own per-resource ratios. Select the bottleneck from unrounded ratios.
Self-test
-
100 rps with 50 ms in system: average concurrency?
5 requests (\(100 \times 0.05\)). Units: \((\text{requests}/\text{s}) \times \text{s} = \text{requests}\). -
Single server at \(\rho\) 0.95: mean wait as a multiple of service time?
M/D/1 gives \(\rho/(2 \times (1 - \rho)) = 9.5\)x; M/M/1 gives \(\rho/(1 - \rho) = 19\)x. State which model you used. -
Capacities \(12000/1\), \(5000/2\) and \(20000/0.5\) per request: max throughput and bottleneck?
2500 rps at the database (\(5000/2\)), the smallest ratio. -
The simulation gives 80.87 ms at \(\rho\) 0.95 against theory 95 ms. Contradiction?
No. Near \(\rho\) 1 the queue relaxes slowly and the run starts empty, so a 60 s run reads low. Lengthen it, drop a warm-up, repeat with several seeds and report the spread beside the theory.
Completion criterion
Stop when
You solve all three Little's Law directions without notes and can size one server count from a stated workload with the model assumptions listed.
Mark passed, then open 6.5 Only mark this when you can do it without notes.Leads to
- 6.5 Queue bounds, first saturation and open-loop load Check the prediction by driving load through the knee.
- 6.9 Unit cost, headroom and simpler designs Price the derived capacity and headroom.
Comes after
- 6.2 Latency distributions, throughput and saturationTurn the measured wait into concurrency and capacity math.
- 6.5 Queue bounds, first saturation and open-loop loadReconcile the measured knee with utilization math.
Resources for this unit
- Google Site Reliability Engineering - selected core chapters Read Chapters 3, 4, 6, 10, 12, 17, 19-22: risk, SLOs, monitoring, alerting, troubleshooting, reliability tests, load balancing, overload and cascading failure. Apply every concept to the same bounded RPC and store rather than inventing separate examples.
- Google SRE Workbook - SLO, load, incident and canary exercises Use Chapters 2, 4, 9-11, 12, 14, 16 and 17. Define one SLO, estimate capacity, load through saturation, canary a changed version, roll it back, and write one evidence-based incident timeline.
- M/M/1 queue - model definition and stationary analysis Read Model definition (Poisson arrivals, exponential service, single server, infinite buffer, FIFO) and Stationary analysis (stability \(\lambda < \mu\), \(\rho = \lambda/\mu\), \(L = \rho/(1 - \rho)\), response time \(1/(\mu - \lambda)\) via Little's Law). Use the closed forms as approximations with assumptions stated, checked by your own simulation.
Also in this section
- OpenTelemetry Python - metrics, logs and traces Instrument request ID, queue wait, handler time, storage time, status and bounded labels. Export locally, retain raw load records and verify that instrumentation does not hide the bottleneck or create unbounded cardinality.
- AlgoMaster System Design - quantitative and failure drills Use Solve Little's Law, Calculate System Availability, Plan Reliability Recovery Targets, Calculate Amdahl's Law Speedup, Analyze Capacity Bottlenecks, Simulate Partition Quorums and Audit Failure Domains only after producing your own estimates. Compare the platform answer with measured service behavior.
- Python Experimental Systems Kit - measurement slice Use its artifact, bounded-pipeline, failure-injection, profiling and reproducibility requirements as the evidence checklist. Reuse the current service instead of building the full project again.
- Gil Tene - How NOT to Measure Latency (talk) Use for coordinated-omission vocabulary only: closed-loop testers that wait for each reply, the missing samples under queueing, and the correction concept of recording intended send time. Do not adopt
wrk,heyorab; write the small Python generator in the saturation unit instead.