Cloud Parts

Load-balancing algorithms

The rule a load balancer uses to pick which healthy server gets the next request or connection.

Live model
What you’re watchingRound robin hands requests to the servers strictly in turn. Server 3 is a smaller machine and answers more slowly, but it still gets every third request; when server 2 fails its health check, the rotation simply skips it.

How it works

Every load balancer has to answer one question many thousands of times a second: of the healthy servers, which one gets this request? **Round robin** takes them in turn: 1, 2, 3, 1, 2, 3. It needs no information about the servers and is the default almost everywhere, but it assumes every server is equally fast and every request equally heavy. **Weighted round robin** gives bigger servers more turns. **Least connections** (or **least outstanding requests**) sends the request to the server with the fewest in flight, so a server stuck on slow requests gets fewer new ones. Counting every server on every pick is costly at scale, and many balancers acting on the same stale counts can all pile onto the same “least busy” server, so **power of two choices** picks two servers at random and sends the request to the less busy of the two, which is nearly as good as checking them all. **Hashing** turns something about the request (client IP, a header, a URL, the TCP connection) into a number that picks the server, so the same key keeps landing on the same server: good for sticky sessions and caches. Plain hash mod N reshuffles almost every key when a server is added or removed; **consistent hashing** (a ring hash, or Google’s Maglev table) moves only about 1/N of them. Finally, **slow start** ramps a newly healthy server from a trickle up to its full share, so a cold cache or a JIT that hasn’t warmed up isn’t flooded the moment it joins.

Think of it as

Supermarket checkouts. Round robin is a staff member sending each shopper to the next till in order, even if that till has a trainee. Least connections is sending them to the shortest queue. Power of two choices is glancing at two random tills and picking the shorter. Hashing is “surnames A to F use till 1”, so the same family always meets the same cashier.

Reach for it when

  • Round robin: identical servers and short, similar requests (a typical stateless web API)
  • Least connections or outstanding requests: request times vary a lot, or connections are long-lived (WebSockets, database sessions)
  • Hashing: each server keeps state worth reusing, such as a local cache, a session or a shard of data
  • Slow start: servers need warm-up time (JIT compilation, empty caches) after scaling out or a deploy

Think twice when

  • Round robin when servers differ in size or a few requests are much heavier; one server falls behind while it still gets its full share
  • Hashing on client IP when many users share one address (offices, mobile carriers, NAT); one server gets them all
  • Plain (non-consistent) hashing in front of caches; every scale event empties most of them

A real example

An image API runs on three servers, but one of them is a smaller instance. Under round robin each gets a third of the requests, and the small one’s p99 latency climbs from 80 ms to 900 ms. Switching the target group to least outstanding requests sends it fewer requests while it is busy, and p99 drops back. Thumbnails are then served through a cache tier keyed by hash $request_uri consistent, so adding a fourth cache node moves only about a quarter of the URLs instead of nearly all of them.

What each provider calls it

AWS
Elastic Load Balancing: ALB routing algorithms (round robin, least outstanding requests, weighted random), NLB flow hash
Google Cloud
Cloud Load Balancing locality policies: ROUND_ROBIN, LEAST_REQUEST, RING_HASH, RANDOM, MAGLEV, WEIGHTED_ROUND_ROBIN
Azure
Azure Load Balancer distribution modes (five-tuple hash, source IP affinity); Application Gateway (round robin)
Open source & others
NGINX (round robin, least_conn, ip_hash, hash consistent, random two), HAProxy (roundrobin, leastconn, source, uri, random), Envoy (round robin, least request, ring hash, Maglev, random)

Hashing: the same key, the same server#

Each colour is a different key, such as a user ID or a URL. The balancer hashes the key to pick a server, so a key always lands in the same place and that server’s cache stays warm for it.

Live model
What you’re watchingRequests are coloured by key. Hashing sends every request with the same key to the same server, whatever order they arrive in.

What each balancer offers#

From each product’s documentation, checked 2026-10-06.

