A different ring tradeoff
Classic consistent hashing minimizes key movement but can be uneven without many virtual nodes, which inflate memory. Maglev hashing, from Google's software load balancer, trades a little disruption for near perfect balance and a compact, fast lookup.
The lookup table
Maglev builds a fixed-size lookup table, typically a large prime number of slots. Each backend gets a permutation that proposes preferred slots, and backends take turns filling empty slots in round robin order.
- Every backend ends up owning a nearly equal share of slots.
- A flow is hashed to a slot, and the slot names the backend.
- Lookup is a single array index, so it is extremely fast.
Properties
- Even balance: shares differ by at most one slot across backends.
- Low disruption: when a backend leaves, only flows on its slots move, though slightly more churn than pure consistent hashing.
- Resilience: each balancer rebuilds the same table from the same membership, so connections survive across balancers.
Where it fits
Maglev sits in front of huge backend pools where both even load and stable flow to backend mapping matter, such as a global edge.
Key idea
Maglev hashing fills a fixed lookup table by backend preference and round robin, giving near perfect balance and constant time lookup while still moving few flows when membership changes.