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

Why are they algorithmically ideal?

  • $\begingroup$ How it works in practice: you take a bunch of actual pcap files and test them against a shortlist of data structures for throughput. Some data structures will be faster for creates, some for cancellations but choosing one structure that is faster for the entire set of commands is a good start. Then add optimizations and defenses against market participants who are aware of the data structure and may attempt to exploit its shortcomings. $\endgroup$ – Sergei Rodionov Apr 2 at 13:05
  • $\begingroup$ for example see github.com/DrAshBooth/JavaLOB/blob/master/src/lob/…, my question is about the engineering concepts $\endgroup$ – Trajan Apr 2 at 18:27
  • $\begingroup$ see also, github.com/JPalounek/order-book $\endgroup$ – Trajan Apr 2 at 18:33
  • $\begingroup$ linked question: quant.stackexchange.com/questions/63211/… $\endgroup$ – Trajan Apr 5 at 14:00

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:

  1. 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.
  2. 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 options instruments, there may be very few order events, so it may be cheaper to just store everything in arrays and linearly walk through them.
  • In liquid futures contracts, 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.

  • $\begingroup$ Great answer!!! $\endgroup$ – Trajan Apr 5 at 14:07

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 read-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.

  • 1
    $\begingroup$ whilst everything you have written is interesting and I will look into further, my question was really about the engineering behind this, for example see github.com/DrAshBooth/JavaLOB/blob/master/src/lob/… $\endgroup$ – Trajan Apr 2 at 18:26
  • 1
    $\begingroup$ yes @Trajan, I answered too quickly (because I like this topic), now I updated my answer with a paragraph exactly for you $\endgroup$ – lehalle Apr 3 at 3:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.