Regarding Consistent Hashing....

[Tobias Lütke]

I think standards are best when there is only one of them. Lets not
add choices to the mix. We should find out what is the "less bad" of
the two options or eliminate one at random with all things being
equal. I'm certain that 99% of the memcached user base is not partial
to either crc or fnv and the implementors probably appreciate crc
because of the general availability of the algorithm ( there is a very
fast implementation in zlib which is bundled and exposed in almost
every scripting language ).

On 8/30/07, Mikael Johansson <mikael at synd.info> wrote:
> 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).
> >
>
>
>


-- 
Tobi
http://shopify.com       - modern e-commerce software
http://typo.leetsoft.com - Open source weblog engine
http://blog.leetsoft.com - Technical weblog