mirror of
https://github.com/caddyserver/caddy.git
synced 2026-08-29 13:32:19 +00:00
b2be548275
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> |
||
|---|---|---|
| .. | ||
| caddyauth | ||
| encode | ||
| fileserver | ||
| headers | ||
| intercept | ||
| logging | ||
| map | ||
| proxyprotocol | ||
| push | ||
| requestbody | ||
| reverseproxy | ||
| rewrite | ||
| standard | ||
| templates | ||
| tracing | ||
| app.go | ||
| autohttps.go | ||
| autohttps_test.go | ||
| caddyhttp.go | ||
| caddyhttp_test.go | ||
| celmatcher.go | ||
| celmatcher_test.go | ||
| errors.go | ||
| http2listener.go | ||
| httpredirectlistener.go | ||
| invoke.go | ||
| ip_matchers.go | ||
| ip_range.go | ||
| logging.go | ||
| marshalers.go | ||
| matchers.go | ||
| matchers_test.go | ||
| metrics.go | ||
| metrics_test.go | ||
| replacer.go | ||
| replacer_test.go | ||
| responsematchers.go | ||
| responsematchers_test.go | ||
| responsewriter.go | ||
| responsewriter_test.go | ||
| routes.go | ||
| server.go | ||
| server_test.go | ||
| staticerror.go | ||
| staticresp.go | ||
| staticresp_test.go | ||
| subroute.go | ||
| urlpatternmatcher.go | ||
| urlpatternmatcher_test.go | ||
| vars.go | ||
| vars_test.go | ||