I’ve been meaning to talk about this law for some time, and it was mentioned in an interview I was in recently so I thought that I should actually put a post together on this.

In November 1960 John DC Little submitted A Proof for the Queuing Formula which proved that he long-term average number L of customers in a stationary system is equal to the long-term average effective arrival rate λ multiplied by the average time W that a customer spends in the system. Expressed algebraically the law is

L = λ W

The formula can be used to determine how many people, on average, will be waiting in a queue

For example, if an average of 40 customers per hour arrive at a shop wanting to be served, and they have an average W of 6 minutes (0.1 hours) then the length of the queue is

λ = 40
W = 0.1
L = λ W
L = 40*0.1
L = 4

That is, the average length of the queue of people waiting to be served is 4.

This turns out to be really helpful for computer science too. Most Go developers know that a buffer in a channel is for handling bursts, that is, brief moments where the producers out produce what the consumers can consume from the channel. But the question is, how long should that queue be.

Using Little’s law we can estimate that.

We rarely know in advance how a burst will manifest itself, but what normally know is how long a consumer takes to deal with an item in the channel.

If we say that it takes 10ms for a consumer to process, and we create a buffer of length 10, then, with Little’s law

W = 0.01s
L = 10
λ = L / W
λ = 10 / 0.01
λ = 1000/s

Little’s Law tells us that our channel with a buffer of 10 will be sufficient for a burst of 1000 items/seconds (1 every millisecond).

We can also use Little’s Law to determine how quickly our consumers need to handle items on a channel.

If we have a channel buffer of 10, and 4000 items arriving per second

L = 10
λ = 4000
W = L / λ
W = 10/4000
W = 0.0025sec
or
W = 2.5ms

Our consumers must be able to process each item within 2.5ms in order for the producers to continue unimpeded.

If a single consumer cannot manage this, then multiple consumers need to be created to handle that load. If we know that a consumer takes (on average) 100ms to process the item, then we need 40 consumers working concurrently to ensure that the producers are not blocked waiting for a consumer to be ready (the producers may still be waiting for the consumer to process the item, depending on if the producer is coupled to the item).

This is a very handy piece of knowledge, developers can use it to determine queue lengths, site reliability engineers can use the formula to determine how many instances of a consumer need to be spun up when a certain level of traffic is experienced (magically too, with cloud or kubernetes doing the calculations).