4 ms·

Anyone interested in consistent hashing should take a look at the simpler and more general rendezvous hashing[1] too. [1] https://en.m.wikipedia.org/wiki/Rende

• Snawoot 2y ago
  There is also Aggregated Rendezvous Hashing[1] available, which kind of solves problem of growth of required calculations for large numbers of nodes. [1] https://github.com/SenseUnit/ahrw https://github.com/SenseUnit/ahrw
  • vlovich123 2y ago
    I used a different technique that seems to work well in practice. Prehash the names of the nodes beforehand. Then hash the key and combine the hashes using a much cheaper algorithm [1]. You only need to do a single hash per key as with consistent hashing and then a very fast O(n) operation instead of a hash to find the optimal node. This does degrade to an O(nlogn) sort if you need to find the N best nodes instead of the single best node (e.g. to have a concept of fallbacks that you hand off to the next link in the chain), but I found that to not actually matter where I implemented it (generally was routing on < 100 nodes total in the first place). [1] https://stackoverflow.com/a/27952689 https://stackoverflow.com/a/27952689
• T0pH4t 2y ago
  There is also jump consistent hashing https://arxiv.org/pdf/1406.2294 https://arxiv.org/pdf/1406.2294