Implementation

Given the nature of fast paced, low-touch nature of the majority of trading activity these days it is imperative that limit order books operate efficiently. To give an idea of the kind of volume to expect, the Nasdaq TotalView ITCH feed (shows every instrument traded in Nasdaq) can have data rates of 3 Mb/second or more. Given that one message is around 20 bytes each, this means handling 100,000-200,000 messages/second.

In a simulated environment we may not need to be quite this fast, but certain LOB operations will always be hammered, even in simulation, so speed is something to keep in mind. The majority of activity in real world LOBs is made up of add and cancel operations as high-frequency market makers jostle for position, with executions a distant third. The goal is to implement these operations in O(1) time while allowing the model to be probed with questions like "what are the best prices?" or "how much volume is there at price X?".

Given that we want to use the price-time-priority model use by most modern exchanges, the simplest way to imagine a LOB is as a pair of list of lists, as shown below:

In the visualisation above, the bids and asks can be seen as separate lists of limit prices that each contain a list of all of the orders at that price. At each price, the list of orders is sorted according to its time of arrival. In the figure above, the orders labeled "1" arrived first. An add operation places an order at the end of one of a list of orders to be executed at a particular limit price and a cancel operation removes an order from anywhere in the book. An execution removes an order from the inside of the book, that is the oldest buy order at the highest price and the oldest sell order at the lowest price.

In order to keep things fast, I chose to use a red-black binary tree of OrderList objects sorted by Price, each of which is itself a doubly linked list of Order objects. Each side of the book is represented with a separate tree so that the inside of the book corresponds to the end and beginning of the buy Limit tree and sell Limit tree, respectively. Each order is also an entry in a map keyed off idNum, and each OrderList is also an entry in a map keyed off Price.

This structure allows the key operations to operate with the following performance:

• Add - O(log M) for the first order at a price, O(1) for all others
• Cancel - O(1)
• Execute - O(1)
• GetVolumeAtLimit - O(1)
• GetBestBid/Offer - O(1)

where M is the number of OrderLists (prices).