Little's Law: Concurrency, Arrival Rate, and Time in System

Three numbers describe any system that work flows through: how many items are inside it at a given moment, how fast items arrive, and how long each item stays. Little’s Law states that in steady state the first equals the product of the other two. Written as $L = \lambda W$, it relates mean concurrency, mean arrival rate, and mean time in system.

The identity is unusual among performance results in that it requires almost nothing. It does not assume Poisson arrivals, exponential service, independence, or a single server. It does not assume that service times are identically distributed. It holds for a supermarket checkout, a thread pool, a TCP connection table, and a garbage collector’s live set, provided the quantities are measured consistently over the same interval and the system is not drifting.

The identity is a conservation statement

The proof is a counting argument over a window of length $T$. Draw the number of items in the system as a function of time. The area under that curve is the total time that all items collectively spent inside, measured in item-seconds. If $N$ items passed through the window and each spent $W$ seconds on average, the area is also $N \cdot W$. Dividing by $T$ gives the average concurrency on the left and the arrival rate $\lambda = N/T$ on the right:

$$ \frac{1}{T}\int_0^T L(t),dt = \frac{N}{T} \cdot W = \lambda W $$

Nothing in that step refers to a distribution. The only approximations are the boundary terms: items already inside when the window opens and items still inside when it closes. If those are bounded, their contribution to the integral is $O(1)$ while the rest grows with $T$, so the error vanishes as the window lengthens. This is why a one-minute sample of a busy service is enough to check the identity to a few percent, and why a one-second sample is not.

The practical value is that the identity converts between quantities that are easy to measure and quantities that are hard to measure. Concurrency and arrival rate can be sampled cheaply: a counter incremented on entry and decremented on exit, plus a request counter. Time in system requires either instrumenting both ends of each request or holding every request until it completes, and that is exactly what a load generator does when it keeps a fixed number of clients in flight.

Choosing the boundary changes all three terms

The identity is only meaningful once the boundary of “the system” is fixed, because every term is defined relative to it. For an HTTP handler, the boundary might be the handler function, the socket read-to-write interval, or the whole client-visible exchange including DNS and TCP setup. Each choice yields a different $W$, and correspondingly a different $L$: a request that is sitting in the kernel’s accept queue is inside the socket boundary but outside the handler boundary.

This is the source of a common inconsistency in dashboards, where a concurrency gauge counts requests that have entered application code while a latency histogram measures from the first byte read to the last byte written. The two numbers satisfy Little’s Law only if the gauge also counts the kernel queue, and it usually does not. The resulting product $\lambda W$ then exceeds the observed $L$ by exactly the time spent waiting to be accepted, which is the very quantity the queue is supposed to reveal.

A consistent measurement answers a specific operational question. If the boundary is the client-visible exchange, then $L$ is the number of outstanding requests and $W$ is what the client experiences, so the identity states that a client holding 200 requests in flight against a service that answers 2,000 per second will see 100 milliseconds per request. If the boundary is the handler, the same identity constrains only the handler’s own occupancy, and the client’s number will be larger by the network and queueing time outside it.

Closed systems invert the direction of the inference

The most frequent misuse appears in load testing. A generator with a fixed number of virtual users is a closed system: it cannot issue a new request until a previous one completes. In that arrangement, arrival rate is not an independent input. It is determined by the system’s own latency, since each of the $C$ clients completes a request every $W$ seconds, giving $\lambda = C/W$ and therefore $L = C$.

The identity still holds; it has simply become a tautology. Concurrency is pinned at the number of clients, so measuring $L$ tells nothing new, and the observed throughput is a consequence of latency rather than a property of the server. The consequence for interpretation is severe: a closed-loop test that doubles the client count and sees throughput rise by less than a factor of two has not shown that the server saturates at that point. It has shown that latency rose, which reduced the offered rate. The service might be able to accept far more load from clients that are not waiting on it.

An open-loop generator, which issues requests on a schedule independent of completions, produces the opposite bias. Its arrival rate is a genuine input, and the identity becomes informative about queue growth. The cost is that an open-loop generator must decide what to do when its schedule falls behind, and the naive answer, skipping the missed request, is precisely the measurement error described in Coordinated Omission and the Samples a Closed Loop Never Takes.

Accounting failures that break the identity

Four bookkeeping errors make the identity appear to fail, and each corresponds to a real defect in the measurement rather than in the theorem.

Requests that are dropped or rejected before completing are inside the system for the duration of their rejection but are often omitted from the arrival count, since the counter increments only on successful admission. The visible effect is that $\lambda W$ falls short of $L$: concurrency includes the rejected requests, arrival rate does not. The fix is to count admissions, not successes, at the boundary being measured.

Retries double-count arrivals. A client that retries twice contributes three arrivals and three times the server-side work for one logical operation. If the retry happens outside the measured boundary, the arrival rate at the boundary is inflated relative to the useful work, and the time-in-system figure describes an attempt rather than an operation. Whether that is the right number depends on the question being asked, but it has to be stated, because the two differ by the retry multiplier.

Long-lived requests break the steady-state assumption. A single request that never completes contributes to $L$ forever while never contributing to the completed count $N$. Over a long window it dominates the area under the concurrency curve, and the computed $W$ becomes a number that describes no real request. Systems with streaming connections or hung handlers need the window to be chosen so that the non-completing fraction is small, or the analysis has to be split by request class.

Non-stationarity breaks it in a subtler way. If arrival rate is climbing, the requests in the system at the end of the window are a sample from a heavier-load regime than the ones that completed, so the mean of the completions understates the current time in system. The direction of the bias is predictable, and it means that during an incident the completed-request latency always looks better than the latency a newly arriving request will experience.

Measuring the three terms from an event log

A trace of enter and exit events is enough to compute all three quantities, and doing so exposes which of them were actually observed rather than assumed.

from collections import defaultdict

def little(events):
    """events: list of (timestamp, 'in'|'out', request_id)"""
    events.sort()
    inside = 0
    area = 0.0          # item-seconds
    t_prev = events[0][0]
    entered = completed = 0
    dwell = defaultdict(float)
    start = {}

    for t, kind, rid in events:
        area += inside * (t - t_prev)   # rectangle under the concurrency curve
        t_prev = t
        if kind == 'in':
            inside += 1
            entered += 1
            start[rid] = t
        else:
            inside -= 1
            completed += 1
            dwell[rid] = t - start[rid]

    window = events[-1][0] - events[0][0]
    L = area / window
    lam = completed / window
    W = sum(dwell.values()) / completed
    return L, lam, W, L - lam * W      # last term is the boundary error

The residual is not zero, and should not be. It equals the area contributed by requests that entered before the window opened or were still inside when it closed, divided by the window length. Printing it is the cheapest available check that the window was long enough and that the enter and exit events are balanced.

What the identity does not constrain

Little’s Law says nothing about how time in system is divided between waiting and being served. That split is what the utilization curve governs, and it is where the interesting nonlinearity lives: a system can satisfy $L = \lambda W$ at every load level while its wait time grows without bound as utilization approaches one. The identity also says nothing about the distribution of $W$, only its mean, so it cannot distinguish a service where every request takes 100 milliseconds from one where half take 1 millisecond and half take 199. Both satisfy the identity and behave completely differently under load, which is the argument for measuring percentiles rather than means and is treated in Means, Percentiles, and What a Tail Measurement Can Answer.