A Fast, Minimal Memory, Consistent Hash Algorithm • Hacker News Board

Re: A Fast, Minimal Memory, Consistent Hash Algorithm

#21

Post by kordless » Wed, Aug 06, 2014, 6:23 AM UTC

dchichkov wrote: post #18

teraflop wrote: post #11

It doesn't seem to be mentioned anywhere in the paper, but this is a description of the "consistent hashing" algorithm in Google's Guava library: http://docs.guava-libraries.googlecode.com/git/javadoc/src-h... I find it kind of funny that they created and released an apparently novel hashing method, and then waited 2.5 years to actually explain how it works.

It takes time and effort to do a writeup. And it is easy to procrastinate. That reminds me... A bit of a plug here. I have a cute nearly-minimal perfect hashing algorithm designed to have good cache-friendly properties. Briefly, it is somewhat similar to hopscotch hashing, only you pre-calculate the positions of the elements to put them into the 'best' spots by solving the assignment problem. Works for up to about 50…

I first read that as prohashtinate.

Re: A Fast, Minimal Memory, Consistent Hash Algorithm

#22

Post by vilda » Wed, Aug 06, 2014, 11:17 AM UTC

Just small note: This is not a pair-to-pair competition to consistent hashing.

This algorithm requires consistent mapping between nodes and (consecutive) integers--that's not something you get for free in distributed systems where nodes may join or leave the pool at any time.

Re: A Fast, Minimal Memory, Consistent Hash Algorithm

#23

Post by infinite8s » Wed, Aug 06, 2014, 12:20 PM UTC

simpsond wrote: post #9

It seems a simple key mod bucket_size works to divide a workload based on a numeric key. I imagine this has a different distribution which works better for certain use cases. Anyone have an example of when mod will fail for something like this? Edit: The paper covers this.

It fails when bucket_size changes.

Re: A Fast, Minimal Memory, Consistent Hash Algorithm

#24

Post by jones1618 » Wed, Aug 06, 2014, 4:50 PM UTC

simpsond wrote: post #9

It seems a simple key mod bucket_size works to divide a workload based on a numeric key. I imagine this has a different distribution which works better for certain use cases. Anyone have an example of when mod will fail for something like this? Edit: The paper covers this.

The problem this algorithm solves is not how to distribute keys in buckets (key mod bucket_size works fine for that) but how to gracefully adapt when bucket_size needs to increase. This algorithm minimizes the number of keys that have to be moved to new buckets while incurring no memory overhead nor requiring a complex data structure.