Consistent Hashing for Dummies
franzoni.eu
Consistent Hashing for Dummies
1–8 of 8 posts
Re: Consistent Hashing for Dummies
#2Every rendering person's hero, Eric Veach, makes an appearance again! He basically invented modern rendering for his thesis[1], then developed AdWords, among many other things...
[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
Re: Consistent Hashing for Dummies
#3This is one of those algorithms that, once you understand the fundamental concepts, opens up so many doors for you in systems-level thinking. Great tool to have, portable, and relatively easy to implement.
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.
Re: Consistent Hashing for Dummies
#4For some reason I didn't find this explanation intuitive at all, and I would consider myself to be at least "dummy" level. After a quick search, I found this [0] much more intuitive.
Re: Consistent Hashing for Dummies
#5I hadn’t heard of the “Jump Consistent Hashing” algorithm that this article uses. The original paper is much more informative than the article:
Re: Consistent Hashing for Dummies
#6I've always had a hard time understanding consistent hashing, and find rendezvous hashing [1] to be much more understandable. It provides better load-balancing properties and uses less memory than consistent hashing, but requires more computation.
It seems like consistent hashing is much more popular though, which definitely makes it worthwhile to learn.
Re: Consistent Hashing for Dummies
#7I've always had a hard time understanding consistent hashing, and find rendezvous hashing [1] to be much more understandable. It provides better load-balancing properties and uses less memory than consistent hashing, but requires more computation. It seems like consistent hashing is much more popular though, which definitely makes it worthwhile to learn. [1] https://en.wikipedia.org/wiki/Rendezvous_hashing
I think jump-based consistent hashing also requires less memory, O(1), than rendezvous hashing.
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.
Re: Consistent Hashing for Dummies
#8I hadn’t heard of the “Jump Consistent Hashing” algorithm that this article uses. The original paper is much more informative than the article: https://arxiv.org/abs/1406.2294
The paper is linked in the blog post as well.
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.