int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
int64_t b = 1, j = 0;
while (j < num_buckets) {
b = j;
key = key * 2862933555777941757ULL + 1;
j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
}
return b;
}
https://arxiv.org/pdf/1406.2294Jump hash does allow adding more targets and preserves the property that most request targets stay the same when adding a new target, so if you had 3 targets and add a fourth, ~8% of the requests that would have been sent to targets 1-3 are sent to target 4, evenly chosen from servers 1-3.
https://github.com/cloudflare/pingora/issues/1014
I have now solved the problem once and for all