Load Balancing Algorithms: Maglev Hashing, Consistent Hashing with Bounded Loads, and P2C

Fundamentals: Why Round-Robin Fails

Before examining Maglev and P2C, it is useful to establish why round-robin fails in real-world scenarios.

Round-robin assumes all requests cost the same and all backends have the same capacity. Neither is true in practice. A request that triggers a cache miss takes 10x longer than a cache hit. A backend running on a c5.xlarge handles twice the load of a t3.medium. Round-robin ignores both factors.

# simulation.py - Why round-robin fails with variable latency
import random
import statistics
from dataclasses import dataclass, field

@dataclass
class Backend:
 name: str
 capacity: int # max concurrent requests
 active: int = 0
 total_served: int = 0
 latencies: list = field(default_factory=list)

def simulate_round_robin(backends: list[Backend], requests: int):
 idx = 0
 for _ in range(requests):
 backend = backends[idx % len(backends)]
 latency = random.expovariate(1/50) if random.random() < 0.1 else random.expovariate(1/2)
 backend.active += 1
 backend.total_served += 1
 backend.latencies.append(latency)
 if backend.active > backend.capacity:
 backend.latencies[-1] *= 3 # Overloaded penalty
 backend.active = max(0, backend.active - 1)
 idx += 1

def simulate_least_conn(backends: list[Backend], requests: int):
 for _ in range(requests):
 backend = min(backends, key=lambda b: b.active)
 latency = random.expovariate(1/50) if random.random() < 0.1 else random.expovariate(1/2)
 backend.active += 1
 backend.total_served += 1
 backend.latencies.append(latency)
 if backend.active > backend.capacity:
 backend.latencies[-1] *= 3
 backend.active = max(0, backend.active - 1)

# Run simulation
rr_backends = [Backend(f"rr-{i}", capacity=50) for i in range(5)]
lc_backends = [Backend(f"lc-{i}", capacity=50) for i in range(5)]

simulate_round_robin(rr_backends, 10000)
simulate_least_conn(lc_backends, 10000)

for label, backends in [("Round Robin", rr_backends), ("Least Conn", lc_backends)]:
 p99s = [statistics.quantiles(b.latencies, n=100)[98] for b in backends]
 print(f"{label}: p99 range = {min(p99s):.1f}ms - {max(p99s):.1f}ms")
# Typical output:
# Round Robin: p99 range = 142.3ms - 148.7ms (all backends suffer equally)
# Least Conn: p99 range = 4.8ms - 7.2ms (slow requests concentrated)

Consistent Hashing: The Cache Locality Problem

Consistent hashing maps both keys and servers onto a ring. A key is served by the next server clockwise on the ring. When a server is added or removed, only the keys that were assigned to it get remapped, the rest stay put.

The classic implementation uses virtual nodes to improve distribution:

// consistent_hash.go
package lb

import (
 "hash/crc32"
 "sort"
 "strconv"
 "sync"
)

type ConsistentHash struct {
 mu sync.RWMutex
 ring []uint32
 nodes map[uint32]string
 vnodeCount int
}

func NewConsistentHash(vnodes int) *ConsistentHash {
 return &ConsistentHash{
 nodes: make(map[uint32]string),
 vnodeCount: vnodes,
 }
}

func (ch *ConsistentHash) hash(key string) uint32 {
 return crc32.ChecksumIEEE([]byte(key))
}

func (ch *ConsistentHash) AddNode(node string) {
 ch.mu.Lock()
 defer ch.mu.Unlock()

 for i := 0; i < ch.vnodeCount; i++ {
 vkey := node + "#" + strconv.Itoa(i)
 h := ch.hash(vkey)
 ch.ring = append(ch.ring, h)
 ch.nodes[h] = node
 }
 sort.Slice(ch.ring, func(i, j int) bool { return ch.ring[i] < ch.ring[j] })
}

func (ch *ConsistentHash) GetNode(key string) string {
 ch.mu.RLock()
 defer ch.mu.RUnlock()

 if len(ch.ring) == 0 {
 return ""
 }

 h := ch.hash(key)
 idx := sort.Search(len(ch.ring), func(i int) bool { return ch.ring[i] >= h })
 if idx == len(ch.ring) {
 idx = 0
 }
 return ch.nodes[ch.ring[idx]]
}

The problem: hot keys. If 30% of your traffic hits a single cache key, consistent hashing sends 30% of traffic to one backend. That backend melts while the others idle.

Consistent Hashing with Bounded Loads

Google's 2017 paper introduced a fix: cap the maximum load any backend can receive. When a backend reaches its bound, the request spills to the next node on the ring.

