Catalog My learning Blog
Scalability Patterns: Load Balancing, Caching, Sharding · Phase 1 · Lesson 2 · 9 min read

Load Balancing Algorithms: Round Robin vs Least Conn

On this page
  1. Learning Objective
  2. Concept Explanation
  3. Worked Example: Why Power of Two Choices Beats a Global Best Scan
  4. Real-World Examples
  5. Review Questions & Answers

Learning Objective

Compare the common backend selection algorithms, round robin, weighted round robin, least connections, least response time, random, and power of two choices, in terms of what each one assumes about the workload, and predict which one will misbehave for a given traffic shape.

Concept Explanation

Every load balancing algorithm is an answer to one question: given a set of healthy backends, which one should receive this request? What separates the algorithms is the information each one uses and, more importantly, the assumption each one makes about the work. Round robin assumes every request costs roughly the same and every backend is roughly equally capable. Least connections assumes outstanding connection count is a good proxy for current load. Least response time assumes recent latency predicts near-future capacity. When the assumption holds, the algorithm works beautifully and the choice barely matters. When it does not hold, the algorithm actively concentrates load on exactly the backend least able to handle it.

Round robin is the default almost everywhere because it is stateless, trivially cheap, and provably even in request count. Its failure mode appears as soon as request cost varies: if one in fifty requests is an expensive report generation that takes four seconds while the rest are 5 millisecond key lookups, round robin will keep handing new work to a backend that is currently grinding through three concurrent reports, because it has no idea that backend is busy. Weighted round robin extends it by assigning each backend an integer weight, which is the right tool for a heterogeneous fleet where some machines genuinely have more cores, or for gradually shifting traffic to a new deployment. Weights fix capacity differences between backends but do nothing about cost differences between requests.

Least connections directly addresses the variable-cost problem by tracking how many requests are currently in flight to each backend and sending the next request to the smallest count. This is self-correcting in a way round robin is not: a backend stuck on slow work accumulates outstanding requests and naturally stops receiving new ones. Its weakness is the flip side of the same mechanism. A backend that is failing fast, returning a 500 in two milliseconds, has almost no outstanding connections and therefore looks like the least loaded machine in the fleet, so least connections will enthusiastically route the entire traffic stream into the one broken server. This failure mode is common enough to have a name, the black hole or the death spiral, and it is why least connections must always be paired with health checking and error-rate-aware ejection.

Least response time, sometimes called least time, ranks backends by a blend of outstanding requests and observed recent latency. It is more responsive to real conditions than either simpler algorithm, but it requires the balancer to maintain per-backend latency statistics, and it is susceptible to herding: when one backend reports a momentarily good latency, every balancer instance observing that same signal simultaneously sends it traffic, overwhelming it, after which its latency spikes and every balancer simultaneously steers away. With many independent balancer instances all reacting to the same lagging signal, the fleet can oscillate instead of converging.

Power of two choices, often written P2C, is the algorithm that quietly solves the herding problem and is now the default in several modern proxies. Instead of scanning all backends for the single best one, the balancer picks two at random and sends the request to whichever of those two has fewer outstanding requests. The theoretical result, from the balanced allocations literature, is that this reduces the expected maximum load from something growing like log n over log log n, which is what pure random gives, down to log log n, which is a dramatic improvement for a negligible amount of extra work. Crucially, because each balancer instance samples a different random pair, independent balancers do not all pile onto the same apparently-best backend, so the herding oscillation of a global least-response-time scan simply does not occur.

AlgorithmInformation UsedAssumption That Must HoldCharacteristic Failure
Round robinA counter onlyAll requests cost about the same; all backends are equally capableConcentrates slow work on an already-busy backend
Weighted round robinA counter plus static per-backend weightsRelative capacity is known ahead of time and stableWeights drift out of date as instance types or workloads change
Least connectionsOutstanding request count per backendOutstanding count is a good proxy for loadA fast-failing backend looks idle and attracts all traffic
Least response timeOutstanding count plus recent latencyRecent latency predicts near-future capacityIndependent balancers herd onto the same backend and oscillate
RandomA random numberNothing; it is unbiased by constructionMaximum load grows noticeably faster than the average
Power of two choicesOutstanding count for two random backendsSampling two is enough to avoid the worst backendSlightly worse than a perfect global scan, which is the point

Worked Example: Why Power of Two Choices Beats a Global Best Scan

The counterintuitive part of P2C is that sampling only two backends performs better in a real fleet than checking all of them. The reason is that a global scan is only better when the load information is fresh and there is exactly one balancer. Add staleness and concurrency, which every real system has, and the global scan turns into a coordinated stampede.

Code
# Three balancer instances, ten backends, load data refreshed every 500ms.

# --- Global "least outstanding" scan ---
# t=0.00  backend-3 finishes a batch; outstanding drops to 0.
# t=0.10  all three balancers read the same stats snapshot.
#         All three see backend-3 as the clear best.
# t=0.10  all three send their next N requests to backend-3.
# t=0.30  backend-3 is now the most loaded machine in the fleet.
# t=0.60  stats refresh; all three balancers steer away simultaneously.
#         backend-3 goes idle again. Oscillation, not convergence.

