Comment by cyberpunk
13 hours ago
Anyone have an idea how it behaves differently from google's jump hash algorithm? The cool thing about google's one is it's so short I can include it in a HN comment:
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;
}
Well I looked it up; nginx, apparently, uses ketama -- it's a ring-style hash probably works better for web backends than the jch above, as when given [0,1,2,3] and replacing the server in slot 1 you're going to have a lot of hash moves. With ketama, you'd only have the '1' hashes moving. You can't really beat google's for brevity, though.
I have used Google's jump hash. As I recall, one of the main differences is that jump hash doesn't have a mechanism to remove targets, eg, a server dies and you don't want to route requests to it. Traditional consistent hashing can do that. I guess if you had 4 servers, server #4 dies, then you can go back to 3 servers by just changing num_buckets from 4 to 3. But if server 1 dies, you can't.
Jump 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.