5 ms·

Load is not what you should balance: Introducing Prequal

173 points by signa11 2y ago

intellix 2y ago
is this available anywhere yet or still not outside of Google? it would be great to test it on our K8S which uses nginx-ingress
cozos 2y ago
The previous policy uses weighted round robin (WRR), which is described as: > weight wi is calculated as qi/ui, where qi and ui represent the recent query-per-second (QPS) rate and CPU utilization of replica i. The pathological case describes a situation where antagonist loads are soaking up CPU on some on the machines, but WRR equally distributes the load because weight formula prioritizes the utilization of the individual tenant, not of the entire machine. Wouldn't including the the machine utilization (probably downweighted) into the WRR formula also solve the issue?
tedd4u 2y ago
A few notes on Power-Of-Two-Choices (Po2C) which is part of the solution described in the paper. NGINX appears to have Po2C available as an option on the "random" balancing algorithm. [1] It only considers load (requests in flight), unlike the paper which also considers recent latency (and does many other things). However NGINX "Plus" (the paid version) appears to have a couple additional settings that use actual traffic as latency probes (not asynchronous synthetic probes as described in the paper). [also 1] It's not fully clear to me but I think if you use these options it's going to only use latency, not load. The paper described in this post actually uses both load (RIF) and latency. Eager to try these out. Also, I noted that HAProxy author and kernel maintainer Willy Tarreau wrote an article in 2019 about adding Power-of-two-choices to HAProxy. [2] He builds a test bed with a few micro services and compares several balancing algorithms to Po2C, considering response time, throughput, and max load. One conclusion is that "At the very least, Power of Two is always better than Random. So, we decided to change the default number of draws for the Random algorithm from one to two, matching Power of Two." However, in the response time data, the test appears to consider only average response time. I would love to see the p90 and p99 tail latency of these tests. The main focus of the paper in this post is minimizing p90/99, not average latency. Tarreau also helpfully provides links to both a 2001 research report by Mitzenmacher, Richa & Sitaraman and also the original 1996 Po2C PhD thesis by Mitzenmacher. [1] https://docs.nginx.com/nginx/admin-guide/load-balancer/http-load-balancer/ https://docs.nginx.com/nginx/admin-guide/load-balancer/http-... [2] https://www.haproxy.com/blog/power-of-two-load-balancing https://www.haproxy.com/blog/power-of-two-load-balancing
djoldman 2y ago
> With Prequal we saw dramatic improvements across all metrics [for youtube], including reductions of 2x in tail latency, 5-10x in tail RIF, 10-20% in tail memory usage, 2x in tail CPU utilization, and a near-elimination of errors due to load imbalance. In addition to meeting SLOs, this also allowed us to significantly raise the utilization targets that govern how much traffic we are willing to send to each datacenter, thereby saving significant resources. This feels like one of those "my company realized savings greater than my entire career's expected compensation."
- up2isomorphism 2y ago
  The biggest YouTube tail latency is “skip after x seconds”. And I don’t think this paper helps.
- toenail 2y ago
  The person chose to be employed instead of starting their own business. Less risk, less reward.
  - eikenberry 2y ago
    This is pretty much the only option for a person to have any sort of ownership... at least in the US where co-ops and the like are extremely rare w/ little legal help.
  - FooBarWidget 2y ago
    I disagree with toenail being downvoted. In Europe, employees enjoy a great deal of stability. In Netherlands, it's nigh-impossible to fire someone: you have to fill in 10 pages of justification paperwork and have an independent government agency review and approve it. If someone has a long-term illness then you have to pay 70% of their salary for up to 2 years, even when they do no work at all. Most people don't want to be entrepreneur: they want clear instructions and stability. When you try to give stock to employees, the tax authorities raise an eyebrow: why would you give stock to employees when they enjoy none of your risks? It makes no sense, so we'll treat it as a form of salary, so we'll tax you 52% on the stock's paper value. At the end of the day, what's left for the entrepreneur? You enjoy all the risk, but you don't get to have a paid 2 year sick leave. Even sympathy for your hard work can be hard to get. The potential of money is all you have. Things are different in the US of course, where people can be fired the next minute without reason. That looks like just borderline abuse to me. But from a European perspective, the above comment does not deserve downvoting at all.
