[infinispan-dev] Hash calculation in DefaultConsistentHash

Manik Surtani manik at jboss.org
Thu Oct 1 13:15:08 EDT 2009


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.

>  On point 2:
>  Keep in mind that the n in O(log n) is not the range of values,
> but the number of elements. So a locate method call with 30 virtual
> servers will be O(log 30), independent of the range of values. Not
> using abs or % makes the code faster and cleaner, the later actually
> reducing the likelihood of issues as the code evolves. Simpler and
> cleaner is usually better.

Yes I agree, my mistake (as Krzysztof pointed out earlier).

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







More information about the infinispan-dev mailing list