Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Consistent hashing

eli.thegreenplace.net

Post reply on HN
Print view View original

21–26 of 26 posts

Re: Consistent hashing

#21

Post by gopalv »

eru wrote: post #7

Have a look at rendezvous hashing ( https://en.wikipedia.org/wiki/Rendezvous_hashing ). It's simpler, and more general than 'consistent hashing'. Eg you don't have to muck around with virtual nodes. Everything just works out, even for small numbers of targets. It's also easier to come up with an exact weighted version of rendezvous hashing. See https://en.wikipedia.org/wiki/Rendezvous_hashing#Weighted_re... for the w…

> if you are into load balancing, you might also want to look into the 'power of 2 choices'.

You can do that better if you don't use a random number for the hash, instead flip a coin (well, check a bit of the hash of a hash), to make sure hash expansion works well.

This trick means that when you go from N -> N+1, all the keys move to the N+1 bucket instead of being rearranged across all of them.

I've seen this two decades ago and after seeing your comment, felt like getting Claude to recreate what I remembered from back then & write a fake paper [1] out of it.

See the MSB bit in the implementation.

That said, consistent hashes can split ranges by traffic not popularity, so back when I worked in this, the Membase protocol used capacity & traffic load to split the virtual buckets across real machines.

Hot partition rebalancing is hard with a fixed algorithm.

[1] - https://github.com/t3rmin4t0r/magic-partitioning/blob/main/M...

Re: Consistent hashing

#22

Post by eatonphil »

anotherhue wrote: post #4

Can't mention this without mentioning Akamai founder Lewin, who had a sad ending. https://en.wikipedia.org/wiki/Daniel_Lewin

Wow I didn't know this history about Akamai, thanks for mentioning, interesting as a former Linode guy and a fan of consistent hashing.

Re: Consistent hashing

#24

Post by dataflow »

zvr wrote: post #16
dataflow wrote: post #9

Is it just me or can you describe the whole scheme in one sentence? tl;dr: subdivide your hash space (say, [0, 2^64)) by the number of slots, then utilize the index of the slot your hash falls in. Or, in another sense: rely on / rather than % for distribution. Is this accurate or am I missing something?

You're missing that the hash space is not divided uniformly. Which means one can vary the number of slots without recomputing the hash space division -- and without reassigning all of the existing entries.

I must've totally misunderstood what I read then. I'll give it another read, thanks!

Re: Consistent hashing

#25

Post by eru »

karakot wrote: post #20
Snawoot wrote: post #17

Earlier quoted context omitted.

I also double that rendezvous hashing suggestion. Article mentions that it has O(n) time where n is number of nodes. I made a library[1] which makes rendezvous hashing more practical for a larger number of nodes (or weight shares), making it O(1) amortized running time with a bit of tradeoff: distributed elements are pre-aggregated into clusters (slots) before passing them through HRW. [1]: https://pkg.go.dev/github.…

Does it really matter? Here, n is a very small number, which is almost a constant. I'd assume the iteration over the n space is negligible compared to the other parts of a request to a node.

Yes, different applications have different trade-offs.

Re: Consistent hashing

#26

Post by eru »

gopalv wrote: post #21
eru wrote: post #7

Have a look at rendezvous hashing ( https://en.wikipedia.org/wiki/Rendezvous_hashing ). It's simpler, and more general than 'consistent hashing'. Eg you don't have to muck around with virtual nodes. Everything just works out, even for small numbers of targets. It's also easier to come up with an exact weighted version of rendezvous hashing. See https://en.wikipedia.org/wiki/Rendezvous_hashing#Weighted_re... for the w…

> if you are into load balancing, you might also want to look into the 'power of 2 choices'. You can do that better if you don't use a random number for the hash, instead flip a coin (well, check a bit of the hash of a hash), to make sure hash expansion works well. This trick means that when you go from N -> N+1, all the keys move to the N+1 bucket instead of being rearranged across all of them. I've seen this two de…

> This trick means that when you go from N -> N+1, all the keys move to the N+1 bucket instead of being rearranged across all of them.

Isn't that how rendezvous hashing (and consistent hashing) already work?

Post reply on HN