WhyPlayground

Little's law

The problemThe arrival rate and the time an item spends in the system are on every dashboard. The third quantity — how many items are in the system — is the product of those two, yet it usually gets estimated separately and approximately. Hence pools sized by the number of users, and queue-depth thresholds that say nothing about waiting time.

  1. Step 1 of 8

    Three quantities, one equality

    Little's law ties together three quantities: L, the average number of items in the system, λ, the rate at which they arrive, and W, the time each one spends inside. Any two of them give the third.

    By 1954 the relation was already in use as self-evident — Cobham states it without proof. John Little proved it in 1961; simpler proofs came later from Jewell, Eilon and Stidham.

  2. Step 2 of 8

    L = λ × W

    The statement: the long-term average number of items L in a stationary system equals the long-term average arrival rate λ multiplied by the average time an item spends in the system, W.

    Ten items a second, each spending thirty seconds inside — three hundred items in the system on average. The dimensions work out: items per second times seconds gives items.

    The relation does not depend on the arrival distribution, the service distribution or the service order. Items arrive evenly or in bursts, get served in order, from the back or by priority — the equality holds either way. The number of servers does not appear in it either.

    This is what sets the law apart from the rest of queueing theory. There you need the distributions to compute anything. Here two measured averages are enough.

    little.ts
    // L = lambda * W
const inSystem = arrivalsPerSecond * secondsInSystem;

    Output

    10 /s × 30 s = 300 in the system at any moment
no assumption about arrival pattern, service order or server count

  3. Step 3 of 8

    Any of the three from the other two

    The calculator is on the right. λ and W enter the product symmetrically: doubling the rate and doubling the time in the system give the same result.

    W itself has no slider — it is waiting plus service. So cutting service time brings down W, L and the number of servers together: λS falls with S. The other way round, an external service that gets three times slower raises W, L and the infrastructure bill, without a single quantity on our own side changing.

    Waiting stays an input, and that is not a simplification. By how much the queue shortens when service speeds up is something Little's law does not say — it has neither distributions nor utilisation in its conditions. That belongs to queueing theory, and the step on limits says so.

    Known quantities

    What follows from them

    Time in system W
    30 s
    Items in system L
    300 items
    In service λS
    100 items
    In the queue λWq
    200 items
    Servers needed
    100 servers

    W = 20 + 10 = 30 s, so L = λW = 300 items

    The same law on service: λS = 10 × 10 = 100. The other 200 are in the queue.

    More items are waiting than are in service: most of W is waiting, and that is what has to come down.

  4. Step 4 of 8

    Queue length as a difference

    The law applies not only to a system as a whole but to any subsystem of it. In the classic bank example the customer queue is one subsystem and each of the tellers is another.

    Apply it twice. To the whole system: λW, every item inside. To service: λS, where S is service time without the waiting. The difference is the queue length.

    Ten items a second, thirty seconds in the system, ten of them service. Three hundred in the system, a hundred in service, two hundred waiting.

    Hence the rule for pool size: size it by λS. A waiting item occupies a place in the queue, not a server. Sizing by λW buys three times more machines than the work needs.

    Brian Goetz writes this in Java Concurrency in Practice as threads = cores × target utilisation × (1 + wait time / service time). The ratio in brackets is the same wait-to-service proportion, and it is why a pool needs more threads than the machine has cores.

    little.ts
    // The same law on a smaller box: service only.
const inService = arrivalsPerSecond * serviceSeconds;
const waiting = inSystem - inService; 

// The pool is sized by service: waiting items do not hold a worker.
const workers = Math.ceil(inService / itemsPerWorker);

    Output

    10 /s × 10 s = 100 being served, 200 waiting in the queue
100 / 1 item per worker = 100 workers

  5. Step 5 of 8

    The other substitution: W = L / λ

    The equality solved for time in the system.

    This is how queue charts are read. The number "forty thousand messages" cannot be interpreted on its own: it can be normal operation or an outage. Divide it by the drain rate — two hundred a second — and you get two hundred seconds. The threshold "depth above forty thousand" means "an item waits more than three minutes".

    Hence the practice of alerting on the age of the oldest item rather than on queue depth. Age is W, the very quantity the promise to the user is about. Depth without λ cannot be interpreted: a thousand messages drained at ten thousand a second is a tenth of a second, while a hundred messages drained at one a second is a hundred seconds.

    little.ts
    // W = L / lambda — the same equality, solved for time.
const secondsToDrain = queueDepth / drainedPerSecond;

    Output

    40 000 messages / 200 per second = 200 s before the queue is empty
alert threshold "depth > 40 000" == "the oldest message is 200 s old"

  6. Step 6 of 8

    Conditions for it to hold

    Little is asked of the system: it has to be stationary and free of preemption. Both conditions rule out transient states, start-up and shutdown among them.

    Stationarity gets checked in practice like this: over a long enough window, as many items leave the system as entered it. If the arrival rate exceeds throughput, there is no stationarity. The queue grows, W grows with it and has no average value. The equality does not fail — it shows that L is growing — but there is nothing to predict with it: what has to be computed is the gap between λ and throughput.

    Throughput comes from the same quantities: the number of servers divided by service time. A hundred servers at ten seconds each give exactly ten items a second. At λ = 10 utilisation is a hundred per cent, and any deviation produces a queue that will not drain again.

    The observation window has to be long relative to W. For an item that takes a minute, the law describes tens of minutes, not about what happened inside one of them.

  7. Step 7 of 8

    What the law does not give

    All three quantities are averages, and long-term ones at that. Three limits follow, and all three regularly get assumed away.

    L = 300 does not mean three hundred items are always in the system. It can be a steady three hundred, or zero for half a day and three thousand at the peak hour. A pool sized by the average will not hold at peak, which is where the separate peak factor in estimates comes from.

    The law is silent about spread as well. An average W of twenty seconds is compatible with one per cent of items waiting ten minutes. Which is why promises to users are written in percentiles rather than averages.

    And it does not say what happens to W as λ grows. A throughput of ten items a second does not mean nine is a normal operating point: as utilisation approaches one, the queue grows non-linearly. That is queueing theory proper, and there distributions are unavoidable. Little gives L for a known W; how W changes as λ grows, he does not say.

  8. Step 8 of 8

    Where it gets used

    Three substitutions into one equality:

    • the number of servers — λS divided by how many items one of them holds;
    • queue length — λW minus λS;
    • waiting time — L divided by λ.

    Outside queueing theory the same equality goes by other names. Kanban writes it as "cycle time = WIP / throughput", and work-in-progress limits are a way of holding L down so that W does not grow.

    None of it starts with the formula. It starts with the boundary of the system: what counts as the system, what enters it and what leaves it. The multiplication comes after. The scraping jobs walkthrough sizes its worker pool this way.

Use ← and → to move between steps.

Check yourself

The job flow has not changed, but the target API has become twice as slow. What happens to the number of jobs running at once?

There are twenty thousand messages in the queue and consumers drain a thousand a second. How long does a message arriving right now wait?

Three hundred units are inside on average: a hundred being served, two hundred waiting. How many servers are needed if one holds one unit?

Answered 0 of 3