Explain Little's law and how you would use it, together with observed utilization and queue depth, both to choose the number of workers for a queue-driven service and to explain why response time degrades sharply as the pool approaches saturation.

## Little's law For any system in steady state, over a long enough window, ``` L = lambda x W ``` where L is the average number of items in the system, lambda the average arrival rate (equal to the completion rate in steady state), and W the average time an item spends in the system. It requires only stability - nothing about the distribution of arrivals or service times, nothing about scheduling order. That generality is why it holds simultaneously at several boundaries of the same system. Draw the boundary around the **service** (workers only) and it reads L_busy = lambda x S: the average number of busy workers equals arrival rate times service time. Draw it around the **queue** and it reads L_queue = lambda x W_queue. Draw it around **queue plus service** and you get end-to-end latency and total items in flight. ## Sizing with it Suppose measured demand is 500 requests per second and the average task occupies a worker for 40 ms (compute plus any blocking): L_busy = 500 x 0.04 = 20. Twenty workers is the absolute floor - a pool of exactly 20 runs at 100% utilization, which is not a viable operating point. Choosing a target utilization of 0.7 gives about 29 workers. Sizing therefore has two inputs: the demand product lambda x S, and the headroom factor 1/U. ## Why the last few percent are ruinous Utilization rho is the fraction of capacity consumed. For an idealized single server with random arrivals, residence time is ``` R = S / (1 - rho) ``` so the queueing component is S x rho/(1-rho). The consequences: ``` rho 0.50 0.70 0.80 0.90 0.95 0.99 R/S 2.0 3.3 5.0 10.0 20.0 100.0 ``` Utilization is a poor control variable exactly where it matters most: moving from 90% to 95% looks like a five-point change and doubles latency. Kingman's approximation extends this to general arrivals - queueing delay scales as (rho/(1-rho)) x ((Ca^2 + Cs^2)/2) x S, where the C terms are the coefficients of variation of interarrival and service times. Two systems at identical utilization can therefore have wildly different latency: variable service times (a slow 1% of requests) or bursty arrivals inflate the second factor. Adding servers helps twice - it lowers rho, and pooling many servers behind one queue reduces the variability each sees. ## What to measure - **Queue depth** and, better, **queue wait time**. By Little's law average queue wait = depth / throughput, so a depth of 60 at 500 rps means 120 ms of pure waiting added to every request. Depth rises before utilization pins, which makes it the earlier signal. - **Utilization per pool** (fraction of workers busy, and CPU utilization separately). A pool 100% busy while the CPU is idle means the workers are blocked on something else - the pool is not the bottleneck, the dependency is. - **Service time distribution**, not just the mean. The variability term is often the real cause of a bad tail. - **Arrival rate and burst shape.** A mean of 500 rps arriving in 50 ms bursts behaves like a much higher rate. ## Using the law as a cross-check Because the identity must hold, it exposes bad measurements. If throughput is 500 rps, average latency is 200 ms, and the pool has 12 workers with an empty queue, the numbers are impossible: L = 100 items in flight cannot fit in 12 workers, so either latency includes time spent outside the pool, or the queue is not being measured, or the throughput figure is wrong. Interviewers like this use because it separates people who memorized L = lambda x W from those who apply it. ## Limits Steady state is required: during a burst or an outage the law says nothing about the transient. It gives averages only, never percentiles - a tail problem needs the distribution. And it is an identity, not a causal model: it tells you the relationship the three quantities must satisfy, not which one you can change.