Skip to content

Maglev Hashing

Google's Maglev is a specialized consistent hashing algorithm engineered for high-throughput, software-based Layer 4 load balancing. Standard load balancing hashing mechanisms (such as simple modulo or basic 5-tuple hashing) encounter severe limitations when the pool of backend targets scales or experiences host failures.

When backend targets are added or removed in traditional systems, the vast majority of existing connections get remapped to different servers. This triggers massive state disruptions across active TCP connections.

Maglev solves this problem by generating a uniform lookup table that minimizes connection remappings during topology changes.

Key Benefits

  • Minimal Connection Disruption: When a backend host fails or scales down, only the connections specifically mapped to that host are redistributed (\(1/N\)). All other connections stay mapped to their original backend.
  • Uniform Load Distribution: Traffic is spread across available backends evenly, preventing "hotspots" or imbalanced node resource consumption.
  • Low Computational Overhead: By decoupling connection table generation from real-time packet processing, Maglev enables kernel-level load balancers to route millions of packets per second with negligible CPU usage.

In Depth Details

The core mechanism behind Maglev lies in its construction of a fixed-size lookup table (of size \(M\), where \(M\) is a prime number) populated by a set of backend servers (set \(N\)).

[ Backend Server Pool ]
│
▼ (Permutation Generation via Dual Hashing)
[ Permutation Arrays: H1(b), H2(b) ]
│
▼ (Interleaved Lookup Table Population)
[ Maglev Lookup Table (Size M) ]
│
▼ (Packet Lookup)
[ Incoming Connection Hash % M ] ──► [ Assigned Backend ]

1. Permutation Generation

For each backend \(b\), Maglev generates a pseudo-random permutation of the numbers \(0\) through \(M-1\). This permutation determines the preference order in which that backend claims slots in the global lookup table.

The permutation sequence for backend \(b\) is generated using two independent hash functions, \(h_1\) and \(h_2\):

\[\text{Offset} = h_1(b) \pmod M\]
\[\text{Skip} = h_2(b) \pmod {M-1} + 1\]

The \(i\)-th entry in backend \(b\)'s preference list is calculated as:

\[\text{Permutation}[i] = (\text{Offset} + i \times \text{Skip}) \pmod M\]
  • Note: To ensure every slot in the lookup table can be visited, \(M\) must be a prime number, and \(\text{Skip}\) must be coprime to \(M\).

2. Lookup Table Population Algorithm

Once permutation arrays are computed for all healthy backends, Maglev fills the lookup table of size \(M\) using a round-robin interleaved selection process:

  1. Each active backend takes turns attempting to fill a position in the lookup table.
  2. A backend inspects its permutation array sequentially to find its most preferred slot.
  3. If that slot in the lookup table is empty, the backend claims it. If it is already occupied by another backend, the current backend moves to its next preference in its permutation list.
  4. This process repeats until all \(M\) slots in the lookup table are filled.

3. Packet Forwarding Phase

When a packet arrives at the load balancer: 1. The 5-tuple (source IP, destination IP, source port, destination port, protocol) is hashed. 2. The hash value modulo \(M\) yields an index in the Maglev lookup table. 3. The packet is instantly routed to the backend assigned to that specific index.

Because the lookup table remains identical across all load balancer nodes in an active-active cluster, any packet belonging to the same 5-tuple will consistently hit the exact same backend, regardless of which load balancer node receives the ingress packet.

Keepalived Implementation

The Linux kernel incorporates Maglev hashing natively within the IPVS (Linux Virtual Server) framework via the mh (Maglev Hashing) scheduler module. You can configure Keepalived to automatically build and manage IPVS tables using the Maglev algorithm.

Pre-requisites

Ensure the ip_vs_mh kernel module is loaded on the Linux host: 

modprobe ip_vs_mh

Keepalived Configuration (/etc/keepalived/keepalived.conf)

Set the load balancing algorithm (lb_algo) to mh inside the virtual_server definition: 

global_defs {
    router_id LB_NODE_01
    enable_script_security
}

# Configure IPVS with Maglev Hashing (mh)
virtual_server 192.168.100.1 80 {
    delay_loop 3
    lb_algo mh               # Enables Maglev Consistent Hashing in IPVS
    lb_kind NAT              # Supports NAT, DR, or TUN modes
    protocol TCP

    # Optional flag for flag-based tuning (e.g., fallback options)
    # lvs_sched_flags fallback

    real_server 10.0.1.11 80 {
        weight 100
        TCP_CHECK {
            connect_port 80
            connect_timeout 3
            retry 3
            delay_before_retry 2
        }
    }

    real_server 10.0.1.12 80 {
        weight 100
        TCP_CHECK {
            connect_port 80
            connect_timeout 3
            retry 3
            delay_before_retry 2
        }
    }

    real_server 10.0.1.13 80 {
        weight 100
        TCP_CHECK {
            connect_port 80
            connect_timeout 3
            retry 3
            delay_before_retry 2
        }
    }
}

