Regarding Consistent Hashing....

[Richard Jones]

On Thursday 30 August 2007 13:04:14 Ajinkya Nahar wrote:
> 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?


libketama is what we currently use in production and is considered stable
libketama-fnv is newer and still being tested

the php_ketama stuff works in php5 too, just build it as a module (phpize etc)

I haven't yet tested fnv vs crc32 so can't comment on that yet.

RJ


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



-- 
Richard Jones
Last.fm Ltd. | http://www.last.fm/
Office: +44 (0) 207 780 7080