Consistent hashing(eli.thegreenplace.net) |
Consistent hashing(eli.thegreenplace.net) |
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 weighted variant.
Faintly related: if you are into load balancing, you might also want to look into the 'power of 2 choices'. See eg https://www.eecs.harvard.edu/~michaelm/postscripts/mythesis.... or this HN discussion at https://news.ycombinator.com/item?id=37143376
The basic idea is that you can vastly improve on random assignment for load balancing by instead picking two servers at random, and assigning to the less loaded one.
It's an interesting topic in itself, but there's also ways to combine it with consistent hashing / rendezvous hashing.
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...
Isn't that how rendezvous hashing (and consistent hashing) already work?
As a side effect, it's possible to define a logical topology that reflects the physical layout, spreading data across hosts, racks, or by other arbitrary criteria. Things are exactly where you expect them to be, and there's very little searching involved. Combined with a consistent view of the cluster state, this avoids the need for centralized lookups.
The original paper is a surprisingly short read: https://ceph.com/assets/pdfs/weil-crush-sc06.pdf DOI: 10.1109/SC.2006.19
Ketama implementation of consistent hashing algorithm is really intuitive and battle tested.
Unless it's a clever play on "consistent", that is. In which case: carry on.
https://github.com/chiefnoah/mehdb
It's used as the index for a simple KV store I did as an interview problem awhile back, it pretty handily does 500k inserts/s and 5m reads/s and it's nothing special (basic write coalescing, append-only log):
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?