JPELGRIMS

Matching engines

An order matching engine operates on a limit order book to match buyers and sellers, resulting in a series of trades. It is the mechanism behind price movement; the price at which the last trade was executed usually determines the exchange rate for whatever security is being traded.

Limit order books

All incoming orders are passed on to the matching engine, which then tries to match them against the passive orders in the limit order book (LOB). The book contains all limit orders for which no matches have been found as of yet, divided in a bid side (sorted in ascending order) and an ask side (sorted in descending order). If no matches can be found for a new order it will also be stored in the order book, on the appropriate side.

A limit order book is usually summarized by the following characteristics:

Suppose we have the following LOB:

           LIMIT ORDER BOOK              
      BID SIDE            ASK SIDE     
 QUANTITY    PRICE   PRICE    QUANTITY 
[131.00  -  102.54 | 103.23  -   48.00]
[32.00   -  101.87 | 103.98  -   84.00]
[293.00  -  101.48 | 104.17  -   38.00]
[65.00   -  101.10 | 104.75  -  127.00]

The bid is 102.54, while the ask is 103.23. The spread (ask-bid) is 0.69. The midpoint ((ask+bid)/2) is then 102.885.

The following (often used) visualisation condenses all the LOB information into one simple graph:

Cumulative LOB visualisation

Matching algorithms

The most common matching algorithm is called 'Price/time priority'. Orders in the LOB are filled primarily based on price; if multiple orders are present at the same price level the oldest order will be filled first. This is the same principle as a FIFO queue: first in, first filled.

As an example we will use the previously used limit order book and simulate some incoming orders.

Suppose two orders come in right behind each other; the first one a limit buy order for 24 shares at $102.55 and the second one also a limit buy order for 14 shares at the same price. Seeing as the orders don't match with any asks (due to their prices being lower than the lowest ask) they are both placed in the limit order book. The first order and the second order are stored at the same price level, but the former has priority over the latter due to time priority. This basically means that the first order will be placed on top of the second order in the bid queue.

      BID SIDE            ASK SIDE     
 QUANTITY    PRICE   PRICE    QUANTITY 
[24.00   -  102.55 | 103.23  -   48.00]
[14.00   -  102.55 | 103.98  -   84.00]
[131.00  -  102.54 | 104.17  -   38.00]
[32.00   -  101.87 | 104.75  -  127.00]

Suppose another order comes in, a limit sell order this time, for 40 shares at $102.55. This sell order clearly should have some matches; its price is lower than the highest bid. The matching engine will then use the first two bids at price level $102.54 to fill the incoming order for 38 shares, after which it stops filling due to the limit price (even though the incoming order still has 2 shares left to be filled). The remaining order for two shares is then stored in the limit order book at the limit price, as shown here:

      BID SIDE            ASK SIDE     
 QUANTITY    PRICE   PRICE    QUANTITY 
[131.00  -  102.54 | 102.55  -    2.00]
[32.00   -  101.87 | 103.23  -   48.00]
[293.00  -  101.48 | 103.98  -   84.00]
[65.00   -  101.10 | 104.17  -   38.00]

Note: I have ignored market orders in this section. That is because a market order is in fact just a special case of limit orders. They are supposed to keep on going until they are completely filled, so it may seem like they do not have a limit price at which the order will halt. They do, in fact, but the limit prices are set high/low enough so that they will most likely never be reached while filling the order. So, in order to simulate a market order with a limit order you can just set the limit price either to 0 (for a market sell order) or to +infinity (for a market buy order).

Python implementation

We will need to implement data structures for orders, trades and the limit order book before we can implement a matching engine.

An order is simply an object with price, quantity, side (bid/ask) and order type attributes. A trade can be implemented with only a price and a quantity.

class Order:

    def __init__(self, order_type, side, price, quantity):
        self.type = order_type
        self.side = side.lower()
        self.price = price
        self.quantity = quantity

class Trade:

    def __init__(self, price, quantity):
        self.price = price
        self.quantity = quantity

A limit order book can be easily implemented as a data structure with two sorted lists containing order instances sorted by price; one sorted in ascending order (bids) and one sorted in descending order (asks).

import sortedcontainers

