Load balancing: why two random choices beat round-robin

What this question is really about

The ladder looks like this:

1. "What balancing methods do you know?" — a warm-up in enumeration.
2. "What is wrong with round-robin?" — the substance starts here, and the usual answer "nothing, it is even" is already wrong.
3. "What is least-connections and why is it not always used?" — a question about the price of knowing.
4. "What is the power of two choices?" — the question the topic exists for.
5. "Why did our load test show no difference?" — a trap about uniform requests.
6. "Where does balancing not help at all?" — a question about the limits.

This lesson rests on a model rather than on a measurement: balancing rules have no common standard, only the documentation of particular products. The model answers not "how many milliseconds for you" but "what the difference depends on".

Base: who picks the server, and by what rule

When there are more requests than one machine can take, several identical servers are put up with a balancer in front of them. Its whole job fits in one sentence: a new request has arrived — decide which of the servers will handle it. It does nothing else: it does not make processing faster and does not reduce the amount of work, it only spreads that work across machines.

Three rules for making that decision are usually named, and all three can be explained in ordinary words.

1. In turn. The first request goes to the first server, the second to the second, and so on down the list; at the end of the list you start again. Nothing has to be known about the servers — it is enough to remember who got the last request.
2. At random. Toss a coin on every request. Here you do not even have to remember the previous choice.
3. To the least loaded one. Look at the servers and give the request to whichever is freer than the rest right now. Of the three, only this one needs knowledge of the servers' state.

The third sounds the most sensible — and that is where the first difficulty hides: what does "least loaded" mean? The phrase has no single meaning. Busyness is measured by the number of requests a server is handling right now; by the number of open connections; by the length of the queue in front of it; by a smoothed response latency; by processor utilisation. Those are different quantities, and a rule that picks by one of them is a different rule from one that picks by another.

There is a fourth rule too, the one this topic exists for: ask two random servers and give the request to the less loaded of the two. It resembles the third but does not look at everyone.

And here is the question this lesson is about: if the first rule gives everyone an equal share, what is wrong with it? The short answer: equal by number of requests, not by work. While requests cost the same, the two meanings of "equal" coincide; as soon as one request costs more than another, the server that got the expensive one is busy for a long time — and its turn still comes round, because the rule knows nothing about it being busy.

That is already enough to answer the basic interview question. Everything below is about how large that difference is, how much has to be known about the servers to remove it, and why a load test usually cannot see it.

Mechanism 1: even by count is not even by work

Now the same thing in numbers. Round-robin hands out requests in turn, and by count the balancing is perfect: sixteen servers get exactly one sixteenth of the stream each.

The problem is that requests are not alike. Here is what happens when 90 % of them cost 10 ms and the other 10 % cost 100 ms:

1. THE SAME REQUESTS, FOUR RULES: TIME SPENT WAITING IN A QUEUE
---------------------------------------------------------------
           rule   mean, ms   p50, ms   p99, ms   worst, ms
    round-robin      110.3      69.6     582.4      1041.2
         random      161.2     101.8     787.7      1504.8
     least-work        4.9       0.0      42.9        90.6
    two-choices       24.7      10.7     123.6       287.2

The same requests, the same servers. Only the rule differs — and the tail moves by a factor, not by a percent.

Why round-robin loses. It knows only who got the last request. What that work cost, and whether the server is busy now, it does not know. The server that received a hundred-millisecond job gets the next request sixteen steps later, whether it is busy or idle. While it is busy, its queue grows and its neighbours stand empty.

And why random placement is worse still — 787.7 against 582.4. Randomness does not guarantee evenness over a short stretch: some server gets several long requests in a row simply because the coin fell that way. Round-robin is at least protected from that.

Note the p50 column in the least-work row: zero. At a utilisation of 0.85 with sixteen servers there is usually an idle one — and a rule that can find it finds it. The other three do not look for it: two never inspect a server at all, and two-choices looks for an idle one among two at random.

And a word about the name. In the model least-work picks the server that frees up soonest — that is, by the exact remaining work, including the length of the request already running. A real least-connections counts connections and cannot tell a connection carrying a ten-millisecond request from one carrying a hundred-millisecond one: it is blind to exactly the spread this whole lesson rests on. So 42.9 ms is the ceiling of a rule that knows everything, not the result of least-connections.

Mechanism 2: the price of knowing

The second level is about what really separates the rules. Not "cleverness" but how much has to be known to make a decision.

2. HOW MUCH EACH RULE NEEDS TO KNOW
-----------------------------------
           rule   servers inspected   p99, ms   p99 improvement
    round-robin                   0     582.4              1.0x
         random                   0     787.7              0.7x
     least-work                  16      42.9             13.6x
    two-choices                   2     123.6              4.7x

Read the two columns together. The first two rules know nothing about the servers and perform worst. least-work knows about all sixteen and performs best. And two-choices knows about two — and takes a large part of the gain.

Why picking two works. Of the two, the rule takes the one that frees up sooner, so a request waits as long as the less loaded of them would make it wait. It waits long only when both are loaded. That follows from the rule itself rather than from a separate measurement: the model computes no probabilities.

And why that matters more than it sounds. To pick the best of a thousand, you have to know the state of a thousand, hold it somewhere and keep it fresh; two probes do not care about the fleet size. The model does not count that price — by assumption, balancing in it is free — but it follows from how the rules are stated: sixteen probes against two.

