Concepts
Maglev hashing and connection tracking
Intuition
Imagine a reception desk with several attendants and a queue of customers: the rule is that anyone who has already started being served by someone keeps being served by that same person until the end. To do this, each attendant jots down in a little notebook who they are serving. But the notebook has few pages and, sometimes, the queue is redistributed among different reception desks, which cannot see each other's notebooks. So they all agree beforehand on a fixed table of "customer of type X goes to attendant Y", built so that each attendant gets practically the same number of customers. That way, even without consulting the notebook, any reception desk arrives at the same answer.
How it works
Maglev is a software network load balancer: each Maglev machine announces the VIPs to the router via BGP at the same cost, and the router spreads packets across them using ECMP. The forwarder hashes the 5-tuple (source IP and port, destination IP and port, protocol), looks up a fixed-size local connection table that maps that hash to the backend and, if there is no entry, picks a backend with Maglev hashing and records the decision in the table. The local table alone is not enough, for two reasons: ECMP can redistribute traffic among Maglevs when the set of machines changes (as in rolling upgrades), and the table is finite and can fill up under high load or a SYN flood. In those cases consistent hashing gives all Maglevs the same choice without sharing state. Maglev hashing fills a lookup table of size M (prime): each backend has a preference list, a permutation of the table positions derived from two hashes of its name (offset and skip), and the backends take turns claiming their preferred position that is still free until the table is full. As a result, the number of entries per backend differs by at most one, and different weights can be obtained by changing the relative frequency of the turns. Unlike classic consistent hashing (Karger) and rendezvous hashing, which prioritize minimal disruption, Maglev prioritizes uniform balance, accepting that changes to the table alter more assignments. The authors choose M greater than 100 times the number of backends to limit the difference in share to about 1%; the default is 65537, since there is one table per VIP and larger tables take longer to generate (from 1.8 ms to 22.9 ms in the experiments).
In practice
In the paper, with 1,000 backends, Maglev hashing gave near-perfect balance at any table size, while with 65,537 entries Karger and rendezvous required overprovisioning of 29.7% and 49.5%; this balance avoids having to oversize the backends for peak load. In Google's operation, Maglevs moved from active-passive pairs to the ECMP model with all machines active, gaining capacity, efficiency and simplicity, because Maglev hashing protects against occasional ECMP flaps. Consider this combination (per-flow connection table, consistent hashing as a fallback, and ECMP in front) when designing a distributed L4 load balancer with no shared state, where load uniformity matters more than moving the minimum number of flows on each change.
Use it in a design
Practice the cases that rely on this concept in the System Design school.