Re: Random with Two Choices Load Balancing Algorithm
Hi Norman, On Fri, Sep 25, 2020 at 03:58:54PM +, Branitsky, Norman wrote: > Wondering if this was ever implemented? Yes it was merged into 2.0, it's used by default when you select random since it's always slightly better than a naive random, and you can even configure it to set the number of draws you want. I also made some experiments to measure the gains : https://www.haproxy.com/blog/power-of-two-load-balancing/ TL;DR: it's only better than the default random, but isn't as good as the real leastconn like the one we have which is combined with round robin hance limits collisions between LB nodes in a distributed system. Willy
RE: Random with Two Choices Load Balancing Algorithm
Wondering if this was ever implemented? Norman Branitsky Senior Cloud Architect P: 416-916-1752 -Original Message- From: Willy Tarreau Sent: Saturday, December 15, 2018 11:09 AM To: Norman Branitsky Cc: haproxy@formilux.org Subject: Re: Random with Two Choices Load Balancing Algorithm Hi Norman, On Thu, Dec 06, 2018 at 04:57:18PM +, Norman Branitsky wrote: > NGINX just announced the following load balancing method as default for their > Ingress Controller for Kubernetes. > Will this appear on the HAProxy roadmap? That's interesting because we've had a discussion about this very same algo not too long ago with a coworker. I said that it should be trivial to implement, though I think that it might make sense to make the number of tries configurable. Indeed, I need to read the complete thesis on it but I suspect it can make sense to take more than 2 tries if the number of servers and/or LB nodes (or the product of the two) is very high. Maybe we'll end up picking log()+1 or something like this. But yes that's definitely very interesting. Thanks, Willy
Re: Random with Two Choices Load Balancing Algorithm
Hi again, On Sat, Dec 15, 2018 at 05:09:07PM +0100, Willy Tarreau wrote: > Hi Norman, > > On Thu, Dec 06, 2018 at 04:57:18PM +, Norman Branitsky wrote: > > NGINX just announced the following load balancing method as default for > > their Ingress Controller for Kubernetes. > > Will this appear on the HAProxy roadmap? > > That's interesting because we've had a discussion about this very same > algo not too long ago with a coworker. I said that it should be trivial > to implement, though I think that it might make sense to make the number > of tries configurable. Indeed, I need to read the complete thesis on it > but I suspect it can make sense to take more than 2 tries if the number > of servers and/or LB nodes (or the product of the two) is very high. Maybe > we'll end up picking log()+1 or something like this. > > But yes that's definitely very interesting. So yesterday I've implemented this as intended with the ability to configure the number of tries. I've spent quite some time studying the thesis, and it clearly explains that the primary purpose of the algorithm is to provide an almost equivalent of our leastconn algorithm for situation where figuring what server is the least loaded is expensive. I've ran some quick comparative tests with 2.0-dev on a 20-server farm, and it's interesting : - the single random is uneven between servers in terms of maximum experienced load, which varies by almost +/-50%, though the total number of requests is roughly fair ; - the power-of-two random is way better in that the difference between the least loaded and the most loaded servers varies by around +/-10% ; - the leastconn algo is even better because the maximum load experienced by all servers is exactly the same among the farm, and this max is about 30% lower than with power-of-tow ; I may run a more detailed test eventually. Nevertheless, I merged it and changed the random algo to make two draws by default because it behaves much better this way, and this will have an impact in distributed environments where people used to prefer to use random over any other for whatever reason, taste, or belief. This would be very easy to backport to 1.9 in case there's interest in having it there. Given that the random algorithm was introduced with 1.9 it's unlikely that anyone has yet made their opinion on it ;-) Cheers, Willy
Re: Random with Two Choices Load Balancing Algorithm
Hi Norman, On Thu, Dec 06, 2018 at 04:57:18PM +, Norman Branitsky wrote: > NGINX just announced the following load balancing method as default for their > Ingress Controller for Kubernetes. > Will this appear on the HAProxy roadmap? That's interesting because we've had a discussion about this very same algo not too long ago with a coworker. I said that it should be trivial to implement, though I think that it might make sense to make the number of tries configurable. Indeed, I need to read the complete thesis on it but I suspect it can make sense to take more than 2 tries if the number of servers and/or LB nodes (or the product of the two) is very high. Maybe we'll end up picking log()+1 or something like this. But yes that's definitely very interesting. Thanks, Willy
Random with Two Choices Load Balancing Algorithm
NGINX just announced the following load balancing method as default for their Ingress Controller for Kubernetes. Will this appear on the HAProxy roadmap? Support for the New Random with Two Choices Load‑Balancing Algorithm In NGINX Plus R16<https://www.nginx.com/blog/nginx-plus-r16-released/#r16-random-two-choices> and open source NGINX 1.15.1<https://nginx.org/en/CHANGES> we added a new method that is particularly suitable for distributed load balancers. The algorithm is referred to in the literature as “power of two choices”, because it was first described in Michael Mitzenmacher’s 1996 dissertation, The Power of Two Choices in Randomized Load Balancing<https://www.eecs.harvard.edu/~michaelm/postscripts/mythesis.pdf>. “Power of two choices” avoids the undesirable “herd” behavior that traditional best‑choice algorithms such as Least Connections<https://nginx.org/en/docs/http/ngx_http_upstream_module.html#least_conn> can exhibit when there are multiple load balancers, each with incomplete and inconsistent views of the cluster.