Verification

Confirm that IPVS is running with the Maglev scheduler: 

sudo ipvsadm -Ln

Key Parameters Discussion

Configuring Maglev consistent hashing effectively requires balancing lookup table granularity against computational overhead and memory consumption. In Linux IPVS implementations (such as through Keepalived), specific kernel modules expose parameters like maglev and maglev_port to fine-tune how traffic is hashed and distributed.

Core Mathematical & Algorithmic Parameters

Lookup Table Size (\(M\))

The table size \(M\) is the primary parameter governing Maglev performance and load distribution accuracy.

  • Prime Number Requirement: \(M\) must be a prime number. This guarantees that during permutation generation, the skip step length is coprime to \(M\), allowing full coverage of the array without getting stuck in infinite loops.
  • Load Balance Uniformity: Larger values of \(M\) yield significantly better, more uniform load distribution across backends (closer to an ideal \(1/N\) spread).
  • Sizing Rule of Thumb: Set \(M\) to a prime number significantly larger than the total count of backend servers \(N\) (\(M > 100 \times N\)). Common production values in kernel LVS setups are \(M = 65537\) or \(M = 1000003\).
  • Trade-off: Larger values of \(M\) marginally increase initial table generation time and memory footprint, though runtime lookup speed remains a fast \(O(1)\) operation.

Backend Weights

Maglev natively supports weighted backends by altering how many slots a server can claim during each iteration of the interleaved population algorithm.

  • Operation: A backend with weight=200 claims twice as many positions in the lookup table per allocation cycle compared to a host with weight=100.
  • Impact: Enables heterogeneous host deployments, allowing higher-capacity servers to take a proportionally larger share of incoming traffic without altering the consistent hashing characteristics.

Linux IPVS Parameters: maglev vs. maglev_port

In IPVS, the Maglev scheduler algorithm (mh) provides flags to determine which elements of an incoming packet's 5-tuple are included in the hashing function. These flags directly impact connection persistence and traffic distribution across backend servers.

maglev (Default Hashing Mode)

The standard maglev parameter configures the scheduler to compute the lookup hash using a 3-Tuple (or Source IP / Target IP only) depending on the exact kernel flag variant.

  • Hashing Elements: Source IP Address, Destination IP Address, and Protocol.
  • Behavior: All incoming packets originating from the same source IP address heading to the same Virtual IP (VIP) will map to the exact same backend server, regardless of the client port or destination port.
  • Use Cases:
  • Session Persistence: Ideal for multi-port applications or scenarios where client connections across multiple ports (e.g., HTTP on 80 and HTTPS on 443) must land on the same physical backend server.
  • Stateful Applications: Helps maintain client state on backends without needing external shared session storage like Redis.
  • Drawback: High-density NAT environments (e.g., thousands of users behind a single corporate gateway IP) will send all traffic to a single backend, creating severe traffic hotspots.

maglev_port (Port-Aware Hashing Mode)

The maglev_port flag extends the hashing input to include the full 5-Tuple, incorporating transport-layer port numbers into the Maglev lookup function.

  • Hashing Elements: Source IP Address, Source Port, Destination IP Address, Destination Port, and Protocol.
  • Behavior: Different TCP/UDP connections originating from the same source IP address will hash to different slots in the Maglev table if their source or destination ports differ.
  • Use Cases:
  • Large Carrier NAT / CGNAT Environments: Distributes connections evenly across the backend pool even when millions of requests originate from a small pool of shared public proxy IPs.
  • Stateless Microservices: Excellent for high-throughput, stateless web services where maximum connection spreading across all backends is preferred over client IP stickiness.
  • Drawback: Breaks IP-based affinity. Two concurrent connections from the same user machine may be routed to different backend instances.

Summary Comparison Matrix

  • Lookup Table Size (\(M\)): Governs lookup array granularity and load balancing uniformity. Must be a prime number.
  • Backend Weights: Controls relative capacity allocation per server during lookup table generation.
  • maglev: Hashes IP addresses only. Ensures client IP stickiness across ports at the expense of potential hotspotting behind large NAT gateways.
  • maglev_port: Hashes the full 5-tuple (including ports). Maximizes uniform distribution across all backends but breaks single-client IP stickiness.