Coding a simple limit order book with Python

I will walk through designing and coding a simple two-sided continuous auction limit order book using an object-oriented approach with Python 3. The full code is available on GitHub as orderbook3.py. The limit order book will have attributes and methods. Private attributes (things the order book has) and methods (things the order book does) are not used outside of the class declaration. These are denoted with a leading underscore. Public attributes and methods are called from other modules that import the orderbook. These have no leading underscore.

The first step is to import some python modules we will need within the class: bisect and pandas. We will use bisect.insort to maintain two ordered lists of prices – thereby maintaining price priority in both the bid and ask queue and pandas to facilitate permanent results storage in hdf5 files.

import bisect
import pandas as pd 

Next, we declare the Orderbook class and initialize the attributes. For now, we will skip the documentation comments.

class Orderbook(object):

    def __init__(self):
        self.order_history = []
        self._bid_book = {}
        self._bid_book_prices = []
        self._ask_book = {}
        self._ask_book_prices = []
        self.confirm_modify_collector = []
        self.confirm_trade_collector = []
        self._sip_collector = []
        self.trade_book = []
        self._order_index = 0
        self.traded = False 

First, Orderbook inherits from object – the default in Python 3. order_history is a list of all of the orders sequenced by arrival time. This is used to reconstruct the orderbook after the simulation is run. _bid_book_prices and _ask_book_prices are lists of existing prices in ascending order. The sorted order is established by using bisect.insort. The prices act as pointers to the two books: _bid_book and _ask_book. An example of the _ask_book_prices:

[998, 999, 1000, 1001, 1005, … , 1010]

And an example of the _ask_book:

{998: {‘num_orders’: 2, ‘size’: 5, ‘order_ids’: [id1, id2], ‘orders’: {id1: {order for id1}, id2: {order for id2}}, 999: …}

confirm_modify_collector and confirm_trade_collector are public lists that carry messages (dictionaries) to the traders. _sip_collector is a private list of dictionaries containing best bid and ask prices along with their associated sizes for each discrete event. This top-of-book information is provided to traders via a public Orderbook method called in the looping logic contained in a separate module. trade_book is a list of dictionaries containing details for each trade. _order_index is used to generate unique incremented order ids and traded is a public boolean attribute used in the simulation looping logic to determine if a trade occurred or not. Much of this will become clearer as we introduce the Orderbook methods.

There are three major types of methods in Orderbook. The actual order processing and matching is done by a public process_order method and a private _match_trade method, respectively. Several methods are helper functions called from these two main order processing methods. The remaining methods prepare and save some important data for processing after the simulation is run.

_add_order_to_history adds a unique order index to an existing order (dict) and appends the modified order to the order_history list.

    def _add_order_to_history(self, order):
        '''Add an order (dict) to order_history'''
        hist_order = {'order_id': order['order_id'], 'timestamp': order['timestamp'], 'type': order['type'],
                      'quantity': order['quantity'], 'side': order['side'], 'price': order['price']}
        self._order_index += 1
        hist_order['exid'] = self._order_index
        self.order_history.append(hist_order)

Here we can see how simple the order book really is. To extend this orderbook, we could add reserve or hidden features to the order. We would also have to modify the bookkeeping and matching logic that follows. Note that hist_order is just a hand-written copy of the order parameter. This is much faster than using copy.deepcopy().

add_order_to_book performs all of the book maintenance for incoming orders that do not result in a full trade (i.e., either the order is not priced to trade or the size is not fully exhausted if it is priced to trade).

    def add_order_to_book(self, order):
        '''
        Use insort to maintain on ordered list of prices which serve as pointers
        to the orders.
        '''
        book_order = {'order_id': order['order_id'], 'timestamp': order['timestamp'], 'type': order['type'],
                      'quantity': order['quantity'], 'side': order['side'], 'price': order['price']}
        if order['side'] == 'buy':
            book_prices = self._bid_book_prices
            book = self._bid_book
        else:
            book_prices = self._ask_book_prices
            book = self._ask_book
        if order['price'] in book_prices:
            book[order['price']]['num_orders'] += 1
            book[order['price']]['size'] += order['quantity']
            book[order['price']]['order_ids'].append(order['order_id'])
            book[order['price']]['orders'][order['order_id']] = book_order
        else:
            bisect.insort(book_prices, order['price'])
            book[order['price']] = {'num_orders': 1, 'size': order['quantity'], 'order_ids': [order['order_id']],
                                    'orders': {order['order_id']: book_order}}

Again, the incoming order is copied to a new dict object. The order side determines which book we are using: bid or ask. Then we check if the order price is in the list of book_prices – a very expensive task that would take longer if we were to check for “not in” prices. If the order price is already in the book, the order book is updated with the new information. If not, a new price is inserted in the proper sorted slot and the book is (re-)established for the new price.

_remove_order removes an order from the order book and removes the price from the price list if removal results in an empty book for that price. Maintaining a list of valid prices instead of merely keeping all of the prices (with some prices pointing to empty books) speeds up the trade matching algorithm.

    def _remove_order(self, order_side, order_price, order_id):
        '''Pop the order_id; if  order_id exists, updates the book.'''
        if order_side == 'buy':
            book_prices = self._bid_book_prices
            book = self._bid_book
        else:
            book_prices = self._ask_book_prices
            book = self._ask_book
        is_order = book[order_price]['orders'].pop(order_id, None)
        if is_order:
            book[order_price]['num_orders'] -= 1
            book[order_price]['size'] -= is_order['quantity']
            book[order_price]['order_ids'].remove(is_order['order_id'])
            if book[order_price]['num_orders'] == 0:
                book_prices.remove(order_price)

_modify_order behaves similarly, but also checks if the modify actually results in removal.

    def _modify_order(self, order_side, order_quantity, order_id, order_price):
        '''Modify order quantity; if quantity is 0, removes the order.'''
        book = self._bid_book if order_side == 'buy' else self._ask_book        
        if order_quantity < book[order_price]['orders'][order_id]['quantity']:
            book[order_price]['size'] -= order_quantity
            book[order_price]['orders'][order_id]['quantity'] -= order_quantity
        else:
            self._remove_order(order_side, order_price, order_id)

_add_trade_to_book is a helper function that facilitates trade bookkeeping.

    def _add_trade_to_book(self, resting_order_id, resting_timestamp, incoming_order_id, timestamp, price, quantity, side):
        '''Add trades (dicts) to the trade_book list.'''
        self.trade_book.append({'resting_order_id': resting_order_id, 'resting_timestamp': resting_timestamp, 
                                'incoming_order_id': incoming_order_id, 'timestamp': timestamp, 'price': price,
                                'quantity': quantity, 'side': side})

_confirm_trade and _confirm_modify are helper functions that append trade or modify messages to a list that is conveyed to the traders.

    def _confirm_trade(self, timestamp, order_side, order_quantity, order_id, order_price):
        '''Add trade confirmation to confirm_trade_collector list.'''
        trader = order_id.partition('_')[0]
        self.confirm_trade_collector.append({'timestamp': timestamp, 'trader': trader, 'order_id': order_id, 
                                             'quantity': order_quantity, 'side': order_side, 'price': order_price})
    
    def _confirm_modify(self, timestamp, order_side, order_quantity, order_id):
        '''Add modify confirmation to confirm_modify_collector list.'''
        trader = order_id.partition('_')[0]
        self.confirm_modify_collector.append({'timestamp': timestamp, 'trader': trader, 'order_id': order_id, 
                                              'quantity': order_quantity, 'side': order_side})

process_order determines whether an incoming order results in a match with a resting order or not.

    def process_order(self, order):
        '''Check for a trade (match); if so call _match_trade, otherwise modify book(s).'''
        self.confirm_modify_collector.clear()
        self.traded = False
        self._add_order_to_history(order)
        if order['type'] == 'add':
            if order['side'] == 'buy':
                if order['price'] >= self._ask_book_prices[0]:
                    self._match_trade(order)
                else:
                    self.add_order_to_book(order)
            else: #order['side'] == 'sell'
                if order['price'] <= self._bid_book_prices[-1]:
                    self._match_trade(order)
                else:
                    self.add_order_to_book(order)
        else:
            book_prices = self._bid_book_prices if order['side'] == 'buy' else self._ask_book_prices
            if order['price'] in book_prices:
                book = self._bid_book if order['side'] == 'buy' else self._ask_book
                if order['order_id'] in book[order['price']]['orders']:
                    self._confirm_modify(order['timestamp'], order['side'], order['quantity'], order['order_id'])
                    if order['type'] == 'cancel':
                        self._remove_order(order['side'], order['price'], order['order_id'])
                    else: #order['type'] == 'modify'
                        self._modify_order(order['side'], order['quantity'], order['order_id'], order['price'])

It does some bookkeeping then checks the type of order. If it is an add order, it results in a trade if it is priced to match an existing order. This is assessed by checking the order price against the best bid (_bid_book_prices[-1]) or best ask (_ask_book_prices[0]). If it is not an add order, then it must be a cancel or modify and the order book is updated and messages are created for the trader.

_match_trade enforces price-time priority for matching incoming orders against resting orders.

    def _match_trade(self, order):
        '''Match orders to generate trades, update books.'''
        self.traded = True
        self.confirm_trade_collector.clear()
        if order['side'] == 'buy':
            book_prices = self._ask_book_prices
            book = self._ask_book
            remainder = order['quantity']
            while remainder > 0:
                if book_prices:
                    price = book_prices[0]
                    if order['price'] >= price:
                        book_order_id = book[price]['order_ids'][0]
                        book_order = book[price]['orders'][book_order_id]
                        if remainder >= book_order['quantity']:
                            self._confirm_trade(order['timestamp'], book_order['side'], book_order['quantity'], book_order['order_id'], book_order['price'])
                            self._add_trade_to_book(book_order['order_id'], book_order['timestamp'], order['order_id'], order['timestamp'], book_order['price'], 
                                                    book_order['quantity'], order['side'])
                            self._remove_order(book_order['side'], book_order['price'], book_order['order_id'])
                            remainder -= book_order['quantity']
                        else:
                            self._confirm_trade(order['timestamp'], book_order['side'], remainder, book_order['order_id'], book_order['price'])
                            self._add_trade_to_book(book_order['order_id'], book_order['timestamp'], order['order_id'], order['timestamp'], book_order['price'],
                                                    remainder, order['side'])
                            self._modify_order(book_order['side'], remainder, book_order['order_id'], book_order['price'])
                            break
                    else:
                        order['quantity'] = remainder
                        self.add_order_to_book(order)
                        break
                else:
                    print('Ask Market Collapse with order {0}'.format(order))
                    break
        else: #order['side'] =='sell'
            book_prices = self._bid_book_prices
            book = self._bid_book
            remainder = order['quantity']
            while remainder > 0:
                if book_prices:
                    price = book_prices[-1]
                    if order['price'] <= price:
                        book_order_id = book[price]['order_ids'][0]
                        book_order = book[price]['orders'][book_order_id] 
                        if remainder >= book_order['quantity']:
                            self._confirm_trade(order['timestamp'], book_order['side'], book_order['quantity'], book_order['order_id'], book_order['price'])
                            self._add_trade_to_book(book_order['order_id'], book_order['timestamp'], order['order_id'], order['timestamp'], book_order['price'],
                                                    book_order['quantity'], order['side'])
                            self._remove_order(book_order['side'], book_order['price'], book_order['order_id'])
                            remainder -= book_order['quantity']
                        else:
                            self._confirm_trade(order['timestamp'], book_order['side'], remainder, book_order['order_id'], book_order['price'])
                            self._add_trade_to_book(book_order['order_id'], book_order['timestamp'], order['order_id'], order['timestamp'], book_order['price'],
                                                    remainder, order['side'])
                            self._modify_order(book_order['side'], remainder, book_order['order_id'], book_order['price'])
                            break
                    else:
                        order['quantity'] = remainder
                        self.add_order_to_book(order)
                        break
                else:
                    print('Bid Market Collapse with order {0}'.format(order))
                    break

It does a little bookkeeping then checks whether the incoming order is a buy or sell. The “while” loops ensure price priority by checking for the best price pointer (price = book_prices[0], for example), then ensures time priority by walking through the resting orders in the order of arrival for each price (book_order_id = book[price][‘order_ids’][0]; book_order = book[price][‘orders’][book_order_id]). The remaining portions of the while loop check if the remaining order size is greater than the size available for the current best price and behaves accordingly.

Three helper functions facilitate saving data to an hdf5 for use after the simulation has ended.

    def order_history_to_h5(self, filename):
        '''Append order history to an h5 file, clear the order_history'''
        temp_df = pd.DataFrame(self.order_history)
        temp_df.to_hdf(filename, 'orders', append=True, format='table', complevel=5, complib='blosc', 
                       min_itemsize={'order_id': 12}) 
        self.order_history.clear()
        
    def trade_book_to_h5(self, filename):
        '''Append trade_book to an h5 file, clear the trade_book'''
        temp_df = pd.DataFrame(self.trade_book)
        temp_df.to_hdf(filename, 'trades', append=True, format='table', complevel=5, complib='blosc', 
                       min_itemsize={'resting_order_id': 12, 'incoming_order_id': 12}) 
        self.trade_book.clear()
        
    def sip_to_h5(self, filename):
        '''Append _sip_collector to an h5 file, clear the _sip_collector'''
        temp_df = pd.DataFrame(self._sip_collector)
        temp_df.to_hdf(filename, 'tob', append=True, format='table', complevel=5, complib='blosc')
        self._sip_collector.clear()

The final function is a public method for conveying the top of book information to the traders.

    def report_top_of_book(self, now_time):
        '''Update the top-of-book prices and sizes'''
        best_bid_price = self._bid_book_prices[-1]
        best_bid_size = self._bid_book[best_bid_price]['size']   
        best_ask_price = self._ask_book_prices[0]
        best_ask_size = self._ask_book[best_ask_price]['size']
        tob = {'timestamp': now_time, 'best_bid': best_bid_price, 'best_ask': best_ask_price, 'bid_size': best_bid_size, 'ask_size': best_ask_size}
        self._sip_collector.append(tob)
        return tob

That is it! Easy? Maybe not the first time. Creating order book code is an iterative process, even when a lot of planning and forethought is applied and even with a lot of prior knowledge about how order books are actually created by professional trading firms. The logic here can be extended to include more order information like hidden or iceberg orders. The order processing, trade matching and bookkeeping would have to be updated as well. Adding more functionality like pegged or sliding features would require considerable modification to the order processing and trade matching algorithms. But it can be done! And finally, the basic organization of this order book module can be applied to other matching mechanisms like auctions or dealer markets. Simulations will always require a module or set of functions to determine which agents traded and the prices the agents received.

Next posts will cover unit testing and designing various trader agents with Python.

[2/12/2018: Updated to properly format “less than” in code blocks.]

Published by

Chuck Collver

Quant, Programmer, Data Scientist, Developer

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s