A Fast, Minimal Memory, Consistent Hash Algorithm
1–10 of 24 posts
Re: A Fast, Minimal Memory, Consistent Hash Algorithm
#2One point to consider is that this algorithm appears to rely on a double-precision floating-point divide at its core, so the speediness measured on a Xeon E5 may not translate to speediness on architectures with weaker floating point units.
Re: A Fast, Minimal Memory, Consistent Hash Algorithm
#3The algorithm is called "Jump". A quick search on GitHub revealed three projects that implement it and they are all written in Go: https://github.com/benbjohnson/jmphash
Re: A Fast, Minimal Memory, Consistent Hash Algorithm
#4In case anyone is interested in the random number, `2862933555777941757`, but didn't catch it while scanning the PDF, it is shared with the "64-bit Linear Congruential Generator" [1]
The author specifies that if the key is larger than 64 bits, then it should get a 64 bit hash for use in input. But I wonder, supposing the compiler or processor handled higher bits in a single register and we had a need for it, would this algorithm handle a change of the magic number without a problem? Where would one look for such numbers?
Re: A Fast, Minimal Memory, Consistent Hash Algorithm
#5The algorithm is called "Jump". A quick search on GitHub revealed three projects that implement it and they are all written in Go: https://github.com/benbjohnson/jmphash
Given that the paper is by people from Google, where Go is fairly well adopted, and that both Go's and this algorithm's primary use-cases are server-related, that makes kind of sense.
Re: A Fast, Minimal Memory, Consistent Hash Algorithm
#6super quick, super dumb comparison to a variant on bob jenkins 64-bit mix/hash: https://gist.github.com/robmccoll/38f03971df66ca15e030
$./bin/googlehash 512 1000000 google hash 0.0765907 255374889 2.18324e+10 bob jenkins hash 0.0158996 255484409 2.18324e+10 google is 0.207592x faster bob is 4.81714x faster
$./bin/googlehash 29 1000000 google hash 0.0478618 14000129 6.99994e+07 bob jenkins hash 0.0158052 13999989 6.99994e+07 google is 0.330225x faster bob is 3.02824x faster
./bin/googlehash 65536 1000000 google hash 0.117784 32781492370 3.57002e+14 bob jenkins hash 0.0162152 32744680953 3.57004e+14 google is 0.137668x faster bob is 7.26383x faster
print out is time(s), sum, variance (could use a suggestion on better test for uniformity - only other idea was look at a histogram, anyone have suggestions?).
edit: it is likely that this is a poor comparison :-)
Re: A Fast, Minimal Memory, Consistent Hash Algorithm
#7i'd rather have collision avoidance and collision generation aversion than "fast, minimal memory"
Re: A Fast, Minimal Memory, Consistent Hash Algorithm
#8Using doubles in a hash algorithm seems (to me) very dangerous.
For years I have had problems with different optimisation levels providing different results for floating point code, as different registers have different internal sizes, FP registers can have different internal precision, etc.
Can this hash function be trusted to produce repeatable results?
Re: A Fast, Minimal Memory, Consistent Hash Algorithm
#9It 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.
Re: A Fast, Minimal Memory, Consistent Hash Algorithm
#10One point to consider is that this algorithm appears to rely on a double-precision floating-point divide at its core, so the speediness measured on a Xeon E5 may not translate to speediness on architectures with weaker floating point units.
The purpose of reals is just to map from [0-1) to [0-n) where n is the number of hosts.
Floating points are used to ease the presentation, I think the algorithm can be ported to integer operations without loss of performance (didn't prove it, I just tried to write a pure integer implementation and checked distribution of results on some inputs).