NSDI '24 - Load is not what you should balance: Introducing Prequal

NSDI '24 - Load is not what you should balance: Introducing Prequal
Bartek Wydrowski, Google Research; Robert Kleinberg, Google Research and Cornell; Stephen M. Rumble, Google (KZbin); Aaron Archer, Google Research
We present PReQuaL (Probing to Reduce Queuing and Latency), a load balancer for distributed multi-tenant systems. PReQuaL is designed to minimize real-time request latency in the presence of heterogeneous server capacities and non-uniform, time-varying antagonist load. To achieve this, PReQuaL actively probes server load and leverages the power of d choices paradigm, extending it with asynchronous and reusable probes. Cutting against received wisdom, PReQuaL does not balance CPU load, but instead selects servers according to estimated latency and active requests-in-flight (RIF). We explore the major design features of PReQuaL on a testbed system and describe our experience using it to balance load within KZbin, where it has been running for more than a year. PReQuaL has dramatically decreased tail latency, error rates, and resource use, enabling KZbin and other production systems at Google to run at much higher utilization.
View the full NSDI '24 program at www.usenix.org...