Tymofii

Maglev: A Fast and Reliable Software Network Load Balancer - Google, 2016

Paper: PDF

Mirror: PDF

Overview

  • Network routers deliver packets to Maglev instances using Equal Cost Multipath (ECMP)
    • ECMP is a forwarding strategy that basically just spreads the traffic across several "equally best" paths
    • Sidenote on how routers work: router is a machine that operates on 2 levels -- data plane and control plane. Control plane hosts routing strategies, computes paths, talks to other routers AND (most important) updates the lookup tables for data plane. Data plane, on each packet, parses a packet, does longest-prefix match on destination IP of a packet, gets ECMP group, then computes a hash of 5-tuple (src IP, dest IP, protocol, src port, dest port) of the packet, %-divides it by group size, rewrites the next MAC address and send the packet further.
  • When Maglev instance gets a packet, it matches it with the service and spreads it evenly across service instances.
  • Uses consistent hashing to accommodate the change in service instance group.
  • At the time of writing paper, load balancers were typically hardware appliances
    • problems: scalability, availability (mostly only 1+1 redundancy), lack of flexibility, expensive
    • software based approach would solve most of these issues + add more control over infra

Requirements

  • Connection persistence: single connection must go to the same service instance
  • Achieve line-rate packet throughput

End-to-end flow for small clusters

  • Setup:
    • Each Google service is assigned a virtual IP. Maglev maps VIP to a set of service instances.
    • VIPs are tied to a location.
  • Flow:
    1. User makes a request to a DNS server
    2. DNS server decides what VIP to return based on user's location
    3. VIP (service-at-location) is returned to user and user sends packet with destination IP set to the VIP
    4. Packet arrives at the router in the Google datacenter
    5. Router has multiple Maglev instances that serve the same VIP. It decides where to forward the packet based on the 5-tuple.
    6. Packet arrives at Maglev instance. Based on the hash it decides which service instance to forward the packet.
    7. Service instance processes the request. Wraps the response and sends it directly to the router (not Maglev (!), it skips it. They call it Direct Server Return (DSR))

VIP configuration

  • VIPs are defined in configuration objects (files or pushed via RPC)
  • Each VIP configuration contains a set of backend pools
    • Backend pool is a collection of service endpoints
    • Each backend pool is health-checked by specific health-checkers inside the forwarder
    • As I understood, we divide servers in backend pools, because different servers need to be checked differently. Also, it's easier to account them.

Maglev instance overview

  • Consists of 2 components : controller and forwarder
    • Controller has 2 jobs:
      1. announce/withdraw VIPs to routers via BGP.
      2. check the forwarder health.
    • Forwarder forwards VIP traffic to service instances.
  • Maglev can be sharded inside the same cluster. The sharding key is VIP served.
  • Forwarder:
    • Critical component that needs to process the packets
    • Uses kernel bypass to read from NIC, add outer IP headers, and write back to NIC

Maglev hashing

  • Recap on consistent hashing
    • The default (Karger) implementation is a ring [0, 2^32) where we put keys of backends. All hash values on ring section belong to the first clockwise key.
      • The backend lookup up is done using binary search, hence it's log time.
    • There can be imbalance of sections during outages, but this is traditionally solved by virtual nodes.
  • Maglev hashing
    • Problem 1: Karger's consistent hashing demands log-time backend lookup which is slow for LB. We want constant time backend query.
      • Trade-off: We are prepared to pay with the need to reorder more keys than n/m.
    • Problem 2: if you don't use virtual nodes (usually 100-200 virtual nodes per real node), you end up with very unbalanced load. Here we can't afford so many virtual nodes, because it inflates the table size.
    • Solution. Start with what we want: a mapping from a key (like packet hash % (number of slots)) to a backend. This should be a table lookup.
    • The central idea is to generate a "preference list" of slots for each backend. Then populate the lookup table the following way: take the most preferred free slot of a backend and set the backend index there.
      • Because the backends take turns, we get even distribution (each backend gets (+-1) same number of slots)
    • The big question is to how to generate preference lists. Properties of such function:
      • Each preference list should be:
        • deterministic (so that we can avoid state sharing, and thus synchronization)
        • permutation (each slot must occur only once).
        • depend only on the backend name
        • uniform
        • cheap
      • The permutations must be independent
    • The paper uses this function:
      • formula
      • M is prime ($M >> N$)
      • Table is rebuilt locally on each Maglev

How to implement this in practice

  • For BGP routing you can use bird, frr or ExaBGP. There're lots of BGP implementations
    • ECMP is configured directly inside these daemons as maximum-paths N
  • For kernel bypass use DPDK or XDP
  • To encapsulate packets sent between LB and service instance (backend) make a use of standard methods: IPIP, GRE
    • note that you cannot use ip tunnel, because this means going through the full network stack, so you need to add outer headers directly inside XDP/DPDK

System that use ideas from Maglev

Takeaways

  • Small inconsistency resulting in error is fine, if solving this inconsistency incurs trade-off with speed (because of synchronization, for example), given the clients can retry.
  • Separate fast path from the control path (data plane vs. control plane)