And the other half of that price, the half that gets forgotten first. In a distributed system the servers' state does not lie ready in front of the balancer. It has to be collected: the servers are polled over the network, or they report about themselves — and either way that takes time. So by the moment of the decision the picture describes not "now" but "some time ago": the bigger the fleet, the more data there is to collect and the older the part of the picture that was collected first. Knowing the state of every server is not merely expensive — it also goes stale while it is being collected, and that is a property of being distributed rather than of a poor implementation. A rule with full knowledge pays twice: for the volume of the knowledge and for its age. The second is not cured by making the polling cheaper.

Hence the rule worth answering with: picking two is not "almost least-connections" but a different trade. It gives up part of the gain so that the cost of a decision stops depending on the size of the system.

Mechanism 3: why a load test sees no difference

The third level explains where round-robin's reputation comes from. Remove one thing from the model — the spread in service time:

3. WITH UNIFORM REQUESTS, ROUND-ROBIN TIES WITH THE BEST RULE
-------------------------------------------------------------
  round-robin: p99 with even service, ms       16.1
  random: p99 with even service, ms            272.7
  least-work: p99 with even service, ms        16.1
  two-choices: p99 with even service, ms       42.3

Round-robin matched inspecting all sixteen exactly: 16.1 against 16.1. That is not a coincidence: when every request costs the same, "pick the one that frees up first" is going round the circle. Servers free up in the order they were given work, so least-work keeps pointing at the server whose turn it was anyway.

Random placement stayed bad, though — 272.7. It does not need a spread of request sizes to miss: it misses on its own.

And note two-choices: 42.3, worse than round-robin. Two random probes cannot beat a guaranteed sweep when there is nothing to choose between.

Hence the boundary the rule should be written from. Asking two random servers wins not "in general" but where the current load of the servers carries useful information — that is, where the servers really are busy to different degrees at the moment of the decision. Remove the spread in service time and there is nothing left to report: the rule that compares two at random loses to the rule that simply goes round everyone in turn, and knowing the state of all of them buys nothing over that sweep either. That is the whole of the third block: 42.3 for asking two against 16.1 for round-robin and exactly the same 16.1 for inspecting everyone. So the correct statement is not "picking two beats round-robin" but "picking two wins where the servers' load differs".

And hence a point worth keeping in mind at every load test: a measurement on uniform requests cannot show round-robin's weakness — on them it ties with the rule that knows every server's state. If your test sends the same request in a loop, it will show that round-robin is no worse — and it will be right about that test.

Real load is almost never uniform: a request for one record and a request for a year's report go into the same handler.

Deeper: what the model leaves out

The last level is about the limits of the model itself, and they are worth naming yourself.

The servers in the model are identical. A real fleet is not: different hardware generations, different neighbours on a host, differently warmed caches. The model does not test that, but the rule says what to expect: round-robin hands out evenly whether or not the machines are equal.

The decision is taken once. The balancer in the model never revises a choice and cannot take a request back. Real balancers sometimes can — sending a copy of a request to a second server when the first stays silent too long, for instance.

No failures and no retries. A server in the model does not fall over and a client does not retry. Both add load exactly when there is already too much of it; that is the subject of the lesson on retries and jitter.

Balancing itself is free. Inspecting two servers costs nothing in the model. In a real system the state has to come from somewhere, and that knowledge has a delay: the balancer acts on a picture that is already out of date.

The last one is not a detail but the reason a rule with full knowledge does not deliver that 13.6x in reality: a real balancer picks by yesterday's picture, and by a proxy at that — a connection count or a rolling average of response time rather than the exact moment of freeing up that exists only in the model.

How to answer in an interview

Short answer: round-robin hands out an even number of requests rather than an even amount of work, so it loses as soon as requests are not alike. Asking two random servers takes a large part of the gain of asking all of them, and its price does not grow with the fleet. Model: a p99 wait of 582.4 ms for round-robin, 123.6 for two choices and 42.9 for inspecting every server.

That is enough for a correct answer. What follows is what you add when the interviewer digs.

If the interviewer digs deeper

Three things separate a good answer. First, you say the rules differ only on a non-uniform workload, and offer your own counter-example: with identical requests round-robin tied with the best rule while asking two lost to it — 42.3 against 16.1. Second, you name the price of full inspection concretely rather than as "complexity": every server's state has to be known, that knowledge grows with the fleet and goes stale while it is being collected, and least-connections on top of that counts connections rather than work — and it is worth saying straight away that "least loaded" is measured in several different ways: requests in flight, open connections, queue length, smoothed latency, processor utilisation. Third, you mention that random placement is worse than round-robin rather than better — which is a test of whether you thought about it or repeated it.

What not to say: "we switched to least-connections and it improved by so many percent". Without describing the spread of request sizes that number means nothing — on a uniform workload there would have been no improvement at all.

Next they ask

Common misconceptions

Practice

Two exercises. Answer first, then check against the real output: in both, the correct answer is what the model script prints.

print(inspected["round-robin"])
print(inspected["least-work"])
print(inspected["two-choices"])

0
16
2

1
16
2

0
1
2

16
16
2

Knowledge check