5.2 Scheduling Algorithms: least_conn, hash, ip_hash, random

Intermediate

What you will learn

1. least_conn — load-aware routing, proven live with a slow peer.

2. hash — deterministic placement, the cache-affinity algorithm, and what consistent actually buys.

3. ip_hash — the legacy session-persistence tool and its honest limits.

4. random (including random two least_conn) — the cloud-native default and why "power of two choices" is genuinely good.

5. The selection table: one line per workload shape.

1. least_conn — route around the busy

upstream pool-lc {
    least_conn;
    server 127.0.0.1:9004;      # the SLOW backend (2s per request)
    server 127.0.0.1:9001;
}

The rule: pick the peer with the fewest active requests (ties broken by round-robin). Round robin would happily hand three concurrent requests to three peers regardless that one of them takes two seconds each; least_conn notices who's actually busy.

The proof is a race — one slow request in flight, then a fast one fired 0.4 s later:

$ curl -s …/lc/slow?delay=3 | jq -r .server &     # occupies a peer
$ sleep 0.4
$ curl -s …/lc/fast | jq -r .server                # 0.4s later…
b-node-1                                           # the idle peer — 0 active wins

The slow request was serving on the first-listed peer (9004 — idle at selection time); the fast request saw "9004 has 1 active, 9001 has 0" and chose 9001. One honest caveat: with a two-peer pool this single shot also matches round robin’s rotation — the discriminator is the next request. Fire another /lc/fast while the slow one still runs: least_conn lands on the idle peer again, while round robin would alternate onto the busy one. Two requests, one still in flight — that is the whole algorithm, visible.

2. hash — deterministic placement

upstream pool-hash {
    hash $request_uri consistent;
    server 127.0.0.1:9001;
    server 127.0.0.1:9002;
    server 127.0.0.1:9003;
}

hash <key> maps the key onto the peer list deterministically: same key → same peer, every time, from every worker. Two assertions:

$ for i in 1 2 3 4 5; do curl -s …/hash/same-uri | jq -r .server; done | sort -u
b-node-2                     # one line: 5/5 identical

$ for u in a b c d e f g h; do curl -s …/hash/$u | jq -r .server; done | sort -u | wc -l
3                            # distinct URIs spread across all 3 peers

Two superpowers follow immediately:

Cache affinity. Point hash $request_uri at a tier of caching proxies and every copy of a URL lives on exactly one node — maximal hit ratio for a given total memory (this is how sharded CDNs are routed). Same trick with $cookie_user for per-user affinity.

The consistent modifier. Plain hash is modulo-N: change the peer count and every key remaps (cache apocalypse — N−1/N of your entries miss). Ketama consistent hashing remaps only ~1/N of keys: add a 4th peer to a 3-peer pool and ~75 % of keys keep their home. The example pools use consistent — and testing stability across your own peer-adding experiments (add a 4th server line, reload, re-hash the same URIs) is the exercise.

3. ip_hash — the legacy stickiness tool

upstream pool-ih {
    ip_hash;
    server 127.0.0.1:9001;
    server 127.0.0.1:9002;
    server 127.0.0.1:9003;
}

ip_hash is hash $remote_addr with 1990s ergonomics: the client IP (/24-collapsed for IPv4 — a whole office is "one client") decides the peer, forever. The output below demonstrates the property and, honestly, its weakness:

$ curl -s -H 'Host: lb.example.test' http://127.0.0.1:8500/ih/x | jq -r .server
b-node-3
$ curl -s --interface 127.0.0.2 … http://127.0.0.1:8500/ih/x | jq -r .server
b-node-3        # a DIFFERENT source IP — same peer anyway!

Stickiness is per-IP (both clients are stable), but different IPs may collide on the same peer — hash placement is not a promise of separation. That's fine (it's a placement function, not a router), but it kills the "ip_hash spreads my users evenly" assumption in the field.

The modern verdict, learned once and applied forever:

• IP stickiness is dead for mobile — carrier-grade NAT puts thousands of users behind one IP (all pinned to one peer!), and one user’s phone hops addresses across requests (sticky to nothing).

• Prefer application session affinity: hash $cookie_session_id consistent; — stable, evenly spread (cookie IDs are high-cardinality), and survives network changes. ip_hash remains the right tool only for legacy apps that can’t issue cookies and sit behind fixed-IP office networks.

• True cookie-learning stickiness (inspect response, learn the backend) is Plus territory; open source composes hash $cookie_… instead.

4. random — and the power of two choices

upstream pool-random {
    random two least_conn;
    server 127.0.0.1:9001;
    server 127.0.0.1:9002;
    server 127.0.0.1:9003;
}

random picks a peer at random. random two least_conn — the form worth memorizing — picks two candidates at random, then routes to the less busy. That tiny addition is a famous result (the "power of two random choices"): it captures most of least_conn's load-smoothing without a global lock on the peer list, which is why large dynamic fleets (and cloud LBs) favor it. When your pool churns (autoscaling, Module 13's dynamic membership), random-two degrades gracefully where deterministic algorithms would cascade-remap.

5. The selection table

All of them compose with the failure machinery of the next lesson — algorithms choose among available peers; quarantine happens first.

Try it yourself

1. Reproduce the least_conn race (§1) with longer delays ( ?delay=5) and multiple concurrent slow requests — map who gets what with jq -r .server and confirm the busy peer is skipped every time.

2. Prove hash stability across reloads. Hash 8 URIs, note the mapping, nginx -s reload (config unchanged) — identical mapping. Now add a 4th peer to pool-hash, reload, re-hash: with consistent, most keys keep their peer; remove consistent and repeat — near-total remap. The cache-apocalypse experiment, live.

3. The ip_hash collision (§3) — try more source IPs ( --interface 127.0.0.3 … 127.0.0.6): all sticky, unevenly placed. Count how many land on each peer; feel the clumping.

4. Random-two vs plain random. Time 20 concurrent slow-ish requests ( /random/slow?delay=1) under both random and random two least_conn — the max-finish-time difference is the power-of-two choices, measurable.

Q&A

Q1. Why does least_conn outperform round robin on mixed-cost traffic but tie it on uniform traffic?

Q2. You add a 4th cache shard. With consistent, roughly what fraction of cached URLs must now miss, and why is that the minimum possible?

Q3. A mobile-heavy product wants session stickiness. Attack or defend ip_hash.

Q4. What problem does random two least_conn solve that plain least_conn doesn't?

Takeaways

• Four definitions of fairness: even choices (rr/weights), load-aware ( least_conn), deterministic placement ( hash, consistent), sticky ( ip_hash, legacy; cookie-hash, modern), plus lock-free smoothing ( random two least_conn).

• Consistent hashing is the cache-tier algorithm; its value appears exactly when membership changes (~1/N remap instead of ~all).

• ip_hash is stable per IP but not a spread guarantee — and mobile networks broke its assumptions a decade ago.

• Hash keys want high cardinality; placement quality tracks key quality.