Some systems, especially the financial ones require that the sequence of orders coming into the system be maintained after processing. This sounds like a simple problem to solve. But consider the same system in a scaled up scenario. There could be multiple receiver that picks up the order from an incoming queue and processes it in parallel pipes. How do we ensure that the after processing, the orders are sent out of the system in the same order? The problem we are trying to solve is what is known as resequencer problem.
Solution: Make each of the order coming into the system pass through a unique id generator. If each order has a unique sequence id, this step can be skipped. As soon as the unique id is generated, create an empty entry in an in-memory collection with the order id as key. The in-memory collection can be a SortedList or HashTable. Once the processing of each processing pipe is complete, the empty object in the in the in-memory queue is updated with the processed object. If the processed object is the first node in the in-memory queue, start sending the order to the external queue until an empty object is encountered.
1. What if the processing of one of the pipes slows down? Wouldn't it cause the other orders to wait before being sent to the external system?Ans: Right! But remember, a system can only be as fast as its slowest link. This holds true in this case also.
2. Wouldn't the id generator and in-memory queue become a single point of failure?Ans: To avoid this, you can maintain a copy of it in a cache. Server Appfabric cache with proper locks would help you achieve it.
Do share your thoughts and feedback on this solution; especially if you can think of a better solution. Happy coding! :)
Even though the problem I was researching recently had nothing to do with financial systems this was exactly what I was looking for.
Thank you, great article.
Mind sharing a high level detail of the system that needed this solution? :)
Thanks for the post...I have a question.
You said there will be a list (queue data structure) be maintained containing the unique Id.
In your diagram Where exactly this list be maintained ? Which component will be maintaining this list?
The receiver 1,2,3 will be running in 3 different threads and each one will not be aware of the other's message.
Even the main thread which started the reciver threads will also be not aware about the messages.
Your solution will work if you have single reciver and multiple processing threads. In this case the reciver code can maintain the list that you are referring to. Please correct my understanding if I am wrong.
In this diagram, I have not shown the queue data structure. You can easily maintain the queue in an external system which the recievrs will interact with. As soon as the reciever recieves the message, it will sent a request to add the message id to the queue. The external system can use an in-memory queue or even a list object in server appfarbic cache.
If all these components are running in seperate systems, then the reciver will not be able to maintain the queue because before sending the message will have to go back to reciver to identify queue position. Hope that helps.
Thanks for the reply
Sure, you can maintain the list in an external system/thread. But, since you are running the receiver in multiple threads - what is the guarantee that the message 1 that is being read by the reciver 1/2/3 is going to call the external system/thread to update the list first?
Let's say the messages 1 2 and 3 are being read in time T1, T2 and T3 respectfully by the receivers 1,2 and 3
Now, the queue that is being maintained by the external system needs to be updated with the new message arrivals. Is there any guarantee that the message 1 that is being read by receiver 1 in time T1 will call the external system to update the queue first? What if the receiver 1 had a delay in calling the external system to update the queue and meanwhile the receiver 2 made a call to update the queue? Now, the sequence is incorrect.
Correct. The scenario explained above is ideal when there is only one receiver and multiple processing pipes. But if you take a real case scenario (like financial), these messages come via high performance queues. These queues inherently support features like guaranteed message sequence, generating a unique id for the messages etc. I have taken into consideration only the core solution to give an idea of how the re-sequencing problem can be solved. You will have to tweak the solution based on the problem at hand which would vary from system to system.