WeightedLeastRequest LB not fully respecting P2C

[mariusp]

Title: WeightedLeastRequest LB not fully respecting P2C - question.

Description:
The WeightedLeastRequest load balance algorithm is not really respecting P2C algorithm. The implementation is selecting 2 (or more = choice_count) random choices, however they are not necessarily unique. This translates into the probability of sending traffic to a new host as follows:
Pb1 = (1 - pow(((N-1)/N),C)),

while for unique hosts it will be:
Pb2 = C/N

where:

• C = choice_count.
• N = number of hosts.

Example:
For N=2 and C=2 => Pb1 = 0.75 and Pb2 = 1

For N=4 and C=2 => Pb1 = 0.43 and Pb2 = 0.5
For N=4 and C=3 => Pb1 = 0.57 and Pb2 = 0.75
For N=4 and C=4 => Pb1 = 0.68 and Pb2 = 1

For N=30 and C=2 => Pb1 = 0.065 and Pb2 = 0.066
For N=30 and C=20 => Pb1 = 0.49 and Pb2 = 0.66
For N=30 and C=25 => Pb1 = 0.57 and Pb2 = 0.83
For N=30 and C=29 => Pb1 = 0.62 and Pb2 = 0.96
For N=30 and C=30 => Pb1 = 0.63 and Pb2 = 1

Note that even choice_count is the same as number of hosts, only 63% of the traffic is sent to the host with less active requests; choice_count should be 88 in order to reach a 95% probability.
In case choice_count = N (number of hosts) the current implemented algorithm will only send a maximum of 70%(N>=3) of traffic to the host having the lowest number of active requests.

Question: Is this intended?
Indeed when choice_count is 2, probabilities do converge with increased number of hosts. However, expectation was that if choice_count = number of hosts, all traffic should go to the host with less active requests, however as explained above the max percentage is 70% and dropping when number of hosts increases (for hosts=2 and choice_count=2, we have 25% & 75% traffic distribution).

Thank you!

Repro steps:

Admin and Stats Output:

Config:

Logs:

Call Stack:

[mattklein123]

This is a known issue and has been discussed off and on over the years. There is no simple way to fix this. I think an attempt was made a while ago to do a full scan if the number of hosts is small enough, but I can't remember the details. There are performance vs. correctness tradeoffs and the algorithm definitely was not originally built for a very small number of hosts.

cc @antoniovicente @euroelessar @tonya11en

[mariusp]

Thank you for clarifications,
I have kind of a reverse problem where trying to reach 90% and my choice_count has to be huge, more than 2*N(number of hosts). Will try to investigate some more on a possible solution.

Thank you again!

[github-actions]

This issue has been automatically marked as stale because it has not had activity in the last 30 days. It will be closed in the next 7 days unless it is tagged "help wanted" or "no stalebot" or other activity occurs. Thank you for your contributions.

[tonya11en]

There was some discussion related to this in an old issue you can find here: #11006.

[github-actions]

This issue has been automatically marked as stale because it has not had activity in the last 30 days. It will be closed in the next 7 days unless it is tagged "help wanted" or "no stalebot" or other activity occurs. Thank you for your contributions.

[github-actions]

This issue has been automatically closed because it has not had activity in the last 37 days. If this issue is still valid, please ping a maintainer and ask them to label it as "help wanted" or "no stalebot". Thank you for your contributions.