Maglev hashing

Deep dive

How it works

In: backend names (build), packet 5-tuple (lookup) · Out: the chosen backend · State: a table of M entries (M prime) holding backend ids · Cost: lookup O(1); build O(M log M) expected

1. For each backend i: offset = h1(name) mod M, skip = h2(name) mod (M−1) + 1. Its preference list is perm_i[j] = (offset + j·skip) mod M, a full permutation because M is prime.
2. Round-robin over backends: each takes the next slot in its list that is still empty. Stop when all M slots are filled.
3. Lookup: backend = table[h(5-tuple) mod M].
4. On a backend change, rebuild the table (milliseconds) and swap it in atomically; packets of existing flows hit the connection-tracking table first.

M = 7, backends A(offset 3, skip 4), B(offset 0, skip 2), C(offset 3, skip 1)
perm A: 3 0 4 1 5 2 6     perm B: 0 2 4 6 1 3 5     perm C: 3 4 5 6 0 1 2
round 1: A→3  B→0  C→4      round 2: A→1 (0,4 taken)  B→2  C→5
round 3: A→6 (5,2 taken)    table: [B A B A C C A]

Code

/// Maglev lookup table (Eisenbud et al., NSDI 2016). Hash must be stable across machines.
fn fnv1a(seed: u64, data: &[u8]) -> u64 {
    let mut h = 0xcbf2_9ce4_8422_2325 ^ seed;
    for &b in data { h ^= b as u64; h = h.wrapping_mul(0x100_0000_01b3); }
    h ^ (h >> 32) // FNV's low bits are weak; fold the high half in
}

pub struct Maglev { table: Vec<u32>, m: u64 }

impl Maglev {
    /// `backends` must be in the same order on every balancer (sort by name).
    pub fn new(backends: &[&str], m: u64) -> Self {
        assert!(!backends.is_empty() && m > backends.len() as u64);
        let n = backends.len();
        let offset: Vec<u64> = backends.iter().map(|b| fnv1a(0x9e37_79b9, b.as_bytes()) % m).collect();
        let skip: Vec<u64> = backends.iter().map(|b| fnv1a(0x85eb_ca6b, b.as_bytes()) % (m - 1) + 1).collect();
        let mut next = vec![0u64; n];
        let mut table = vec![u32::MAX; m as usize];
        let mut filled = 0u64;
        loop {
            for i in 0..n {
                // Walk backend i's permutation lazily; never materialize N x M.
                let mut c = (offset[i] + next[i] * skip[i]) % m;
                while table[c as usize] != u32::MAX {
                    next[i] += 1;
                    c = (offset[i] + next[i] * skip[i]) % m;
                }
                table[c as usize] = i as u32;
                next[i] += 1;
                filled += 1;
                if filled == m { return Maglev { table, m }; }
            }
        }
    }

    #[inline]
    pub fn lookup(&self, flow_hash: u64) -> u32 { self.table[(flow_hash % self.m) as usize] }
}

pub fn flow_hash(src: [u8; 4], dst: [u8; 4], sport: u16, dport: u16, proto: u8) -> u64 {
    let mut k = [0u8; 13];
    k[..4].copy_from_slice(&src);
    k[4..8].copy_from_slice(&dst);
    k[8..10].copy_from_slice(&sport.to_be_bytes());
    k[10..12].copy_from_slice(&dport.to_be_bytes());
    k[12] = proto;
    fnv1a(0, &k)
}

#[test]
fn balanced_and_stable() {
    let names: Vec<String> = (0..100).map(|i| format!("10.0.0.{i}:443")).collect();
    let refs: Vec<&str> = names.iter().map(|s| s.as_str()).collect();
    let t = Maglev::new(&refs, 65_537);
    let mut count = vec![0u32; 100];
    for &b in &t.table { count[b as usize] += 1; }
    assert!(count.iter().all(|&c| c == 655 || c == 656));
    let t2 = Maglev::new(&refs[..99], 65_537); // remove the last backend
    let moved = t.table.iter().zip(&t2.table).filter(|(a, b)| a != b && **a != 99).count();
    assert!(moved < 65_537 / 50); // well under 2 % extra churn
}

