Every 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...
This 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.
For 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.
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'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.
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.
7 comments
[ 2.8 ms ] story [ 34.4 ms ] thread[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 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.
[0] https://www.toptal.com/big-data/consistent-hashing
https://arxiv.org/abs/1406.2294
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.
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
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.