[infinispan-dev] Hash calculation in DefaultConsistentHash

[Manik Surtani]

Hi Alex

I've been having a look at your impl, it certainly does look  
interesting.  A few points:

1.  Limiting the hashcode function on a key to work on the String  
representation of that key could be problematic.  As you mention in  
the Javadoc of GenericConsistentHash#locate(Object, T[], int): "...  
toString method on the key class must present the variables that  
contain the relevant state... ".  Keep in mind that the keys are  
typically user-generated, and we cannot guarantee proper toString  
implementations here.  I understand your reasons for requiring this  
(looking at the way you have implemented the FNV hash).  I wonder if  
there is another way to achieve this though?  Or perhaps switch to the  
"SuperFastHash" that you have referenced as well?

2.  The use of the entire range of ints on the number line.  I can see  
the benefits here (removal of the mod and abs functions in my impl),  
but this greatly increases the range of numbers to scan.  Granted a  
binary search is fast - O (log n) - but still such a massive number  
range is unnecessary given that, even at a push (for now anyway), we'd  
see 10,000 servers in a cluster?  :-)

Cheers
Manik

On 18 Sep 2009, at 16:20, Alex Kluge wrote:

>>  Any chance of sharing this work with the rest of Infinispan  
>> community
>> at some point?
>
>  My apologies, The embedded link in the original message did not
> propagate through the mailing list. The doc is at
>    http://www.vizitsolutions.com/ConsistentHashingCaching.html.
>
>  There an an implementation of an AddressHash at the bottom, which  
> should
> be very close in functionality to the current DefaultConsistentHash.  
> If
> it looks correct it can be used directly, or I can tweak it if need  
> be.
> The doc will get more interesting when the section on adding a new  
> server
> is finished, as you will need it if you go with the virtual nodes.
>
>                                                     Alex
>
> --- On Wed, 9/16/09, Galder Zamarreno <galder.zamarreno at redhat.com>  
> wrote:
>
> From: Galder Zamarreno <galder.zamarreno at redhat.com>
> Subject: Re: [infinispan-dev] Hash calculation in  
> DefaultConsistentHash
> To: infinispan-dev at lists.jboss.org
> Date: Wednesday, September 16, 2009, 2:57 AM
>
> Hey Alex,
>
> On 09/14/2009 10:05 PM, Alex Kluge wrote:
>> Hi,
>>
>>     I would even make the case that the abs and the remainder  
>> operator are unnecessary.  I  have an version of a consistent hash  
>> which is similar to this, and made a few modifications so that my  
>> code delivers the same functionality as the current infinispan  
>> DefaultConsistentHash. The consistent hash is much more natural if  
>> you directly use the hash values. I had meant to contribute this  
>> code a while back, but I was simply too busy getting the full  
>> project of which this is a part to a testable state to make the  
>> infinispan modifications to the code.
>>
>>     These classes are under the examples section in a Consistent  
>> hashing and Caching doc I am working on.
>>
>>      This code also supports virtual nodes, but with the settings  
>> in the example do not produce any. The builder is there to  
>> facilitate the creation of the hash through an XML parser, while  
>> keeping the hash itself immutable. These things can all be tuned or  
>> changed for infinispan's specific needs.
>
> Any chance of sharing this work with the rest of Infinispan  
> community at
> some point?
>
> Regards,
>
>>
>>                                                       Alex
>>
>>
>> --- On Mon, 9/14/09, Krzysztof Sobolewski<Krzysztof.Sobolewski at atm.com.pl 
>> >  wrote:
>>
>> From: Krzysztof Sobolewski<Krzysztof.Sobolewski at atm.com.pl>
>> Subject: [infinispan-dev] Hash calculation in DefaultConsistentHash
>> To: "infinispan-dev at lists.jboss.org"<infinispan-dev at lists.jboss.org>
>> Date: Monday, September 14, 2009, 4:25 AM
>>
>> I took a look at the implementation of DefaultConsistentHash and I  
>> was
>> wondering: does the key hash value have to be positive? As in:
>>
>>         int hash = Math.abs(key.hashCode());
>>
>> I can see that the resulting hash is used to pull a tail map of the  
>> hash
>> space, but there's no reason the SortedMap key has to be positive.  
>> I'm
>> actually most concerned about the fact that Math.abs 
>> (Integer.MIN_VALUE) ==
>> Integer.MIN_VALUE so you have at least one negative key anyway :)
>> -KS
>> _______________________________________________
>> infinispan-dev mailing list
>> infinispan-dev at lists.jboss.org
>> https://lists.jboss.org/mailman/listinfo/infinispan-dev
>>
>>
>>
>>
>>
>>
>> ------------------------------------------------------------------------
>>
>> _______________________________________________
>> infinispan-dev mailing list
>> infinispan-dev at lists.jboss.org
>> https://lists.jboss.org/mailman/listinfo/infinispan-dev
>
> -- 
> Galder Zamarreño
> Sr. Software Engineer
> Infinispan, JBoss Cache
> _______________________________________________
> infinispan-dev mailing list
> infinispan-dev at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/infinispan-dev
>
>
>
>
>
> _______________________________________________
> infinispan-dev mailing list
> infinispan-dev at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/infinispan-dev

--
Manik Surtani
manik at jboss.org
Lead, Infinispan
Lead, JBoss Cache
http://www.infinispan.org
http://www.jbosscache.org