The Power of Two Choices

Every time you load a video or run a search, your request lands on one of many identical servers. A load balancer decides which one, and a large service makes that decision millions of times a second.

The obvious rule is to send each request to the least busy server. The rule inside YouTube, NGINX and Envoy is stranger: pick two servers at random, and send the request to the less busy of the two.

Here are two clusters handling the same traffic. The left one sends each request to a random server. The right one picks the better of two.

Requests on the right finish about three times faster. That part is not too surprising: looking at two servers is better than looking at none. But why only two? To find out, we'll start with the simplest rule there is, picking at random.

1Picking at random

Let's look at one cluster up close. The balancer is at the top and ten servers are along the bottom. Each face is a request: the one sitting on a server is being handled, and the ones stacked above it are waiting. A line flashes each time the balancer sends a request, and faces get grumpier the longer they wait.

Each request takes about 100 ms, so the ten servers can handle about 100 requests a second. Here 90 arrive each second, keeping the servers busy 90% of the time.

This balancer sends every request to a random server. Watch for servers that turn orange. That's a server sitting idle while requests at other servers wait in line: there is work to do and a free server to do it, but they're in different places.

Random is fair on average: over time, every server gets the same share of requests. But in any moment some servers get unlucky streaks, and when the servers are busy, unlucky streaks are expensive. Try the slider. At 50 requests a second, a request spends about 200 ms in the system in total. At 90 a second it's about 1,000 ms, and at 95 a second about 2,000 ms. Those numbers come from a classic formula from queueing theory:

average time in the system = time per request1 − how busy the server is

At 90% busy, that's 100 ms ÷ 0.1 = 1,000 ms. As a server gets close to fully busy, the bottom of the fraction gets close to zero and the wait shoots up. A server that's busy almost all the time has little slack to catch up after a burst, so any line it builds takes a long time to drain. A little unfairness turns into a lot of waiting.

2Looking at every server

The obvious fix is to check every server before sending a request, and pick the one with the shortest line. Engineers call this least loaded, or "least connections." Here is the same traffic, 90 requests a second. Switch between the two rules.

With least loaded, the lines nearly vanish, the average drops from about 1,000 ms to under 200 ms, and no server ever sits idle while others have a line, because an idle server is always the first choice.

With one load balancer in front of ten servers, this is close to the best you can do. Real systems are not built that way, though.

3Many load balancers

A large service gets far too many requests for one load balancer to handle, and a single balancer would be a single point of failure. So there are many of them, dozens or hundreds, each taking a share of the incoming requests and deciding where to send them on its own.

Each balancer knows what it has sent. It doesn't know what the other balancers have sent. To find out how busy the servers really are, it would have to ask them, and asking every server before every request would add a network round-trip to every request. So a common design is for a monitor to collect every server's queue length and send a load report to all the balancers at once, here every 500 ms. Between reports, each balancer adds its own requests to the report's numbers.

In the picture, the gold mark in each server's line shows what the last report said, and the bar at the top shows how old the report is. The small bars under the servers count how many requests each server has received since the last report. Every balancer below uses least loaded. Start with one balancer, then add more.

With one balancer it works well. With twenty, it falls apart. Every balancer reads the same report, sees the same server as least loaded, and sends its next requests there. Each one counts its own requests, but none of them can see that the other nineteen are doing the same thing. Watch the bars under the servers: right after a report, nearly all the new requests go to one or two servers. By the next report those servers have long lines and different ones look emptiest, so the whole crowd moves there. With twenty balancers, least loaded does no better than picking at random.

This is called herd behavior. Michael Mitzenmacher, who analyzed it in 2000, compared it to a supermarket announcing that "Aisle 7 is now open": everyone rushes over, and Aisle 7 is soon the longest line (Mitzenmacher, 2000). Real systems run into it. The engineers who built TranSend, an early web proxy at Berkeley, "noticed rapid oscillations in queue lengths" because their balancers acted on stale load reports (Fox et al., 1997).

