Regarding Consistent Hashing....

[a.]

I'm using a slightly modified FNV hash in my client (http:// 
codeplex.com/EnyimMemcached), taken from here: http:// 
bretm.home.comcast.net/hash/6.html

The site has a good evaluation of common hash functions, good read.



a.



On Aug 30, 2007, at 1:32 PM, Mikael Johansson wrote:

> 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
>>>>
>>>>
>>>>
>>>
>>
>> )
>
>