The Least Loaded Server Is a Rumor

You have a hundred servers and a stream of jobs. Where should each job go? The obvious answer is the server with the shortest queue. The famous answer from the theory of load balancing is better than obvious: pick two servers at random and send the job to the shorter of the two. That one comparison takes you most of the way from random to perfect. It's called the power of two choices.

Both answers assume you know the queue lengths right now. You usually don't. In a real system the load numbers come from somewhere: a report every few seconds, a shared table that's refreshed now and then. By the time you read it, it's old. Michael Mitzenmacher asked what that does in a 2000 paper, "How useful is old information?", and the answer was: least loaded turns into a disaster, and two choices holds up much better.

I rebuilt his setup to see the numbers myself, and then tried two things he didn't put front and centre: comparing against round robin instead of random, and the obvious fix of counting the jobs you sent yourself. The first changes the scorecard a lot. The second works well for one dispatcher and blows up spectacularly for three.

The setup

A hundred identical servers, each with its own queue, each serving one job at a time. Service times are random (exponential) with a mean of one unit, so I'll measure everything in service times. Jobs arrive at random at a rate that keeps the servers busy 50%, 70%, 90% or 95% of the time. The score is the average time a job spends in the system, waiting plus being served. A perfect balancer approaches 1.

The dispatcher reads queue lengths from a load board that's refreshed every T service times, all at once (Mitzenmacher's "periodic update" model). Between refreshes the board doesn't change, however many jobs pour in.

First I checked the simulator against the known answers with live information. Random dispatching is a set of independent single queues, so at 90% load the mean is 1/(1 − 0.9) = 10; I got 10.08 ± 0.08. For two choices there's an exact formula for very many servers (Vvedenskaya, Dobrushin and Karpelevich, 1996): 2.614 at 90% load; with 1,000 servers I got 2.616 ± 0.012. Three choices and other loads agreed similarly, within about 1%.

Stale information, one dispatcher

The left panel reproduces Mitzenmacher's picture. With live information, least loaded is almost perfect: 1.07 service times at 90% load. Make the board a little old and it degrades fast. Every job that arrives between refreshes sees the same board, so they all go to the same few servers that looked empty. A herd. Once the board is refreshed every few service times, least loaded is worse than picking at random, and it keeps getting worse: 55 at 20, over 1,400 at 100.

Best of two degrades much more gently. Picking two servers at random spreads the herd out: a server that looked empty only gets the jobs whose random pair happened to include it. It stays better than random until the board is refreshed only every 20 to 100 service times, depending on the load.

T is the time between board refreshes, in service times. The ranges are the two grid points where the curve crosses.

So far, that's the paper's lesson: with old information, use fewer choices. But I think the comparison is rigged in a way that flatters every policy here.

Random is the wrong baseline

Random dispatching uses no information, so it looks like the natural floor. It isn't. Round robin also uses no information about queues, only a counter, and it's much better. Each server gets every hundredth job, so its arrivals are almost perfectly regular instead of bunched, and regular arrivals queue far less. At 90% load, round robin averages 5.2 service times against random's 9.9. That's close to the textbook answer for perfectly regular arrivals (5.18).

Against that baseline, the budget for staleness shrinks:

At half load, round robin with no information at all ties two choices with perfect, live information. That isn't a fluke of my simulator. Using the exact formulas for very many servers, round robin (regular arrivals) beats live two-choice whenever the load is below about 52%; above that, two choices pulls ahead, and by 95% it's three times better. Least loaded with a board older than a service time or two loses to the counter at every load I tried.

The fix: count what you sent

The herd happens because the dispatcher ignores something it knows for certain: where it just sent jobs. So keep a private tally since the last refresh and add it to the board. A server that looked empty stops looking empty after the dispatcher has sent it a few jobs.

With one dispatcher, this works beautifully (the green line on the left). Least loaded plus its own tally stays below round robin at every staleness I tried at 90% and 95% load, and with a very old board it smoothly becomes round robin, since then the tally is the only thing that changes. At 50% and 70% load it ends slightly worse than round robin with a very stale board (1.33 vs 1.26 at 50%), but never by much. That's a policy that's never terrible.

Then I added more dispatchers. Real systems rarely have just one: several front ends share a load board, each knowing only its own sends. Each job goes to a random one of them.

With two, it stays tame: at worst about a third slower than round robin (at 70% load), and always better than random. With three or more, the herd comes back, and worse than before (the right panel). At 90% load with three dispatchers the mean passes random once the board is refreshed every 20 service times, and reaches 42 at 100. Five dispatchers reach 133; ten reach 590. That's still better than plain least loaded with no tally at all, but far worse than best of two with no tally, which stays between 5 and 21 over the same range.

Then, past a certain staleness, the curve falls off a cliff to near round robin. Three dispatchers at 90% load: 42 at T = 100, 6.4 at 200. Ten: 590 at 500, 10 at 1,000. Two independent runs agree within a few percent at nearly every point; right at the edge they can differ (133 vs 82 for five dispatchers at 200), which is what you'd expect next to a tipping point. The drop itself shows up in every run.

I scanned finely around the cliff to see where it sits. For five dispatchers the peak came at 31, 77 and 307 service times at 70%, 80% and 90% load. Multiply by (1 − load)² and you get 2.8, 3.1 and 3.1: the same number. For three dispatchers at 90% it's 0.9. That (1 − load)² is also how the time a single queue needs to forget where it started grows with load, so the cliff seems to be tied to how fast queues drain. I measured the scaling, but I don't have an explanation of the cliff that I'd trust yet, so take this as a regularity, not a theory. Update: The Cliff Was a Trap Door explains it, and the queue-forgetting guess was wrong. Past the cliff the herd still exists; a large enough imbalance flips the system back into it.

One more unpleasant detail: with many dispatchers the tally makes best of two worse too. At 90% load, a board refreshed every 10 service times, best of two with no tally averages 5.1. With ten dispatchers each adding their own tally, 6.8.

What I take from it

• Compare against round robin, not random. A load balancer that uses queue information should have to beat the policy that uses none but is still smart. Below about half load, live two-choice doesn't.
• With old information, sample a few servers at random. Best of two degraded gently in every run and never became the catastrophe least loaded did.
• Counting your own sends is excellent with one dispatcher and dangerous with three or more, in a way that depends sharply on how stale the board is. I would not have guessed that, and I'd test for it before trusting the trick in any system with several front ends.

The limits are real. Every job here takes the same time on average, with exponential spread; servers are identical; arrivals are random and steady; the board refreshes for everyone at once. Round robin is blind to job sizes, so I'd expect heavy-tailed jobs to hurt it more than the queue-reading policies, but I didn't measure that here. (Later the same day I did: it's true, and by a lot.) The simulator is one small file, the same code as the demo.