4Two choices

Here is the trick. For each request, the balancer picks two servers at random, compares their lines in the report, and sends the request to the shorter one, the way you might glance at two checkout lines and join the shorter. The setup is the same as before: twenty balancers and a load report every 500 ms. Switch between the three rules, and use slow motion to watch each request check its two servers (dashed lines) and pick one (solid line).

With two choices, the average comes back down to about 450 ms, less than half of what least loaded manages with twenty balancers.

Look at the bars under the servers. Under least loaded, a few servers get almost everything after each report. Under two choices, new requests spread out over most of the servers. That spread comes from the randomness. Every balancer still reads the same report, but each request compares a different random pair of servers, so the balancers no longer all reach the same answer. The server that looks emptiest only gets a request when it happens to be in that request's pair, which is a few times its fair share instead of all of it.

Is checking more servers better?

It's natural to guess that if checking two servers helps, checking three helps more, and checking all ten helps most. But we've already seen that least loaded (the equivalent of checking all ten) falls apart when balancers share an old report. So where is the sweet spot? The chart shows the average response time for each number of servers checked, with twenty balancers. Checking one server is random, at the left end, and checking all ten is least loaded, at the right end. Start at 500 ms reports, then try the other report ages.

With 500 ms reports, the best choice is two. Checking three is already worse, and checking all ten is no better than random. Now switch to live: with perfectly fresh information, checking more keeps helping, and the best choice is to check them all. In between, the sweet spot slides: about five servers at 100 ms, three at 250 ms, and two from 500 ms on.

Why would more information ever hurt? Each extra check gives a request more information, but it also makes it more likely that every balancer picks the same server. With fresh information that's fine. With a stale report, that agreement is what creates the herd. So there's a balance between picking the shortest line and picking a line nobody else is about to pick, and as the report ages, the balance tips toward fewer checks.

Two holds up across the whole range. The next section shows why: the first extra check is worth far more than all the others.

5But why two?

Let's go back to a single balancer with live information, so nothing goes stale. Picking at random averages about 1,000 ms. Checking every server averages about 190 ms. Checking just two averages about 300 ms: most of the way from no information to perfect information, from one extra look. Why is a single extra look worth so much?

Bad luck has to strike twice

Say 1 server in 10 has a long line right now. A request sent to a random server lands in one of those lines 1 time in 10. A request that checks two servers lands in one only if both of the servers it checked had long lines, since otherwise it takes the shorter. That happens 1 time in 10 × 10, or 1 in 100. One extra look turns a 1-in-10 risk into a 1-in-100 risk.

And it compounds

The same thing happens at every line length. For a line to grow to 3, a request had to find two servers that both already had at least 2. Lines of 2 were already fairly rare, so lines of 3 are much rarer, and lines of 4 rarer still. At each step up, the share of servers with a line that long is roughly squared, and squaring a fraction makes it smaller, fast: a tenth becomes a hundredth, then a ten-thousandth. Here is how many servers out of a million have a line at least a given length, at 90% busy:

With random routing, almost half of all servers have a line of 7 or more. With two choices, about two servers in a million do. Random routing trims the count by the same 10% at every step. Two choices squares it.

How long can a line get?

Squaring also explains the most famous form of this result. Take n servers and drop n requests onto them, one after another, with nothing finishing in between. Then look at the longest line. Here it is for clusters from 10 servers to 10 million:

With random routing, the longest line keeps growing as the cluster grows: about 5 at a thousand servers, about 9 at a million. With two choices it barely moves: 3 at a thousand, 4 at a million. That pattern holds in general. With two choices, you have to square the number of servers to make the longest line one request longer: a thousand servers to a million, a million to a trillion.

The share of servers with longer and longer lines goes roughly ½, ¼, 1/16, 1/256, 1/65,536: the number of digits roughly doubles at every step. Computer scientists write the length of the longest line as log log n, which is 5 or less for any cluster that has ever existed. With random routing it grows like log n / log log n, which keeps climbing. In Azar, Broder, Karlin and Upfal's own experiments with about 16 million servers, the longest random line was usually 10; with two choices, it was 4 in every run.

