Maglev vs Rendezvous: GCP's Load Balancer Hashing Change

GCP notice: from 21 Sep 2026 (complete by 9 Oct), most internal passthrough NLBs switch backend selection from Maglev to Rendezvous. Connection tracking, session affinity and health checks are unchanged.

Implemented both from their papers — Maglev (Eisenbud et al., NSDI 2016), Rendezvous/HRW (Thaler & Ravishankar, 1996) — over the same 32-bit MurmurHash3, to check the trade rather than take the release note's word for it. Every number below is measured, not quoted.

The Two Algorithms

• Maglev — precompute a table of M slots (prime; 65537 in the paper). Each backend derives an offset and a skip from two hashes, generating its preference list. Backends take turns claiming the first free slot on their list until the table is full. Lookup = 1 hash + 1 array read.
• Rendezvous — no table. For each backend, hash (flow, backend name); highest score wins. Lookup = N hashes.
• Both are consistent hashing: no shared state, no coordination, every LB instance independently reaching the same answer for the same flow.

Watching The Table Get Built

The turn-taking is the part Rendezvous has no equivalent for, and it is easier to watch than to describe. Each backend walks its own (offset + j·skip) mod M sequence, claiming the first slot nobody has taken.

Turn-taking is what makes the result exactly balanced — at M = 127 with 4 backends the slots split 32 / 32 / 32 / 31, no statistics involved. It is also what makes it expensive to change: add or remove a backend and the permutations interleave differently, so the whole table is rebuilt.

What The Simulation Shows

Drain a backend and watch what moves. 20,000 synthetic flows, both algorithms, before and after:

• Rendezvous churn is provably minimal. Drain a backend, only its flows move. The "needless" column reads exactly 0, every time, at any table size. Property of the algorithm, not a tuning result.
• Maglev at production table size is already close. M = 65,537 → ~0.02% needless. A handful of flows in 20,000.
• That closeness is bought with the table. Shrink M and it climbs sharply.

Why The Switch, Then

• Not churn — Maglev was already within a fraction of a percent at production table sizes.
• It's the state: M entries per forwarding rule, replicated to every LB instance, rebuilt from scratch on every backend-set change.
• Rendezvous holds nothing and rebuilds nothing. Matches Google's stated reason ("scalability and efficiency") far better than any disruption argument.
• Cost: O(N) per lookup instead of O(1). Only paid by flows that miss the connection-tracking table.
• Bonus: weights are exact and closed-form in Rendezvous (-w / ln(u)), vs approximated in Maglev by giving backends extra turns.

	Maglev	Rendezvous
State per rule	table of M entries, on every instance	none
Work per new flow	1 hash + 1 array read	N hashes + N comparisons
Work per backend change	rebuild the whole table	none
Load balance	exact by construction	even in expectation
Churn on backend loss	near-minimal, because M is large	exactly minimal, at any size
Weights	approximated via extra turns	exact, -w / ln(u)

What To Check

• Established connections are unaffected — selection only runs on a connection-tracking miss.
• The same 5-tuple can resolve to a different backend after the switch. One-time remap of new flows, not ongoing instability.
• Watch anything holding per-client state outside the connection: in-memory sessions keyed by client IP, per-tenant caches warmed on the backend.
• Long-idle flows that age out of connection tracking re-resolve, and may not return to the same backend.
• Carve-out: stays on Maglev where backend VMs have 2+ NICs and at least two of those NICs are eligible backends of at least two internal passthrough NLBs.

Caveat: Google hasn't published its own implementation details. These are properties of the published algorithms, not predictions about a specific load balancer.