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>
* reverseproxy: validate on weighted_round_robin policy
Validate that weighted_round_robin has a non-zero total weight.
This prevents configurations such as:
weighted_round_robin 0 0
from being accepted and causing a divide-by-zero panic during request handling.
* test: validation test on zero weight upstreams.
* test: provision called instead of totalweight setting
* reverseproxy: validate on negative upstream weights
* test: regression test on weighted_round_robin selection policy
* chore: upgrade .golangci.yml and workflow to v2
run `golangci-lint fmt`
Signed-off-by: Mohammed Al Sahaf <msaa1990@gmail.com>
* run `golangci-lint run --fix`
Signed-off-by: Mohammed Al Sahaf <msaa1990@gmail.com>
* more lint fixes
Signed-off-by: Mohammed Al Sahaf <msaa1990@gmail.com>
* bring back comments to .golangci.yml
Signed-off-by: Mohammed Al Sahaf <msaa1990@gmail.com>
* appease the linter some more
Signed-off-by: Mohammed Al Sahaf <msaa1990@gmail.com>
* oops
Signed-off-by: Mohammed Al Sahaf <msaa1990@gmail.com>
* use embedded structs
Signed-off-by: Mohammed Al Sahaf <msaa1990@gmail.com>
* use embedded structs where they were used before
Signed-off-by: Mohammed Al Sahaf <msaa1990@gmail.com>
* disable rule `-QF1006`
Signed-off-by: Mohammed Al Sahaf <msaa1990@gmail.com>
* missed a spot
Signed-off-by: Mohammed Al Sahaf <msaa1990@gmail.com>
---------
Signed-off-by: Mohammed Al Sahaf <msaa1990@gmail.com>
* Allow 0 as weights
Change positive to non-negative
* reverseproxy: allow 0 as weighted round robin value
* test: add more wrr select test
---------
Co-authored-by: peanutduck <peanutduck@yahoo.com>
* reverseproxy: cookie should be Secure and SameSite=None when TLS
* Update modules/caddyhttp/reverseproxy/selectionpolicies_test.go
Co-authored-by: Mohammed Al Sahaf <mohammed@caffeinatedwonders.com>
---------
Co-authored-by: Mohammed Al Sahaf <mohammed@caffeinatedwonders.com>
* update quic-go to v0.37.0
* Bump to Go 1.20
* Bump golangci-lint version, yml syntax consistency
* Use skip-pkg-cache workaround
* Workaround needed for both?
* Seeding weakrand is no longer necessary
---------
Co-authored-by: Matt Holt <mholt@users.noreply.github.com>
Co-authored-by: Francis Lavoie <lavofr@gmail.com>
* added weighted round robin algorithm to load balancer
* added an adapt integration test for wrr and fixed a typo
* changed args format to Caddyfile args convention
* added provisioner and validator for wrr
* simplified the code and improved doc
When only a single request has the least amount of requests, there's no need to compute a random number, because the modulo of 1 will always be 0 anyways.
* If upstreams are all using same host but with different ports
ie:
foobar:4001
foobar:4002
foobar:4003
...
Because fnv-1a has not a good enough avalanche effect
Then the hostByHashing result is not well balanced over
all upstreams
As last byte FNV input tend to affect few bits, the idea is to change
the concatenation order between the key and the upstream strings
So the upstream last byte have more impact on hash diffusion
* reverseproxy: Mask the WS close message when we're the client
* weakrand
* Bump golangci-lint version so path ignores work on Windows
* gofmt
* ugh, gofmt everything, I guess
* reverseproxy: Improve hashing LB policies with HRW
Previously, if a list of upstreams changed, hash-based LB policies
would be greatly affected because the hash relied on the position of
upstreams in the pool. Highest Random Weight or "rendezvous" hashing
is apparently robust to pool changes. It runs in O(n) instead of
O(log n), but n is very small usually.
* Fix bug and update tests
* caddyhttp: reverseproxy: fix hash selection policy
Fixes: #4135
Test: go test './...' -count=1
* caddyhttp: reverseproxy: add test to catch #4135
If you revert the last commit, the test will fail.
* ci: Use golangci's github action for linting
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Fix most of the staticcheck lint errors
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Fix the prealloc lint errors
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Fix the misspell lint errors
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Fix the varcheck lint errors
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Fix the errcheck lint errors
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Fix the bodyclose lint errors
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Fix the deadcode lint errors
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Fix the unused lint errors
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Fix the gosec lint errors
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Fix the gosimple lint errors
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Fix the ineffassign lint errors
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Fix the staticcheck lint errors
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Revert the misspell change, use a neutral English
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Remove broken golangci-lint CI job
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Re-add errantly-removed weakrand initialization
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* don't break the loop and return
* Removing extra handling for null rootKey
* unignore RegisterModule/RegisterAdapter
Co-authored-by: Mohammed Al Sahaf <msaa1990@gmail.com>
* single-line log message
Co-authored-by: Matt Holt <mholt@users.noreply.github.com>
* Fix lint after a1808b0dbf209c615e438a496d257ce5e3acdce2 was merged
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Revert ticker change, ignore it instead
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Ignore some of the write errors
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Remove blank line
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Use lifetime
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* close immediately
Co-authored-by: Matt Holt <mholt@users.noreply.github.com>
* Preallocate configVals
Signed-off-by: Dave Henderson <dhenderson@gmail.com>
* Update modules/caddytls/distributedstek/distributedstek.go
Co-authored-by: Mohammed Al Sahaf <msaa1990@gmail.com>
Co-authored-by: Matt Holt <mholt@users.noreply.github.com>
* v2: add documentation for circuit breaker config and "random selection" load balancing policy
* v2: rename circuit breaker config inline key from `type` to `breaker` to avoid json key clash between the `circuit_breaker` type and the `type` field of the generic circuit breaker Config struct used by circuit breaking implementations
* v2: restore the circuit breaker inline key to `type` and rename the name circuit breaker config field from `Type` to `Factor`
This commit goes a long way toward making automated documentation of
Caddy config and Caddy modules possible. It's a broad, sweeping change,
but mostly internal. It allows us to automatically generate docs for all
Caddy modules (including future third-party ones) and make them viewable
on a web page; it also doubles as godoc comments.
As such, this commit makes significant progress in migrating the docs
from our temporary wiki page toward our new website which is still under
construction.
With this change, all host modules will use ctx.LoadModule() and pass in
both the struct pointer and the field name as a string. This allows the
reflect package to read the struct tag from that field so that it can
get the necessary information like the module namespace and the inline
key.
This has the nice side-effect of unifying the code and documentation. It
also simplifies module loading, and handles several variations on field
types for raw module fields (i.e. variations on json.RawMessage, such as
arrays and maps).
I also renamed ModuleInfo.Name -> ModuleInfo.ID, to make it clear that
the ID is the "full name" which includes both the module namespace and
the name. This clarity is helpful when describing module hierarchy.
As of this change, Caddy modules are no longer an experimental design.
I think the architecture is good enough to go forward.