"This apparently minor change in the random allocation process results in an exponential decrease in the maximum occupancy per location." (Azar, Broder, Karlin & Upfal, 1994)

Why not three?

Three checks would cube instead of square, and the chart shows that it helps: the longest line drops from 4 to 3. But that is small next to the jump from one check to two. The first extra look changes how long lines shrink, from a little at each step to squaring at each step. Each look after that raises the power by one, to cubing and then to the fourth power, but by then lines are already disappearing so fast that each extra look saves only a step here and there. And each extra look also makes the balancers more likely to agree on the same server, which is what sets off a herd when their information is stale. Two gets almost all of the benefit, at the smallest possible cost.

"The gain from each ball having two choices is dramatic, but more choices prove much less significant: the law of diminishing returns appears remarkably strong in this scenario!" (Mitzenmacher, 1996)

The formulas behind these results show the same pattern far beyond any real cluster:

6Where this is today

The power of two random choices was worked out in the 1990s. Azar, Broder, Karlin and Upfal proved it for balls thrown into bins (1994), and Mitzenmacher (1996) and, independently, Vvedenskaya, Dobrushin and Karpelevich (1996) worked it out for servers with lines like the ones above. As early as 1986, Eager, Lazowska and Zahorjan had found by simulation that "extremely simple" policies using "very small amounts" of information did nearly as well as complicated ones (1986).

Today the idea is built into NGINX, HAProxy and Envoy, three of the most widely used load balancers. In 2024 Google described Prequal, the load balancer behind most of YouTube's serving stack: it checks a few random servers for each request and picks the best one, and it cut tail latency in half (Wydrowski et al., 2024).

Real systems raise harder questions:

• What does "busy" mean? A short line can still be slow: one request might take 5 ms and the next 5 seconds, and a server can slow down without its line getting any longer.
• Can we stop guessing? Every rule on this page predicts which server will be free soonest, but predictions can be wrong.
• What if servers aren't interchangeable? A server that already has what a request needs, like a cached copy of the data, can handle it far more cheaply, so the emptiest server isn't always the best one.
• What if the fix makes things worse? Retrying a slow request seems sensible, but retries add work at exactly the moment servers are struggling.

The lesson reaches well beyond load balancers. When many decision-makers act on the same information at the same moment, more information can make things worse. A little information plus a little randomness often does better.

Below is a sandbox with everything from this page. Or skip ahead to Part 2: The real world, where we take on the harder questions that real systems raise.

7Sandbox

Here is everything from this page in one place, plus a few things we haven't covered. Change the rule, the number of servers and balancers, how the balancers get their information, and what the requests look like, and watch what happens.

Some things to try:

• Stagger the reports. Set least loaded, twenty balancers, and a 500 ms report, then switch from one shared report to staggered reports. The herd mostly disappears, and least loaded becomes about as good as two choices.
• Stop counting. With a shared report, turn off "balancers count their own requests." Now every balancer keeps sending to the same server until the next report, and least loaded gets even worse than random.
• Mix in some greed. Use two choices with twenty balancers, and make a few requests greedy: they ignore the rule and go to whichever server the report says is least loaded. When only a few requests do this, they come out ahead. When more than about one in ten do, the greedy requests do worse than everyone else, and the whole cluster slows down (Mitzenmacher, 2000).
• Make some requests huge. Switch request sizes to "mostly small, a few huge." With random routing, a request stuck behind a huge one waits a long time, and the average nearly triples. Two choices and least loaded cope much better, because they see the line building and steer around it.
• Scale up. Go to 40 servers. With live information and one balancer, least loaded gets even better, because it has more servers to pick the emptiest from. With twenty balancers and a shared report, it is just as bad at 40 servers as at 10, while two choices stays at about 400 ms.