andyg_blog 2y ago
From TFA: > PReQuaL does not balance CPU load, but instead selects servers according to estimated latency and active requests-in-flight So, still load balancing
- mandarax8 2y ago
  Abstract: We present PReQuaL (Probing to Reduce Queuing and Latency), a load balancer for...
  - binary132 2y ago
    “Don’t load balance, erm, here’s our loadbalancer” struck me as quite humorous too. :)
- cadamsau 2y ago
  Maybe RIF-balancing is a better term. Fascinating that 2-3 probes per request is a sweet spot, intuitively it seems like a lot of overhead.
  - kqr 2y ago
    Rquests (in flight or currently processing) are the load in this case. But I guess "queue balancing" captures the intuittion better: what matters for latency is the future delay more than current delay.
  - hinkley 2y ago
    Least-conn is requests in flight. It’s like they’re trying to make it hard for people to search for prior art. My ass feels very smoky right now.
- 0xdeadbeefbabe 2y ago
  They estimate what load will be in the future too.
- otterley 2y ago
  Load balancing is a term of art; the actual algorithm for distributing requests need not be load-based. A more accurate term for the component might be "request distributor," but I don't foresee people changing their vocabulary any time soon.
Twirrim 2y ago
I'm surprised that S3/AWS hasn't blogged or done a white paper about their approach yet. It's been something like 7 years now since they moved away from standard load balancing. If you think about an object storage platform, much like with YouTube, traditional load balancing is a really bad fit. No two requests are even remotely the same in terms of resource requirements, duration etc.
- Ne02ptzero 2y ago
  Out of curiosity, any documents on this, even for something else than AWS's S3? I find the idea very interesting
  - Twirrim 2y ago
    Nothing specific that I'm aware of. Off the top of my head, and sticking to things that are pretty safe NDA territory, load balancers algorithms typically do things round-robin style, or least current connections, or speed of response etc. They don't know anything about the underlying servers, or the requests, just what they've sent in which direction. If you have multiple load balancers sitting in front of your fleet, they often don't know anything about what each other is doing either. With an Object Storage service like S3, no two GET or PUT requests an LB serves are really the same, or have the same impact. They use different amounts of bandwidth, pull different at different speeds, different latency, require different amounts of CPU for handling or checksumming etc. It didn't used to be too weird to find API servers that were bored stiff, while others were working hard, all while having approximately the same number of requests going to them. Smartphones used to be a nightmare, especially with the number that would be on poor signal quality, and/or reaching internationally. Millions of live connections just sitting there slowly GETing or PUTing requests, using up precious connection resources on web servers, but not much CPU time.
- jbnorth 2y ago
  The latest deep dive on S3 at reinvent sheds some light on how it’s done. https://youtu.be/NXehLy7IiPM https://youtu.be/NXehLy7IiPM
magicalhippo 2y ago
They talked a lot about using probes to select candidate servers, but I struggled to find a good explanation of what exactly a probe was. However the "Replica selection" section seems to shed some detail, albeit somewhat indirectly. From what I can gather a probe consists of N metrics, which are gathered by the backend servers upon request from the load balancers. In the paper they used two metrics, requests in flight (RIF) and measured latency for the most recent requests. I assume the backend server maintains a RIF counter and a circular list of the last N requests, which it uses to compute the average latency of recent requests (so skipping old requests in the list presumably). They mention that responding to a probe should be fast and O(1). At least that's my understanding after glossing through the paper.
- pradn 2y ago
  The key is that the probes a) are fast: they certainly incur the same network cost of a regular request. But more than that, all they do is read two counters, so they're super quick for backends to serve. b) cheap: they don't do nearly as much work as a "real" request, so the cost of enabling this system is not prohibitive. They simply return two numbers. The probes don't compete with "real" requests for resources. c) give the load balancer useful information: among all the metrics they could have returned from the backend, the ones they chose led to good prediction outcomes. One could imagine playing with the metrics used, even using ML to select the best ones, and to adapt them dynamically based on workload and time period.