// bounded_consistent_hash.go
func (ch *BoundedConsistentHash) GetNode(key string, loads map[string]int, avgLoad float64, epsilon float64) string {
 ch.mu.RLock()
 defer ch.mu.RUnlock()

 maxLoad := int(avgLoad * (1 + epsilon))

 h := ch.hash(key)
 idx := sort.Search(len(ch.ring), func(i int) bool { return ch.ring[i] >= h })

 for i := 0; i < len(ch.ring); i++ {
 nodeIdx := (idx + i) % len(ch.ring)
 node := ch.nodes[ch.ring[nodeIdx]]

 if loads[node] < maxLoad {
 return node
 }
 // This node is at capacity, try the next one on the ring
 }

 // All nodes at capacity (shouldn't happen with proper epsilon)
 return ch.nodes[ch.ring[idx]]
}

With epsilon = 0.25, no backend gets more than 125% of the average load. You lose some consistency (hot-key requests might land on different backends during spikes), but you prevent the worst-case scenario.

Maglev Hashing: Google's Production Algorithm

Maglev is Google's hashing algorithm used in their network load balancer. It generates a lookup table where each entry maps to a backend. The table construction ensures minimal disruption when backends change.

# maglev.py - Simplified Maglev lookup table generation
def maglev_table(backends: list[str], table_size: int = 65537) -> list[int]:
 """
 Generate a Maglev lookup table.
 table_size should be a prime number > len(backends).
 """
 n = len(backends)

 # Generate permutation for each backend
 # offset and skip determine each backend's preferred positions
 permutations = []
 for backend in backends:
 h1 = hash(backend + "_offset") % table_size
 h2 = (hash(backend + "_skip") % (table_size - 1)) + 1
 perm = [(h1 + j * h2) % table_size for j in range(table_size)]
 permutations.append(perm)

 # Fill the table using the permutation preferences
 table = [-1] * table_size
 next_idx = [0] * n # Track each backend's next preferred position
 filled = 0

 while filled < table_size:
 for i in range(n):
 # Find backend i's next unfilled preferred position
 while table[permutations[i][next_idx[i]]] != -1:
 next_idx[i] += 1
 # Claim that position
 table[permutations[i][next_idx[i]]] = i
 next_idx[i] += 1
 filled += 1
 if filled == table_size:
 break

 return table

# Usage
backends = ["web-1", "web-2", "web-3", "web-4", "web-5"]
table = maglev_table(backends)

# Lookup: hash the request key, index into the table
def get_backend(key: str, table: list[int], backends: list[str]) -> str:
 idx = hash(key) % len(table)
 return backends[table[idx]]

# When web-3 is removed, regenerate the table
# Only ~1/n of entries change (compared to modular hashing where everything shifts)
remaining = ["web-1", "web-2", "web-4", "web-5"]
new_table = maglev_table(remaining)

Maglev's advantage over ring-based consistent hashing: nearly perfect uniformity. With virtual nodes, ring-based hashing still has variance. Maglev fills a lookup table round-robin style per backend, so the distribution is almost exactly even.

Power of Two Choices (P2C)

P2C is elegantly simple: instead of picking one random backend, pick two random backends and send the request to whichever has fewer active connections.

The theoretical result is remarkable: random selection gives O(log n / log log n) max load, but P2C gives O(log log n) max load. That extra random choice exponentially reduces the worst case.

# p2c.py - Power of Two Choices
import random

class P2CBalancer:
 def __init__(self, backends: list[str]):
 self.backends = backends
 self.active_connections = {b: 0 for b in backends}

 def pick(self) -> str:
 """Pick the less-loaded of two random backends."""
 if len(self.backends) < 2:
 return self.backends[0]

 a, b = random.sample(self.backends, 2)

 if self.active_connections[a] <= self.active_connections[b]:
 chosen = a
 else:
 chosen = b

 self.active_connections[chosen] += 1
 return chosen

 def release(self, backend: str):
 self.active_connections[backend] = max(0, self.active_connections[backend] - 1)

Real Production Configurations

HAProxy

# haproxy.cfg - Production load balancing configuration

global
 maxconn 50000
 log stdout local0

defaults
 mode http
 timeout connect 5s
 timeout client 30s
 timeout server 30s
 option httplog
 option forwardfor

# Backend with least connections - for API with variable latency
backend api_servers
 balance leastconn
 option httpchk GET /health
 http-check expect status 200

 # Slow start: new backends ramp up over 30 seconds
 default-server inter 3s fall 3 rise 2 slowstart 30s

 server api-1 10.0.1.10:8080 check weight 100
 server api-2 10.0.1.11:8080 check weight 100
 server api-3 10.0.1.12:8080 check weight 100
 server api-4 10.0.1.13:8080 check weight 50 # Smaller instance

