Order-book decisions for a hot path

6.8 What follows for a hot path

Everything above justifies the list below, and nothing in it is a trick: each rule is what a mechanism leaves you with once its numbers are in front of you, and a reader who disagrees with one should be able to point at the number it rests on. None of it is particular to trading either; a database replica that mirrors a primary from its change log needs the same sequence check, the same stale state and the same replay test.

Hold every price and quantity as an integer count of ticks and lots, per instrument, and let the tick size and the lot size be the only decimals in the program, applied once when a number enters and once when one leaves. A price of $68,123.45 is 6,812,345 ticks, a number that compares exactly and indexes an array directly; a binary float cannot hold 68,123.45 at all, so a price that has been through arithmetic may no longer equal the one the venue sent, and a level can be written under one key and deleted under another. Ignore the rule and the array is unavailable, because an index must be an integer, and the book falls back to a tree at 100–500 ns an update where the array took 2–5 ns.

Keep the book as a dense array with a window and a bitmap, sized per instrument from its tick size and its daily range, and allocate all of it at startup: both sides and both bitmaps. The array turns a price into an address by one subtraction, the bitmap turns the walk across empty levels into a few word operations, and preallocation keeps the 20–50 ns allocation, and about as much again to free, out of every apply. The window is as many levels as the instrument’s day needs at its own tick size: 65,536 levels at a $0.01 tick is $655.36 wide and costs 512 KB a side, while 4,096 levels is ±$20.48, which a quiet minute can leave. Ignore the structure and an update costs 160–700 ns on a TreeBook, its best-price walks included, or 120–360 ns on a VecBook that must move up to 8 KB to add or remove a level, and in a burst of 30 updates the last one waits 3–15 µs behind the tree’s map operations alone, instead of 60–150 ns.

Check the sequence number before every apply, in the feed handler that calls it, and treat a gap as a change of state, not a line in a log. The structures only store levels and will apply whatever they are given, so a missed delete leaves a level that no later update removes, and nothing inside the book will ever say so. The check costs one compare an update; skipping it costs a book that is wrong from the gap onward, priced in bad fills, and it stays wrong until a resync, which takes 70–200 ms once it is started and never happens if nothing starts it.

Let the top-changed flag be the only thing the strategy hears, and publish it once per batch. Most updates are deep and change nothing the strategy prices from, so waking it for each one buys a recompute, and perhaps a cancel-replace, for nothing; and every hand-off to another core is a cache-line transfer at 50–100 ns, against 2–5 ns for the apply itself. A burst of 30 updates published one by one pays 1.5–3 µs in transfers alone; published once per batch it pays one transfer.

Give the book one owner: one thread applies every update, and everyone else is sent a Top by message. The array, the cursor and the bitmap have to agree with one another, and a second thread reading while the first is half-way through an update would see a cursor that points at a level the bitmap says is empty. Sharing the book instead costs a cross-core transfer of 50–100 ns on every access to a line the other core last touched, and a lock or atomics around code that is meant to take 2–5 ns.

Keep Live, Stale and Syncing as explicit state that the strategy reads before it trusts a number, and measure the time spent in each. A stale book looks exactly like a live one, with the same fields and no error, so only a state the strategy is made to look at stops it quoting from the book; and a time-in-state counter turns “the feed seems flaky” into the fraction of the day the book was Live. Ignore the rule and the cost is priced in money: a quote resting at a price the market has moved through is filled by the trader who knew, and the exposure lasts the whole resync, 70–200 ms or more.

Follow the venue’s join rule verbatim from its documentation, with the venue’s field names in the code (U, u and lastUpdateId on Binance’s spot stream, with pu as well on its futures stream), and write a test that replays the documented sequence of steps against a recorded snapshot and a recorded buffer, boundary cases included. The rule says which buffered delta is the first to apply to a snapshot, and the difference between less than and less than or equal is exactly the detail a paraphrase loses. A wrong boundary makes no noise, since the numbers after it are contiguous and the sequence check passes; the book is wrong by one dropped delta or one stale quantity written over a newer one until a diff finds it or a fill does.

Build a replay harness that feeds recorded updates to all three structures and diffs their tops after every update, and have the live program diff its book against a fresh snapshot from time to time. The first catches the bug in the fast structure, because the TreeBook and the VecBook share none of its cursor or bitmap code; the second catches what no sequence number can, the venue’s own bug and a mistake in the join. Without them a wrong book is found by a fill, and a fill costs money where a replay costs only time.

Keep a BTreeMap book as the reference implementation that the fast one is tested against, in every test. It has no window, no cursor and no bitmap, so it cannot be wrong in the same ways, and its 160–700 ns an update does not matter on a path that exists to be checked rather than to be quick. Without a reference the array is tested against itself, and a bug in the walk inward becomes a bug the test shares.

Three things are deliberately not done. There is no L3 book that tracks each order and its place in the queue at its level, because the strategy in this chapter quotes from levels; there is no aggregation across venues, which needs clocks that agree and a rule for what a combined top means; and there is no smart re-base, so a price that leaves the window is met with the plain copy or a rebuild and nothing cleverer. The capstone does not need any of them, and each is a chapter of its own.