jeffbee 2y ago
I would have liked to have read something quantitative about the measured cost (in terms of client and server CPU) other than describing them as "small". I'm trying to imagine doing this in gRPC and it seems like the overhead would be pretty high. I know Stubby is more efficient but some hard numbers would have been nice.
HiJon89 2y ago
Using observed latency, power of two choices, and requests in flight reminds me a lot of Finagle https://twitter.github.io/finagle/guide/Clients.html#p2c-least-loaded https://twitter.github.io/finagle/guide/Clients.html#p2c-lea...
- jeffbee 2y ago
  They specifically compare to client-side least-loaded with Po2C in section 5.2/figure 7.
lokar 2y ago
Are people really balancing load based on simple cpu utilization for non-trivial services? That seems really surprising to me, but they present it as the current best practice?
- jeffbee 2y ago
  In my experience by far the most widespread solution for directing requests is randomly. Round robin is pretty popular. Everything more sophisticated than that is vanishingly rare outside of large organizations. Look in gRPC. What client side load balancers does it come with? Pick_first and round_robin. Weighted round robin has some traction but even in engineering groups with lots of experience and talent the complexity of measuring CPU rate utilization is underappreciated.
- sitkack 2y ago
  When reading a paper like this, ignore what the paper frames as the current state of the art, a lot of times. Often the research is framed in such a way that gives an impact boost by setting up somewhat of a strawman about the current state. Every production load balancer that I have come across in the last 10 years, load balances on the metric that is important to them.
  - danielmarkbruce 2y ago
    Also, replace "reading a paper" with "reading a startup pitch", "reading a company's marketing material" and any number of other things... Practically any time you ask a company what their value prop is you'll get a description as though we all just came out of the caves.
    - sitkack 2y ago
      Cuts to black and white video of someone struggling, visibly depressed almost panicked about opening a bag of potato chips. Cut to color video of happy relaxed individual after applying entirely obvious sold as-new load balancing heuristic.
- 2y ago
layla5alive 2y ago
What about this is a surprising result? Optimize as directly as possible for load balancing the thing(s) that matter most to your users (e.g. latency), not the thing that indirectly correlates to the thing(s) that matter (CPU Utilization). I've been making this exact argument at work for a while. Funny to read this article today, just after myself and two others at work also just saved the company we work at far more than our combined expected lifetime gross earnings with a single (different) optimization.
- froh 2y ago
  you got me curious. can you share?
- aseipp 2y ago
  The paper reiterates -- multiple times -- that optimizing for latency is obviously the right choice; the other major signal is instantaneous requests-in-flight (RIF). They explicitly mention, on the very first page, that their contributions are not that "low latency is good, aim for that", it's that A) they use a particular combination of RIF and latency to select replicas called their "hot-cold lexicographic rule" which they find works really well, and B) their "probes" (requests by the balancer to the backends, to discover what their current state is) are collected asynchronously rather than in the critical request serving path, to help further drive utilization. Most of the ink in the paper in Section 4 explains the design choices they made around probing as a result. I'm not done with the paper yet, but the basics are in fact written on page one.
bigcat12345678 2y ago
Needs to read this in-depth over weekends. Have fully imersed into LLMs for the past 2 years, ignored system research. This appears a very logical solution, i.e., use estimation service quality instead of resource metrics, for scheduling. This is also more or less a known facts in the recent years, as systems are becoming so complex and so distributed intertwined that scheduling based on host load concerns a minor factors of serving requests. It's like one grew taller, and need to worry not stepping on huddles, but not bumping heads into door frame. But we do need this kind of research to fomalize the practice, and get everyone on board. Google's applied research absolutely winning here.
neonate 2y ago
Paper: https://www.usenix.org/system/files/nsdi24-wydrowski.pdf https://www.usenix.org/system/files/nsdi24-wydrowski.pdf Talk: https://www.youtube.com/watch?v=PSP3GrZP2oo https://www.youtube.com/watch?v=PSP3GrZP2oo
robocat 2y ago
I wonder how predictable the failure modes are? Traditional load balancing has some known failure modes and engineers know to design to avoid them.

