Balancing algorithms

A balancing algorithm decides which healthy backend gets the next request. The simplest algorithms ignore what the servers are doing. Better ones watch a live signal, usually how many requests each backend has in flight.

The big idea

Round robin sends request 1 to A, request 2 to B, request 3 to C, then starts again. It works when every request costs about the same and every server is the same size. Its weakness is that it is blind. If server C pauses for two seconds, round robin keeps sending it a third of the traffic.

Least outstanding requests (called least request in Envoy) sends each new request to the backend with the fewest requests in flight. A slow server holds its requests longer, so its count rises and it gets fewer new ones. The balancer never needs to know why the server is slow.

Walking through it

Take 10 backends handling 1,000 requests per second. Normally each one takes 50 ms per request. Then one slows to 1,000 ms.

Round robin: each backend gets 1,000 / 10 = 100 requests/s
  healthy backend in flight:  100 × 0.05 s = 5 requests
  slow backend in flight:     100 × 1.0 s  = 100 requests
  If its thread pool caps at 64, requests queue and users wait.

Least outstanding requests:
  The slow backend holds far more in-flight requests than its peers,
  so it gets fewer new ones until its count drops back toward theirs.

Scanning every backend for the lowest count is costly, and every balancer would pick the same server, a herd effect. Power of two choices (P2C) avoids both: sample two backends at random and send the request to the less loaded one.

This sketch runs as written. The rolls are fixed so the output is the same every time.

type Backend = { id: string; inflight: number; healthy: boolean }

// Power of two choices: sample two healthy backends, keep the less loaded one
function pick(pool: Backend[], rand: () => number = Math.random): Backend {
  const healthy = pool.filter((b) => b.healthy)
  const a = healthy[Math.floor(rand() * healthy.length)]
  const b = healthy[Math.floor(rand() * healthy.length)]
  return a.inflight <= b.inflight ? a : b
}

const pool: Backend[] = [
  { id: "web-1", inflight: 4, healthy: true },
  { id: "web-2", inflight: 90, healthy: true }, // slow box, requests piling up
  { id: "web-3", inflight: 7, healthy: true },
]
const rolls = [0.1, 0.5, 0.4, 0.9, 0.0, 0.2]
const roll = () => rolls.shift()!

for (let i = 0; i < 3; i++) {
  const chosen = pick(pool, roll)
  chosen.inflight += 1 // the request is now in flight on that backend
  console.log("request", i + 1, "->", chosen.id)
}

Output:

request 1 -> web-1
request 2 -> web-3
request 3 -> web-1

Request 2 drew web-2 and web-3, and the slow web-2 lost. Mitzenmacher's analysis shows two random choices shrink the busiest server's load from about log n / log log n to about log log n / log 2.

Hashing for affinity

Some keys must reach the same backend, such as a server caching a user's data. Plain hash(key) % N remaps almost every key when N changes. Consistent hashing (ring hash, Maglev hashing) moves only about 1/N of the keys when a backend joins or leaves, but one hot key still lands on one backend. Sharding explains the ring.

Common mistakes

• Using round robin with slow or mixed servers. It keeps sending a full share to the slowest box.
• Using hash(key) % N for affinity. Changing N remaps almost everything. Use consistent hashing.

Check yourself

1. A backend slows down but never fails. Why does least outstanding requests send it less traffic without knowing why?

   Its requests stay in flight longer, so its in-flight count climbs and the balancer picks it less often.

2. Why does hash(key) % N break when N changes?

   Almost every key maps to a different backend, so caches go cold all at once.

Key takeaways

• Least outstanding requests uses in-flight counts as a free, live health signal.
• Power of two choices gets most of the benefit from two random samples and avoids the herd effect.
• Consistent hashing keeps keys on the same backend through changes, but hot keys can overload one backend.

Further learning

Sam Rose's interactive essay lets you watch these algorithms run under load.

Load Balancing (Sam Rose, interactive)A bottom-up, animated guide to HTTP load balancing algorithms.samwho.dev

Next: health checks and draining.