subroute.
Advanced12 min readlive prototype

Maglev Hashing

Precompute a lookup table so routing is O(1) and disruption is minimal — Google's hashing for software network load balancers.

Overview

What this concept solves

Maglev hashing comes from Google's network load balancer (Eisenbud et al., NSDI 2016). Its job is brutal: route millions of packets per second to backends, with lookups that must be as close to free as possible. A ring walk or an O(N) score per packet is too slow. So Maglev does the work once, up front, and bakes the result into a flat array.

That array is the lookup table: M slots (M a prime, ~65537 in production), each holding the id of one backend. Once it's built, routing a key is three trivial operations — hash(key), mod M, read table[slot]. That's O(1), no matter how many backends or keys you have. The cleverness is entirely in how the table gets filled so that it's both evenly balanced and barely disturbed when backends change.

Filling is a fair draft. Each backend generates a preference list — a permutation of all slot numbers, the order it would grab slots if it could. Then backends take turns: on your turn you claim your most-preferred slot that's still free. Round after round until the table is full. Because everyone gets roughly equal turns, everyone ends up with roughly equal slots.

Mechanics

How it works

Build the table with a round-robin draft

  1. Pick a table size M (prime). Each backend derives two numbers from its name — an offset and a skip — that generate its preference list: offset, offset+skip, offset+2·skip, … (all mod M).
  2. Go round by round. On each backend's turn, scan down its preference list to the first slot that's still empty and claim it.
  3. If its top choice is taken, it skips to its next preference (the prototype shows these skips).
  4. Continue until all M slots are filled. Now every slot maps to exactly one backend.

Lookup afterwards is the easy part: slot = hash(key) % M, then backend = table[slot]. One hash, one modulo, one array read — the same cost whether you have 3 backends or 300.

Why disruption is bounded

When a backend disappears, Maglev rebuilds the table — but the draft is designed so that most slots keep their previous owner. Only a small, bounded fraction of slots change hands, which means only a small fraction of connections get re-routed. It's not quite as minimal as the ring or jump hash, but it's close — and in exchange you get O(1) lookups and very even balance. A bigger M makes both the balance smoother and the disruption finer-grained.

Built for connection consistency

Maglev pairs this table with connection tracking so that, even during a rebuild, existing TCP connections keep going to the same backend. The hashing gives a good default; the tracking handles the edge cases. Together they let Google run load balancing as software on commodity servers.

It costs O(M) memory and a rebuild

Unlike jump hash's zero state, Maglev keeps an M-slot table and must recompute it when membership changes. With M in the tens of thousands that's cheap and fast, but it is real work and real memory — the price of O(1) lookups.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

About this simulation

Maglev builds a fixed lookup table of M slots up front. Each backend has a pseudo-random preference list, and they take turns in a round-robin draft — each claims its most-wanted free slot — until every slot is filled. Press Play draft to watch it fill, then click a key to see its O(1) lookup: hash(key) % M → read the cell → done. Remove a backend and only a bounded slice of the table changes.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Watch the draft fill the table

Press Play draft. Backends take turns claiming their most-preferred free slot; the status line calls out each pick and any slots it had to skip because they were already taken. When it finishes, every slot is coloured by its owner and lookups are ready.

try 02

Do an O(1) lookup

Click a key chip. The result panel shows the three steps: hash(key), then mod M to get a slot, then table[slot] to get the backend — and the matching cell in the table highlights. No walking, no scoring; just one array read.

try 03

Remove a backend, change M

Click a backend's ✕ and watch the table redraft — most cells keep their colour; only a bounded slice changes. Then try the M buttons (7 → 31): a bigger table balances more smoothly and spreads disruption over finer slots. Production uses M ≈ 65537.

In practice

When to use it — and what you give up

When to reach for it

  • High-throughput network load balancers — the original use: routing packets at line rate where per-lookup cost must be O(1).
  • Many lookups, infrequent membership change — you pay to build the table once, then enjoy cheap reads.
  • *You need even balance and fast lookups* — Maglev gives both, where the ring trades lookup speed and jump hash trades flexibility.
  • Connection-oriented traffic — combined with connection tracking, it keeps flows pinned to their backend through churn.

Pros

  • O(1) lookup — one hash, one mod, one array read, regardless of scale.
  • Very even load by construction (the fair round-robin draft).
  • Bounded disruption when backends change — only a small fraction of slots move.
  • Battle-tested at Google scale; pairs naturally with connection tracking.

Cons

  • Uses O(M) memory for the table — not zero-state like jump hash.
  • Membership changes require rebuilding the table.
  • Disruption is slightly worse than the ring or jump hash (still bounded, just not minimal).
  • More moving parts (preference lists, draft) than a plain ring.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

// Maglev hashing: build a lookup table once, then route in O(1).
package main

func h(s string) int { /* any 32-bit hash */ return 0 }

func buildTable(backends []string, M int) []string {
	// Each backend's preference list is a permutation of [0, M).
	prefs := make([][]int, len(backends))
	for i, name := range backends {
		offset := h(name+":offset") % M
		skip := (h(name+":skip") % (M - 1)) + 1 // 1..M-1
		p := make([]int, M)
		for j := 0; j < M; j++ {
			p[j] = (offset + j*skip) % M
		}
		prefs[i] = p
	}

	table := make([]string, M)
	for i := range table {
		table[i] = "" // empty slot
	}
	next := make([]int, len(backends)) // cursor into each pref list
	filled := 0

	// Round-robin draft: each backend claims its top free slot, in turn.
	for filled < M {
		for i := 0; i < len(backends); i++ {
			slot := prefs[i][next[i]]
			for table[slot] != "" { // skip taken
				next[i]++
				slot = prefs[i][next[i]]
			}
			table[slot] = backends[i]
			next[i]++
			filled++
			if filled == M {
				break
			}
		}
	}
	return table
}

// Lookup is now O(1):
func lookup(key string, table []string) string {
	return table[h(key)%len(table)]
}

func main() {
	buildTable([]string{"alpha", "beta", "gamma"}, 65537)
}

References & further reading

4 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. Sign in to save your best score.

question 01 / 03

After the table is built, how does Maglev route a key?

question 02 / 03

How is the lookup table filled?

question 03 / 03

Compared with jump hash, what does Maglev trade for its O(1) lookups?

0/3 answered

Was this concept helpful?

Tell us what worked, or what to improve. We read every note.

Back to Consistent Hashing