A server that's busy 70% of the time sounds comfortable. It has 30% of its time to spare, so you'd expect a request to get through with barely a pause. Yet if every request needs 1 ms of work and the server is busy 90% of the time, the average request takes about 10 ms from arrival to answer, and nine of those milliseconds are spent waiting in line. Push to 99% and it takes about 100 ms.
This lab lets you watch where that waiting comes from. A few words first. A request's service time is how long the server works on it once it starts; here it averages 1 ms, written S. Requests arrive at random moments, and one that arrives while the server is busy waits in the queue. The fraction of time the server is busy is its utilisation, written ρ (rho). A request's latency is its time in the queue plus its service time. We'll look at two summaries of latency: the mean, the ordinary average, and the p99, the latency that 99 requests in a hundred beat and one in a hundred doesn't.
| job | arrived | waited | served | latency |
|---|---|---|---|---|
| nothing yet | ||||
The top half is the queue itself. "Step one event" moves the clock to the next thing that happens, either a job arriving or the server finishing one, and the line at the bottom says what happened. Each job in the queue shows how much work it needs. The table lists the last few jobs to finish, with how long each waited and how long it was served. The bottom half is a plot of latency against utilisation: the solid line is the formula, and the dots are what the simulation gets when it runs 100,000 jobs at a given ρ. Everything is driven by a seeded random number generator, so the same seed and settings always give the same jobs and the same dots.
Things to try
1. A queue at 70% busy
Leave the settings as they are: ρ = 0.70, exponential service times, one server, seed 9. Before you press anything, guess.
The server is busy 70% of the time on average. Step through the first dozen events. How many jobs are waiting at the end?
Keep stepping, or press "+50 events", and watch the queue drain and refill. The column of waits in the table is the whole story of this lab: the work each job needs stays the same, and the waiting depends on who arrived just before it.
2. Drag toward 1.0
Press "Sweep ρ from 0.1 to 0.95". Eleven dots appear, one per load level, each from 100,000 simulated jobs. For one server with random arrivals and exponential service times (the M/M/1 model: random arrivals, random service, one server), the mean time in the system has an exact formula:
W = S / (1 − ρ)W is the mean latency. At ρ = 0.5 it's 2 ms, at 0.7 it's 3.3 ms, at 0.8 it's 5 ms.
At ρ = 0.9 the mean latency is 10 ms. Drag the slider to 0.95. What does the formula give now?
Now switch the plot to p99. In this model the latency of a single request follows an exponential distribution, the "mostly short, sometimes long" shape, and for that shape the p99 is ln(100), about 4.6, times the mean. At ρ = 0.9 that's 46 ms for 1 ms of work.
Look closely at the dots near the right edge. At ρ = 0.95 the seed-9 dot sits a little under the line, at about 17.5 ms instead of 20. Near full, the queue swings through long busy stretches, and even 100,000 jobs only see a handful of them. Press the seed button a few times and rerun at 0.95: the dot moves around the line, sometimes above it. The formula is a long-run average, and close to ρ = 1 the long run is very long.
3. The same average work, spread differently
Set ρ back to 0.70 and press "Run 100,000 jobs" once with each service-time setting. All three have a mean service time of exactly 1 ms. Constant means every job takes 1 ms. Exponential is the random shape from experiment 2. High-variance is a mix: one job in ten is long and averages 7 ms, and the other nine average a third of a millisecond.
All three settings average 1 ms of work per job, and the server is 70% busy in each. How do their mean latencies compare?
The mix is slow even though nine jobs in ten are tiny. When a 7 ms job reaches the server, every job behind it waits for the whole 7 ms, and a third-of-a-millisecond job that waited 7 ms has a latency more than twenty times its work. Switch the plot to p99 and the high-variance dots sit far above the others.
The dashed line on the plot is the setting you had before the last change, so you can see two curves at once. The waiting part of the high-variance curve sits five times higher than the exponential one at every ρ, and both still go vertical at 1. Lowering variance can't move the wall, but it does lower the curve everywhere before it.
When arrivals aren't random either, Kingman's formula approximates the wait as ρ/(1 − ρ) × (Ca² + Cs²)/2 × S, where Ca² is the same spread measure for the gaps between arrivals. Random arrivals have Ca² = 1, which turns Kingman back into the formula above. Bursty traffic has a larger Ca² and raises the curve the same way variable work does.
4. Four servers, one line
Choose exponential service, set ρ = 0.90, and switch to four servers sharing one queue. Each server is still busy 90% of the time; there's four times the traffic and four times the capacity.
Four servers, each 90% busy, sharing one queue. One server at 90% gives a mean of 10 ms. What's the mean latency now?
Four separate servers, each with its own queue and a quarter of the traffic, would be four copies of the one-server case at 10 ms each. Merging them into one shared line is called pooling, and it's why one large pool can run hotter than several small ones for the same latency. Now switch to high-variance with four servers. The mean rises to about 11 ms, so pooling helps a lot but doesn't cancel variance. (For four servers with non-exponential work there's no exact formula; the line here scales the four-server wait by (1 + Cs²)/2, a standard approximation, and the dots land near it but not exactly on it.)
5. Give the line an end
Go back to one server with exponential service, switch the queue to 8 slots, and drag ρ to 0.99. A job that arrives to find all eight slots taken is turned away, which is what a server with a bounded queue does when it's full; turning work away on purpose to protect latency is called load shedding.
ρ = 0.99 with an unbounded queue gives a mean of 100 ms. With only 8 waiting slots, what happens?
The plot's solid line still shows the unbounded formula, so the dots sit far below it at high ρ: the bounded queue has given up throughput to keep latency flat. Switch to high-variance at ρ = 0.9 and about 22% of arrivals are dropped. Variable work fills the slots faster, so the same bound costs more.
What this shows
Waiting comes from bursts landing on a server that has too little spare time to clear them, and the spare time is 1 − ρ. Near full, that number is tiny, so latency grows as 1/(1 − ρ) and goes vertical at 1, with the p99 several times higher than the mean. The variance of the work scales the whole curve up or down without moving the wall. Sharing one queue among several servers makes waiting rare until every server is busy at once. A bounded queue keeps latency flat by refusing work, so you trade rejected requests for a latency limit. All of these formulas assume steady load and random arrivals, which makes them optimistic: real traffic is burstier, so real queues are usually worse than the line.
Where to read more
- Contention, Queueing & Tail Latency, section 2, "Where the waiting comes from", walks the burst you stepped through in experiment 1, and section 3, "The utilisation curve", derives
W/S = 1/(1 − ρ)and lists where the M/M/1 assumptions break. - Queueing & Capacity, section 3.4, "Bigger pools run hotter", has the Erlang C table behind experiment 4 and works out how pooling changes the size of a fleet.