]> git.ipfire.org Git - thirdparty/rspamd.git/commit
[Rework] Replace broken Jump Hash with Ring Hash (Ketama) for consistent upstream...
authorVsevolod Stakhov <vsevolod@rspamd.com>
Tue, 10 Feb 2026 14:52:30 +0000 (14:52 +0000)
committerVsevolod Stakhov <vsevolod@rspamd.com>
Tue, 10 Feb 2026 14:52:30 +0000 (14:52 +0000)
commit4ea7504663056c3a54476c47264c8df691087596
tree3fff6c609641fdc7cb4762d7a67a98bda4fb4734
parente8f59984a61703cdab6cd746e0974361021e3086
[Rework] Replace broken Jump Hash with Ring Hash (Ketama) for consistent upstream hashing

Jump Consistent Hash (Lamping & Veach 2014) only handles bucket
addition/removal at the end of the range.  When an upstream in the
middle failed, the old code rehashed with mum_hash_step and retried
up to 20 times, which destroyed the consistency property: keys that
mapped to the dead node were redistributed randomly instead of
deterministically, and didn't return when the node recovered.

Replace with a Ketama-style ring hash:
- Each alive upstream gets MAX(weight,1)*100 virtual nodes on a
  sorted hash ring (keyed by name, order-independent).
- Lookup is a binary search: O(log(n*v)) instead of O(ln n) * retries.
- When an upstream fails, only its ~1/n fraction of keys slide to the
  next ring point — true minimal disruption.
- When it recovers, the same keys return — true consistency.
- The 'except' parameter walks forward on the ring instead of rehashing.
- Ring is rebuilt lazily (dirty flag set on active/inactive transitions).
src/libutil/upstream.c