In order delivery in xmpp servers

Looks like I opened a can of worms by asking about ibb (inband data transfer) in the standards list :-)
We always interpreted the xmpp specs to mean that the processing between any two entities at the server MUST be in order, but the spec does not mandate about actual delivery. It is indeed quite simple for client (not just a chat client) implementors if this assumption is mandated: the default binding to tcp encourages the assumption that this is the intention.

Why is it that I believe this so tough to enforce for a server ? or is it really that tough ? And why do I mention ibb in this context ?
I cannot answer the second question for sure, but few of my previous attempts to enforce this when subjected to very high loads have lead to inferior performance. But yes, it is indeed possible that we might be able to get it working at marginally lower throughput at a later point in time.

To the first, is it really that tough ?
Let us consider the case of a simple server which uses one thread per client. A request comes in, server processes it, writes/queues response (if any) and goes back to picking up another request from client.
Things cant get simpler than this (I hope) and for such a server, in order delivery is built into the design.
Would it scale ? Dont immediately write this approach off : you could have a tree of multiplexors which progressively combine input into fatter and fatter pipes, and assuming no latency for reads/writes to multiplexors from server, it could be made to scale for quite a bit.
(Note: I am not intending to make the above look simple: just from the basic server design point of view - rest of the xmpp requirements : the spec requirements, xml parser, xmpp extensions, server management, etc would soon make any competent server product non trivially tough.)
But you will hit the limits to this approach soon enough.

Towards the other end there are various approaches using asynchronous IO, multiple stages and pipelines, thread pools, queues, buffering IO as much as possible (usually necessiated by async io anyway), etc : all carefully tuned considering the load characterstics and deployment considerations along with the behaviour of xmpp : large number clients persistently connected for a long time, but (typically) small xml stanza's and not sustained load of high IO traffic per client. (ofcourse like us, most implementations can and do handle sustained high load too, but that is more uncommon user scenario).
In spite of these, there are limits to how much you can vertically scale a single node: you are bound to hit the limits - be it cpu, memory, IO, etc. Hence, like our product, other xmpp server also support the concept of a pool of servers which collectively behave as a single server.
Horizontal scalability allows you to just add more nodes to the pool as the usage of the server increases (Ofcourse, this is not the only reason for a server pool: fault tolerance, lower latency to client, etc are other reasons but we will focus on this for now).

Now why mention all this ? As the number of pipelines increase as a server implementation/deployment scales: potentially spanning multiple nodes for the purpose of delivery, it becomes progressively tougher to enforce in order delivery. In order processing is much more simpler, the recepient of the stanza processes the input, generates the output to be delivered and it is done with it. The actual delivery could span multiple nodes within a logical server, and potentially get pushed out to a different server altogether.

Does that mean that there will be absolutely no inorder delivery possible at all ? Ofcourse not, atleast in our server, the server always makes a best case effort to deliver in order: but there are a lot of corner cases where a few stanza's could get delivered out of order.
Is this always a bad thing ? Not really - like if two unrelated xml stanza's get 'mixed up', big deal: neither will it be noticable, nor will it have any impact. But there are usecases where this will have impact.
A common enough usecase where it will make it more harder for clients (chat and others) is out of order delivery of messages: like if the recepient client gets "How are you ?" before "Hi", typically it means something is amiss. (There are means to handle corner cases this too btw, but would make clients slightly more complex).
Will this happen very commonly ? Atleast in our server, this can happen when a restricted set of conditions are satisfied: one of which is when a very high number and size of stanzas are transferred between two entities usually hosted on different nodes.

