Papers
Maglev: A Fast and Reliable Software Network Load Balancer
Danielle E. Eisenbud, Cheng Yi, Carlo Contavalli, Cody Smith, Roman Kononov, Eric Mann-Hielscher, Ardas Cilingiroglu, Bin Cheyney, Wentao Shang, Jinnah Dylan Hosein · NSDI 2016 (13th USENIX Symposium on Networked Systems Design and Implementation), 2016
The problem: hardware load balancers cannot keep up with Google's traffic
A network load balancer sits between a service's routers and servers: it matches each packet to its destination service and forwards it to one of that service's endpoints. Traditionally this was done by dedicated hardware appliances, and the authors point out four limitations for Google's case. First, scalability is limited by the maximum capacity of a single unit. Second, these appliances are usually deployed in pairs, offering only 1+1 redundancy, which does not meet the high availability requirement. Third, they lack the flexibility and programmability to iterate quickly on new features. Fourth, increasing capacity requires physically buying and installing new hardware. The proposed alternative is to build the load balancer as a distributed software system running on commodity Linux servers in the cluster itself. This makes it possible to scale horizontally (scale-out) by adding machines, get N+1 redundancy, control and evolve the system on your own, and simplify deployment, since it only uses existing servers. In return, the challenge is twofold: each machine needs high throughput (total capacity is bounded by N x T) and the system must guarantee connection persistence, that is, packets of the same connection always reach the same endpoint, even with frequent failures. Maglev has served Google's traffic since 2008.
Architecture: VIPs, ECMP, GRE encapsulation, and Direct Server Return
Each Google service has one or more virtual IP addresses (VIPs), which do not belong to a specific physical interface: they are served by multiple endpoints behind Maglev. Each Maglev machine announces the VIPs to the router via BGP, all with the same cost. So, when a packet for a VIP arrives at the router, it spreads it across the cluster's Maglev machines using ECMP (Equal Cost Multipath). The Maglev machine picks one of the service's endpoints, encapsulates the packet with GRE (Generic Routing Encapsulation) using an outer IP header addressed to the endpoint, and sends it. The endpoint decapsulates and consumes the packet. The response goes back with the VIP as the source address and the user's IP as the destination, and is sent directly to the router via Direct Server Return (DSR), so Maglev does not need to process the return traffic, which is usually much larger. Each Maglev machine has two components: the controller, which periodically checks the forwarder's health and decides whether to announce or withdraw all VIPs via BGP (so the router only forwards to healthy machines), and the forwarder, which handles the packets. Each VIP is associated with one or more backend pools, whose members go through health checks; packets only go to healthy backends. It is also possible to split a cluster into shards of Maglevs, serving distinct sets of VIPs, to isolate performance.
Fast packet processing: kernel bypass and backend selection
Since incoming requests tend to be small, the forwarder has to handle tiny packets well: assuming IP packets of 100 bytes on average, it would need to process about 9.06 million packets per second to saturate a 10 Gbps link. To get there, Maglev is a user-space application that completely bypasses the Linux kernel network stack. At startup it pre-allocates a packet pool shared with the network interface card (NIC), and packets move between the NIC and the forwarder through pointer ring queues, with no copying and no kernel involvement. Packets are processed in batches to reduce the cost of crossing boundaries, and each packet thread is pinned to a dedicated CPU core and shares no data with the others. A steering module computes the hash of the 5-tuple (source IP and port, destination IP and port, protocol) and distributes packets among the receive queues, instead of using round-robin, which reduces reordering within a connection. Each thread filters out packets that don't belong to any configured VIP, looks up its connection table, picks a backend if needed, encapsulates in GRE and sends. In tests, introducing kernel bypass improved per-machine throughput by more than a factor of five, and a machine with a 10 Gbps NIC reached the card's capacity with small packets using 5 packet threads.
Connection persistence: connection table and consistent hashing (Maglev hashing)
For connection-oriented connections such as TCP, all packets must go to the same backend. Maglev uses a two-part strategy: it picks the backend with a new form of consistent hashing and records the decision in a local, fixed-size connection table that maps the 5-tuple hash to the backend. But the local table alone is not enough, for two reasons: the router's ECMP can redistribute traffic among Maglevs when the set of machines changes (for example, during rolling upgrades), and the table is finite and can fill up under high load or a SYN flood. For these cases consistent hashing comes in, giving the Maglevs the same choice without sharing state. Maglev hashing fills a lookup table of size M (prime) as follows: each backend gets a preference list, a permutation of all the table positions, derived from two hashes of its name (offset and skip). The backends then take turns, each claiming its preferred position that is still free, until the table is full. This makes the number of entries per backend differ by at most one. In practice the authors choose M greater than 100 times the number of backends N, to limit the difference in hash space share to about 1%. Different backend weights can be obtained by changing the relative frequency of the turns.
Trade-offs and operational experience: balance versus minimal disruption
Classic consistent hashing (Karger) and rendezvous hashing prioritize minimal disruption: when backends change, few assignments change. Maglev inverts the priority, for two reasons. First, it needs to balance load as uniformly as possible; otherwise, the backends would have to be overprovisioned for the peak. Second, in steady state, changes to the table do not cause connection resets, because the affinity between connections and Maglevs does not change; only when it changes are resets proportional to the number of changed entries. In experiments with 1000 backends, Maglev hashing gave near-perfect balancing with any table size; with a table of 65537 entries, Karger and rendezvous required overprovisioning of 29.7% and 49.5% respectively, dropping to 10.3% and 12.3% with 655373 entries. On the other hand, Maglev hashing is more resilient to backend changes when the table is larger, but table generation time grows from 1.8 ms to 22.9 ms, and since there is one table per VIP, the size cannot grow indefinitely; the default is 65537. In operation, Maglevs were originally deployed in active-passive pairs, but migrated to the ECMP model with all machines active, gaining capacity, efficiency, and simplicity, since Maglev hashing protects against occasional ECMP flaps.
See the ideas at work
Practice the designs that use this paper in the System Design school.