Order Matching Engine Part 3 - Matching Strategies

In my previous post I explained the data structures used in my Order Matching Engine and how they evolved. In this post I'll explain how each strategy is actually implemented, following a buy order through the system along the way.

Strategies

In the beginning, I only had the price-time priority hard-coded into the Book class, since it served my purposes.

In this commit, I separated the matching logic from the Book class by introducing a Matcher class, which holds a reference to the Book it operates on. After that, I created interfaces for both (IMatcher and IOrderBook).

Lastly, I renamed Matcher to Strategy, replacing IMatcher with the IOrderMatchingStrategy interface, and Matcher with its first implementation, the PriceTimePriorityStrategy class. I also took this chance to decouple it from the Book. Now, instead of the strategy holding a reference to the book, the Book owns its strategy: it receives it through its constructor and passes itself as an argument on every matchOrder() call. I also added a setMatchingStrategy() method, so the strategy can be swapped at runtime.

Doing so made my job easier when it came to adding the top/priority pro-rata strategy: all I did was write an extra implementation of IOrderMatchingStrategy, without touching the Book at all.

For now, let's check what the price-time priority algorithm looks like when a buy order comes in, based on my current code (the sell side mirrors it):

• First, a TCP message is received and (assuming it's a FIX message) the FixOrderHandler calls insertOrder() for the book of that security (I will talk about the TCP servers and message validation in a separate post).
• insertOrder() locks the book using a mutex and calls insertOrderUnlocked() (a pattern I'll keep for now).
• insertOrderUnlocked() does the following checks:
  • Order price must be positive
  • Order quantity must be positive
  • Order price must align with tick size (the price must be a multiple of the tick size)
  • Order id must not be a duplicate
• After these checks, the order is inserted in allOrders and IOrderMatchingStrategy::matchOrder() is called, which then calls the strategy's matchBuyOrder(), since we are dealing with a buy order, and if the sell bucket isn't empty, it calls the strategy's matchBuyAgainstBucket(). This is where the strategy runs and then returns (both strategies explained below).
• At the end, if this order was fully fulfilled or cancelled it's removed from allOrders. If it's still active (unfilled or partially filled) then it's pushed into the buy bucket.

PriceTimePriorityStrategy::matchBuyAgainstBucket()

• First, it is enclosed in a while-loop that runs as long as the bucket isn't empty and the buy order isn't fully fulfilled or cancelled.
• It then finds the ask (best price for a sell order in the bucket) at the top of the bucket and if its price is higher than the buy order's, it exits the loop.
• Afterwards, we see the following code:

  double tradedQty = std::min(buyOrder.quantity, sellOrder.quantity);
   
  buyOrder.quantity  -= tradedQty;
  sellOrder.quantity -= tradedQty;

  which is the actual reduction of quantities. It takes the minimum amount between the buy order and the ask (sellOrder) and then reduces both quantities by that amount.
• After that, both the buy order and the ask are updated to be fully or partially fulfilled using the code:

  buyOrder.fulfilled  = compareDoubles(buyOrder.quantity,  0.0) == 0 ? FULLY_FULFILLED : PARTIALLY_FULFILLED;
  sellOrder.fulfilled = compareDoubles(sellOrder.quantity, 0.0) == 0 ? FULLY_FULFILLED : PARTIALLY_FULFILLED;

• At the end, the ask is checked and, if it's fully fulfilled, removed from the sell bucket and allOrders, so that the loop can continue and check the next ask.

TopProRataStrategy::matchBuyAgainstBucket()

• Like PriceTimePriorityStrategy, it starts with a while-loop and checks the ask's price against the buy order.
• It then gathers all the ids for the sell orders for that level, as well as that level's quantity, through another while-loop.
• If the level's quantity is less than or equal to the buy order's, all the sell orders are filled and the outer loop starts anew. If the level has more quantity than the buy order, we start the interesting part of the top/priority pro-rata algorithm:
  • We start with the first order, which gets (at most) the priority slice, after which we check whether the buy order is fully filled (done), whether the first order is fully filled (drop it), and whether any orders are left at this level.
  • After that, we loop through all the sell orders (first included) to calculate their share.
  • We then calculate the remainder lots that are to be distributed.
  • Lastly, we loop through the sell orders again to fill them with both their share and the remainder lots.

The code for this part is given below:

auto firstOrderId = ids.front();
Order& firstOrder = orders.at(firstOrderId);
double tradedQty = std::min(PRIORITY_LOT, std::min(buyOrder.quantity, firstOrder.quantity));
applyFill(buyOrder, firstOrder, firstOrderId, tradedQty, bucket, orders);
levelQuantity -= tradedQty;
 
if (firstOrder.fulfilled == FULLY_FULFILLED) {
	ids.pop_front();
}
 
if (buyOrder.fulfilled == FULLY_FULFILLED)
	return;
 
if (ids.empty())
	continue;
 
std::vector<double> shares;
shares.reserve(ids.size());
double sharesSum = 0;
 
for (const auto& id : ids) {
	Order& order = orders.at(id);
	double rawShare = (order.quantity * buyOrder.quantity) / levelQuantity;
	double share = std::floor(rawShare / lotSize) * lotSize;
	sharesSum += share;
	shares.emplace_back(share);
}
 
int remainderLots = static_cast<int>(std::round((buyOrder.quantity - sharesSum) / lotSize));
 
size_t idx = 0;
for (const auto& id : ids) {
	Order& order = orders.at(id);
	double tradedQty = shares[idx++] + ((remainderLots-- > 0) ? lotSize : 0);
	applyFill(buyOrder, order, id, tradedQty, bucket, orders);
	levelQuantity -= tradedQty;
}

Why the two passes

The naive way to split a pro-rata is a nested loop that hands out one lot at a time, cycling through the orders, until the incoming order is filled. That costs O(lots × orders), so a big trade means a lot of work.

Instead, the first pass calculates each order's proportional share rounded down to whole lots. The second pass hands out those shares along with leftover lots, one per order in queue order. The result is O(orders) no matter how big the trade is.

What I love about my decision to use interfaces is that in order to create TopProRataStrategy I simply copy-pasted PriceTimePriorityStrategy, renamed the files/classes and rewrote the bodies of matchBuyAgainstBucket() and matchSellAgainstBucket(). Perhaps at some point I can use a template to merge these functions, but for now I think it's best to leave them as is.

Small side note: if you browsed my code you may have realized that I also created applyFill(), but that was to avoid code duplication, not because it was strictly necessary, so the simplicity of the copy-paste argument holds.

That's all I have on the strategies. Between this post and the previous one, I've covered how my data structures evolved, what I'm using now and how each strategy works. Perhaps I'll also add a simple pro-rata by copy-pasting TopProRataStrategy and simplifying it, but for now I think I'll focus on the next step. Look forward to it!