[infinispan-dev] Collocated nodes

[Vladimir Blagojevic]

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 at 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 at redhat.com>
>> Sender: infinispan-dev-bounces at lists.jboss.org
>> Date: Wed, 22 Sep 2010 09:44:54
>> To: infinispan -Dev List<infinispan-dev at lists.jboss.org>
>> Reply-To: infinispan -Dev List <infinispan-dev at 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 at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/infinispan-dev