BalancerDefaultAlso offersSlow start
AWS Application Load BalancerRound robinLeast outstanding requests; weighted random, which can use Automatic Target Weights to steer traffic away from failing targetsYes, linear ramp, with round robin only
AWS Network Load BalancerFlow hash on protocol, source and destination IP and port (plus TCP sequence number); each connection stays on one target
Google Cloud Application and proxy Network Load BalancersROUND_ROBIN (MAGLEV when session affinity is set)LEAST_REQUEST (two random hosts, fewer active requests), RING_HASH, RANDOM, MAGLEV, WEIGHTED_ROUND_ROBIN from custom metrics
Google Cloud passthrough Network Load BalancersMAGLEVWEIGHTED_MAGLEV (regional external)
Azure Load BalancerFive-tuple hash (source and destination IP and port, protocol)Source IP affinity: two-tuple or three-tuple hash
Azure Application GatewayRound robin across healthy servers
NGINX (open source)Weighted round robinleast_conn, ip_hash, hash (optionally consistent), random with “two” choices, least_time (open source since 1.31.0)Only in the commercial NGINX Plus (slow_start)
HAProxyroundrobin (weighted, dynamic)static-rr, leastconn, first, source, uri, url_param, hdr, hash (optionally consistent), random with N draws (default 2)Yes (slowstart), linear from 0 to 100%
EnvoyWeighted round robinWeighted least request (power of two choices by default), ring hash, Maglev, random, client-side weighted round robin from load reportsYes, for round robin, least request and client-side weighted round robin
  • An empty cell means we found no such option in the documentation we checked.

In code · nginx

upstream api {
    least_conn;                        # fewest active connections wins
    server 10.0.1.11:8080 weight=2;    # bigger box, counts double
    server 10.0.1.12:8080;
    server 10.0.1.13:8080;
}

upstream thumbs {
    hash $request_uri consistent;      # same URL, same cache node (ketama)
    server 10.0.2.21:8080;
    server 10.0.2.22:8080;
    server 10.0.2.23:8080;
}

server {
    listen 80;
    location /api/    { proxy_pass http://api; }
    location /thumbs/ { proxy_pass http://thumbs; }
}

Often confused with

Load balancersAutoscalingKey-value storesService discovery & meshDNS
Where it came from1995–2023

The first way to spread web traffic was round-robin DNS: list several addresses under one name and rotate their order, as RFC 1794 described in 1995. It knew nothing about load or health. Dedicated balancers that could see every connection brought smarter schedulers. The Linux Virtual Server project, started in 1998, shipped round robin, weighted round robin, least connections, weighted least connections, and source and destination hashing, and its documentation already warned that round robin can leave servers unevenly loaded when requests vary.

Two pieces of theory from the late 1990s shaped what came next. In 1997 David Karger, Tom Leighton, Daniel Lewin and colleagues published consistent hashing, to spread web caching across a changing set of servers so that adding or removing one moved only a small share of the keys. Michael Mitzenmacher’s analysis of the “supermarket model”, published in 2001, showed that letting each request look at just two random servers and join the shorter queue gives an exponential improvement over picking one at random, while a third choice adds only a constant factor.

Both ideas are now in mainstream products. Google’s Maglev, serving traffic since 2008 and described in 2016, uses its own consistent-hashing lookup table that is fast to build and to query. Envoy, HAProxy and NGINX all offer power-of-two-choices variants, and Google Cloud’s LEAST_REQUEST uses it too. AWS added least outstanding requests to the ALB in 2019 and weighted random with Automatic Target Weights, which sends less traffic to targets that are returning errors, in 2023.

Why it’s built this way

Round robin as the default
It needs no feedback from the servers and spreads load evenly when servers and requests are alike, which is the common case for stateless web tiers. ALB, Google Cloud, NGINX, HAProxy and Envoy all default to it.
Two random choices instead of a full scan
Checking every server on every request costs O(n), and many balancers working from the same slightly stale counts tend to herd onto one server. Mitzenmacher showed two random picks get most of the benefit; Envoy credits his result for its O(1) least-request balancer.
Consistent hashing instead of hash mod N
With mod N, changing N remaps almost every key, which empties caches and breaks affinity. Placing servers on a ring (or in Maglev’s table) means adding or removing one of N servers moves only about 1/N of the keys.
Ramp new servers up slowly
A server that just passed its health check may still have cold caches or unoptimised code. ALB, HAProxy and Envoy raise its share of traffic gradually over a configured period instead of giving it a full share at once.

Timeline

  1. 1995

    RFC 1794 describes rotating DNS answers to spread load

  2. 1997

    Karger and colleagues publish consistent hashing (STOC)

  3. 1998

    Linux Virtual Server starts, with round robin, least-connection and hashing schedulers

  4. 2001

    Mitzenmacher publishes “The Power of Two Choices in Randomized Load Balancing”

  5. 2016

    Google publishes the Maglev paper, with its consistent-hashing table

  6. 2019

    AWS ALB adds least outstanding requests

  7. 2023

    AWS ALB adds weighted random with Automatic Target Weights

Sources15

Improve this page on GitHub