From 40b193fb791e241dec630a37167aac576375bc96 Mon Sep 17 00:00:00 2001 From: Matt Holt Date: Wed, 27 Apr 2022 10:39:22 -0600 Subject: reverseproxy: Improve hashing LB policies with HRW (#4724) * 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/selectionpolicies.go | 29 +++++++++++++--------- 1 file changed, 17 insertions(+), 12 deletions(-) (limited to 'modules/caddyhttp/reverseproxy/selectionpolicies.go') diff --git a/modules/caddyhttp/reverseproxy/selectionpolicies.go b/modules/caddyhttp/reverseproxy/selectionpolicies.go index 001f7f8..125a07f 100644 --- a/modules/caddyhttp/reverseproxy/selectionpolicies.go +++ b/modules/caddyhttp/reverseproxy/selectionpolicies.go @@ -514,21 +514,26 @@ func leastRequests(upstreams []*Upstream) *Upstream { return best[weakrand.Intn(len(best))] } -// hostByHashing returns an available host -// from pool based on a hashable string s. +// hostByHashing returns an available host from pool based on a hashable string s. func hostByHashing(pool []*Upstream, s string) *Upstream { - poolLen := uint32(len(pool)) - if poolLen == 0 { - return nil - } - index := hash(s) % poolLen - for i := uint32(0); i < poolLen; i++ { - upstream := pool[(index+i)%poolLen] - if upstream.Available() { - return upstream + // Highest Random Weight (HRW, or "Rendezvous") hashing, + // guarantees stability when the list of upstreams changes; + // see https://medium.com/i0exception/rendezvous-hashing-8c00e2fb58b0, + // https://randorithms.com/2020/12/26/rendezvous-hashing.html, + // and https://en.wikipedia.org/wiki/Rendezvous_hashing. + var highestHash uint32 + var upstream *Upstream + for _, up := range pool { + if !up.Available() { + continue + } + h := hash(s + up.String()) // important to hash key and server together + if h > highestHash { + highestHash = h + upstream = up } } - return nil + return upstream } // hash calculates a fast hash based on s. -- cgit v1.2.3