5 ms·
Consistent hashing
- Groxx 1y agoseems worth fixing the spelling mistake here - this is a consistent hashing post (currently "constitent hashing")
- wyldfire 1y agos/Constitent/Consistent/ Unless it's a clever play on "consistent", that is. In which case: carry on.
- anotherhue 1y agoCan't mention this without mentioning Akamai founder Lewin, who had a sad ending. https://en.wikipedia.org/wiki/Daniel_Lewin https://en.wikipedia.org/wiki/Daniel_Lewin
- eatonphil 1y agoWow I didn't know this history about Akamai, thanks for mentioning, interesting as a former Linode guy and a fan of consistent hashing.
- alanfranz 1y agoA final mention of the “simplifying” Lamping-Veach algorithm would have been great: https://arxiv.org/ftp/arxiv/papers/1406/1406.2294.pdf?ref=franzoni.eu https://arxiv.org/ftp/arxiv/papers/1406/1406.2294.pdf?ref=fr...
- sidcool 1y agoThe typo is really really bothering me, because the future generations would not be able to search for it.
- eru 1y agoHave a look at rendezvous hashing (https://en.wikipedia.org/wiki/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_rendezvous_hash 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.pdf https://www.eecs.harvard.edu/~michaelm/postscripts/mythesis.... or this HN discussion at https://news.ycombinator.com/item?id=37143376 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.
- Snawoot 1y agoI 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.com/SenseUnit/ahrw https://pkg.go.dev/github.com/SenseUnit/ahrw
- ryuuseijin 1y agoShameless plug for my super simple consistent-hashing implementation in clojure: https://github.com/ryuuseijin/consistent-hashing https://github.com/ryuuseijin/consistent-hashing
- dataflow 1y agoIs 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?
- immibis 1y agoThat's the naive method which tends to redistribute most objects when the number of slots changes.
- zvr 1y agoYou'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.
- dataflow 1y agoI must've totally misunderstood what I read then. I'll give it another read, thanks!
- catoc 1y agoWas the HN-post title also hashed? (It’s inconstitent with the actual title)
- modderation 1y agoCeph storage uses a hierarchical consistent hashing scheme called "CRUSH" to handle hierarchical data placement and replication across failure domains. Given an object ID, its location can be calculated, and the expected service queried. 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 https://ceph.com/assets/pdfs/weil-crush-sc06.pdf DOI: 10.1109/SC.2006.19
- packetlost 1y agoI've implemented a cache-line aware (from a paper) version of a persistent, consistent hashing algorithm that gets pretty good performance on SSDs: https://github.com/chiefnoah/mehdb 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): https://git.sr.ht/~chiefnoah/keeeeyz/tree/meh https://git.sr.ht/~chiefnoah/keeeeyz/tree/meh
- ignoreusernames 1y agoAnother strategy to avoid redistribution is simply having a big enough number of partitions and assign ranges instead of single partitions. A bit more complex on the coordination side but works well in other domains (distributed processing for example)
- sillypointer 1y agohttps://www.metabrew.com/article/libketama-consistent-hashing-algo-memcached-clients https://www.metabrew.com/article/libketama-consistent-hashin... Ketama implementation of consistent hashing algorithm is really intuitive and battle tested.