Complexity and constants

• Lookup: one hash of the 5-tuple plus one read from a 256 KB table (M = 65537, u32 ids): L2-resident, order of 5-20 ns.
• Build: expected O(M log M) probes (coupon-collector tail as the table fills); for M = 65537 that is order of 1M probes, about 1-10 ms. Rebuild off the packet path and swap a pointer.
• Memory: M · 4 bytes per service; with 1000s of services (VIPs), use u16 ids or smaller M per VIP.
• Imbalance bound: (⌈M/N⌉ − ⌊M/N⌋)/(M/N) ≤ N/M, so M ≥ 100·N keeps it ≤ 1 %.

Efficiency

• Cost: lookup is one hash of the 5-tuple and one read of a table entry: M = 65537 with u32 ids is 256 KB, L2-resident, order of 5-20 ns. Build is order of 1M probes, about 1-10 ms for M = 65537, done off the packet path with a pointer swap. Memory is M x 4 bytes per service. The bound is memory latency on the table read (compute for the hash), not bandwidth.
• Levers:
  • u16 ids or smaller M per VIP — halves or shrinks the table (Complexity) — thousands of VIPs.
  • Per-core connection table before the Maglev table — keeps existing flows on their backend through changes (Eisenbud et al., NSDI 2016) — any churn in the backend set.
  • M >= 100 x N — imbalance at most 1 % (Complexity) — sizing the table.
  • XDP/eBPF data path with encapsulation and direct server return — replies skip the balancer (Katran) — high-bandwidth services.
• Naive → standard → state of the art:
  • hash(key) mod N · O(1), but removing one backend remaps almost every flow.
  • Ring consistent hashing (Karger et al. 1997) · minimal remapping, O(log n) lookup, 100s of virtual nodes for balance.
  • Maglev table plus connection tracking · O(1) lookup, near-even load, small disruption on change (Maglev, NSDI 2016).

Implementation notes

• Table size: Google's paper uses M = 65537 (and 655373 for larger backend sets); Envoy defaults to 65537, Cilium to 16381.
• Weights: let a backend take a turn proportionally to its weight (skip its turn while next_turn_credit < 1); Envoy and Katran implement weighted variants.
• Connection tracking: per-core flow table keyed by 5-tuple → backend, consulted first; Maglev hashing is the fallback that makes misses consistent across balancers.
• QUIC: hash the connection ID (with a server-chosen routing prefix), not the 5-tuple, or migration breaks affinity.
• Encapsulate to the backend (GRE/GUE/IPIP) and use direct server return so replies bypass the balancer.

Pitfalls

• Using a process-seeded hash (Rust RandomState, Go map hash) for h1/h2: each balancer builds a different table and flows break.
• Different backend order on different machines: ties are broken by iteration order, so tables diverge. Sort by name.
• Non-prime M: skip values sharing a factor with M give short cycles and the build loops forever.
• Health-check flapping rebuilds the table repeatedly; the extra churn from each rebuild breaks flows not in the connection table. Dampen with hysteresis.
• Hashing on source IP only: NAT gateways concentrate thousands of clients on one backend.

Variants and alternatives

In production

Google Maglev (front-end L4 load balancing), Meta Katran (XDP), Cilium kube-proxy replacement (loadBalancer.algorithm=maglev), Envoy (MAGLEV load-balancing policy), Google Cloud Load Balancing.

Implementations

Sources

• Eisenbud et al., Maglev: A Fast and Reliable Software Network Load Balancer, USENIX NSDI, 2016. paper
• Karger et al., Consistent Hashing and Random Trees, ACM STOC, 1997. paper
• Envoy Proxy documentation, Load balancing: Maglev.