Re: [infinispan-dev] Collocated nodes
Hey, yeah someone mentioned the idea about multiple hash wheels the other day on dev IRC.
I was thinking about multiple hash wheels over the weekend and I think we can do this
elegantly using hierarchical hash wheels. As I mentioned previously, the current
algorithm, is very simple, deterministic, and elegant. The key point, an absolute must for
consistent hashing to work, is that all surviving cache nodes in view V' are
deterministically placed on the same hash wheel positions absolutely and relatively to
each other as they were in previous view V.
In order to accommodate colocation, just as we currently hash a node address to a hash
wheel we would hash rackId and machineId prior to reaching an address hash wheel. Every
time we place a node on a hierarchical wheel we would pick an appropriate branch
determined by hash of identifier (rackId, machine etc). In the end we should end up with a
tree of hash wheels where leafs are wheels belonging to machine ids. On those machine hash
wheels we would place address nodes, again according to current algorithm.
What would change is the implementation of locating neighbour nodes. Given a key of an
object we would traverse tree of hash wheels until we reach the leaf wheel. Now, instead
of picking a neighbour from the same leaf hash wheel we would backtrack up the tree, pick
another tree branch and traverse down the tree until we select a neighbour from another
tree branch. All of these steps are done deterministically, say, selecting a neighbouring
branch (x many levels up) and using hash of an object key to select appropriate node on
each level of a hierarchical tree.
Does this make sense? Any drawbacks?
Regards,
Vladimir
On 2010-09-27, at 11:15 AM, Elias Ross wrote:
My original message bounced. In other words, if in practice you want
N
copies of something to exist, you can either select N nodes from the
same hash wheel, or create N hash wheels. In this case you'd create at
least two.
On Wed, Sep 22, 2010 at 7:37 AM, Elias Ross <genericelias(a)gmail.com> wrote:
> What about multiple hash wheels? One would exclude those nodes co-located, another
would include all nodes.
> -----Original Message-----
> From: Vladimir Blagojevic <vblagoje(a)redhat.com>
> Sender: infinispan-dev-bounces(a)lists.jboss.org
> Date: Wed, 22 Sep 2010 09:44:54
> To: infinispan -Dev List<infinispan-dev(a)lists.jboss.org>
> Reply-To: infinispan -Dev List <infinispan-dev(a)lists.jboss.org>
> Subject: Re: [infinispan-dev] Collocated nodes
>
> The current function that places nodes on a hash wheel is deterministic in case of
node joins and crashes/leaves. Even after a node leaves/crashes all surviving nodes in
view V' are going be positioned to same hash wheel position as in view V. In another
words, all surviving nodes in V' are deterministically placed on the same hash wheel
positions absolutely and relatively to each other as they were in view V. The case for
join is superfluous to my argument.
>
> I am still learning about this topic but it seems that hash wheel node placing
property defined above is necessary for everything to work properly. If so, I find it very
hard to devise an algorithm that places nodes on hash wheel based on distance. As soon as
one node crashes/leaves positioning surviving nodes in V' to same positions as they
were in view V seems impossible since in distance based positioning we need to place nodes
in relation to neighbouring nodes.
_______________________________________________
infinispan-dev mailing list
infinispan-dev(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/infinispan-dev