C++ low-latency Order Book Joshua McKenzie joshua.mckenzie@gmail.com
This was written as an exercise to test out a variety of techniques in an ultra-low-latency environment. I limited myself to 5 days from clean slate to full implementation, so some concessions were made on the implementation - exception handling being the primary one.
Write human readable view of in-memory book every 10 messages Write machine-readable series of mid-quotes On each trade message, write total qty traded at most recent trade price Gracefully handle various garbage messages
OrderGenerator.pl should generate a stream of orders that you can use as input. An easy reference for looking at performance metrics: ./run_test.sh Or alternatively: ./OrderGenerator.pl > Orders.txt make profile ./OrderBookProcessor Orders.txt > test.out 2>&1 less -n test.out
2.7GHz, quad-core i7 920, HT enabled Ubuntu 13.10 3.8.0-19-generic #30-Ubuntu SMP gcc version 4.7.3 (Ubuntu/Linaro 4.7.3-1ubuntu1) Ubuntu clang version 3.2-1~exp9ubuntu1 boost 1.54.0 perl v5.14.2
Meta data structure: std::map of doubly-linked lists of orders, one per side std::unordered_map of all orders to get memory address of underlying order object
Due to needint to keep sorted order on the book, I went with a std::map, rbtree implementation for the following performance profiles: Insert: logN price + hash order id Modify: logN to 2logN price + hash order id, depending on if price changed Delete: logN + hash Trade: 2logN price + variable hashing order id, based on # of orders blown through The data scope of the logN operation is limited to the price levels rather than being wide-open to all order_id's which should limit the scope of the logN cost we have to pay on lookup.
Originally I considered a vector with integer-based indexing on price with pre-reserved memory, however calculating midpoint on each update and checking for a crossed book would represent a worst-case O(n) on every single order, which was clearly unacceptable. Changing from the vector to the map added about 40% latency or so to orderAdd and the other types which I wasn't too thrilled about, but it's necessary. Better logN on insert and staying in sorted order than paying NlogN on every insert just to get O(1) on trade message, though the thought crossed my mind as your knowledge about market conditions is often-times based on getting a fill before the market- data update hits.
The map is of ulonglong price values. On inbound messages, I parse and = 100 the value to avoid double and/or float comparisons in the order book and get single integer comparison on the map. While this only supports prices up to 92.2 quadrillion, I chose to go that route to bypass whole part / fract part Fixed class creation and comparison, as well as to support the initial design of integer based vector offset lookup mentioned above. This class design would need to be augmented to support a Fixed class with a functor comparison object to allow the std::map to sort and compare via that key to have full double price support at the top of the price range. It would be as easy as plugging the Fixed class into the OrderBookMap and templatizing the price value throughout the OrderBook in order to change over to that class. In a production environment, I'd ask my client if it was acceptable for them to max at 92.2 quadrillion in price, and if so, go on with things. The map has doubly-linked lists of pointers to orders hanging off them. Rather than paying a O(n) worst-case to traverse that and finding an order, I created a hash for the orders that should average to O(1). I didn't do analysis on the default hash bucketing that took place, but integer hashing on order_id with a monotonically increasing list of #'s should be pretty evenly distributed. I didn't use a standard container here as I wanted to be able to hash directly to a memory address and ask the container to delete by that address but still retain time priority. I'd be interested to see how shared_ptr's behaved from boost instead of raw pointers - as it is now the pointer maintenance inside the OrderBook represents both a high risk and a point of high mental tax on future work on the code-base. I went with boost::spirit::qi parsing as it's demonstrably faster than atoi and atof in all the benchmarks I was pulling up (up to 5x faster). strtok still reigns supreme, though it means just about everything in there is non-const thanks to underlying buffer modification. Logging is done in a separate thread, since fprintf to stderr was taking a pretty painful amount of time on just printing the book. Printing a midquote every order means we need fast IO every order... downside? Crashing means lost logging state. So don't crash. ;) I didn't use exception handling in this exercise due to time constraints on implementation. The Logger burns a core. Given the various calls median < 1 usec, any amount of sleeping at usec resolution could get our logging very very backed up. As to why I burned a core instead of using a conditional variable - those things can take a long time to get scheduled by the kernel - up to 10 usec or so from what I can recall off the top of my head. Certainly an order of magnitude longer than the time horizons I'm looking at working with. The book printing process is pretty mangled at this point, sprintf'ing into temporary buffers and then finally logging it. fprintf(stderr ...) on every message / sub-message for book-level printing was taking 1+ ms every 10 orders. I managed to get it down to ~ 150 usec per print, depending on how deep the book is. That could be further optimized (char on heap, logger deletes, variadic template arguments into logger instead w/different behavior per data type, etc) but for now, I left it as is as I ran out of time. It DOES make the printBook function very ugly however. ** 2 points of interest: 1) The OrderGenerator.pl should be parameterized. Right now it's hard-coded and can produce some very odd books 2) The program doesn't run with CLANG as there's apparently a known bug with 11x threads and clang that causes an exception on thread instantiation with binding a function. Compile w/clang for clean errors, switch to gcc for release. 2.A) UPDATE: Apparently they've fixed it since I wrote this. Will be interesting to do some benchmarking w/CLANG once I'm not on a VM and can do some bare-metal testing 3) RDTSC on an Oracle VM will give you incorrect results as they virtualize calls to the TSC. 3+ usec on most operations in this book instead of the 300-600 nanosecond on bare metal.
MidQuote print went from 3100 nanoseconds down to 679 median by implementing threaded logger_. Note: io on critical path is bad (except network / necessity). Book print is still very very heavy on perf... sitting at 150-200 usec or so, once per 10 orders when the book is at its heaviest. Not too happy about that, but optimized down from 1.3ms on printf based solution...
The rollowing metrics are in nanoseconds addOrder: samples: 137872 median: 484 95th: 658 99th: 1005 99.99th: 7106 modifyOrder: samples: 33944 median: 539 95th: 773 99th: 1014 99.99th: 6339 removeOrder: samples: 31645 median: 547 95th: 705 99th: 886 99.99th: 7279 trade: samples: 105995 median: 1252 95th: 1650 99th: 2238 99.99th: 10186
make release - build the release without performance metric gathering or debug symbols make profile - build the release with rdtsc performance metric gathering but no debug symbols make debug - build with asserts available (though not widely used), debug printing that was compiled out, book updates on every valid message