# Backend with consistent hashing + bounded loads - for cache affinity
backend cache_servers
 balance uri
 hash-type consistent sdbm
 hash-balance-factor 150 # No backend gets >150% of average

 option httpchk GET /health
 http-check expect status 200

 server cache-1 10.0.2.10:8080 check
 server cache-2 10.0.2.11:8080 check
 server cache-3 10.0.2.12:8080 check
 server cache-4 10.0.2.13:8080 check

# Backend with P2C - for general workloads
backend web_servers
 balance random(2) # Power of two choices

 option httpchk GET /health
 http-check expect status 200

 server web-1 10.0.3.10:8080 check
 server web-2 10.0.3.11:8080 check
 server web-3 10.0.3.12:8080 check

frontend http_front
 bind *:80
 bind *:443 ssl crt /etc/ssl/cert.pem

 acl is_api path_beg /api/
 acl is_cached path_beg /products/ /categories/

 use_backend api_servers if is_api
 use_backend cache_servers if is_cached
 default_backend web_servers

Envoy

# envoy.yaml - Envoy proxy with multiple LB policies
static_resources:
 clusters:
 - name: api_cluster
 type: STRICT_DNS
 lb_policy: LEAST_REQUEST
 least_request_lb_config:
 choice_count: 3 # P3C - pick best of 3
 health_checks:
 - timeout: 2s
 interval: 5s
 unhealthy_threshold: 3
 healthy_threshold: 2
 http_health_check:
 path: /health
 load_assignment:
 cluster_name: api_cluster
 endpoints:
 - lb_endpoints:
 - endpoint:
 address:
 socket_address:
 address: api-1.internal
 port_value: 8080
 - endpoint:
 address:
 socket_address:
 address: api-2.internal
 port_value: 8080

 - name: cache_cluster
 type: STRICT_DNS
 lb_policy: RING_HASH
 ring_hash_lb_config:
 minimum_ring_size: 1024
 maximum_ring_size: 8388608
 hash_function: XX_HASH
 health_checks:
 - timeout: 2s
 interval: 5s
 http_health_check:
 path: /health
 load_assignment:
 cluster_name: cache_cluster
 endpoints:
 - lb_endpoints:
 - endpoint:
 address:
 socket_address:
 address: cache-1.internal
 port_value: 8080
 - endpoint:
 address:
 socket_address:
 address: cache-2.internal
 port_value: 8080

 - name: websocket_cluster
 type: STRICT_DNS
 lb_policy: LEAST_REQUEST
 common_lb_config:
 healthy_panic_threshold:
 value: 50 # If <50% backends healthy, use all
 load_assignment:
 cluster_name: websocket_cluster
 endpoints:
 - lb_endpoints:
 - endpoint:
 address:
 socket_address:
 address: ws-1.internal
 port_value: 8080
 load_balancing_weight: 100
 - endpoint:
 address:
 socket_address:
 address: ws-2.internal
 port_value: 8080
 load_balancing_weight: 100

The choice_count: 3 in Envoy's LEAST_REQUEST config gives you P3C, pick the best of three random backends. Research shows P3C gives marginal improvement over P2C, but it's free in Envoy so why not.

The healthy_panic_threshold for WebSocket backends is critical. Without it, if two of four backends fail health checks, Envoy only sends traffic to the two healthy ones, which might overload them. With the panic threshold at 50%, if more than half the backends fail, Envoy sends traffic to all of them (including "unhealthy" ones) on the theory that partial service is better than cascading failure.

Practical Recommendations

After running these algorithms in production across different workloads, the following defaults emerge:

• Stateless HTTP APIs: leastconn (HAProxy) or LEAST_REQUEST with choice_count: 2 (Envoy). Simple, effective, handles variable latency gracefully.
• Cache layers: Consistent hashing with bounded loads. HAProxy's hash-balance-factor or a custom implementation. Cache hit rates matter enough to justify the complexity.
• WebSocket/gRPC streams: Least connections, always. Long-lived connections need to balance by connection count, not by request count.
• General web traffic: P2C. Almost as good as least connections, but without the overhead of tracking connection counts across all proxies in a distributed setup.

P2C is perhaps the most impactful algorithm in this comparison. The realization that one extra random choice can exponentially reduce worst-case load is a powerful insight. Using random(2) in HAProxy for any backend without a strong reason to use something else is a pragmatic default.