Introduction

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

The source code

Dependencies

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

Building the solution

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 );

Technical Content

Task breakdown

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.

Scope of the task

The following system requirements define the scope of the task:

ID#	Application	Description
1	Order Management API	Match/execute orders
2	Order Management API	Send order buy update to the owner of a buy order
3	Order Management API	Send order sell update to the owner of a sell order
4	Order Management API	Keep track of active orders
5	Order Management API	Publish order book updates and public trades using the Market Data API
6	Order Management API	Sort order book by price
7	Client (trader)	Send buy order requests to the Order Management API
8	Client (trader)	Send sell order requests to the Order Management API
9	Client (trader)	Handle data received from the Market Data API and Order Management API
10	Order	Contain: Contract ID, Unique order ID, Price, Volume, Side
11	Order Book	Group orders by contracts, contract is a unique ID
12	Market Data API	Send order books to all subscribed clients
13	Market Data API	Send public traders to all subscribed clients
14	Matching Engine API	Provide public interface to the client
15	Matching Engine API	Handle order requests from client

Solution description

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.

Matching Engine

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)

Order Management

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

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

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.

Market Data

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

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.

Diagrams

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

Class Diagram

Sequence Diagram

Limitations:

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