Part 4 of 8 · 3 min read
Data
Orders, executions and the book.
Three kinds of data.
- Product: the attributes of a traded symbol (symbol, lot size, tick size, currency). It rarely changes and is cacheable.
- Order: an instruction to buy or sell.
- Execution (fill): a matched result. Each match creates two. Not every order has one.
On the critical path, orders and executions are not written to a database. They are kept in memory and in files owned by the sequencer for quick recovery, and archived after the market closes. The reporter writes them to a database for reports. The market data processor rebuilds books from the stream of fills.
APIs for brokers (REST for ordinary clients, FIX or a binary protocol for the fastest ones): place an order, cancel an order, query executions, ask for the order book at a depth, and ask for candlesticks. REST is too slow for institutions that need microseconds.
Order book design goals.
- Constant-time lookups of the volume at a price level.
- Constant-time add, cancel and match.
- Fast queries of the best bid and ask, and of nearby levels.
Structure.
- Each side (buy and sell) has price levels in sorted order.
- Each price level has a doubly linked list of orders in arrival order.
- A map from order id to order lets the engine find any order directly.
Why these choices make operations fast.
- Add an order: append to the tail of the list at its price. Constant time.
- Match: take orders from the head of the list. Constant time per order.
- Cancel: find the order through the map, then unlink it, using its previous and next pointers. A singly linked list would need a walk to find the previous node, which takes time proportional to the list length.
Matching rule. The simplest is FIFO: at one price, the order that arrived first fills first. Other schemes exist, such as giving a share to a lead market maker first, or filling in proportion to size.
A worked example (made up). The best ask has 3 orders of 100 shares (queue A, B, C) at 100.10, and the next level 100.11 has an order of 500. A market buy for 450 takes A, B, C (300 shares) and then 150 from the 100.11 order, which has 350 left. The best ask is now 100.11.
Candlesticks. Keep a list of sticks per symbol and interval. Memory is a concern with many symbols and intervals. Use pre-allocated ring buffers, keep a limit in memory, and persist older ones to disk. Market data is kept in memory in a column store for analysis and moved to a history database after the close.
Ring buffer
A ring buffer is a fixed-size queue whose end is joined to its start, so that new data overwrites the oldest and no memory is allocated while it runs.
Example: a buffer of 1,000 candlesticks holds the latest 1,000. The 1,001st replaces the first.
Check yourself: 1. Why a doubly linked list at each price? 2. Which data is not stored in a database on the critical path? 3. How does FIFO decide who fills first?