What is a common approach to in-order multi-threaded message processing?
Consider the following example: I have a publisher that sends numbers into a queue: 1, 2, 3, 4, 5, 6, 7
My goal is to process odds and evens sequentially.
One possible solutions I know is to have a separate queue per thread and split original based on n % m criteria.
What I'm worried about is the fact that numbers may be distributed unevenly and I will end up with some threads to have less work to do.
I have been thinking of implementing custom queue that will check if queue element with same criteria is being processed by some other thread and if it does, try to find another one. That might work, I have tried to implement something, but it gets complicated and is harder to test. That is why I first try to find existing solutions to the problem.
- 4,597
- 1
- 19
- 19
-
Do you necessarily need multi threading? Will it work if you are able to sort the list with evens first and odds last? As assylias said, if you could let us know how you would like the thread to work. It will help – Nitin Chhajer Apr 28 '12 at 19:41
-
Yes I need multi-threading, as the real application of this solution will have to deal with large amount of data, not numbers. I took numbers just to make it easier to describe problem – Igor Nikolaev Apr 28 '12 at 20:42
2 Answers
Not an answer but too long for a comment.
My goal is to process odds and evens sequentially.
In that case, you can not have more than one thread for odds and one for evens. Any reasons why you need a sequential run? Do you use the result of process(2) to run process(4)?
What I'm worried about is the fact that numbers may be distributed unevenly and I will end up with some threads to have less work to do.
Possibly, but how could you distribute more work to the idle thread without breaking the sequential constraint?
- 321,522
- 82
- 660
- 783
-
I took numbers only as an example to demonstrate the problem. In reality I don't know how many groups or types I have. I consume messages from JMS queue. Independent messages are ok to processed concurrently, but I have other types of messages (cancel, amend) that should be processed only in order of their arrival. – Igor Nikolaev Apr 28 '12 at 20:38
If you have 2 types and each has to be processed per-type-squentially you can have only 2 threads. If there is no message of the other type to process only 1 thread can work.
In that case use 2 queues and put messages based on type in there & let each thread consume one queue. You could use a third thread to distribute the messages maybe but in case one thread has a full queue you have to wait until you can consume messages from the original producer unless you have a way to request each type individually or you can throw away messages. You are limited by your own constraints here.
Beyond the theoretical part you may want to look at BlockingQueues & ExecuterServices like in that answer: Producer/Consumer threads using a Queue
-
I'm aware of Producer/Consumer pattern, but existing implementations of Queue and ExecutorService are only good for multi-threaded processing of independent data. – Igor Nikolaev Apr 28 '12 at 20:40
-
So you need kind of a dynamic thread+queue pool that maybe repurposes threads to different types of messages? – zapl Apr 28 '12 at 21:05
-
I was thinking about custom queue implementation that can check what elements types are being processed at the moment and which are not. The groups which are not being processed can be dequeued by free threads. – Igor Nikolaev Apr 28 '12 at 21:33
-
Yes, sounds like you need to implement something custom here. E.g. you could use a synchronized Set where threads check if a certain message type is available before they process a message & put it back afterwards so you can dynamically "assign" threads to messagetypes and still ensure sequential processing. And a queue that can find the next message of a type that is not taken. – zapl Apr 28 '12 at 21:47