Basis Lab

Answers · The systems around the model

How can I estimate wait time from the number of requests in the system?

In shortDivide the average number of requests inside the system by the rate at which they arrive, and you get the average time each request spends there.

Divide the average number of requests inside by the arrival rate: T=N/λT = N/\lambda. If the count is only requests waiting and not the ones being served, that quotient is the average wait; if the count includes requests in service, it is the average time from arrival to completion, and the average wait is that value minus the average service time.

FIG 1Time inside from count and rate
the average number of requests inside the system
the rate at which requests arrive, and therefore also leave
the average time a request spends inside
The same three quantities rearranged. The count and the rate are the easy measurements; the time is what falls out.

A queue observed to hold 40 requests waiting while 20 arrive each second implies 40/20=240/20 = 2 seconds of average wait. The same 40 waiting under 80 arrivals a second implies 40/80=0.540/80 = 0.5 seconds. The queue length is identical in the two observations, yet the waits differ by a factor of four, because the second system is clearing work four times as fast.

The natural guess is to treat queue length and wait as separate metrics, then try to predict one from the other by intuition. They are not separate: the count is the arrival rate multiplied by the time, N=λTN = \lambda T. A queue of 100 looks worse than a queue of 40, but at 400 arrivals a second the 100 implies 100/400=0.25100/400 = 0.25 seconds, while at 20 arrivals a second the 40 implies 40/20=240/20 = 2 seconds. The apparently longer queue is the faster system. A count with no arrival rate cannot rank two systems, cannot tell you whether a wait is acceptable, and cannot tell you whether to add capacity or reduce traffic.

What to count

Decide what the count contains before dividing. A queue depth metric usually counts requests waiting, so Nwait/λN_{\mathrm{wait}}/\lambda gives average queue wait. A requests in flight metric counts waiting plus being served, so Nsystem/λN_{\mathrm{system}}/\lambda gives average residence time. To recover the wait from an in flight count, subtract the average service time: Twait=Nsystem/λ−ST_{\mathrm{wait}} = N_{\mathrm{system}}/\lambda - S, where SS is the average time actually spent being worked on. A pool of 100 connections serving 400 requests a second has 100/400=0.25100/400 = 0.25 seconds residence. If the database reports 40 milliseconds of work per query, then 0.25−0.04=0.210.25 - 0.04 = 0.21 seconds is waiting, which is 0.21/0.25=0.840.21/0.25 = 0.84, so about 84% of the time inside is queueing rather than work.

Twait=Nwaitλ,Tsystem=NsystemλT_{\mathrm{wait}} = \frac{N_{\mathrm{wait}}}{\lambda}, \qquad T_{\mathrm{system}} = \frac{N_{\mathrm{system}}}{\lambda}
FIG 2
average count insidearrival rateimplied average timewhat the count is
40 waiting20 per second2 secondswait
40 waiting80 per second0.5 secondswait
100 in flight400 per second0.25 secondsresidence
240 open tickets120 per day2 daysresidence in the ticket system

The units have to match. If 120 tickets arrive per day and 240 are open, 240/120=2240/120 = 2 days open on average. The same sum works per hour, per minute or per second, provided the count and the rate use the same clock. Mixing a per day arrival rate with a per second count gives a wait that is wrong by a factor of 86,400, which is worse than no estimate.

The stable window

The division is an average over a stable window. It requires that the amount inside is not systematically growing or shrinking, so arrivals and departures balance over the window being measured. If a queue is filling, the count divided by today's arrival rate is not the wait a new request will get: the wait is rising, and the quotient describes only the instant. Measure across a window long enough that the queue at the start and the queue at the end are similar, and do not apply the relationship across a boundary where requests are dropped, retried or duplicated.

Within that stable window, the relationship does not care whether arrivals are random or regular, whether service times are constant or heavy tailed, how many servers there are, in what order work is served, or whether the queue is bounded. That is why it can be used before any more detailed queueing formula. It is also why it is the first thing to calculate when a system is slow: two numbers that are already being logged give an average time, and the average time says whether the problem is the arrival rate or the amount of work in progress.

Rearranged as N=λTN = \lambda T, the same statement sizes the system. Four hundred arrivals a second each staying a quarter of a second need 400×0.25=100400 \times 0.25 = 100 requests inside at any moment. A pool of 50 will queue; a pool of 500 will mostly idle. A timeout set below the residence time will cut off requests that would have completed, while one set far above it lets work pile up behind slow requests. The count is a consequence of the rate and the time, not a number to choose and hope about.

Worth keeping

  • The average number of requests inside a stable system equals the arrival rate multiplied by the average time each request spends inside.
  • A queue length on its own cannot rank two systems; the arrival rate has to be divided into it.
  • The relationship stops holding when the amount inside is systematically growing or shrinking over the measurement window.

Where this goes next

This question is one step of Work That Waits in a Queue, a course that works through its subject from the beginning. The page that teaches this part of it is The One Relationship Worth Memorising, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that pageThe whole course

Other questions people ask about this

  1. How can I tell if my traffic is bursty or just high volume?Compare the variance of the gaps between arrivals with the square of their average gap: high volume alone does not make traffic bursty.
  2. Why does average latency hide the slow requests users actually feel?Waiting times are lopsided, so the average sits between the common case and the bad case and describes neither, and it is the bad case that users keep meeting.
  3. What's the difference between a CDN cache and caching inside my own app?A CDN cache sits near the user and can only hold answers that are identical for everyone, while a cache inside your app can be personal but exists once per process.
  4. What's the difference between LRU and LFU, and which one should I use?LRU drops the item unused for longest; LFU drops the item requested least often. Both guess at future use, and the cheap win is refusing one-off arrivals rather than counting requests.
  5. Why can't a system just stay consistent and available when the network splits?During a split, a cut-off machine can only answer from the data it already holds, so it must either risk being wrong or refuse to answer.
  6. Should the gradients be summed or averaged across GPUs?Sum the gradients when each device already divides its loss by the global batch size; average them when each device uses its own local mean. Doing both makes the gradient too small by the number of devices.

Read alongside