Adaptive Minimum-Score Estimation (AME): A New Load Balancing Algorithm for Nginx and OpenResty — An Empirical Study of Latency, Throughput, and Tail-Latency Reduction Under Heterogeneous Workloads

Abstract

Modern web infrastructure rarely looks the way load balancing textbooks describe it. In the real world, back-end servers differ in CPU generation, memory headroom, JVM warm-up state, and container resource limits. They pause for garbage collection at unpredictable moments, slow down when the cloud scheduler throttles their CPU credits, and sometimes recover just fast enough to fool a naive health check before slowing down again. Against this backdrop, the conventional Nginx load balancing options — round-robin, least-connections, IP hash — were designed for a simpler world and show their age under genuinely heterogeneous conditions.
This paper introduces Adaptive Minimum-Score Estimation (AME), a new load balancing algorithm implemented as an OpenResty Lua module. AME maintains a per-upstream exponentially weighted moving average (EWMA) of observed response latency, applies a concurrency penalty to discourage piling traffic onto nodes that are already busy, and incorporates a staleness correction to handle nodes that have been idle long enough that their cached latency estimate may no longer be trustworthy. The result is a routing decision that reflects what the back-end pool is actually doing right now, rather than what it was doing when someone last tuned the static weights.
We evaluated AME on a containerized eight-node test cluster across five workload profiles: uniform cost, heavy-tail request cost, periodic JVM garbage collection pauses, CPU-throttled minority nodes, and bursty arrival rates. Compared to Nginx round-robin, AME reduced mean response latency by 18–41 percent and 99th-percentile tail latency by 31–53 percent. Throughput improved by 9–21 percent. The per-request overhead introduced by the Lua implementation was under 30 microseconds at all tested request rates, making it negligible in practice. We describe the algorithm in full, walk through the OpenResty implementation, and discuss the practical considerations any team would need to think through before deploying it.