6 · The book Draft

Chapter 6 — The book

5 min read

On this page

Every chapter so far has moved bytes: from DRAM into a core, into the kernel, between threads, from a venue’s machine to ours. None asked what the bytes say. This one does. The networking chapter’s 48-byte depth update says one small thing: on instrument 42, as the venue’s change number 1,873,465,902, the buyers at $68,123.45 now want 0.512 BTC in all. What the program asked for sounds as simple: a true copy of the venue’s book, the list of every price at which someone is waiting to buy or to sell and how much waits there, so that the strategy, the part of the program that decides what to buy and sell, can ask “what is the best price to buy at, and to sell at, right now?” and get the venue’s answer. Between that wish and a struct in memory lies a chain the source code does not show: a snapshot of the whole book taken at one instant and stamped with a number; a stream of numbered changes that began before the snapshot and goes on after it; a rule, written in the venue’s documentation, for which change is the first to apply on top of which snapshot; a structure that must find a price among thousands in nanoseconds; and a gap, one missing number, that makes the copy wrong without raising any error. The strategy never sees the venue’s book, only its own copy, always a little behind and wrong from the moment it misses a change.

The prices against the budget of 1 µs per hot-path iteration, 4,000 cycles at 4 GHz, are set mostly by how the copy is laid out in memory. Applying one change to an array with a slot for every price in a range costs 2–5 ns, 8–20 cycles: an index computation, a load, a compare and a store to a line that is usually in L1. Applying it to Rust’s BTreeMap, the standard library’s ordered map and the structure most people reach for first, costs 100–300 ns, and 150–500 ns when a price appears or disappears, because the update follows pointers through three tree nodes and allocates or frees one: a tenth to a half of a budget per change. Changes come in bursts. With 30 updates in 4 µs of wire time, the 30th waits 60–150 ns on the array and 3–15 µs on the tree, three to fifteen budgets.

None of that is where the money goes, and that is the shape of the problem again. The common case is cheap: an update arrives, is applied in nanoseconds, and the copy matches the venue. The tail is correctness. A missed change cannot be repaired by the next one; the copy must be rebuilt from a fresh snapshot, and with a venue 35 ms away that is an HTTPS round trip of 70 ms and up to 200 ms in all, 70,000–200,000 budgets during which the copy cannot be trusted. A stale book, one still showing a market that has moved, costs a bad fill, a trade we would not have chosen: an order of ours left waiting at a price the market has moved through is traded against by someone who knew, and the loss is in dollars. None of this is particular to trading. A database replica joining a running primary copies a snapshot taken at a known position in the primary’s change log and applies the log from there; skip one record and it is wrong in the same silent way. A cache kept fresh by a feed of invalidations serves a stale entry as true when one invalidation is lost, and the conflict-free replicated data types of collaborative editors are a long answer to changes that arrive late or twice. A trading program meets the same problem in smaller units.

The chapter starts with what a market is to a program: orders, the prices at which they wait, the venue’s program that matches them, and what “the book” is in our own memory, with prices held as whole numbers of the venue’s smallest price step rather than as floats. Then how a venue tells you about its book: a snapshot, numbered changes and the rule that joins them, with Binance’s published procedure as the concrete case. Then the ladder of what one update costs in each way of holding the book, the anatomy of one update, and the representations, from a tree to a dense array. Then how a copy goes wrong and is put right, and what a strategy does with a book it can trust. What follows for a hot path is collected near the end, after the understanding that justifies it. The code for every experiment is in the companion repository under ch06-book/; the repository holds the code and this chapter holds the reasons.

Readings in this chapter