Sunday, 9 June 2013

Event loop and multi-threaded ordered execution

I wanted to write about real use case of less known design patterns and how they can help achieving a simplified design and high performance.
In message oriented business use cases, sometimes there is a need to process messages in the received order so that system is consistent according to the time.
For example if trader buys 10 lot of a share at 11:00:00 am and then wants to buy another 15 lot of the share at 11:00:01. Order management system has to process these orders in the received order to make sure trader’s account is updated correctly and system does check remaining funds, purchased shares in a right way.
Another similar use case is processing events of a football match. In a match there is a number of events from scoring a goal, yellow cards, red cards, stop times, free kicks, etc. In a betting portal all these events could be used as a betting market, a market operator may create a betting market for number of free kicks or when/how many yellow/red cards will happen.
A simple use case scenario gets complicated when number of trade orders/ betting market events are in high volume and there is business demand to settle these activities instantly.
A naive approach to process orders from a message queue is to create a multi-threaded executor which receives messages and dispatches the them to the underlying threads. By default a thread executor doesn’t have any logic of dispatching work items to the worker threads.
Problem:
Let’s consider a trader places two trade orders M1, M4 and expects that system process these trades in the received order while another trader places M2 and M5 orders.
How to ensure trades will be processed in the received order in a multi-threaded environment ?
In the naive approach unfortunately there is not guarantee that thread2 will be executed after thread1 which processes M1.
unordered_trade_execution
Following test case and console output shows unordered message processing.
Test case


Unordered message processing
Not so good solution:
To solve this problem, there is a need to mark relevant messages together. For example adding a trader id field to the message as a correlation id helps identifying which messages are for a particular trader.
One approach to solve this problem is creating a map of correlation id and thread id, so that a customized thread executor can figure out how to distribute messages amongst worker threads.
Following code piece demonstrates that approach.

Map implementation can be a self-expiring map, like a cache, to ensure map doesn’t grow over the time.
However this solution introduces a complicated expiring map and how to determine expiration of map items.

A better solution:
The following picture illustrates a better  solution. This solution distributes messages having same correlation id to the same underlying thread. Once messages are assigned to the same thread, thread processes these messages in the received order.ordered_trade_processing
It is easier to use hash value of the correlation id and size of the thread executors to determine which executor should pick the message. In this solution it is assumed correlation is immutable once being assigned.
As hash value of the correlation id is fixed, same thread/executor can be assigned to the messages having same correlation id.
Following code piece shows how hash value is used to find index of a thread/executor.

Whole project can be found on github

Composite pattern in action

I recently found myself frequently using composite pattern to solve some software design problems ranging from numerical calculations to business rules validation and complex form print operations. The more I use this pattern the more I like it. These days my favourite pattern is composite pattern.
Composite pattern helps solving a computation problem by splitting the problem into sub tasks, Each sub task can take some parameter and return a computed value which can be passed to other sub tasks.
For example calculating a polynomial function f (x)=  ( (x^3 + 1/x ) ^4 ) –9 in java may look a bit weird. However once the problem is defined as sub problems, solution is on the horizon.
I will start off first declaring an interface which takes the variable x as the parameter.

Second step is trying some simple polynomials, for example f (x)=x+1, f (x)=4.
In the first example function is sum of two functions, namely identity and constant, so I can try defining an identity and constant function and summation function which is sum of all given functions.
Identity function will return whatever value is passed to itself and looks like below.

On the other hand, a constant function returns a predefined value regardless of the parameter being passed.


With similar approach an add function can be defined as below.

It is interesting to see that add function is made of functions passed as parameters. Add function eventually executes each function passed and then generates a sum of values as its value.

That approach enables splitting problem and solve each sub problem individually. When all sub solutions are combined, a powerful composite whole solution is made of. A composite structure enables solving complex problems meanwhile building strong solution hierarchy and encapsulation. Following same pattern I have created PowerFunction and MultiplyFunction and created a test case to see my function composite in action.


After applying same methology, I have created MultiplyFunction,DivFunction and MinusFunction to complete my class hierarchy.

All completed functions can be found on github