How to preserve order of incoming requests on a multithreaded server

Question

I want to write a multithreaded server application which is able to process requests in a multithreaded fashion while keeping up execution order of incoming requests of the same client.

For example if client A sends a message M1 and then a message M2 the muiltithreaded server must process these requests in exactly the same order, first M1 and then M2. However, there is no guarantee that threads that process these incoming requests do process these messages in the same order.

For example, thread T1 consumes message M1, thread T2 consumes message M2 and completes processing the message and is able to accept further messages before T1 has finished it's job.

After a message has been processed the result will be passed to some other process for further processing (of which only one exists in the whole computation), this process will schedule sending a response to the client.

These mutliple threads do only exist for the purpose of preprocessing data for some other process. This particular problem sounds like a problem with pipeline characteristics, first M1, then M2, then M3, etc. However, I wanted to parallalize as much as possible to achieve a higher number of communication cycles between the server and the clients.

What architecture / pattern / technique is well suited for such a task?

Answer 1

One name for this kind of requirement is "Unit of Order".

For example, in Weblogic JMS, it provide such feature that, conceptually, you can put an UOO identifier with your message when you are putting message to queue. Weblogic JMS will guarantee that messages of same UOO being processed in chronological order. However, messages under different UOOs can be processed in parallel.

It all depends on what platform or technology you are going to implement it, which I believe there are a lot of way to achieve similar effect.

Answer 2

As someone already mentioned in the comments you could use a simple message queue. When a message is sent all you do is add it to the queue. You then have an asynchronously running "Listener" or "Consumer" which simply processes every message retrieved from the queue one at a time. Even though the server is multi-threaded the Listener/Consumer can be single threaded (though you have the option of using multiple when order is not important).

Edit: As pointed out by one of the comments below this will only work if processing prior to adding to the queue is instantaneous. The idea behind the separation is also to move all your logic and processing to the Listener/Consumer and not keep it in the multi-threaded portion of your code.

Answer 3

To restore the original order after they leave your thread pool, you need some sort of data structure that holds completed messages until the next expected unit arrives and then resume releasing them to the waiting consumer thread.

What particular approach is best will depend upon how many messages are coming through, how sensitive the ultimate recipient is to skipping (nothing is happening while you wait for the out of order message to finish processing), how much work each message takes to process, memory available, etc.

If the consumer expects a certain number of messages per period of time, you might be able to accomplish this by feeding completed units of work into a sorting data structure (like a btree/binarytree/etc) and periodically peeling off the lowest ranked unit. This assumes you will be receiving messages and processing them at a rate more than fast enough to keep the buffer full. If finished messages arrive in too wrong an order, you might need to drop them rather than put them at the front of a buffer).