System Design HLD-04.03
Load balancing algorithms
Round robin, weighted, least connections, hashing and power of two choices: how each picks a server, and which ones survive slow or uneven servers.
The big idea
A load balancer makes one tiny decision millions of times: which server gets this request? The simplest answer, take turns, works beautifully when every server is identical and every request costs the same. Real fleets are not like that. Some servers are bigger, some are slowed by a noisy neighbor or a garbage collection pause, and some requests take a thousand times longer than others. An algorithm that ignores this keeps sending work to a server that is already drowning, and the users unlucky enough to land there see terrible latency.
The algorithms differ in what they know. Some know nothing and rotate blindly; some know each server's configured size; some watch how much work each server has in progress right now. The surprise is how little knowledge you need: picking the less busy of just two random servers gets almost all the benefit of checking every server.
Think of supermarket checkouts. Taking turns sends customers to a lane even if its cashier is slow and the queue is long. Glancing at two lanes and joining the shorter one is almost as good as surveying all twenty.
How it works
Step 1: The algorithms
- Round robin: servers in turn, A, B, C, A, B, C. No state needed beyond a counter.
- Weighted round robin: as above, but a server with weight 2 gets twice as many turns. Weights match known capacity, for example machine size.
- Random: pick any server. Statistically even over time, uneven in the short run.
- Least connections (least outstanding requests): send to the server with the fewest requests in progress. It adapts automatically to slow servers and heavy requests, but needs an accurate view of every server's load.
- Least response time: weight by recent latency as well as load.
- Hashing on client IP, user id or URL: the same key always goes to the same server, which helps when servers cache data per key. Use consistent hashing ( Consistent hashing ) so adding a server moves only a fraction of keys.
- Power of two choices: pick two servers at random and send to the one with fewer requests in progress.
Step 2: Why two random choices are enough
Least connections needs the true load of every server at every decision. With many load balancers, each sees only its own traffic, so their views are stale and they can all pile onto the same "least loaded" server at once, a herdingMany independent clients making the same choice at the same moment because they all saw the same stale signal, overloading the target. problem. Pure random avoids herding but ignores load. Power of two choicesPick two servers at random and send the request to the less loaded of the two. sits in between, and the effect is dramatic:
import random
def max_load(servers, requests, choices, seed=7):
rnd = random.Random(seed)
load = [0] * servers
for _ in range(requests):
picks = [rnd.randrange(servers) for _ in range(choices)]
best = min(picks, key=lambda s: load[s]) # least loaded of the sampled servers
load[best] += 1
return max(load), requests / servers
for choices, name in [(1, "random (1 choice)"), (2, "power of two choices"), (3, "three choices")]:
worst, avg = max_load(servers=1000, requests=100_000, choices=choices)
print(f"{name:22} busiest server: {worst} requests (average {avg:.0f})")Output
random (1 choice) busiest server: 138 requests (average 100)
power of two choices busiest server: 102 requests (average 100)
three choices busiest server: 102 requests (average 100) With 100,000 requests over 1,000 servers, pure random leaves the busiest server 38 percent above average. Looking at just two random servers cuts that to 2 percent, and a third choice adds almost nothing. Mathematically, the worst-case imbalance drops from roughly to : an exponential improvement from one extra sample. That is why modern proxies such as Envoy and NGINX offer it.
Try it
Try this:
- With one server 4x slower and 80 percent load, look at round robin. The slow server gets a quarter of the traffic but can only handle a fraction of it, so its queue grows without limit and the p99 explodes.
- Switch to least connections and power of two choices. Both notice the slow server's queue and route around it.
- Choose mixed sizes. Weighted round robin, which knows the sizes, does well. Now imagine one server slows down unexpectedly: the weights would be wrong, while the load-aware algorithms adapt.
- Set all servers equal and load to 50 percent. Every algorithm looks fine: differences only show under stress.
Going deeper
Slow start for new servers
A freshly started server has zero connections, so least-connections sends it a flood of traffic before its caches and code are warm. Proxies offer slow start: ramp a new server's weight up over 30 to 60 seconds.
Measure the right thing
Connection counts are a proxy for load. With HTTP/2 and gRPC, one connection may carry hundreds of requests, so balance on outstanding requests instead. Some systems go further and have servers report their own utilization or queue time.
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Round robin | Identical servers and uniform requests; zero state | Slow, overloaded or differently sized servers |
| Weighted round robin | Known, stable differences in server size | Unexpected slowdowns: weights do not adapt |
| Least connections | Variable request costs and occasional slow servers, with one balancer | Many independent balancers with stale views, which can herd |
| Power of two choices | Large fleets and many balancers: near-optimal with almost no coordination | Very small pools where checking every server is cheap anyway |
| Hashing (consistent) | Cache locality and sticky routing by key | Even load when some keys are much hotter than others |
Common mistakes
- Using round robin across servers of different sizes or health, then blaming the slow server.
- Hashing on client IP when many users share one IP behind a corporate proxy, sending them all to one server.
- Counting connections instead of requests for HTTP/2 and gRPC traffic.
- Sending full traffic to cold servers the instant they join.
Check yourself
-
One of four servers becomes four times slower. Which algorithm keeps sending it a full quarter of the traffic?
Show answer
C. Round robin Round robin ignores load, so the slow server's queue keeps growing.
-
Why can least connections misbehave with many independent load balancers?
Show answer
B. Each balancer's view is stale, so they can all send to the same server at once Stale, shared signals make balancers herd onto the same apparently idle server.
-
What does power of two choices do?
Show answer
B. Picks two random servers and sends to the less loaded one Two random samples and a comparison give most of the benefit of least-loaded with little coordination.
-
When is hashing on a user id useful?
Show answer
B. When servers cache per-user data, so the same user should hit the same server Hashing keeps a key on one server for cache locality; consistent hashing limits reshuffling.
Recap
- Round robin and random ignore load; weighted round robin uses fixed capacity weights.
- Least connections adapts to slow servers and heavy requests but needs a fresh view of load.
- Power of two choices gets near-optimal balance from just two random samples.
- Hashing gives stickiness and cache locality; use consistent hashing.
- Differences only appear under load and with uneven servers, which is exactly when they matter.
Next up
- Crack the system design round learning path