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

I would like to talk more about this after my demo. You answered my
questions, but I don't think we are quite fully on the same page as far
as design is concerned. Particularly with respects to how messages get
routed.

Thanks for your input, I will be looking for lots more guidance too.
But I wont be able to start focusing on this aspect more until after
the demo anyways (and I am interested in what feedback I get before I
start implementing anything into JGroups anyways).

Bela Ban wrote:

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

------------------------------------------------------------------------------
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