class OrderBook:

    def __init__(self, bids=[], asks=[]):
        self.bids = sortedcontainers.SortedList(bids, key = lambda order: -order.price)
        self.asks = sortedcontainers.SortedList(asks, key = lambda order: order.price)

    def __len__(self):
        return len(self.bids) + len(self.asks)

    def add(self, order):
        if order.direction == 'buy':
            self.bids.insert(self.bids.bisect_right(order), order)
        elif order.direction == 'sell':
            self.asks.insert(self.asks.bisect_right(order), order)

    def remove(self, order):
        if order.direction == 'buy':
            self.bids.remove(order)
        elif order.direction == 'sell':
            self.asks.remove(order)

    def plot(self):
        fig = plt.figure(figsize=(10,5))
        ax = fig.add_subplot(111)
        ax.set_title("Limit Order Book")

        ax.set_xlabel('Price')
        ax.set_ylabel('Quantity')

        # Cumulative bid volume
        bidvalues = [0]
        for i in range(len(self.bids)):
            bidvalues.append(sum([self.bids[x].quantity for x in range(i+1)]))
        bidvalues.append(sum([bid.quantity for bid in self.bids]))
        bidvalues.sort()

        # Cumulative ask volume
        askvalues = [0]
        for i in range(len(self.asks)):
            askvalues.append(sum([self.asks[x].quantity for x in range(i+1)]))
        askvalues.append(sum([ask.quantity for ask in self.asks]))
        askvalues.sort(reverse=True)

        # Draw bid side
        x = [self.bids[0].price] + [order.price for order in self.bids] + [self.bids[-1].price]
        ax.step(x, bidvalues, color='green')

        # Draw ask side
        x = [self.asks[-1].price] + sorted([order.price for order in self.asks], reverse=True) + [self.asks[0].price]
        ax.step(x, askvalues, color='red')

        ax.set_xlim([min(order.price for order in self.bids), max(order.price for order in self.asks)])
        plt.show()
        if save:
            fig.savefig('plot.png', transparent=True)

Implementing the matching engine is a bit more difficult. First of all we will need two FIFO queues; one to store all incoming orders and one to store all resulting trades. We will also need a limit order book to store all orders that didn't match. This implementation also includes a threading option, which is not strictly necessary for the basic functionality.

from threading import Thread
from collections import deque

class MatchingEngine:

    def __init__(self, threaded=False):
        self.queue = deque()
        self.orderbook = OrderBook()
        self.trades = deque()
        self.threaded = threaded
        if self.threaded:
            self.thread = Thread(target=self.run)
            self.thread.start()

Orders are passed on to the engine by calling the .process(order) function. The resulting trades are then stored in a queue, which can then be retrieved sequentially (by iterating over the engine trade queue) or in a list by calling the .get_trades() function.


    def process(self, order):
        if self.threaded:
            self.queue.append(order)
        else:
            self.match(order)

    def get_trades(self):
        trades = list(self.trades)
        return trades

The matching logic looks complicated but is actually rather simple. It basically loops through the orderbook until the incoming order is completely filled. For every fill event a trade object is created and added to the list of trades. If the matching engine was not able to completely fill the order then it adds the remaining volume to the limit order book as a separate order.


    def match(self, order):
        if order.side == 'buy' and order.price >= self.orderbook.best_ask():
            # Buy order crossed the spread
            filled = 0
            consumed_asks = []
            for i in range(len(self.orderbook.asks)):
                ask = self.orderbook.asks[i]

                if ask.price > order.price:
                    break # Price of ask is too high, stop filling order
                elif filled == order.quantity:
                    break # Order was filled

                if filled + ask.quantity <= order.quantity: # order not yet filled, ask will be consumed whole
                    filled += ask.quantity
                    trade = Trade(ask.price, ask.quantity)
                    self.trades.append(trade)
                    consumed_asks.append(ask)
                elif filled + ask.quantity > order.quantity: # order is filled, ask will be consumed partially
                    volume = order.quantity-filled
                    filled += volume
                    trade = Trade(ask.price, volume)
                    self.trades.append(trade)
                    ask.quantity -= volume

            # Place any remaining volume in LOB
            if filled < order.quantity:
                self.orderbook.add(Order("limit", "buy", order.price, order.quantity-filled))

            # Remove asks used for filling order
            for ask in consumed_asks:
                self.orderbook.remove(ask)

        elif order.side == 'sell' and order.price <= self.orderbook.best_bid():
            # Sell order crossed the spread
            filled = 0
            consumed_bids = []
            for i in range(len(self.orderbook.bids)):
                bid = self.orderbook.bids[i]

                if bid.price < order.price:
                    break # Price of bid is too low, stop filling order
                if filled == order.quantity:
                    break # Order was filled

                if filled + bid.quantity <= order.quantity: # order not yet filled, bid will be consumed whole
                    filled += bid.quantity
                    trade = Trade(bid.price, bid.quantity)
                    self.trades.append(trade)
                    consumed_bids.append(bid)
                elif filled + bid.quantity > order.quantity: # order is filled, bid will be consumed partially
                    volume = order.quantity-filled
                    filled += volume
                    trade = Trade(bid.price, volume)
                    self.trades.append(trade)
                    bid.quantity -= volume

            # Place any remaining volume in LOB
            if filled < order.quantity:
                self.orderbook.add(Order("limit", "sell", order.price, order.quantity-filled))

            # Remove bids used for filling order
            for bid in consumed_bids:
                self.orderbook.remove(bid)
        else:
            # Order did not cross the spread, place in order book
            self.orderbook.add(order)

In order to run the engine as a separate thread, simply call the .run() function. Orders can be passed on the the engine by adding them to the engine order queue. Any resulting trades can be retrieved by continually checking the trades queue for new trades.

    def run(self):
        while True:
            if len(self.queue) > 0:
                order = self.queue.popleft()
                self.match(order)