Networking
Part 3 of 6 · Load balancingBalancing Algorithms — Round-Robin, Least-Conn, Maglev & Power-of-Two Choices
RR, WRR, least-conn, least-time, Maglev, P2C + bounded load; skew/hot-key behavior; when each wins.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Uniform HTTP vs mixed streams vs keyed affinity
Prefer
Pick the scheduler for the shape
Short homogeneous HTTP → RR or P2C. Mixed duration → least-conn / least-request. Keyed locality → Maglev + bounded-load overflow.
- P2C beats pure random with two samples.
- Maglev beats modulo on membership churn (~1/N vs almost all).
- Hot keys still need salting or (1+ε) overflow — hashing will not save you.
Alternative
Always Maglev, or always RR
Maglev without a cap pins the celebrity key. RR without health pounds the slow box. Least-time without damping herds.
- Weighted RR goes stale the moment capacity changes.
- Least-conn on HTTP/2 TCP conns lies — count streams.
- Packet LB needs per-flow affinity or you reorder TCP.
Overview
Pick a scheduling algorithm that matches traffic: equal short requests, long-lived streams, cache locality, or backend churn. Understand skew, hot keys, and why Maglev and P2C show up in senior interviews.
Ring construction, vnodes, and RF walks are not this lesson. See consistent hashing. Here Maglev is the connection/request lookup table Google used in Maglev/GFE-style LBs.
Algorithm zoo
| Algorithm | State | Wins when | Failure mode |
|---|---|---|---|
| Round-robin | Cursor | Homogeneous, similar cost | Slow backend keeps getting pounded |
| Weighted RR | Static weights | Capacity tiers | Weights go stale |
| Least connections | Inflight count | Mixed durations, WS, uploads | HTTP/2 conn ≠ streams |
| Least time | Latency EWMA | Similar work, want fast boxes | Positive feedback / herding |
| Random | None | Trivial | Worse variance than P2C |
| P2C | Two samples | Near-optimal balance, O(1) | Still need health/outliers |
| Maglev | Lookup table | Stable key→backend, churn ~1/N | Hot key still one node |
| Ring hash (Ketama) | Token ring | Intuitive affinity | More remaps than Maglev; vnode lesson is elsewhere |
Round-robin and weighted RR
Best when backends are homogeneous and requests similar cost. Failure mode: a slow backend keeps getting its fair count of work unless health / outlier detection ejects it.
Weighted RR is how you encode "this box is 2×." It does not see runtime saturation.
Least connections and least time
Least-conn tracks active streams — ideal for uploads, WebSockets, DB pools. Least-time adds a latency EWMA — risk of positive feedback (everyone herds to whoever looked fast 100ms ago). Mitigate with P2C + damping, not a global min.
Power of two choices + bounded load
Picking the less loaded of two random backends exponentially improves imbalance versus one random choice. Bounded load: if the hashed backend is above ~1.25× (or (1+ε)) average, overflow — that is how you fight hot keys without giving up most affinity. Depth: hot keys / bounded loads.
Decisions
- 1
1 Incoming request
- next2 Sample two healthy backends
- 2
2 Sample two healthy backends
- next3 Compare inflight
- ?
3 Compare inflight
- A lighter4a Send to A
- B lighter4b Send to B
- 4
4a Send to A
- next5 Update inflight
- 5
4b Send to B
- next5 Update inflight
- 6
5 Update inflight
Diagrams - step by step
Three small diagrams. Step numbers in the labels give the animation order. The lesson map under Diagram 1 plays those steps.
Diagram 1 - Happy path: power of two choices
Decisions
- 1
Step 1 Request arrives
- nextStep 2 Sample two random healthy backends
- 2
Step 2 Sample two random healthy backends
- nextStep 3 Which has fewer outstanding requests?
- ?
Step 3 Which has fewer outstanding requests?
- AStep 4a Send to A
- BStep 4b Send to B
- 4
Step 4a Send to A
- nextStep 5 Increment inflight, decrement on reply
- 5
Step 4b Send to B
- nextStep 5 Increment inflight, decrement on reply
- 6
Step 5 Increment inflight, decrement on reply
- rank by stale latency, no dampingFailure path - herding onto one fast backend
- 7
Failure path - herding onto one fast backend
The request samples two random healthy backends and goes to the one with fewer outstanding requests. Inflight is incremented, then decremented on the reply. Ranking backends by a stale latency with no damping is the failure path: traffic herds onto one backend that looked fast.
Lesson map
Balancing Algorithms — Round-Robin, Least-Conn, Maglev & Power-of-Two Choices
Diagram 1 walks 6 steps from Step 1 Request arrives through Step 5 Increment inflight, decrement on reply.
Architecture. Step 1 Request arrives Ready. Step 2 Sample two random healthy backends Ready. Step 3 Which has fewer outstanding requests? Ready. Step 4a Send to A Ready. Step 4b Send to B Ready. Step 5 Increment inflight, decrement on reply Ready. Failure path - herding onto one fast backend Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB A["Step 1 Request arrives Ready"] B["Step 2 Sample two random healthy backends Ready"] C["Step 3 Which has fewer outstanding requests? Ready"] D["Step 4a Send to A Ready"] E["Step 4b Send to B Ready"] F["Step 5 Increment inflight, decrement on reply Ready"] X["Failure path - herding onto one fast backend Ready"] A -->|continues| B B -->|continues| C C -->|A| D C -->|B| E D -->|continues| F E -->|continues| F F -->|rank by stale latency, no damping| X
Diagram 2 - Failure path: hot key with Maglev
Sequence
- 1
Celebrity user traffic → LB with Maglev
Step 1 20 percent of writes share one user_id
- 2
LB with Maglev → Shard 17
Step 2 Maglev maps that key to shard 17 every time
- 3
Shard 17 → Shard 17
Step 3 queue grows and p99 explodes
- 4
LB with Maglev → Shard 3
Step 4 other shards stay mostly idle
- 5
Celebrity user traffic
Step 5 stable mapping does not mean balanced load
- 6
Celebrity user traffic
Fix - bounded load overflow at about 1.25x average, or salt the hot key
Twenty percent of writes share one user id. Maglev maps that key to shard 17 every time, so shard 17's queue and p99 explode while shard 3 stays mostly idle. A stable mapping is not a balanced load. Overflow near 1.25x average load, or salt the hot key.
Diagram 3 - Decision: choose the algorithm
Decisions
- ?
Step 1 Traffic shape?
- short homogeneous HTTPRound-robin or P2C
- mixed latency or long streamsLeast-conn or P2C on outstanding requests
- key or connection affinityStep 2 Hot keys likely?
- 2
Round-robin or P2C
- Wrong pick - heterogeneous request costSlow backend keeps getting its full share
- 3
Least-conn or P2C on outstanding requests
- ?
Step 2 Hot keys likely?
- noMaglev or ring hash
- yesConsistent hash with bounded load
- 5
Maglev or ring hash
- Wrong pick - assume it fixes hot keysOne shard melts
- 6
Consistent hash with bounded load
- 7
Slow backend keeps getting its full share
- 8
One shard melts
Short homogeneous HTTP can use round-robin or power of two choices. Mixed latency or long streams want least-conn, or power of two choices on outstanding requests. Key or connection affinity with no hot keys can use Maglev or a ring hash. Hot keys need consistent hash with bounded load. Round-robin on uneven request cost keeps giving a slow backend its full share. Maglev does not fix a hot key.
Maglev consistent hashing
Google Maglev builds a lookup table so each backend gets ~equal slots. Adding or removing a backend remaps about 1/N of lookups — unlike hash % N, which reshuffles almost all. Used for connection affinity and packet load balancing.
The hot-key problem remains. Celebrity user_id → 20% of writes → Maglev maps stably to shard 17 (locality and hotspot). Fixes: salt/fan-out, local queue, bounded-load overflow — not a bigger table.
Do not draw a vnode ring here. Maglev's permutation table is the interview artifact. Rings, HRW, and jump hash: CH hub, HRW, jump.
Flow
- 1
Backend joins the pool
- nexthash key mod N
- nextMaglev lookup table
- 2
hash key mod N
- nextAlmost all keys remap
- 3
Maglev lookup table
- nextAbout 1/N keys remap
- 4
Almost all keys remap
- 5
About 1/N keys remap
Skew scenarios
- Elephant flows: a few TCP connections carry most bytes — per-flow affinity at L4 is mandatory or you reorder.
- Hot partition key piles onto one pod — Maglev/ring/HRW all agree on the victim.
- Slow backend + undamped least-time concentrates wrongly.
Choosing in production
- Short homogeneous HTTP → RR / P2C
- Mixed latency / streams → least-conn or P2C on outstanding requests
- Session / conn affinity → Maglev / ring hash
- Cache locality by key → consistent hash + bounded load (app servers still RR/P2C)
- Extreme churn → Maglev (table rebuild, ~1/N move)
Envoy names: ROUND_ROBIN, LEAST_REQUEST (often P2C on outstanding requests), RING_HASH, MAGLEV, RANDOM.
Sandbox: Maglev table sketch (Python)
Table size 97 is prime (Maglev wants prime M). This is a teaching sketch, not a 65537-slot production table.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Sandbox: P2C (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
A celebrity user_id is 20% of writes. Maglev maps it stably to shard 17. What happens to p99 on 17 if you add five more pods? Name three overlays (salt, coalesce, bounded-load spill) without redrawing a vnode ring.
Interview Q&A
Why is P2C better than pure random?
Answer
Two independent samples cut tail imbalance with O(1) extra state. One random choice has high variance; the min of two is much tighter (power-of-two-choices).
Does consistent hashing fix hot keys?
Answer
No. It only makes the mapping stable. The celebrity key still has one home. Overlay salt, coalescing, or bounded load.
Maglev vs modulo?
Answer
Modulo reshuffles nearly all keys when N changes. Maglev remaps about 1/N. Same ~1/N story as rings/HRW/jump — different data structure.
What is Envoy least-request?
Answer
Often P2C on outstanding requests, not a global min scan of every host on every call.
Weighted RR pitfall?
Answer
Ignores runtime saturation. A 2× box that is already on fire still gets 2× of new work.
When is RR harmful?
Answer
Heterogeneous costs or sizes without weights — and whenever a slow box is still "healthy." Pair RR with outlier ejection.
Packet vs request load balancing?
Answer
Packet LB must keep per-flow affinity (5-tuple) or TCP reorders. Request LB can pick a new backend per HTTP request (watch HTTP/2 streams).