173 points by signa11 2y ago

is this available anywhere yet or still not outside of Google? it would be great to test it on our K8S which uses nginx-ingress

cozos 2y ago

The previous policy uses weighted round robin (WRR), which is described as: > weight wi is calculated as qi/ui, where qi and ui represent the recent query-per-second (QPS) rate and CPU utilization of replica i. The pathological case describes a situation where antagonist loads are soaking up CPU on some on the machines, but WRR equally distributes the load because weight formula prioritizes the utilization of the individual tenant, not of the entire machine. Wouldn't including the the machine utilization (probably downweighted) into the WRR formula also solve the issue?

tedd4u 2y ago

A few notes on Power-Of-Two-Choices (Po2C) which is part of the solution described in the paper. NGINX appears to have Po2C available as an option on the "random" balancing algorithm. [1] It only considers load (requests in flight), unlike the paper which also considers recent latency (and does many other things). However NGINX "Plus" (the paid version) appears to have a couple additional settings that use actual traffic as latency probes (not asynchronous synthetic probes as described in the paper). [also 1] It's not fully clear to me but I think if you use these options it's going to only use latency, not load. The paper described in this post actually uses both load (RIF) and latency. Eager to try these out. Also, I noted that HAProxy author and kernel maintainer Willy Tarreau wrote an article in 2019 about adding Power-of-two-choices to HAProxy. [2] He builds a test bed with a few micro services and compares several balancing algorithms to Po2C, considering response time, throughput, and max load. One conclusion is that "At the very least, Power of Two is always better than Random. So, we decided to change the default number of draws for the Random algorithm from one to two, matching Power of Two." However, in the response time data, the test appears to consider only average response time. I would love to see the p90 and p99 tail latency of these tests. The main focus of the paper in this post is minimizing p90/99, not average latency. Tarreau also helpfully provides links to both a 2001 research report by Mitzenmacher, Richa & Sitaraman and also the original 1996 Po2C PhD thesis by Mitzenmacher. [1] https://docs.nginx.com/nginx/admin-guide/load-balancer/http-load-balancer/ https://docs.nginx.com/nginx/admin-guide/load-balancer/http-... [2] https://www.haproxy.com/blog/power-of-two-load-balancing https://www.haproxy.com/blog/power-of-two-load-balancing

djoldman 2y ago

> With Prequal we saw dramatic improvements across all metrics [for youtube], including reductions of 2x in tail latency, 5-10x in tail RIF, 10-20% in tail memory usage, 2x in tail CPU utilization, and a near-elimination of errors due to load imbalance. In addition to meeting SLOs, this also allowed us to significantly raise the utilization targets that govern how much traffic we are willing to send to each datacenter, thereby saving significant resources. This feels like one of those "my company realized savings greater than my entire career's expected compensation."

up2isomorphism 2y ago
The biggest YouTube tail latency is “skip after x seconds”. And I don’t think this paper helps.
toenail 2y ago
The person chose to be employed instead of starting their own business. Less risk, less reward.
- eikenberry 2y ago
  This is pretty much the only option for a person to have any sort of ownership... at least in the US where co-ops and the like are extremely rare w/ little legal help.
- FooBarWidget 2y ago
  I disagree with toenail being downvoted. In Europe, employees enjoy a great deal of stability. In Netherlands, it's nigh-impossible to fire someone: you have to fill in 10 pages of justification paperwork and have an independent government agency review and approve it. If someone has a long-term illness then you have to pay 70% of their salary for up to 2 years, even when they do no work at all. Most people don't want to be entrepreneur: they want clear instructions and stability. When you try to give stock to employees, the tax authorities raise an eyebrow: why would you give stock to employees when they enjoy none of your risks? It makes no sense, so we'll treat it as a form of salary, so we'll tax you 52% on the stock's paper value. At the end of the day, what's left for the entrepreneur? You enjoy all the risk, but you don't get to have a paid 2 year sick leave. Even sympathy for your hard work can be hard to get. The potential of money is all you have. Things are different in the US of course, where people can be fired the next minute without reason. That looks like just borderline abuse to me. But from a European perspective, the above comment does not deserve downvoting at all.