# --- Power of two choices ---
pick_backend(backends):
    a = random_choice(backends)
    b = random_choice(backends)   # may equal a; harmless
    return a if outstanding[a] <= outstanding[b] else b

# t=0.10  balancer-1 samples {backend-3, backend-7} -> backend-3
#         balancer-2 samples {backend-1, backend-9} -> backend-9
#         balancer-3 samples {backend-3, backend-2} -> backend-3
# backend-3 gets some of the new load, not all of it. No synchronized
# pile-on is possible because each balancer looks at a different pair.

# Expected maximum load with n requests over n backends:
#   pure random          ~ log(n) / log(log(n))
#   two random choices   ~ log(log(n))
# Sampling a third choice improves this only marginally, which is why
# production implementations stop at two.
Four backend pools under the same uneven workload, showing round robin concentrating slow requests, least connections routing into a fast-failing backend, a global least-time scan oscillating as multiple balancers herd, and power of two choices spreading load smoothly by sampling independent random pairs.
Four backend pools under the same uneven workload, showing round robin concentrating slow requests, least connections routing into a fast-failing backend, a global least-time scan oscillating as multiple balancers herd, and power of two choices spreading load smoothly by sampling independent random pairs.

Real-World Examples

  • Netflix documented in 2018 that its client-side load balancer moved away from a round-robin-style default to a choice-of-two approach combined with per-server scoring on outstanding requests and observed failures, after finding that its previous scheme routed traffic into servers that were slow or failing rather than away from them. The published result was a substantial reduction in load-related errors and a much flatter distribution of per-server utilization during partial outages, which is the least-connections black hole problem being solved in production.
  • NGINX ships round robin as its default upstream method and documents least_conn, least_time, and consistent hashing as explicit alternatives, while Envoy, the proxy underpinning many service meshes, uses weighted least request implemented as power of two choices as its default policy and documents the full-scan variant as a special case only used when all weights are equal and the pool is small. The divergence in defaults between a traditional reverse proxy and a mesh-era proxy tracks exactly the shift from one balancer instance to hundreds of independent sidecars, where herding becomes the dominant concern.
Common PitfallLeast connections is the most commonly recommended upgrade from round robin, and it is also the algorithm most likely to route your entire traffic stream into a single broken backend, because a server failing in two milliseconds has the fewest outstanding requests in the fleet. Never deploy a load-aware algorithm without pairing it with health checks and error-rate-based ejection, or you will have built a mechanism that actively seeks out your worst server.

Review Questions & Answers

Weights describe relative backend capacity, not relative request cost, and they are static. Round robin with weights still hands out requests in a fixed pattern that is blind to what any backend is currently doing, so a backend that happens to receive three consecutive report-generation requests will queue them up while its peers sit idle handling cached lookups. No static weight can encode "this particular backend is busy right now," which is precisely the information needed. The problem requires an algorithm that observes current in-flight work, such as least connections or power of two choices, or it requires separating expensive and cheap requests into different backend pools so that round robin operates over a homogeneous workload again.

A backend that has begun failing immediately, returning errors in microseconds rather than doing real work, drains its outstanding request count to near zero. Least connections interprets a low outstanding count as low load, so it preferentially selects that backend, which then fails those requests instantly, keeping its count low and making it even more attractive. The feedback loop is self-reinforcing, so a partial failure becomes a total one. The first mechanism that prevents it is active health checking, which probes the backend independently and removes it from the pool on failure regardless of what its connection count looks like. The second is outlier detection, tracking the error rate per backend and ejecting any backend whose error rate diverges from the fleet, which catches the case where the health check endpoint is trivially still returning 200 while real requests fail.

The global scan assumes its load information is current and that it is the only entity acting on it. Neither holds in a real system: per-backend statistics are refreshed on an interval so they are always somewhat stale, and there are typically many balancer instances, or many sidecar proxies, all reading substantially the same view. When they all identify the same least-loaded backend simultaneously, they all send it traffic simultaneously, converting the best backend into the worst one before the next stats refresh reveals what happened. P2C breaks the correlation because each decision samples an independently chosen random pair, so no synchronized pile-on can form even when the underlying load data is stale.

When the workload is genuinely homogeneous in cost and the backends are genuinely homogeneous in capacity, round robin is optimal in the sense that it is perfectly even, costs nothing to compute, requires no shared state, and has no feedback loop that can misfire. A fleet of identical instances serving a single cheap endpoint, a static asset tier, or a stateless transformation service, will not benefit measurably from anything smarter. Round robin also has the underrated property of being completely predictable, which makes capacity math and load test interpretation simple. Reaching for a load-aware algorithm adds state, adds a failure mode, and should be justified by an actual observed imbalance rather than adopted on principle.