The random_choose selection policy is meant to implement
power-of-d-choices: sample d available upstreams uniformly, then pick
the least-loaded of that sample. The sampling loop, however, was not a
correct reservoir sample (Algorithm R): it never filled the first k
reservoir slots unconditionally, instead writing every candidate to a
random slot j = rand(i+1), which can evict an earlier candidate while
leaving another slot nil. It also derived j from the upstream's index
in the pool rather than from the number of available upstreams seen,
skewing the sample whenever unavailable upstreams precede available
ones.
As a result the reservoir frequently held fewer than min(k, available)
upstreams, so the least-load comparison often never happened. Most
notably, with two upstreams and 'random_choose 2' (the canonical
power-of-two-choices setup), half of all requests were routed to the
more-loaded upstream even when it was saturated and the other idle --
identical behavior to plain 'random'. The nil slots this leaves behind
were also the cause of the panic reported in #3810, which was patched
by skipping nils in leastRequests rather than by fixing the sampling.
Replace the loop with a standard Algorithm R reservoir sample over the
available upstreams: fill the first k slots, then replace a random slot
with probability k/n. Every available upstream is now sampled uniformly
and the reservoir always holds min(k, available) candidates.
Co-authored-by: Claude Fable 5 <noreply@anthropic.com>
b2be548275