This project is a basic implementation of a market data matching engine. The matching engine allows a client to create an order, send it to a market and then receive market data. The engine use multi threads to enable sending orders request at high throughput. The solution is developed and tested in Mac OS X, using Clang 4.2.1 and BOOST 1.68

• CMAKE 3.0
• Clang C++14
• BOOST unit test framework

From the project directory, execute the following commands:

mkdir build
cd build
cmake ..
make

Running the unit tests

make test

Example

using namespace market;
matchingEngine _market;

// Add traders to the market
auto _traderA = _market.addTrader();    
auto _traderB = _market.addTrader();    

// Set a callback to read data when order is executed
_traderA->setOnOrderExecutionCallBack([](const tradeData& p_tradeData) {
std::cout << p_tradeData.m_tradedVolume;  });

// Trader A sends a BUY order with contract ID:7, Volume:100, Price:12.30
_traderA->sendOrder(7, 100, 12.30, orderSide::BUY );

//  Trader B sends a SELL order with contract ID:7, Volume:100, price 12:30  
_traderB->sendOrder(7, 100, 12.30, orderSide::SELL );

Basic operation of the matching engine requires the following functionalities:

1. Matching algorithm, that matches a buy bid with the highest price to an ask bid with the lowest price.
2. Asynchronous order matching so the engine is always available to receive order requests.
3. Notification engine to publish market updates to the participants.

The following system requirements define the scope of the task:

The system is separated into the following components:

1. Matching Engine
2. Order Management
3. Order Book
4. Order
5. Market Data
6. Trader

Description of each component follows next.

The matching engine is the main interface to the clients, it is responsible for initializing all the components required for market operations and handles requests from clients (traders)

The core of matching engine. Main responsibilities are:

• Matching received orders
• Notify orders owners
• Publish order book updates using the market data API.

Design approach:

• Single Producer Single Consumer queue is used to store and dispatch order requests. This allows matching orders asynchronously.
• Active orders are stored in a container. Choice of the container is influenced by answering the following questions:
  1. Performance is critical? Yes, when large number of orders are stored.
  2. Sorting required? No, only min/max elements needed for the matching algorithm.
  3. Lookups required? No.
  4. Insertions/deletions from the container. No insertion happens in the middle or at the front of the container.

  Although choosing a sorted data structure like std::set or std::map is a possibility, they are not the most efficient option for this task, because they are always sorted which is not needed and might slowdown insert operations. Also std::set and std::map are implemented on top of linked list which is not efficient for traversal, if cache locality is considered. To make use of CPU cache and thus a performance boost, choice of contiguous memory is desirable. Binary heap on top of an array is better choice, benefiting from heap properties as well as data locality. Heap is not a sorted but access to min/max items is trivial when heap property is preserved, which is just enough for the purpose of the matching algorithm. average insertion complexity is O(Log(n)) and min/max retrieval is O(1).

Using two heaps, a max heap for buy orders, and a min heap for sell orders. First (max) element in the buy order heap is matched with the first (min) element the sell orders. If the price crosses, then trade will be executed and volume will be deducted. This operation is repeated until price can’t be crossed anymore or there are no orders in the queue. The use this algorithms is inspired from a classical problem of running medians using two heaps (http://www.dsalgo.com/2013/02/RunningMedian.php.html). The payout of performance happens as the size of the order queue grows.

order book groups orders by contracts and ensure that only orders with the same contract ID are matched against each other. Hash map (std::unordered_map) is used to represent order book with contract used as a hash key.

Order contains all data required to compose a market order, such as price, volume etc.. It is worth to mention that price is represented in cents, thus allow integer representation of the price instead of double, which is much simpler when it comes to compare operations, i.e no need for epsilon.

Main responsibility is notifying all subscribed clients with order updates. Delegations design pattern is used to implement events behaviour. Any class that is interested in receiving event must inherit from a event class named Delegate and then implements the virtual functions of the delegate class. The choice of this approach is inspired from Objective-C OS API which I used back in 2011.

Trader is a Representation of client used to initiate order requests and handle received updates. A callback function can be created to be invoked when an event occurs.

The following diagrams are presented to help with understanding the source code implementation

1. The matching engine does not support sending orders from more than one thread.