Google Cloud · internal passthrough network load balancer

Maglev vs Rendezvous

Google is replacing the backend‑selection algorithm inside most internal passthrough NLBs. Same connection tracking, same session affinity, same health checks — a different answer to one question: given this flow, which backend? Here is what each algorithm actually does, and what changes when the backend set does.

Rollout begins 21 Sep 2026 Complete by 9 Oct 2026 Exempt multi‑NIC backends serving 2+ ILBs Unchanged connection tracking

One packet, two ways to choose

Both algorithms are consistent hashing: no shared state, no coordination, every load balancer instance independently reaching the same answer for the same flow. They get there in opposite ways — one precomputes an answer for every possible hash, the other computes the answer on demand.

Maglev

Build a table, then read it

Each backend derives two numbers from its own name: an offset and a skip, from two independent hashes.
Those generate its preference list — offset, offset+skip, offset+2·skip… all mod M, a prime table size (65537 in the paper).
Backends take turns. On your turn, claim the first slot on your list that nobody has taken. Repeat until all M slots are full.
A packet arrives: hash the 5‑tuple, take it mod M, read that slot. One array lookup, whatever the backend count.

The table is the product. Every load balancer holds a copy, and any change to the backend set means building a new one.

Rendezvous

Score everyone, keep the highest

Nothing is precomputed. No table exists.
A packet arrives: for each backend, hash the pair (flow, backend name) into a number — its score for this specific flow.
The highest score wins. That is the entire algorithm.
Every load balancer computes the same winner from the same inputs, with nothing to build and nothing to keep in sync.

Also called Highest Random Weight (HRW), Thaler & Ravishankar, 1996 — two years older than consistent hashing rings, and quietly better behaved.

Resolve a flow

Type any flow identifier below — a 5‑tuple, a hostname, anything. Both algorithms run on it live, against the same four backends, using the same 32‑bit hash.

Flow key (5‑tuple)

Maglev — table read

Rendezvous — scores for this flow

Demo table size is M = 127 so all slots fit on screen; production Maglev uses a much larger prime (65537 or 655373). The simulation further down uses 65537.

Watch the table get built

This is the part Rendezvous does not have. Backends take turns claiming slots from their own preference sequence; when a slot is already taken they skip ahead to the next free one on their list. The turn‑taking is what makes the result exactly balanced — every backend ends up with either ⌊M/N⌋ or ⌈M/N⌉ slots, no statistics involved.

It is also what makes it expensive to change. Add or remove one backend and the permutations interleave differently, so the table is rebuilt from scratch — every instance, every forwarding rule, before the next packet gets the right answer.

Maglev population, M = 127, N = 4

What moves when a backend does

This runs for real: 20,000 synthetic flows, resolved by both algorithms before and after every change you make, in your browser. Drain a backend, bring it back — the numbers are measured, not quoted.

The bar to beat is the unavoidable churn. When a backend is drained its own flows have to go somewhere; nothing else needs to move. Rendezvous hits that bar exactly, always — the needless column is provably zero, not just small.

Maglev misses it, but at a full‑size table it barely misses: a fraction of a percent of flows. That is the honest headline, and it is why the table size matters. Shrink M and Maglev's needless churn climbs — the big table is what buys the near‑minimal behaviour, and the big table is exactly what has to be held and rebuilt.

Backends: Maglev table size M

Maglev

M = 65,537 · table rebuilt

Before — 180 sampled flows

After

Flows that moved

Remapped

—

Unavoidable

—

Needless

—

Rendezvous

no table · nothing rebuilt

Before — 180 sampled flows

After

Flows that moved

Remapped

—

Unavoidable

—

Needless

—

The trade Google is making

Google's stated reason is scalability and efficiency, and the lab above shows why it is not primarily about churn: at a full‑size table Maglev is already within a fraction of a percent of optimal. The thing Rendezvous removes is the table itself — the memory every load balancer spends per forwarding rule, and the rebuild every one of them performs whenever a backend appears or disappears.

It is not free. Rendezvous gives up the O(1) lookup and pays a hash per backend on every new flow. That cost lands in the one place it is affordable: only flows that miss the connection‑tracking table pay it.

	Maglev	Rendezvous
State per rule	A lookup table of `M` entries, replicated to every LB instance	None. The backend list is the only state.
Work per new flow	1 hash + 1 array read — O(1)	`N` hashes + `N` comparisons — O(N)
Work per backend change	Rebuild the whole table before the next packet is right	Nothing. The next lookup is already correct.
Load balance	Exact by construction: `⌊M/N⌋` or `⌈M/N⌉` slots each	Statistical: even in expectation, with binomial spread
Churn on backend loss	Near‑minimal, and only because `M` is large — the reshuffle moves a little extra	Exactly minimal at any size. Provably nothing else moves.
Weights	Approximated — heavier backends are given extra turns	Exact and closed‑form: `−w / ln(u)`, `u = h/2³²`
Scaling pressure	Memory and rebuild cost, per rule, per instance	Per‑flow CPU, growing with backend count

Lookup cost, measured here

Resolves 200,000 flows with each algorithm and reports nanoseconds per lookup.

JavaScript in a browser, on one core — indicative of the shape of the difference, not its magnitude in a production datapath, where selection is vectorised and, for the vast majority of packets, skipped entirely thanks to connection tracking.

What it means for your ILB

Established connections are not affected

Backend selection only runs for a flow with no entry in the connection‑tracking table. Tracked connections keep going to the backend they already have, straight through the migration.

The mapping itself changes once

The same 5‑tuple can resolve to a different backend after the switch, even with an unchanged backend set. It is a one‑time remap of new flows, not ongoing instability.

Watch for state outside the connection

If a backend keeps per‑client state that is not carried in the connection — an in‑memory session keyed by client IP, a local cache warmed per tenant — that is where a remap is visible. Long‑idle flows that age out of connection tracking re‑resolve too.

The carve‑out

Load balancers stay on Maglev when backend VMs have two or more NICs and at least two of those NICs are eligible backends of at least two internal passthrough NLBs. If that is your topology, nothing changes for you.

Both algorithms here are implemented from their published descriptions — Maglev per Eisenbud et al., NSDI 2016 (offset/skip permutations, prime table, turn‑based population); Rendezvous per Thaler & Ravishankar, 1996 (highest‑score wins) — both over the same MurmurHash3 32‑bit function. Google has not published the details of its own implementation, so treat the measured numbers as properties of the algorithms, not predictions about your specific load balancer.