Consistent Hashing for Dummies
franzoni.eu
franzoni.eu
[1] https://graphics.stanford.edu/papers/veach_thesis/
[2] https://en.wikipedia.org/wiki/Eric_Veach
[3] Funny video of him winning an Academy Award: https://www.youtube.com/watch?v=a3ReTBe06Kw
I didn’t want to re-explain such algorithm, since the paper does a good job at that. I just wanted to clarify what consistent hashing is, since a lot of people seem to misunderstand its behaviour.
I recently had to figure out a short-term way of horizontally scaling a graphite service. I didn't really like the stateful complexity around the carbon relay-based solution, so I decided to build a simple orchestration layer in node that routes statsd metrics to graphite nodes using consistent hashing.
Given the use cases for that particular service, I didn't have to worry about long term data storage so I could hand wave some of the pain points in cluster membership changes. A simple keyspace-aware rsync daemon was enough to get the job done.
It seems like consistent hashing is much more popular though, which definitely makes it worthwhile to learn.
From my limited perspective and the paper linked in the article it sounds like consistent hashing is best for numbered sharding (disk storage systems and databases) and rendezvous hashing is best for arbitrarily distributed storage where nodes can't be consecutively numbered.
My best attempt at explaining jump consistent hashing is that it's possible to determine how likely a given key will be to move to a nearby bucket (small hash values make it less likely, large hash values make it more likely) and use that likelihood to choose a next bucket candidate for each key. About half of keys are likely to move from 1 bucket to 2, but only a third are likely to move from 2 buckets to 3, etc. and in general 1/n of keys are likely to move to bucket n.