The encyclopedia · Software & IT · Technical decision · 2016
Maglev balanced Google's traffic with one lookup table per packet
Google's Maglev turned consistent hashing into a compact table, giving O(1) lookups and near-minimal disruption.
The solution
Google's cloud needed software load balancers that spread packets across many backends and survive backend changes without dropping connections. Classic consistent hashing with virtual nodes solved disruption but cost a large lookup table in memory.
Maglev's paper, presented at NSDI 2016, uses a different scheme: a compact lookup table with one entry per backend, filled from per-backend random permutations. A connection's packet hashes once and reads one table cell.
The construction guarantees near-equal load, minimal disruption when backends are added or removed, and no protocol or memory cost at lookup time. The table is rebuilt from scratch on each membership change, making behavior deterministic.
Why it worked
- One hash plus one table read per packet
- Table rebuild concentrates work at change time
- Per-backend permutations give near-equal load
- About 1/N of connections move when backends change
What can be applied
If a structure is too expensive per lookup, precompute the mapping when the world changes: a rebuilt table gives O(1) lookups and bounded disruption, trading setup for savings on every packet.
Aftermath
Maglev carried production traffic into Google's cloud at scale, and the NSDI paper became a reference for load-balancer design; similar table-based hashing ideas spread to open-source load-balancing projects.
Sources
- Maglev: A Fast and Reliable Software Network Load Balancer
- Maglev: A Fast and Reliable Software Network Load Balancer (session page)
spotted an error? The archive wants to know.