Architecture: Solving a resequencing problem

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! :)

Comments

• Anonymous
  December 27, 2011
  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.

• Anonymous
  December 27, 2011
  The comment has been removed

• Anonymous
  January 12, 2012
  The comment has been removed

• Anonymous
  January 13, 2012
  The comment has been removed

• Anonymous
  January 14, 2012
  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. Thanks Karthikeyan

• Anonymous
  January 15, 2012
  The comment has been removed

• Anonymous
  January 17, 2012
  Sure, Thanks Karthikeyan