Algorithm::ConsistentHash::JumpHash - The jump consistent hash algorithm
use Algorithm::ConsistentHash::JumpHash qw(jumphash_numeric jumphash_siphash); my $bucket_num = jumphash_siphash($item_key, $nbuckets);
The jump consistent hash algorithm is, according to its authors, "a fast, minimal memory, consistent hashing algorithm." It's usable in most situations where a ring based consistent hashing algorithm such as Ketama would have been used except that it only supports numbered buckets (shards). The time complexity of the algorithm is less than <O(ln(num_buckets))>.
<O(ln(num_buckets))
The string-key implementation currently uses the SipHash string hash function.
All functions documented below can be exported to your namespace using standard Exporter semantics.
Given a string as key, and the number of buckets (or the number of shards), computes and returns the id of the bucket that the key falls into. Buckets are numbered from 0.
Uses SipHash to compute a 64bit integer from the string before using jumphash to compute the bucket.
As jumphash_siphash, takes a key and a number of buckets and computes and returns the id of the bucket that the key falls into. However, the SipHash step is skipped and the key needs to be a (64bit) unsigned integer.
64bit. Portability?
The jumphash note at http://arxiv.org/pdf/1406.2294.pdf. Much recommended read, great fun.
SipHash string hash function: http://en.wikipedia.org/wiki/SipHash
For alternative consistent hash algorithms/implementations, search CPAN, but here's some:
Algorithm::ConsistentHash::CHash
Algorithm::ConsistentHash::Ketama
Steffen Mueller, <smueller@cpan.org>
Copyright (C) 2014 by Steffen Mueller
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.8.0 or, at your option, any later version of Perl 5 you may have available.
To install Algorithm::ConsistentHash::JumpHash, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Algorithm::ConsistentHash::JumpHash
CPAN shell
perl -MCPAN -e shell install Algorithm::ConsistentHash::JumpHash
For more information on module installation, please visit the detailed CPAN module installation guide.