Regarding Consistent Hashing....

Mikael Johansson mikael at synd.info
Thu Aug 30 19:46:14 UTC 2007


Hi,

Good point about abstracting the hash function as well as the node
selection strategy, pecl/memcache used the latter concept to support
standard and consistent hashing strategies transparently.

I've added support for using either "new-style" CRC32 or 32bit FNV-1a
(like libketama-fnv) which can be combined with either hashing strategy.
The code is committed to the NON_BLOCKING_IO branch at
cvs.php.net/pecl/memcache but I'll merge it to HEAD during the weekend.

The relevant INI directives are

 memcache.hash_strategy = {standard, consistent}
 memcache.hash_function = {crc32, fnv}

The consistent strategy is now implemented like Brad's version but with
160 points per server and a choice of CRC32 or FNV-1a, I'll also make
the number of points and precomputed buckets (default 1024)
configurable. Points for a server are calculated like

 hash("127.0.0.1:11211-0")
 hash("127.0.0.1:11211-1")
 hash("127.0.0.1:11211-2")
 ...

Note the 0-based offset (libketama uses 0-based, Brad's version uses
1-based)

Sounds good for a standard?

//Mikael

Dustin Sallings wrote:
> 
> On Aug 30, 2007, at 1:48 , dormando wrote:
> 
>> Mikael, I think now's as good of a time as ever to decide on the
>> hashing standard. Believe brad's asked a few times if anyone has any
>> complaints with the Perl version, or any reasons/preferences as to one
>> implementation or the other. There's no authority on this other than
>> the people who respond here and have compelling arguments :)
> 
>     I didn't quite understand the perl well enough to comment on it.  :/
> 
>> I only know of (offhand):
>>
>> - Yours
>> - libketama
>> - Set::ConsistentHash
>>
>> ... maybe Dustin wrote one? Maybe apr_memcache has one? I forget.
>>
>> All that really matters is that an approach not everyone completely
>> absolutely hates is decided on, so this can get into use. Based on
>> MD5? Based on CRC32? What works best?
> 
>     My client has a separate concept of hashing vs. node location, so I
> can use any hash algorithm in a ketama node locator (well, one of the
> four I have written support for:  crc32, fnv, md5, and java native).
> 

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 250 bytes
Desc: OpenPGP digital signature
Url : http://lists.danga.com/pipermail/memcached/attachments/20070830/39b4a774/signature.pgp


More information about the memcached mailing list