[jgroups-dev] Hierarchical message dissemination with JGroups for large clusters

I've been talking to Mike Jensen about a new scheme to disseminate 
messages to a large cluster. This would be based on building up a tree 
from view changes and sending messages to child nodes instead of all 
nodes in a cluster. This would allow for a much more scalable message 
broadcasting.

Below is my (edited) email, I thought other folks might be interested, too.

> Mike Jensen wrote:
>
>
>> When I mentioned having several places within JGroups that would need 
>> to be changed for the mesh logic, let me expand on that with a 
>> specific example. I am currently planning on having only reliable 
>> delivery to directly connected nodes.
>
> By 'directly connected' I assume you mean the immediate child nodes of 
> a parent, in a tree ?
>
>> Example of broadcast messages that are sent will only be reliable in 
>> the fact that one node will verify that it's directly connected 
>> neighbors have received the message, but wont do any verification 
>> from remote nodes. 
>
> OK
>
>> In theory I think this should provide reliable transport overall, but 
>> I am not sure if the current ACKing mechanism will work with that 
>> idea in mind. I am also not sure if within the protocol scope I can 
>> distinguish currently from directly connected nodes, or nodes which 
>> just exist in the view.
>
> Here's a rough idea how this would work. In TREE (just above the 
> transport), you'd create a binary tree from the view changes. E.g. if 
> you have view {A,B,C,D,E,F,G}, you'd have the tree
>
>           
          A
      ____|____
      |       |
      B       C
  ____|__  ___|____
  |      | |      |
  D      E F      G
>
>
>
> The tree doesn't need to be sorted; as long as it is the *same* for 
> all members given the same view, this should be fine.
>
> So the idea is for A to send a message M only to B and C, which would 
> then forward M to their child nodes. If a child (G) sends a message, 
> it would send it to their parent (C) which would send it to A and F. A 
> would then send it to the subtree starting with B (not to C !).
>
> Basically bubble-up/bubble-down.
>
>
> This way, we avoid a mesh of connections. (BTW you shouldn't call your 
> protocol MESH, because that's what we're trying to avoid...).
>
> However, retransmission as it currently works would break this: If C 
> broadcasts a message, and D discovers a gap to C's previous message, 
> then D would ask C for retransmission (or it would send a multicast, 
> if configured in NAKACK). However, what C should do here is to ask B 
> first, then A.
>
> I think this could be implemented by making the target of a 
> retransmission in NAKACK *pluggable*: there would be a callback that's 
> called to compute the target of a retransmission request, say
>
> Address getTarget(Address original_sender, Address requester);
>
> In the example above, where D is missing a message from C, the 
> callback would contain the original sender (C), the local address (D), 
> and would return B as target. (The default plugin would return either 
> C or null (if use_mcast_xmit_req=true)).
>
> (This is actually needed for my daisy chaining [1] protocol as well: 
> in it the callback will always return as target the neighbor from 
> which I received a message).
>
> So, I think with the above scheme, we can implement hierarchical 
> message dissemination, plus retransmission as well. This works well 
> for multicasts (dst=null).
>
> Having done this, we also need to analyze the unicasts used in 
> JGroups. For example, FD creates its own logical ring over a view, 
> where A sends heartbeats to B, B to C, C to D and so on. A solution to 
> this (if it turns out to be a problem) would be to trash FD and use 
> FD_ALL (which uses multicasts), or to create an additional FD_TREE 
> protocol, which uses hierarchical heartbeats, e.g. A pings B and C, C 
> pings F and G and so on...
>
>
>> Right now that is the worst example I can think of, but I have not 
>> had time to fully explore everything yet. Do you think modifications 
>> outside a protocol would be necessary to achieve something like that? 
>
> Yes, see above, but I think they could be kept to a minimum...
>
>
>
>
>
>
> [1] https://jira.jboss.org/browse/JGRP-1021
>


-- 
Bela Ban
Lead JGroups / Clustering Team
JBoss


------------------------------------------------------------------------------
This SF.net email is sponsored by 

Make an app they can't live without
Enter the BlackBerry Developer Challenge
http://p.sf.net/sfu/RIM-dev2dev 
_______________________________________________
Javagroups-development mailing list