4

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?

4
  • Sounds like a simple message queue with a timestamp on each message will solve your problem?
    – Zolomon
    Jan 16, 2013 at 18:05
  • @Zolomon: What if the items aren't received in timestamp order? Or what if they're received at roughly the same time and they take non-trivial amounts of time to process, how do you know to wait on M2 while M1 is computing, and process unrelated operations on other threads? Jan 16, 2013 at 21:20
  • nono, the messages will be received ordered from the same client due to TCP, however, I don't see how a timestamp on a queue could guarantee ordered processing of requests from the same client when multiple threads process those requests. Jan 17, 2013 at 8:19
  • 1
    It seems to me that if M1 and M2 must be processed sequentially, then either the caller should wait to send M2 until M1 is done, or alternatively a single message saying "M1-then-M2" should be sent (and processed by a single thread).
    – AakashM
    Jan 17, 2013 at 9:41

3 Answers 3

4

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.

0
4

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.

2
  • 1
    -1: This only works if the operations are virtually instantaneous. Jan 16, 2013 at 21:19
  • @SnOrfus Do you mean if the process of adding to the queue is instantaneous or do you mean if the process done prior to adding it to the queue is instantaneous? The former should be handled by whatever queue technology one chooses to use. It should be atomic at least. As for the latter, you are correct. I will edit my answer to specify this assumption.
    – Asaf
    Jan 16, 2013 at 21:29
0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.