Load Balancing Algorithms: Weighted Round-Robin & Least Connections
Uniform round-robin degrades clusters containing heterogeneous hardware or long-lived websocket connections. Smooth Weighted Round-Robin distributes requests proportional to server CPU capacities, while Least Connections dynamically steers incoming traffic to the backend node managing the fewest active sockets ⚖️⚡🌐.
class WeightedBalancer:
def __init__(self, weights):
self.weights = weights
self.current = {k: 0 for k in weights}
def pick(self):
# NGINX smooth weighted round-robin
total = sum(self.weights.values())
for node, w in self.weights.items():
self.current[node] += w
best = max(self.current, key=self.current.get)
self.current[best] -= total
return best
lb = WeightedBalancer({"core-8c": 3, "edge-2c": 1})
sequence = [lb.pick() for _ in range(4)]
print(f"Smooth Routing: {sequence} 🚀")
# 99. Load Balancing Algorithms: Weighted Round-Robin & Least Connections Treating all server nodes equally is a recipe for catastrophic tail latency. In production, backend instances possess varying CPU topologies (e.g., 64-core bare metal vs 4-core cloud spot instances), and request workloads range from 2ms health checks to 10-minute streaming database exports 🛑. ```python # Load Balancing Comparison: # 1. Round-Robin: Blind 1-2-3 rotation. Flails when servers have unequal specs. # 2. Weighted Round-Robin: Distributes requests proportional to hardware capacity weights. # 3. Least Connections: Dynamically routes to node with min(active_in_flight_sockets). ``` ### The NGINX Smooth Weighted Invariant Naively assigning weights (e.g. Server A = 5, Server B = 1) by sending 5 requests back-to-back to Server A and then 1 to B creates bursty contention on A. The **Smooth Weighted Round-Robin** algorithm interleaves choices cleanly: 1. For each candidate, increment `current_weight += effective_weight`. 2. Select the node with the highest `current_weight`. 3. Decrement the winner's `current_weight -= sum_of_all_weights`. 4. Result: Uniform distribution without clumping bursts! ⚖️⚡ --- ### Interactive Pop-Quiz 🧠 #### Why does the Least Connections algorithm drastically outperform Round-Robin for WebSocket or SSE services? - [ ] Persistent long-lived connections vary wildly in lifespan; Round-Robin blindly overloads nodes with accumulated connections while Least Connections balances the active socket load ⚖️ - [ ] Round-Robin requires root Linux kernel permissions - [ ] Least Connections rewrites HTTP requests into UDP datagrams - [ ] WebSocket connections cannot be routed over TCP --- ### Practical Challenge 🎯 Implement `LoadBalancer` initialized with a dictionary of `{server_id: weight}`. Implement `smooth_weighted_round_robin() -> str` (NGINX algorithm) and `least_connections() -> str` selecting the node with minimum active connections from an internal `active_conns` dict (ties broken by higher weight). Test with `{'srv-a': 5, 'srv-b': 1}`, verify 6 picks yield 5 `'srv-a'` and 1 `'srv-b'`, set active connections to 10 and 2, assert least connection picks `'srv-b'`, and print results. <details> <summary>Solution</summary> ```python class LoadBalancer: def __init__(self, backends: dict[str, int]): self.backends = backends self.current_weights = {k: 0 for k in backends} self.active_conns = {k: 0 for k in backends} def smooth_weighted_round_robin(self) -> str: total_weight = sum(self.backends.values()) for k in self.backends: self.current_weights[k] += self.backends[k] best = max(self.backends.keys(), key=lambda k: self.current_weights[k]) self.current_weights[best] -= total_weight return best def least_connections(self) -> str: return min(self.backends.keys(), key=lambda k: (self.active_conns[k], -self.backends[k])) lb = LoadBalancer({"srv-a": 5, "srv-b": 1}) picks = [lb.smooth_weighted_round_robin() for _ in range(6)] assert picks.count("srv-a") == 5 assert picks.count("srv-b") == 1 lb.active_conns["srv-a"] = 10 lb.active_conns["srv-b"] = 2 best_least = lb.least_connections() assert best_least == "srv-b" print(f"Picks: {picks}, Least Connections: {best_least}") ``` </details>