# Architecture: Solving a resequencing problem

### Architecture: Solving a resequencing problem

Rate This

Problem:

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.

Sample Flow:

1. Consider orders 1,2,3 in the incoming queue.
2. An in-memory sorted list is created with null values whose key is 1,2,3. Each order is processed by a different receiver and processing pipe.
3. Assume that for some reason that the pipe processing order 1 is slow. Hence orders 2,3 finished processing first and the processed object got updated in the empty queue.
4. The first node in the in-memory queue is still empty, but there are processed objects in the next nodes 2,3
5. As soon as order 1 is processed, the empty node is updated. Since this is the first node, the object is send to external queue and removed from in-memory queue. The pointer is incremented to find that there is object in node 2. This cycle is repeated until it encounters an empty node.

Questions:

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.

• @Pantelis44999

Mind sharing a high level detail of the system that needed this solution? :)

• Prathul,

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.

Thanks!

Karthikeyan

• Hi Karthikeyan,

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.

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.

Thanks

Karthikeyan

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

• Sure, Thanks

Karthikeyan

Page 1 of 1 (7 items)