Regarding Consistent Hashing....

[Ajinkya Nahar]

Hi,

I am working on PHP 5.2.3 and looking for consistent hashing implementation
for this release. 

I think the libketama was developed for PHP 4.

Which one is the better one libketama, libketama-fnv or the PECL/PHP (crc32)
based implementation?

Please let me know.
Thanks in advance.
Regards,
Ajinkya

-----Original Message-----
From: memcached-bounces at lists.danga.com
[mailto:memcached-bounces at lists.danga.com] On Behalf Of Mikael Johansson
Sent: Thursday, August 30, 2007 5:02 PM
To: Mikael Johansson; dormando
Cc: memcached at lists.danga.com
Subject: Re: Regarding Consistent Hashing....

Hi,

My vote is on using Brad's implementation but switch from SHA1 to CRC32 for
simplicity's sake and to get a nice 32bit hash, MD5 is slow and generates a
long
digest of which we only need the first bytes.

Richard Jones wrote that he would compare the CRC32 to FNV with regards to
distribution and speed. If FNV would indeed be a better/faster choice I'd
propose
to use FNV-1a to generate 32bit hashes using the FNV_prime and offset_basis
from

 http://isthe.com/chongo/tech/comp/fnv/

 "Some people use FNV-1a instead of FNV-1 because they see slightly better
dispersion for tiny (<4 octets) chunks of memory." - 

 i.e. short keys

An argument for using CRC32 over FNV could be that many script languages
ship
with a native CRC32 implementation, so it'd easier and result in higher
performance for folk who writes clients in these languages.

//Mikael

On Thu Aug 30 10:48 , dormando  sent:

>A couple, I think ;)
>
>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 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?
>
>-Dormando
>
>Mikael Johansson wrote:
>> Hi,
>> 
>> I believe there's already people using consistent hashing on large
>> installs out there. As to the pecl/memcache client the code is not
>> released and still in CVS, but it is stable (and certainly ready to be
>> evaluated/tested), also a release is coming up so you can either wait
>> for that or build from source like
>> 
>>  cvs -d :pserver:cvsread at cvs.php.net:/repository checkout pecl/memcache
>>  cd pecl/memcache
>>  phpize
>>  ./configure
>>  make && make install
>> 
>> Enable it by setting an php.ini entry like
>> 
>>  memcache.hash_strategy = consistent
>> 
>> Please note that the consistent hashing implementation might still
>> change in the future when a standard is reached on the subject.
>> 
>> //Mikael
>> 
>> Ajinkya Nahar wrote:
>>> Hi all,
>>>
>>> I want to know whether consistent hashing technique can be used in
>>> production environment.
>>>
>>> Is it still too young or is it of production quality?
>>>
>>> Also, what configuration needs to be done in the PHP client when using
>>> consistent hashing?
>>>
>>> Please let me know.
>>>
>>> Thanks in advance.
>>>
>>> Regards,
>>>
>>> Ajinkya
>>>
>>>  
>>>
>> 
>
>)