[Spread-users] Optimizing inter-segment communication to reduce packets

[Jonathan Stanton]

I'm hope to have a more detailed discussion on friday as this 
gets compilcated, but John definitely covered some of the basics.

It is possible to do some optimizations on the message dissmemination
and we have tried out some ideas before, but it's hard to keep the 
guaranteed services and performance while not sending some of the messages to
everyone.

A few comments below:

On Sun, Feb 03, 2008 at 10:44:32AM -0800, Jim Kleckner wrote:
> I'm creating a new thread to hold discussion about the
> optimization discussed in two other threads.  I would like to
> explore how to make the smallest change that gets the most "bang
> for the buck" and doesn't violate messaging guarantees.
> 
> Here are some questions/ideas on the topic:
> 
> - Would it simplify the problem if we limit the optimization to
> omit messages only if they are "payload" messages and require
> all membership messages to be transmitted globally?
> In mainstream use, the payload messages ought be significantly
> more numerous than membership messages.

Membership messages are generally small (and less frequent), but currently they use the
same ordering service as other AGREED data messages so they appear
like normal 'data' messages to the lower level send/routeing code. This could be changed.

The tricky bits aren't really knowing when we can try to optimize the content removal, but
in making sure in failure cases we can get the message bodies when we need them to correctly
deliver the messages with the appropriate guarantees.

> 
> - Having a reliable and complete view of all memberships might
> permit you to know definitively whether there are no members
> of a particular group in a given segment and allow you to
> elide sending non-membership messages to that segment.

Spread currently has a 2-level model internally -- groups are implemented at the
top level and the lower level message-sending and routing code doesn't know anything about them. To it 
there is only one group -- that of currently connected daemons. 

> 
> - Would it simplify the optimization if we limited it to classes
> of message with lesser guarantees?  What level of guarantee
> causes the optimization to get very difficult?

Good question. This is possible. 
> 
> - Is there some strategic "weakening" of some type of guarantee
> that would greatly simplify implementing the optimization?

Good topic for a reserach paper or thesis :-)

Cheers,

Jonathan

> 
> 
> I'm including excerpted copies of prior discussion below:
> 
> =============================
> 
> John Schultz wrote:
> ...
> > Yes, as I said before, Spread currently sends all traffic to
> > all daemons. There *might* be an optimization already
> > implemented for private messages within a single daemon.
> ...
> > I wouldn't say it *can't* be changed.  On the other hand, I
> > have thought about it and it is quite difficult to do.  The
> > general idea would be to have the sender send the full message
> > only to those segments that have participating group members
> > and to send small meta-messages to the other segments,
> > indicating that they don't need the full message.  The most
> > difficult changes would be in recovering holes for receivers
> > and handling group membership changes that happen around the
> > time of the send.
> >
> > On the first issue, when a daemon requests a hole to be
> > filled, a responding daemon would need to know whether or not
> > the requestor(s) needs the full message or the meta-message.
> > So, both versions of the message would need to include, at
> > least, the group names to which the messages were sent.  The
> > responder would then need to differentiate resend requests
> > based on the requestor, and for example, not respond if the
> > requestor needs the whole message and the responder only has
> > the meta-message. (Someone with the whole message can derive
> > the meta-message from it and respond to either type of
> > request).  This differentiation might require changes in the
> > way resend requests are put onto and taken off the token (i.e.
> > - the logical byte layout of the token itself).
> >
> > A trickier problem occurs when the membership of the group
> > changes around the time of a send.  If the sender has a
> > hole(s) when it goes to send, then the message that hole(s)
> > represents could actually be changing the group membership(s)
> > for the groups to which it is sending.  Imagine the following
> > scenario:  Daemon #1 sends a join message adding a new member
> > to group X and it is the first member for group X on daemon
> > #1.  Daemon #2 doesn't get that message before it is his turn
> > to send.  According to #2's view of the world, Daemon #1
> > doesn't need the messages A he is sending to group X and so it
> > should (incorrectly) only get the meta-message.  This problem
> > would require every daemon to check every message to ensure
> > that it got the correct version, and to request the full
> > version if it got the meta-message.  A similar problem is that
> > daemons trying to recover message A for daemon #1 may also
> > have the incorrect view of him and will answer his requests
> > with the wrong version.  So, maybe once Daemon #1 incorrectly
> > gets the meta version he will have to re-request the full
> > version explicitly somehow.
> >
> > There might be other considerations / problems that Yair or
> > Jonathan can point out.
> 
> =============================
> 
> John Schultz wrote:
> > On Fri, 1 Feb 2008, John Robinson wrote:
> >
> >> Would it be better if the recovers always sent full messages?
> >> Assuming holes are rare the incremental cost over optimal
> >> would not be too great.
> >
> > This would mean then that only daemons that have gotten the
> > full message can act as recovery nodes.  However, this might
> > not be a bad trade off to make.
> >
> > On your assumption, I would say that holes are rare on a LAN,
> > but not on a WAN.  On a LAN, most of your daemons are probably
> > going to be in one or two segments and so you are going to be
> > sending the full message to the segment usually regardless.
> > Unless you further complicate sending by using unicast to pick
> > out the daemons that need the full message and broadcast the
> > meta-message.
> >
> > There are lots of different tradeoffs and strategies that you
> > could use.
> >
> >> Treading a little off the list, but John started it ;-)...
> >>
> >> John Schultz wrote:
> >>> A trickier problem occurs when the membership of the group
> >>> changes around the time of a send.
> >> ...
> >>> A similar problem is that daemons trying to recover message
> >>> A for daemon #1 may also have the incorrect view of him and
> >>> will answer his requests with the wrong version. So, maybe
> >>> once Daemon #1 incorrectly gets the meta version he will
> >>> have to re-request the full version explicitly somehow.
> 
> 
> _______________________________________________
> Spread-users mailing list
> Spread-users at lists.spread.org
> http://lists.spread.org/mailman/listinfo/spread-users

-- 
-------------------------------------------------------
Jonathan R. Stanton         jonathan at cs.jhu.edu
Dept. of Computer Science   
Johns Hopkins University    
-------------------------------------------------------