[infinispan-dev] Hash calculation in DefaultConsistentHash
Alex Kluge
java_kluge at yahoo.com
Thu Oct 1 12:55:06 EDT 2009
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.
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.
Alex
--- On Thu, 10/1/09, Manik Surtani <manik at jboss.org> wrote:
> From: Manik Surtani <manik at jboss.org>
> Subject: Re: [infinispan-dev] Hash calculation in DefaultConsistentHash
> To: "infinispan -Dev List" <infinispan-dev at lists.jboss.org>
> 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 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
>
>
>
>
>
> _______________________________________________
> infinispan-dev mailing list
> infinispan-dev at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/infinispan-dev
>
More information about the infinispan-dev
mailing list