Architecture: Solving a resequencing problem

  • Article

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