IBB to the problem
And yes, you guessed it, file transfer using ibb for a large enough file which results in transfer of large number of 'big' stanzas : sizes which are an order of magnitude higher than typical xmpp stanzas, could hit this problem when clients push it fast enough.
Does it mean we do not support ibb ? Ofcourse not !
Even with the way the spec stands today (strict enforcement of inorder delivery), there are a bunch of things which are done to handle the higher sustained load of ibb file transfers and to ensure that all ibb stanza's within a transfer are always delivered in order.
Is this a good solution ? Definitely not. Other than the fact that this approach leads to all sorts of special casing and small overhead within some of the critical server codepaths, it is also an approach which does not scale at all. A high enough number of fast clients can make the expierence for all users in a server node a bit sluggish: not to mention additional resource overhead if remote servers cannot drain the stanza's fast enough.
It was this which lead me to query the list: each stanza is marked with a sequence id, use that to 'fill in the gaps' if stanza's are delivered out of order for a small enough window - but the very idea of out of order delivery was percieved as a bit too radical I guess :-)

A best case effort at inorder delivery is different from gaurentee'ed inorder delivery - the latter is much more stringent and has some very severe repurcussions on server scaling. When you position xmpp not just as a means to chat, but as a presence enabled, authenticated, realtime messaging middleware it becomes extremely useful as a messaging infrastructure for applications. As an example try doing async (gamma) notifications using webservices and through xmpp : the former will have all sorts of webservice callbacks, saml assertions, etc and the latter will be a simple message to the reciepent JID. Applications typically 'ramp up' the throughput per session remarkedly (it is not a user typing at 60 words per min anymore) and if current expierences with ibb is anything to go by, it is going to be a very interesting challenge ahead for xmpp server implementations if strict inorder delivery semantics is to be mandated :-)
Comments:

Maybe there could be an exception for "bulk" data transfer where the client is expected to deal with buffering and ordering because it would be a lot of effort for the server. Sort of a quality-of-service improvement that could also provide delayed/deprioritized delivery, although still guaranteed. For things like file transfer it's much better to let the client have the data even if it's not in order, because it's going to have to save it to disk at some point anyway, whereas the server is going to have to sit on a lot of data it doesn't really want to deal with. If the client is really dumb or resource-limited, then maybe it could still ask the server to deliver things in order.

Posted by ey on December 16, 2006 at 06:04 PM IST #

We've been doing a lot of work to move Wildfire over to asynchronous I/O and so are dealing with the in-order delivery problem too (given that each session != one thread anymore). As painful as it looks like implementation is going to be, I think XMPP servers \*should\* ensure in-order delivery of all stanzas. Anything else increases complexity on the client side and the guiding philosophy behind the success of XMPP has been "simple clients, complex servers". Regards, Matt

Posted by Matt Tucker on December 17, 2006 at 06:35 PM IST #

FWIW, I have begun to experience a new slight problem with XMPP packet ordering, particularly with server to server connections. When doing a cut-and-paste of a series of lines, if the client decides, as some clients are wont to do, to send the lines as multiple message stanza's, those messages can get re-ordered when getting to the other user. So, this is an example where there is human consumption of XMPP stanza's that can result in them being delivered out of order. I'm sorry, but I have to come down on the side of requiring in-order delivery. I understand that it makes server implementations, and particularly highly scaleable server implementations, more difficult, but I just can't see pushing this problem out to clients being a real solution to the problem. Jeff

Posted by Jeff McAdams on January 10, 2007 at 03:49 PM IST #

Hi Jeff
When I mention the problem with in order delivery above, I am talking more in terms of strict enforcement - such that protocol extensions can leverage that (like ibb does).
You should not under 'normal' circumstances get out of order delivery stanzas : but if this is a MUST requirement, then it will be needed to be enforced in a lot of corner cases - some of which totally messes up the scalability aspects.
Like while initiating an S2S session with a remote server, while splitting 'load' across multiple servers (so presence could be processed & dispatched faster than the bulkier ibb stanza), etc.
But as a general rule, especially for asynchronous stanza's which cannot enforce reordering, in order delivery should be enforced.
Hence, the example you show, must not happen :-)
Regards,
Mridul

Posted by Mridul on January 10, 2007 at 06:04 PM IST #

Post a Comment:
  • HTML Syntax: NOT allowed
About

mridul

Search

Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today
Bookmarks
Blogroll

No bookmarks in folder