One Queue or Several

Last timeArrivals Come in Clumps

One queue feeding many servers beats a separate queue for each one, and the reason is the idle server standing next to somebody who is waiting.

One queue or many

Picture a bank with four tellers. In one arrangement there is a single line and

whoever reaches the front goes to the next free teller. In the other there are

four lines, one per teller, and each arrival picks one and stays in it.

The single line waits less. The arrival rate is the same, the service times are

the same, the utilisation is the same, and the single line still wins. The

reason is narrow and worth stating exactly: in the single line arrangement it is

impossible for a teller to be idle while anybody is waiting, and in the four

line arrangement it happens constantly, because the person who picked the slow

line stays in it while the teller next door finishes early and stands there.

Every other explanation of this effect is a restatement of that one. Nothing is

being balanced, no server is faster, and no work has been removed. The only

thing the shared queue does is close off the state where capacity and demand

exist at the same moment and cannot find each other.

FIG 1Four tellers, two arrangements, the same minute

step	arrangement	what happens when one server finishes early	what happens to a long job	chance of an idle server with someone waiting
1	one shared queue	it takes the next waiting arrival	it blocks nobody else	none, by construction
2	four separate queues	it waits for its own next arrival	it blocks everybody behind it	high, and rising with load
3	separate queues, arrivals choose at random	the same, it idles	the same, it blocks its line	the same as the row above
4	separate queues, arrivals ask two and pick the shorter	it is likely to be chosen next	it is avoided by later arrivals	much lower, though not nothing

4 steps

The third row is the arrangement most systems have by default, since a load balancer that spreads requests evenly is making the choice described there. The fourth row is the practical repair and it is remarkable how well it works: asking just two servers at random and sending the work to whichever has less waiting recovers most of the benefit of a single shared queue, without needing the shared queue that a distributed system cannot easily have.

The waste, measured

The size of the loss can be computed rather than described. Take an arrival that

finds its own chosen server busy, which happens with probability equal to the

utilisation. Ask how likely it is that at least one of the other servers is

idle, which is one minus the chance that all of them are busy. Multiply the two

and the result is the share of arrivals that wait while capacity is sitting

there unused.

Four servers at eighty per cent gives nought point eight multiplied by one minus

nought point eight cubed, which is nought point three nine. Thirty nine per cent

of arrivals wait next to an idle server. That is not a small inefficiency at the

margin, it is most of the waiting in the system.

FIG 2The share of arrivals that wait beside an idle server

at eighty per cent loadat fifty per cent load

Both curves start at nothing, because with one queue and one server there is no other server to be idle, and both rise and flatten as the number of separate queues grows. The upper curve flattens near the utilisation itself, which is the worst case: at high load and many queues, almost every arrival that waits is waiting beside spare capacity. The gap between the curves says that the cost of separating queues is much higher on a busy system than a quiet one, which is the same compounding seen with clumping in the previous lesson.

What the sharing buys

For deciding anything it helps to express the benefit as a fraction of the

waiting removed, because that is directly comparable with the other way of

reducing waiting, which is buying more servers.

The lesson stops here

3 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents