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

From: Manik Surtani <manik(a)jboss.org&gt; Subject: Re: [infinispan-dev] Hash calculation in DefaultConsistentHash To: "infinispan -Dev List" <infinispan-dev(a)lists.jboss.org&gt; Date: Thursday, October 1, 2009, 7:25 AM 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(a)redhat.com&gt; > wrote: > > From: Galder Zamarreno <galder.zamarreno(a)redhat.com&gt; > Subject: Re: [infinispan-dev] Hash calculation in  > DefaultConsistentHash > To: infinispan-dev(a)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&lt;Krzysztof.Sobolewski(a)atm.com.pl >> >  wrote: >> >> From: Krzysztof Sobolewski&lt;Krzysztof.Sobolewski(a)atm.com.pl&gt; >> Subject: [infinispan-dev] Hash calculation in DefaultConsistentHash >> To: &quot;infinispan-dev@lists.jboss.org&quot;&lt;infinispan-dev(a)lists.jboss.org&gt; >> 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(a)lists.jboss.org >> https://lists.jboss.org/mailman/listinfo/infinispan-dev >> >> >> >> >> >> >> ------------------------------------------------------------------------ >> >> _______________________________________________ >> infinispan-dev mailing list >> infinispan-dev(a)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(a)lists.jboss.org > https://lists.jboss.org/mailman/listinfo/infinispan-dev > > > > > > _______________________________________________ > infinispan-dev mailing list > infinispan-dev(a)lists.jboss.org > https://lists.jboss.org/mailman/listinfo/infinispan-dev -- Manik Surtani manik(a)jboss.org Lead, Infinispan Lead, JBoss Cache http://www.infinispan.org http://www.jbosscache.org _______________________________________________ infinispan-dev mailing list infinispan-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/infinispan-dev

From: Manik Surtani <manik(a)jboss.org&gt; Subject: Re: [infinispan-dev] Hash calculation in DefaultConsistentHash To: "infinispan -Dev List" <infinispan-dev(a)lists.jboss.org&gt; Date: Thursday, October 1, 2009, 12:15 PM On 1 Oct 2009, at 17:55, Alex Kluge wrote: > Hi, > >  Thanks for the comments. > >  On item 1: >   I chose the way we use the hashing to fit in with the > current Dell-MessageOne use cases. It is an easy change to use > a different hash in the locate method , you just want to be careful > about getting uniform distributions of values, as this determines the > distribution of key/value pairs among the caches. So you exchange > one requirement for another. I could even implement a strategy pattern > here to make it very adaptable. > >  For generating the original bins in the constructor, however, it is > important to use a representation that is malliable, like a string, to > generate the virtual nodes. For the server class you also have  > complete > control so it is a reasonable restriction. Yes, this is fine for the Address type.  Just that we can't depend on  meaningful toString() impls on keys.  The only thing we can really  rely on (which we can reasonably expect users to implement) is hashcode ().  So what would be ideal is to take the hashcode() generated by the  user's algo, and use a bit spreader to ensure it is properly  distributed.  A bit like the way JDKs do with HashMap, etc.  I'm open  to suggestions as to the bit spreader algo to use. Cheers -- Manik Surtani manik(a)jboss.org Lead, Infinispan Lead, JBoss Cache http://www.infinispan.org http://www.jbosscache.org _______________________________________________ infinispan-dev mailing list infinispan-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/infinispan-dev

Hi Alex. Looks good - except for the name collision, as you mentioned :) You mentioned (in ReHash.java) that "It is important that ... and not use the Object hashcode.". Could you explain this a bit more? Again, this is not something we can mandate, since folks could use JDK types as keys (Integer, String, even Object). Cheers Manik On 12 Oct 2009, at 06:54, Alex Kluge wrote: > Hi, > > I had a few moments to do a bit of reading on the desirable traits > of such a hash function, and I have modified the proof of concept > to to utilize the key's hash function, then use another hash to > ensure a uniform distribution of hashes. It also supports the > injection of a different hash function. As before, it is at the > bottom of > > http://www.vizitsolutions.com/ConsistentHashingCaching.html > > Of course after I uploaded it, I saw the (almost) name collision > with ReHash... > > Alex > > > --- On Thu, 10/1/09, Manik Surtani <manik(a)jboss.org&gt; wrote: > >> From: Manik Surtani <manik(a)jboss.org&gt; >> Subject: Re: [infinispan-dev] Hash calculation in >> DefaultConsistentHash >> To: "infinispan -Dev List" <infinispan-dev(a)lists.jboss.org&gt; >> Date: Thursday, October 1, 2009, 12:15 PM >> >> On 1 Oct 2009, at 17:55, Alex Kluge wrote: >> >>> Hi, >>> >>> Thanks for the comments. >>> >>> On item 1: >>> I chose the way we use the hashing to >> fit in with the >>> current Dell-MessageOne use cases. It is an easy >> change to use >>> a different hash in the locate method , you just want >> to be careful >>> about getting uniform distributions of values, as this >> determines the >>> distribution of key/value pairs among the caches. So >> you exchange >>> one requirement for another. I could even implement a >> strategy pattern >>> here to make it very adaptable. >>> >>> For generating the original bins in the >> constructor, however, it is >>> important to use a representation that is malliable, >> like a string, to >>> generate the virtual nodes. For the server class you >> also have >>> complete >>> control so it is a reasonable restriction. >> Yes, this is fine for the Address type. Just that we >> can't depend on >> meaningful toString() impls on keys. The only thing >> we can really >> rely on (which we can reasonably expect users to implement) >> is hashcode >> (). So what would be ideal is to take the hashcode() >> generated by the >> user's algo, and use a bit spreader to ensure it is >> properly >> distributed. A bit like the way JDKs do with HashMap, >> etc. I'm open >> to suggestions as to the bit spreader algo to use. >> >> >> Cheers >> -- >> Manik Surtani >> manik(a)jboss.org >> Lead, Infinispan >> Lead, JBoss Cache >> http://www.infinispan.org >> http://www.jbosscache.org >> >> >> >> >> _______________________________________________ >> infinispan-dev mailing list >> infinispan-dev(a)lists.jboss.org >> https://lists.jboss.org/mailman/listinfo/infinispan-dev >> > > > > _______________________________________________ > infinispan-dev mailing list > infinispan-dev(a)lists.jboss.org > https://lists.jboss.org/mailman/listinfo/infinispan-dev -- Manik Surtani manik(a)jboss.org Lead, Infinispan Lead, JBoss Cache http://www.infinispan.org http://www.jbosscache.org _______________________________________________ infinispan-dev mailing list infinispan-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/infinispan-dev

On 13 Oct 2009, at 15:30, Jason T. Greene wrote: > We've always had that requirement. Hes referring to classes which do > not > define a hashCode, and thus inherit Object.hashCode(), which > produces a > number based on the reference pointer which is different per-vm. Sure, but for folks that don't expect to be able to retrieve a key from anywhere, it should still work. But that is a weird use case anyway, unless the cache is in local mode in which case DIST doesn't apply.

Hi, I expect that using the Object hashCode, even within the same VM, will be problematic. Two instances of such a class will not have the same hashCode. Hence using one as a key to insert a value into the cache, then using the other to retrieve the value will not produce the expected results. This is true of pretty much any type of hash table, distributed or not. Your key can not use the Object hashCode method.