"LEAST_REQUEST" lb_policy can possibly select the host with most active requests.

[AdiJohn]

Title: "LEAST_REQUEST" lb_policy can possibly select the host with most active requests.

Description:
With regarding to unweighted least request loadbalacing, the behavior described in Envoy doc:

An O(1) algorithm which selects N random available hosts as specified in the configuration (2 by default) and picks the host which has the fewest active requests. This is also known as P2C (power of two choices). The P2C load balancer has the property that a host with the highest number of active requests in the cluster will never receive new requests.

However, with the current implementation, it can possibly select the host with most active requests, because it is possible that the N randomly selected hosts are the same, or at least contain duplicates (i.e., when the resulted rand_idx are the same across iterations). Is this expected?

[mattklein123]

I think this is by design at least with the current implementation. Feel free to do a doc update. In the future we could consider an option to retry to avoid duplicates but that seems like a different feature request, and I'm not sure it matters in practice. cc @tonya11en

[tonya11en]

We had a fairly lengthy discussion in a PR submitted to avoid duplicates when going P2C (#11006). Take a look at the discussion for context, but I believe the gist of it is that the selection probability differences from preventing duplicate selections were negligible if you had >5 hosts. We'd also need to keep a copy of the host vector in each worker thread to do the fisher-yates shuffle, so the memory footprint was non-trivial.

[AdiJohn]

I see. Thanks for the explanation.

[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.