andyg_blog 2y ago

From TFA: > PReQuaL does not balance CPU load, but instead selects servers according to estimated latency and active requests-in-flight So, still load balancing

mandarax8 2y ago
Abstract: We present PReQuaL (Probing to Reduce Queuing and Latency), a load balancer for...
- binary132 2y ago
  “Don’t load balance, erm, here’s our loadbalancer” struck me as quite humorous too. :)
cadamsau 2y ago
Maybe RIF-balancing is a better term. Fascinating that 2-3 probes per request is a sweet spot, intuitively it seems like a lot of overhead.
- kqr 2y ago
  Rquests (in flight or currently processing) are the load in this case. But I guess "queue balancing" captures the intuittion better: what matters for latency is the future delay more than current delay.
- hinkley 2y ago
  Least-conn is requests in flight. It’s like they’re trying to make it hard for people to search for prior art. My ass feels very smoky right now.
0xdeadbeefbabe 2y ago
They estimate what load will be in the future too.
otterley 2y ago
Load balancing is a term of art; the actual algorithm for distributing requests need not be load-based. A more accurate term for the component might be "request distributor," but I don't foresee people changing their vocabulary any time soon.

Twirrim 2y ago

I'm surprised that S3/AWS hasn't blogged or done a white paper about their approach yet. It's been something like 7 years now since they moved away from standard load balancing. If you think about an object storage platform, much like with YouTube, traditional load balancing is a really bad fit. No two requests are even remotely the same in terms of resource requirements, duration etc.

Ne02ptzero 2y ago
Out of curiosity, any documents on this, even for something else than AWS's S3? I find the idea very interesting
- Twirrim 2y ago
  Nothing specific that I'm aware of. Off the top of my head, and sticking to things that are pretty safe NDA territory, load balancers algorithms typically do things round-robin style, or least current connections, or speed of response etc. They don't know anything about the underlying servers, or the requests, just what they've sent in which direction. If you have multiple load balancers sitting in front of your fleet, they often don't know anything about what each other is doing either. With an Object Storage service like S3, no two GET or PUT requests an LB serves are really the same, or have the same impact. They use different amounts of bandwidth, pull different at different speeds, different latency, require different amounts of CPU for handling or checksumming etc. It didn't used to be too weird to find API servers that were bored stiff, while others were working hard, all while having approximately the same number of requests going to them. Smartphones used to be a nightmare, especially with the number that would be on poor signal quality, and/or reaching internationally. Millions of live connections just sitting there slowly GETing or PUTing requests, using up precious connection resources on web servers, but not much CPU time.
jbnorth 2y ago
The latest deep dive on S3 at reinvent sheds some light on how it’s done. https://youtu.be/NXehLy7IiPM https://youtu.be/NXehLy7IiPM

magicalhippo 2y ago

They talked a lot about using probes to select candidate servers, but I struggled to find a good explanation of what exactly a probe was. However the "Replica selection" section seems to shed some detail, albeit somewhat indirectly. From what I can gather a probe consists of N metrics, which are gathered by the backend servers upon request from the load balancers. In the paper they used two metrics, requests in flight (RIF) and measured latency for the most recent requests. I assume the backend server maintains a RIF counter and a circular list of the last N requests, which it uses to compute the average latency of recent requests (so skipping old requests in the list presumably). They mention that responding to a probe should be fast and O(1). At least that's my understanding after glossing through the paper.

pradn 2y ago
The key is that the probes a) are fast: they certainly incur the same network cost of a regular request. But more than that, all they do is read two counters, so they're super quick for backends to serve. b) cheap: they don't do nearly as much work as a "real" request, so the cost of enabling this system is not prohibitive. They simply return two numbers. The probes don't compete with "real" requests for resources. c) give the load balancer useful information: among all the metrics they could have returned from the backend, the ones they chose led to good prediction outcomes. One could imagine playing with the metrics used, even using ML to select the best ones, and to adapt them dynamically based on workload and time period.

