On Wed, Sep 30, 2026 at 10:03 PM Willy Tarreau <[email protected]> wrote:
> Hi David, > > On Wed, Sep 30, 2026 at 04:37:25PM -0700, David Birdsong wrote: > > I've done some background work to see how my idea would thread through. > > > > On Sat, Sep 26, 2026 at 2:14 PM David Birdsong <[email protected] > > > > wrote: > > > > > > It's me again asking about hashing again almost 20 years later. I'm > > > curious how this new feature would be received: a new hashing type, > > > rendezvous hashing (aka HRW, "highest random weight") alongside > > > map-based and consistent. > > > > > > We want a way to bound a given tenant's traffic to a fixed, small > > > subset of backend servers, irrespective of what fails or scales in the > > > backend as a means for containing the tenant. > > > > > > Concretely: with N servers and a per-tenant hash key, rank the > > > configured server list independently of health, and let a tenant only > > > ever land on the top Y of that ranking. We would allow health/load to > > > filter within that fixed set, but must never expand outside it. So > > > this would pair well with hash-balance-factor settings. The rough > > > > Health and load would be enforced via a mode of selection scoped to the > > fixed candidate set itself (e.g. picking the least-loaded of the top Y, > or > > walking a decayed priority order), rather than the existing > > hash-balance-factor mechanism, whose fairness quota is computed against > the > > whole backend and doesn't have a coherent meaning against a small > > per-tenant subset. > > > > So I'm leaning heavily towards dropping the use of hash-balance-factor. > > > > > shape I have in mind is a new directive, hash-candidates <count>, > > > valid only alongside hash-type rendezvous, where <count> sets Y: how > > > many top-ranked servers from a given key's fixed candidate set. > > > > > > Consistent hashing doesn't give this property at any virtual node > > > count. Its fallback path (walking the ring past an unhealthy node) is > > > health dependent by construction, so there's no fixed, addressable > > > candidate set per key to point to and say "this tenant can never leave > > > this set" which is why I think this is worth a new algorithm rather > > > than tweaks to the existing one. > > > > > > Impact-wise, this would not be a performance win over chash. One would > > > only reach for this when they want the containment vs request > > > distribution: > > > - request path: O(N) per lookup (score every configured server), > > > versus chash's O(log M) tree descent. chash wins here as N grows. > > > Again only use rendezvous for its containment property. > > > - server add/remove: O(1), versus chash's O(m_s) removal / O(m_s log > > > M) insertion (i.e. no tree to touch at all). > > > > > > We would trade slower per-request lookup for zero membership-update > > > cost and a fixed, enumerable per-tenant candidate set. I'd like to get > > > some feedback on whether that tradeoff is worth a new lb_ops module > > > and a widened hash-type field. > > > > > > I'm happy to follow up with more details on complexity and a rough > > > sketch design (candidate-set directive, backup-server model options, > > > retry/redispatch interaction) but wanted to gauge interest and > > > receptiveness to this new feature. > > > > If nobody has any feedback for now, I'll just get a patch going and try > it > > out on our side. > > To be honest, I'm totally ignorant of rendezvous hashing, and I have not > yet understood from your description above what problem it tries to solve > better. I think that you have a use case in mind, it would be great if you > could illustrate how such a workload is currently handled now versus how > it would be handled with your approach. > Concretely: take a multi-tenant backend with, say, 200 application servers, one hash key per tenant. Today, with map-based or consistent hashing, a tenant's traffic is deterministic under steady state, but there's no fixed membership guarantee once servers churn. With consistent hashing specifically, when a server goes down the ring walk moves that tenant's traffic to whatever server is next around the ring — which is a function of everyone else's current health, not a fixed property of the tenant's key. Over enough failures or scaling events, a tenant's traffic can, in the worst case, land on any server in the backend. There's no way to answer, ahead of time, "which servers can tenant X's requests ever reach" with anything narrower than "the whole backend, eventually." That's the problem I want to solve: containment. If a tenant is noisy — a bug, an abusive client, a runaway batch job — its blast radius today is effectively unbounded. It can, over time, degrade service for every other tenant sharing the backend, because nothing enforces a ceiling on how many distinct servers it can touch. With rendezvous-subset and, say, hash-candidates 3, each tenant key is ranked against all 200 servers up front, independent of health, and is permanently bound to its top 3. Health and load only ever pick among those 3 (or let us queue/redispatch within them); a tenant literally cannot reach a 4th server, no matter what else happens in the backend. So "which servers can tenant X ever reach" becomes a static, computable fact — three named servers — instead of "potentially all of them, given enough churn." That's the property the ring walk's health-dependent fallback can't give at any virtual-node count, which is why I think it needs a new algorithm rather than a tweak to consistent hashing. > > Aside this, if you need to extend lb_ops, do not restrict yourself! You > may need to add info to the struct proxy (be more careful about what can > increase its size), and the server struct (be even more careful there), > but I'm saying this as indications, just do not block yourself while you > are experimenting. > > Willy >
