11–20 of 26 posts
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?
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
The typo is really really bothering me, because the future generations would not be able to search for it.
You can get things like this fixed with the Contact link at the bottom of the page (I just emailed them about it). It's so much better to copy and paste the title of articles.
Earlier quoted context omitted.
You can get things like this fixed with the Contact link at the bottom of the page (I just emailed them about it). It's so much better to copy and paste the title of articles.
They seem to have fixed the title. It looks wrong only here on HN now.
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?
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…
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):
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…
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.…