jeffbee 2y ago

I would have liked to have read something quantitative about the measured cost (in terms of client and server CPU) other than describing them as "small". I'm trying to imagine doing this in gRPC and it seems like the overhead would be pretty high. I know Stubby is more efficient but some hard numbers would have been nice.

HiJon89 2y ago

Using observed latency, power of two choices, and requests in flight reminds me a lot of Finagle https://twitter.github.io/finagle/guide/Clients.html#p2c-least-loaded https://twitter.github.io/finagle/guide/Clients.html#p2c-lea...

jeffbee 2y ago
They specifically compare to client-side least-loaded with Po2C in section 5.2/figure 7.

lokar 2y ago

Are people really balancing load based on simple cpu utilization for non-trivial services? That seems really surprising to me, but they present it as the current best practice?

jeffbee 2y ago
In my experience by far the most widespread solution for directing requests is randomly. Round robin is pretty popular. Everything more sophisticated than that is vanishingly rare outside of large organizations. Look in gRPC. What client side load balancers does it come with? Pick_first and round_robin. Weighted round robin has some traction but even in engineering groups with lots of experience and talent the complexity of measuring CPU rate utilization is underappreciated.
sitkack 2y ago
When reading a paper like this, ignore what the paper frames as the current state of the art, a lot of times. Often the research is framed in such a way that gives an impact boost by setting up somewhat of a strawman about the current state. Every production load balancer that I have come across in the last 10 years, load balances on the metric that is important to them.
- danielmarkbruce 2y ago
  Also, replace "reading a paper" with "reading a startup pitch", "reading a company's marketing material" and any number of other things... Practically any time you ask a company what their value prop is you'll get a description as though we all just came out of the caves.
  - sitkack 2y ago
    Cuts to black and white video of someone struggling, visibly depressed almost panicked about opening a bag of potato chips. Cut to color video of happy relaxed individual after applying entirely obvious sold as-new load balancing heuristic.
2y ago

layla5alive 2y ago

What about this is a surprising result? Optimize as directly as possible for load balancing the thing(s) that matter most to your users (e.g. latency), not the thing that indirectly correlates to the thing(s) that matter (CPU Utilization). I've been making this exact argument at work for a while. Funny to read this article today, just after myself and two others at work also just saved the company we work at far more than our combined expected lifetime gross earnings with a single (different) optimization.

froh 2y ago
you got me curious. can you share?
aseipp 2y ago
The paper reiterates -- multiple times -- that optimizing for latency is obviously the right choice; the other major signal is instantaneous requests-in-flight (RIF). They explicitly mention, on the very first page, that their contributions are not that "low latency is good, aim for that", it's that A) they use a particular combination of RIF and latency to select replicas called their "hot-cold lexicographic rule" which they find works really well, and B) their "probes" (requests by the balancer to the backends, to discover what their current state is) are collected asynchronously rather than in the critical request serving path, to help further drive utilization. Most of the ink in the paper in Section 4 explains the design choices they made around probing as a result. I'm not done with the paper yet, but the basics are in fact written on page one.

bigcat12345678 2y ago

Needs to read this in-depth over weekends. Have fully imersed into LLMs for the past 2 years, ignored system research. This appears a very logical solution, i.e., use estimation service quality instead of resource metrics, for scheduling. This is also more or less a known facts in the recent years, as systems are becoming so complex and so distributed intertwined that scheduling based on host load concerns a minor factors of serving requests. It's like one grew taller, and need to worry not stepping on huddles, but not bumping heads into door frame. But we do need this kind of research to fomalize the practice, and get everyone on board. Google's applied research absolutely winning here.

neonate 2y ago

Paper: https://www.usenix.org/system/files/nsdi24-wydrowski.pdf https://www.usenix.org/system/files/nsdi24-wydrowski.pdf Talk: https://www.youtube.com/watch?v=PSP3GrZP2oo https://www.youtube.com/watch?v=PSP3GrZP2oo

robocat 2y ago

I wonder how predictable the failure modes are? Traditional load balancing has some known failure modes and engineers know to design to avoid them.