Red Black Trees for Limit Order Book

Question

Why do people suggest using red black trees/balanced binary trees for the levels in a limit order book?

Why are they algorithmically ideal?

Answer 1

Why do people suggest using red black trees/balanced binary trees for the levels in a limit order book?

Because people are unoriginal and keep referencing the same blog post.

Why are they algorithmically ideal?

They're not necessarily ideal. In fact, they're rarely used in production trading systems with low latency requirements. However, your source probably had the following considerations:

1. They were given more of an engineering objective rather than a trading objective. Without business constraints or queries that you're supposed to optimize, a reasonable prior is to optimize for the worst case runtime of inserts and deletes, since inserts and deletes often dominate executions.
2. They were designing this order book structure based on sample data from an asset class with sparse prices, like equities.

Because of (1) and (2), they needed to take into account the following market properties:

3. New prices are often inserted towards the outside of the book, since (i) the inside levels tend to be dense and (ii) insertions towards the inside are likely to be matched and truncated by the opposite book.
4. Forming a new level gives significant queue priority and orders towards the outside have more time value, so price levels are less likely to be removed by order cancels towards the outside, and more likely to be removed by cancels or executions towards the inside of the book.

(3) and (4) would promote an unbalanced and tall BST, which has much worse amortized runtime than its idealized form. There are various ways to mitigate this. Self-balancing is just one naive solution, as red-black trees are very widely implemented in container libraries and a simple way to guarantee $\mathbb{O}\left(\log n\right)$ inserts and deletes of price levels.

---

When evaluating the optimal data structure, I would keep in mind the following three main topics.

1. Start with the business use case

Such as:

• What queries need to be optimized for your application?
• Sparsity of the book.
• Statistical distribution of book events.

For example:

• In illiquid options, there may be very few resting orders on the book, so it may be cheaper to just store everything in arrays and linearly walk through them.
• In liquid futures, most events only affect a few hundred price levels, and price bands might give you a bound on levels that you actually care about, so it is possible to preallocate the levels in an array and represent index prices as an offset from some initial state in number of ticks.
• Some trading strategies need to act very quickly to the change to the top of the book, and can afford to defer level inserts or deletes outside the BBO till later, so it is unimportant to optimize for level inserts or deletes.

2. Understand the messaging protocol and data feed

For example:

1. Some data feeds are bursty, so you might design your application to flush all data events before performing the critical path of your business action (e.g. order placement, model update). The optimal order book structure may differ if events are batched.
2. Successive events in the data feed may have some price ordering.

3. Hardware codesign

In practice, when you're operating at memory or cache access time scales or dealing with a small number of events relative to cache size, asymptotic time complexity often goes out of the window and it's more important to look at the actual implementation and real benchmarks, and codesign your order book for the architecture that it is running on.

In such cases, a simple array or vector with linear access patterns will often outperform any complex data structure with better asymptotic runtime because a simple array makes it easier to exploit hardware optimizations that are more important:

• Locality
• Prefetching
• Instruction pipelining
• Fitting all relevant/qualifying data into fewer "pages" that have to move up the memory hierarchy, e.g. not chasing pointers across non-contiguous regions of memory.
• SIMD intrinsics.

How does this translate to order book design? For example:

• The C++ STL implementation of unordered_map will often have worse performance than map for order ID lookup of instruments with a small number of orders.
• It is possible to represent each price level with an intrusive doubly-linked list, which has $\mathbb{O}\left(1\right)$ lookup of the neighboring nodes, so you can unlink an order that was deleted in $\mathbb{O}\left(1\right)$. But you will often get better performance by creating a linked list of preallocated arrays, and removing orders by marking them with a tombstone flag.

---

In many of the situations that I described above, a linked list of arrays or an array of arrays will outperform a general purpose design with red-black trees of intrusive doubly-linked lists.

Answer 2

There is a difference about understanding LOB dynamics and using an algorithmic solution to capture these dynamics.

How LOB evolves. We understood now long ago (see Jeremy Large's papers) that a Markov chain on "pictures" of the LOB would be an interesting model. After few years of modeling LOB dynamics with Hawkes processes (see for instance Emmanuel Bacry and co-authors' paper), and thanks to the interesting push by Rama Cont and Adrien de Larrard, we came to the idea that heterogenous Poisson process to model each event (insert, cancel, market) was really good. Especially if the intensities of these processes are functions of the state of the orderbook (i.e. of the "pictures" I referred too). See the Queue Reactive Model. This incorportaes the predicting power of orderbook imbalence.

How to compress the dynamics. I do believe that intensities are a good way to keep track of the dynamics. It is only if you want to associate the best next action (between insert/cancel/stay/market) that somehow a decision tree, i.e. a binary tree. Can be useful. But I would suggest to rely on reinforcement learning (see the examples of this paper) to choose the branches of your tree.

[EDIT] If your goal is to implement a matching engine, this is another story. It is something I had to do to debug or backtest trading algorithms. I would say that in theory you just need something that is equivalent to a quicksearch logic, and yes red-black tree is a solution that for. The important point is not to redo the search each time you want to insert an order in your list of price levels, since it is already sorted. Most programming language already have a solution that for (in python, why not simply use a dictionary), but if you want to do it from scratch because you are really concerned by the implementation speed, then it could be a good idea to start to search at the mid-price (and not at the lowest or highest price), because you have more order insertions and updates around the mid.

Answer 3

Like many that have said here, the data structure depends on what your most important requirements are. I have implemented LOB for back-testing. I have had to choose different data structures for different securities. I have also had to build an aggregate ORDER BOOK for FX. I have also built Execution systems for Options strategies. Each has its own twist to the tale. In terms of performance. RBT on average is a good performer but not necessarily most optimal. I have typically ended up using linear data structures and indexed them with a RBT or a hash table on top depending on what kind of search I have had to do. Options algorithms many a times require finding an option by delta, atm strike etc. The RBT is an excellent structure for this as you can actually update the iterators to options with these properties in real time and just hold on to those iterators. This is because prices rarely jump significantly.

At the end of the day, you will have to optimize for what you are doing and figure out what works best. There is no universal solution.

As we speak, I am trying to optimize LOB analysis using HFT data. I am yet to figure out what is the best way to organize to data to generate all the statistics I need.