Fundamentos: por qué round-robin falla

Round-robin asume que todos los requests cuestan lo mismo y todos los backends tienen la misma capacidad. Ninguna de las dos cosas es cierta en la práctica.

# simulation.py - Por qué round-robin falla con latencia variable
import random
import statistics
from dataclasses import dataclass, field

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

def simulate_round_robin(backends, requests):
 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
 backend.active = max(0, backend.active - 1)
 idx += 1

def simulate_least_conn(backends, requests):
 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)

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)

# Output típico:
# Round Robin: p99 rango = 142.3ms - 148.7ms (todos los backends sufren igual)
# Least Conn: p99 rango = 4.8ms - 7.2ms (requests lentos concentrados)

Consistent Hashing: El Problema de Localidad de Cache

Consistent hashing mapea tanto keys como servidores a un anillo. Una key es servida por el siguiente servidor en sentido horario. Cuando se agrega o elimina un servidor, solo las keys que estaban asignadas a él se remapean.

El problema: hot keys. Si el 30% de tu tráfico pega en una sola cache key, consistent hashing manda el 30% del tráfico a un solo backend.

Consistent Hashing con Cargas Acotadas

El paper de Google de 2017 introdujo un fix: poner un tope a la carga máxima de cualquier backend. Cuando un backend alcanza su límite, el request se derrama al siguiente nodo del anillo.

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
 }
 }
 return ch.nodes[ch.ring[idx]]
}

Con epsilon = 0.25, ningún backend recibe más del 125% de la carga promedio.

Maglev Hashing: El Algoritmo de Producción de Google

Maglev genera una tabla de lookup donde cada entrada mapea a un backend. La construcción de la tabla asegura mínima disrupción cuando los backends cambian.

# maglev.py
def maglev_table(backends: list[str], table_size: int = 65537) -> list[int]:
 n = len(backends)
 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)

 table = [-1] * table_size
 next_idx = [0] * n
 filled = 0

 while filled < table_size:
 for i in range(n):
 while table[permutations[i][next_idx[i]]] != -1:
 next_idx[i] += 1
 table[permutations[i][next_idx[i]]] = i
 next_idx[i] += 1
 filled += 1
 if filled == table_size:
 break
 return table

La ventaja de Maglev sobre consistent hashing basado en anillo: uniformidad casi perfecta.

Power of Two Choices (P2C)

P2C es hermosamente simple: en vez de elegir un backend aleatorio, elegir dos backends aleatorios y mandá el request al que tenga menos conexiones activas.

El resultado teórico es notable: selección aleatoria da O(log n / log log n) de carga máxima, pero P2C da O(log log n). Esa elección extra reduce exponencialmente el peor caso.

Configuraciones Reales de Producción

HAProxy

# Backend con least connections - para API con latencia variable
backend api_servers
 balance leastconn
 option httpchk GET /health
 http-check expect status 200
 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 50 # Instancia más chica

# Backend con consistent hashing + cargas acotadas - para afinidad de cache
backend cache_servers
 balance uri
 hash-type consistent sdbm
 hash-balance-factor 150
 server cache-1 10.0.2.10:8080 check
 server cache-2 10.0.2.11:8080 check

# Backend con P2C - para cargas de trabajo generales
backend web_servers
 balance random(2)
 server web-1 10.0.3.10:8080 check
 server web-2 10.0.3.11:8080 check

Envoy

clusters:
 - name: api_cluster
 lb_policy: LEAST_REQUEST
 least_request_lb_config:
 choice_count: 3 # P3C - elegir el mejor de 3
 - name: cache_cluster
 lb_policy: RING_HASH
 ring_hash_lb_config:
 minimum_ring_size: 1024
 hash_function: XX_HASH
 - name: websocket_cluster
 lb_policy: LEAST_REQUEST
 common_lb_config:
 healthy_panic_threshold:
 value: 50

El healthy_panic_threshold para backends de WebSocket es crítico. Sin él, si dos de cuatro backends fallan health checks, Envoy solo manda tráfico a los dos sanos, que podrían sobrecargarse. Con el threshold en 50%, si más de la mitad falla, Envoy manda tráfico a todos (incluyendo los "unhealthy") bajo la teoría de que servicio parcial es mejor que falla en cascada.

Recomendaciones Prácticas

Después de correr estos algoritmos en producción con diferentes cargas de trabajo, los siguientes defaults emergen:

  • APIs HTTP stateless: leastconn (HAProxy) o LEAST_REQUEST con choice_count: 2 (Envoy).
  • Capas de cache: Consistent hashing con cargas acotadas.
  • WebSocket/gRPC streams: Least connections, siempre.
  • Tráfico web general: P2C.

P2C es quizás el algoritmo más impactante en esta comparación. La realización de que una elección aleatoria extra puede reducir exponencialmente la carga del peor caso es un insight poderoso. Usar random(2) en HAProxy para cualquier backend sin una razón fuerte para usar otra cosa es un default pragmático.