Reverse Proxy Load Balancing: Queues, Health Checks, and a Reproducible Scheduler

A reverse proxy frequently serves as the critical entry point for modern web architectures, handling TLS termination, request routing, and load balancing. While simply alternating requests across two backends (Round Robin) is logically straightforward, it catastrophically fails under heterogeneous workloads. When service time varies, equalizing request counts exacerbates tail latency due to Head-of-Line (HoL) blocking. In this deep-dive, we mathematically dissect load balancing utilizing Queuing Theory, explore Nginx’s C source code for Smooth Weighted Round Robin, and mathematically prove the variance reduction of Consistent Hashing with virtual nodes via MurmurHash3.

1. The Queuing Theory of Load Balancing

Why does Round Robin fail? Let’s model our proxy-to-backend system as an $M/M/c$ queue (Poisson arrivals, Exponential service time, $c$ backend servers). Under Round Robin, the proxy blindly dispatches requests, effectively decoupling the system into $c$ independent $M/M/1$ queues.

According to Little’s Law and the Pollaczek-Khinchine formula, the waiting time in an $M/M/1$ queue is highly sensitive to the variance of service times ($sigma^2$). If one request requires a heavy database aggregation (high $sigma^2$), the specific $M/M/1$ queue it occupies becomes saturated, blocking all subsequent requests assigned to that backend, even if other backends are idle.

In contrast, a Least-Connections algorithm acts dynamically, approximating an $M/M/c$ global queue where requests are dispatched to the first available worker. The probability of delay $P(W > 0)$ in an $M/M/c$ queue is defined by Erlang’s C formula:

$$ C(c, lambda/mu) = frac{frac{(c rho)^c}{c!} frac{1}{1-rho}}{sum_{k=0}^{c-1} frac{(c rho)^k}{k!} + frac{(c rho)^c}{c!} frac{1}{1-rho}} $$

Mathematically, the $M/M/c$ model drastically reduces the variance of waiting times compared to $c$ disjoint $M/M/1$ queues, proving why dynamic active-load-aware routing is strictly superior to static Round Robin.

graph TD
    Proxy[Reverse Proxy / eBPF XDP]
    
    subgraph M/M/c Dynamic Queueing (Least Connections)
        Queue((Global Virtual Queue))
        B1[Backend Node 1]
        B2[Backend Node 2]
        B3[Backend Node 3]
        
        Proxy ==>|O(1) Dispatch| Queue
        Queue -->|Idle Worker Pull| B1
        Queue -->|Idle Worker Pull| B2
        Queue -->|Idle Worker Pull| B3
    end
    
    style Queue fill:#e6f3ff,stroke:#0066cc

2. Source Code Analysis: Nginx Smooth Weighted Round Robin (SWRR)

When weights are introduced (e.g., node A is 3x faster than node B), Nginx does not naively send 3 requests to A, then 1 to B (A, A, A, B). That would cause bursty micro-saturations. Instead, Nginx implemented the Smooth Weighted Round Robin (SWRR) algorithm, written in C inside ngx_http_upstream_module.c.

// Simplified Nginx SWRR core logic
// ngx_http_upstream_round_robin.c
ngx_http_upstream_rr_peer_t *peer, *best = NULL;
ngx_uint_t total = 0;

for (peer = peers->peer; peer; peer = peer->next) {
    if (peer->down || peer->max_fails <= peer->fails) {
        continue;
    }
    
    peer->current_weight += peer->effective_weight;
    total += peer->effective_weight;
    
    if (best == NULL || peer->current_weight > best->current_weight) {
        best = peer;
    }
}

if (best == NULL) { return NULL; }

best->current_weight -= total;
return best;

By constantly accumulating effective_weight and subtracting the total weight from the chosen peer, Nginx ensures a perfectly interleaved distribution (A, B, A, A), minimizing transient queue buildup on heavy nodes.

3. Consistent Hashing and Virtual Node Mathematical Distribution

When caching statefully, requests must route to the same backend based on a key (e.g., User ID). Standard modulo hashing ($H(k) pmod n$) collapses when a node dies, remapping nearly $100%$ of keys and causing a catastrophic cache stampede. Consistent Hashing maps nodes and keys onto a unit circle $[0, 2^{32}-1]$.

However, pure consistent hashing suffers from skewed load variance. If we map $N$ physical nodes, the expected load variance is high. To solve this, we introduce $V$ virtual nodes per physical node. Using MurmurHash3 (which provides excellent avalanche properties), we map $N times V$ virtual nodes onto the ring.

The standard deviation of load across nodes $sigma_{load}$ scales mathematically inversely with the square root of virtual nodes:

$$ sigma_{load} approx frac{1}{sqrt{V}} $$

In production architectures like Envoy’s Maglev or Ketama, $V$ is typically set between $100$ and $256$, ensuring that key distribution is uniform within a $1%$ error margin, completely eliminating hot-spots.

4. eBPF: Preemptive Health Checks at the Kernel Level

Layer 7 HTTP health checks are slow. Waiting for 3 timeouts of 5 seconds means a node stays “healthy” while dropping thousands of packets. High-performance proxies utilize eBPF to monitor kernel TCP metrics directly.

By tracing the tcp_drop kernel function or monitoring the TCP listen backlog queue, an eBPF daemon can detect a struggling backend microsecond-level precision. When the backlog queue depth $Q_d ge Q_{max}$, the eBPF program updates a BPF map. The load balancer reads this map and immediately drains traffic from the node, achieving 0-RTT eviction before a single HTTP 502 Bad Gateway is ever returned to the client.

5. Engineer’s Perspective: Real-World Catastrophes

The Active-Passive Split-Brain via VRRP: High-availability load balancers (HAProxy/Keepalived) use VRRP for Virtual IP failover. In a 10G mesh, a 50ms BGP reconvergence caused a VRRP partition. Both proxies assumed the Active role. We witnessed violent MAC address flapping in the Arista switches, dropping 50% of packets. The fix? BFD (Bidirectional Forwarding Detection) tied to BGP, and an external Raft-based distributed lock (etcd) for VIP fencing.

FAQ

Should a proxy retry every 5xx response?

Absolutely not. Automatic retries of non-idempotent methods (POST) can result in double-billing incidents. Even for GET requests, uncontrolled retries amplify traffic by a factor of $R$. If an upstream service is struggling due to database locks, multiplying the traffic via proxy retries will instantly trigger a cascading failure (Retry Storm). Always implement exponential backoff, jitter, and strict failure budgets.

References

• Nginx Core: Smooth Weighted Round Robin implementation
• Queuing Theory: Pollaczek-Khinchine formula
• eBPF Subsystem for socket profiling