What is an efficient data structure to model order book of prices and quantities to ensure:
- constant look up
- iteration in order of prices
- retrieving best bid and ask in constant time
- fast quantity updates
The specifics depend on if you're implementing for equities (order-based) or futures (level-based). I recommend https://web.archive.org/web/20110219163448/http://howtohft.wordpress.com/2011/02/15/how-to-build-a-fast-limit-order-book/ for a general overview of a good architecture for the former.
Building off of that, though, I have found that using array-based over pointer-based data structures provides faster performance. This is because for modern pipelining, caching CPUs, branching and dereferences (especially from uncached memory) are the biggest performance killers because they introduce data dependencies resulting in pipeline / memory stalls.
If you can, you should also optimize for the particular exchange. For instance, it turns out that, last I checked, Nasdaq generates order IDs incrementally starting from a small number, so you can store all the orders in a giant array instead of a hashtable. This is really cache- and TLB-friendly compared to a hashtable because most updates tend to happen to recently-dereferenced orders.
Speaking from experience with equities (order-based), my preferred architecture is:
std::vectorif you can swing it such as in the case of Nasdaq).
O(1)decrement for an
Order Reduceoperation. If you want to keep track of time-priority as well, you can keep pointers to the
previousorders in the queue.
vectorfor the price levels for each book will result in the fastest average price lookup. Searching linearly from the end of the
vectoris on average faster than a binary search, too, because most of the time the desired price is only a few levels at most from the inside, and a linear search is easier on the branch predictor, optimizer and cache. Of course, there can be pathological orders far away from the inside of the book, and an attacker could conceivably send a lot of updates at the end of the book in order to slow your implementation down. In practice, though, most of the time this results in a cache-friendly, nearly
delete(with a worst-case
O(N)memcpy). Specifically for a Best Bid / Offer (BBO) update, you can get an implementation to calculate the update in just a few instructions (essentially appending or deleting an element from the end of the
vector), or about three dereferences.
O(1)best-case behavior for insertion, lookup, delete and update with very low constants (I've clocked it to be on average the cost of a single fetch from main memory - roughly 60ns). Unfortunately you can get
O(N)worst case behavior, but with low probability and still with very good constants due to the cache-, TLB- and compiler-friendliness. It is also very fast, nearly optimally so, in the case of BBO updates which is what you are usually interested in anyways.
I have a reference implementation here for Nasdaq's ITCH protocol which illustrates these techniques and more. It clocks in at a mean of just over 61ns / tick (about 16 million ticks / second) by only keeping track of the quantity at each price-level and not the order queue, and uses almost no allocation besides
I recently stumbled upon this question after needing to do this to do some real-time microstructure analysis and have taken a look at the various possible implementations. Here are some of the pros/cons of each implementation (I'll use C/C++ terminology):
Array: You have an array of structs ordered from top of book (index 0) to worst (index N). You have to pre-allocate the array to be big enough.
Insertion is O(LOG N): Perform binary search to find the insertion point, then performing a memcpy to shift the tail of the array. Finally, you overwrite the item at the insertion point.
Lookup is O(1): Your indices directly correspond to levels of market depth. Just hop to where you want.
Deletions are O(LOG N): You seek to the order you want to delete, then perform a memcpy shifting everything back by 1 index.
Updates are worst case a deletion + insertion. Best case, you check if the updated order changes ordering at all.
Singly-linked List: Same concept as an array (head in linked list is top of book, tail is bottom of book).
Insertion is O(N): You have to seek through the list, update your new order's "next pointer" to the previous order's "next pointer", update the previous order's "next pointer" to point to your new quote, and update the head/tail/length of the list if applicable.
Lookup is O(N): Top of book is trivial O(1) since it's the head of the list. Otherwise you'll need to seek through the list.
Deletion is O(N): You have to seek through the list to find the target spot. Then swap two pointers.
Updates are a deletion + insertion in the worst case. Best case is O(1) assuming you know the right index (I'll get into this deeper in this response)
A few optimizations give it acceptable performance:
Pros: - No repeated copying once you seek to the right place - Updates/inserts/lookups very fast if most operations are near head of list
Ultimately, I found that the array version has the best average performance if you're ok with just price/qty priority. If you need the precision of price/qty/time priority the arrays just get far too large.
If you're OK with price/qty priority: We can use the property that quantities tend to be very similar for securities to limit the number of copy operations:
Create an array 4x the size of the expected possible price range for the day (you'll obviously need to re-allocate your array if something wild happens). Place the price level corresponding to the expected open in the middle of the array. Whenever you get a new order, the desired index is close to the number of cents difference from this price and the order's price. You can then look forward/backwards to see if the price/qty level exists. If it doesn't, then you'll need to shift the array via a copy. But if it does, you're all set. This "centered array" approach means that after a few minutes of quotes, you'll have the vast majority of your price/qty levels defined. This method only works if you're ok with just price/qty priority. If you require price/qty/time priority then you should probably go with the linked list.
I do not know in which context you want to implement a matching engine (ME). But according to me the two nice challenges in this context are:
The last point is about simulating one day in few seconds.
To answer more directly your question, the reference is Josh Levine's code of Island in foxpro. Levin's has been one of the pioneer in the raise of electronic trading. It is not only an executable spec, but a piece of history.
If you assume that most updates will happen near the top of the book (a fair assumption) a linked-list ordered by price levels will be very efficient.
You can check CoralMD for an example of a very fast, garbage-free market data book implementation that provides not just the global view of the market (all exchanges) but also a per-exchange book view. It also provides the infra-structure to write exchange feeds and to distribute market data internally.
Disclaimer: I am one of the developers of CoralMD
Why not just implement it with two price-amount maps, as shown here?