Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Load Balancing and Traffic Management

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.

Intermediate 12 min Last reviewed

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.
The same requests under round robin and least connections Left: round robin sends requests to servers A, B and C in turn, so server C, which is slow, builds a long queue drawn in red. Right: least connections sends new requests to whichever server has the fewest in progress, so the slow server C gets fewer requests and the queues stay short. Round robin Least connections LB A [2] fast B [2] fast C [9] slow, queue growing LB A [3] fast B [3] fast C [2] slow, gets less Figure 1. Server C is slow. Round robin keeps feeding it its share and its queue grows (red). Least connections notices C is busy and sends new requests elsewhere, so all queues stay short.

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:

two-choices.pyruns with python3 (standard library)
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

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Try this:

  1. 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.
  2. Switch to least connections and power of two choices. Both notice the slow server's queue and route around it.
  3. 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.
  4. 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

OptionWins whenLoses 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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy

Next up