Things Arriving, and Things Being Served

Every waiting system is two rates, the rate work arrives and the rate it can be served. The whole subject starts with the condition that keeps the queue from growing forever.

The two rates

A queue is not a thing somebody built. It is what happens between two rates.

The first is how fast work arrives: requests a second, jobs an hour, customers

a minute. The second is how fast work can be finished, which is usually easier

to think about as its reciprocal, the time one unit of work takes. A service

that handles a request in forty milliseconds finishes twenty five a second per

worker, and with ten workers it finishes two hundred and fifty a second.

That is the entire description of a waiting system at this level: a rate in,

and a rate out. Everything in the rest of this course is a consequence of those

two numbers and of how regular or irregular they are.

FIG 1Four systems, described by their two rates

	arrivals a second	service time in seconds	servers	can it keep up
a web service	240.00	0.04	12.00	1.00
a payment processor	50.00	0.30	10.00	0.00
a nightly batch	1.00	0.50	1.00	1.00
a support desk	30.00	300.00	100.00	0.00

Coded 1 for yes and 0 for no in the last column, and the support desk row is per hour rather than per second so the shape of the arithmetic is visible on a human scale. The second and fourth rows cannot keep up: fifty arrivals a second at three tenths of a second each needs fifteen servers and has ten, and thirty arrivals an hour at five minutes each needs a hundred and fifty people and has a hundred. In both cases the queue grows for as long as the arrivals continue, and nothing inside the system can prevent it.

The condition for a queue not growing

Put the two rates side by side and the condition is almost obvious. Work has to

leave at least as fast as it arrives, or the amount waiting grows.

FIG 2The servers needed to keep up

: the arrival rate, in units of work per second
: the time one server takes to finish one unit, in seconds
: the number of servers needed to just keep up

The relation being rearranged is that m servers each finishing one unit every s seconds complete m over s units a second, and that has to match the arrivals. Two hundred and forty arrivals a second at four hundredths of a second each needs nine point six servers, so ten. Notice that the units cancel: work per second multiplied by seconds per unit of work leaves a bare count. This is a floor and not a target, for the reason the next lesson is about, and running a system at exactly this number is the same as running it at a hundred per cent busy.

The condition is a strict inequality. Arrivals must be less than capacity, not

equal to it, and the difference between the two is not a technicality. At

exactly equal rates the queue does not settle at some length; it wanders

upwards without bound, because any run of arrivals slightly closer together

than average builds a queue that the system has no spare capacity to work off.

FIG 3Queue length over an hour at three loads

arrivals below capacityarrivals equal to capacityarrivals above capacity

Three different shapes, and only the first is a system in a steady state: the queue rises and settles, and the level it settles at is the subject of the third lesson. The second does not settle, because at equal rates there is nothing to work a backlog off with, so the queue drifts upward at a slowing rate forever. The third is the one people recognise from an incident, where the line is straight and the only question is which runs out first, memory or patience.

How many servers are needed

The arithmetic of the figure above is worth doing deliberately, because it is

the one capacity calculation that is always available and it needs no model of

anything.

Measure the arrival rate and measure the service time, multiply them, and the

answer is the number of servers that would exactly keep up. A real system needs

more than that, and how much more is what the third lesson quantifies, but the

floor is immediate and it frequently settles an argument on its own: a team

planning six servers for a load that needs twelve has a planning problem rather

than a tuning problem.

The same arithmetic works at every level of a system. Database connections,

threads in a pool, file handles, outbound sockets, people on a rota: each is a

set of servers with a service time and an arrival rate, and each has its own

floor.

Where the queues actually are

Most systems contain several queues and have named none of them. The ones that

cause incidents are usually the undeclared ones.

FIG 4One request, and every place it can wait

step	where	what the servers are	what happens when it is full
1	the operating system accept queue	the processes calling accept	new connections are refused
2	the thread or worker pool	the workers	requests wait, invisibly to the client
3	the database connection pool	the connections	the worker blocks, holding its own slot
4	the database own lock queue	whatever holds the lock	transactions pile up behind one row
5	the outbound call to another service	that service capacity	this system inherits that queue

5 steps

Five queues in a request that most diagrams draw as two boxes and an arrow. The third row is the one that produces the characteristic failure, because a worker waiting for a connection is occupying a worker slot while doing nothing, so one exhausted pool fills the pool in front of it and the symptom appears at the front door rather than where the problem is. The last row is the reason the sixth lesson exists: a queue in a service you call is a queue in your system too, whether you can see it or not.

Finding them is a matter of asking, at every point in a request, what would

happen if the next thing were not immediately available. Wherever the answer is

that the work waits, there is a queue, and it has a depth, even if that depth

was never chosen and is whatever the library default happens to be.

FIG 5Measuring the two rates from an ordinary service

python

arrivals = count_requests(window=60) / 60.0    # work per second

service = mean(duration_of(r) for r in sampled_requests)   # seconds each

print(arrivals, service, arrivals * service)   # the third number is the floor

Three quantities, two of which most services already record. The arrival rate is a count over a window, and the window matters because a short one is noisy and a long one hides the bursts that the fourth lesson is about. The service time is the time a request occupies a worker, which is not the same as the time the client waited, since the client time includes queueing. Mixing those two up is the commonest measurement error in this subject, and it makes a busy system look like a slow one.

The next lesson takes the ratio of the two rates, which everybody already

reports, and shows that on its own it says almost nothing about waiting.

Recap

A queue is described by two rates, how fast work arrives and how fast it can be finished, and almost everything else follows from those two.
If arrivals exceed the rate work can be served, the queue grows without limit and no amount of patience, buffering or retrying changes that.
Both rates are measurable from an ordinary service, and measuring them is the first thing to do before any discussion of capacity.

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

NextHow Busy Is Busy →