---
title: "The Order Book Builder"
book: "Low-Latency Software"
subject: quant
language: en
chapter: 19
exercises: 8
source: https://one-course.com/books/quant/13/en/chapter/19-the-order-book-builder
---

# Chapter 19 — The Order Book Builder

On a small-tick instrument, a book kept in balanced trees takes about $70\,\mathrm{n}\mathrm{s}$ per update on this book’s laptop; an array of price levels around the touch takes about $30\,\mathrm{n}\mathrm{s}$. The array wins, until the day the stock moves thirty percent: an array of 256 ticks must then be moved and refilled almost twenty thousand times, and the day’s book costs $0.7\,\mathrm{s}$ of processor time instead of four milliseconds. The [book builder](#def-ll-the-order-book-builder-builder) turns the [feed handler](https://one-course.com/books/quant/13/en/chapter/18-the-feed-handler#def-ll-the-feed-handler-handler)’s events into the answer every strategy asks first, what is the best price and how much is there, and the answer must be right, fast and still fast on the day that matters. This chapter states what the book must answer, compares the structures that answer it by feed type and tick regime, builds an order-by-order book on an open-addressing order map and a recentring price ladder, and tests it against two books written earlier in the series.

## 19.1 What the book must answer, and how fast

**Definition 19.1 (Book builder).**

A *book builder* maintains the limit order book (One Quant Book 10, chapter 1) of an instrument from the [feed handler](https://one-course.com/books/quant/13/en/chapter/18-the-feed-handler#def-ll-the-feed-handler-handler)’s events: from a market-by-order feed (Book 1, chapter 19) it keeps every resting order and aggregates them into price levels; from a market-by-price feed it keeps the levels directly. It answers level-1 and level-2 queries (Book 1, chapter 28) after every event, and knows when its book cannot be trusted.

A strategy asks three kinds of question. Level 1, the best bid and ask and their sizes, after every event: the microprice of One Quant Book 7, chapter 8, needs nothing more. Level 2, the first few levels on each side, for depth imbalance and queue estimates. And, for its own orders, level 3: where is my order in its queue. The builder serves all three from one structure, at a rate of one update per event of the feed, and the update is on the critical path of chapter 1’s budget: a book that takes $100\,\mathrm{n}\mathrm{s}$ longer per event delays every decision by that much, and at the open, when events come in bursts (chapter 18), it delays them by the queue of events behind it.

Each event names an order by its reference, so every update starts with a lookup: which order, at what price and side. Then it changes one price level: adds to it, reduces it, removes it when it empties. An add at a new price creates a level; a replace (Nasdaq’s specification: the original order’s “remaining shares … must be removed” and a new reference “will be used henceforth”) removes an order and adds another. The two costs of a book are therefore the order lookup and the level update, and the structures below differ in both.

## 19.2 Structures by feed type and tick regime

**Definition 19.2 (Dense price ladder).**

A *dense price ladder* keeps the price levels of a book in an array indexed by the distance in ticks from a base price, one slot per tick whether or not a level exists there, covering a window around the touch; levels outside the window live in a sparse structure, and the window is moved (recentred) when the touch approaches its edge.

![The build’s book. Levels live in a dense array indexed by ticks from a base price (blue: bids, red: asks, grey: empty); the best bid and ask are indices kept up to date. When a best price leaves the middle half of the array, the base is moved to centre the touch and the orders are filed again. Orders are found through an open-addressing map from their reference to a slot in a fixed pool.](https://one-course.com/images/onecourse/chapters/quant-13/ll-the-order-book-builder/fig-beca98de7ef3.svg)

***Figure 19.1.** The build’s book. Levels live in a dense array indexed by ticks from a base price (blue: bids, red: asks, grey: empty); the best bid and ask are indices kept up to date. When a best price leaves the middle half of the array, the base is moved to centre the touch and the orders are filed again. Orders are found through an open-addressing map from their reference to a slot in a fixed pool.*

Three structures compete for the levels. A balanced tree per side, the textbook answer (`std::map`, whose search, removal and insertion are logarithmic and which is “usually implemented as red-black trees”), allocates a node for each new level and walks a few of them for each update. A vector of levels sorted best first finds a level by binary search and keeps the touch at its front, but inserting a level in the middle shifts all the levels behind it. A dense ladder ([Figure 19.1](#fig-ll-the-order-book-builder-ladder)) finds a level by one subtraction and one division and never allocates; its costs are elsewhere: the memory of the whole window, the scan to the next non-empty level when the best one empties, and the recentring when the touch drifts.

The feed type and the tick regime decide. On a large-tick instrument, whose spread is one tick most of the time and whose levels are all occupied near the touch, every structure is fast, because the book is small and the touch rarely moves: on the simulator’s minute from chapter 18 the three builders take about $28\,\mathrm{n}\mathrm{s}$ (ladder), $36\,\mathrm{n}\mathrm{s}$ (sorted vector) and $37\,\mathrm{n}\mathrm{s}$ (tree) at the median. On a small-tick instrument, whose orders spread over hundreds of ticks with gaps between them, the tree and the vector pay for the larger book, 65 to $72\,\mathrm{n}\mathrm{s}$, while the ladder stays at about $31\,\mathrm{n}\mathrm{s}$ ([Figure 19.2](#fig-ll-the-order-book-builder-update)). The ladder’s tail, about $150\,\mathrm{n}\mathrm{s}$ at the p99 on the large-tick stream, is its scan: when the best level empties, the next one may be several empty slots away.

![Time to apply one event with three book structures, on the simulator’s minute of chapter 18 (a large-tick instrument, about 190 000 events) and on 100 000 synthetic small-tick events (orders up to 300 ticks from the mid). The timer’s own cost is subtracted. Measured on a laptop (Intel Core Ultra 7 155H) under WSL2, no isolated cores. Data: bench_books.py.](https://one-course.com/images/onecourse/chapters/quant-13/ll-the-order-book-builder/fig-5e29c2c1f25e.svg)

***Figure 19.2.** Time to apply one event with three book structures, on the simulator’s minute of chapter 18 (a large-tick instrument, about 190 000 events) and on 100 000 synthetic small-tick events (orders up to 300 ticks from the mid). The timer’s own cost is subtracted. Measured on a laptop (Intel Core Ultra 7 155H) under WSL2, no isolated cores. Data: `bench_books.py`.*

## 19.3 Order lookup: hash tables and open addressing

**Definition 19.3 (Open addressing).**

*Open addressing* stores a hash table’s entries in one flat array: a key goes to the slot its hash selects or, if that slot is taken, to the next free one in a fixed probe sequence (linear probing: the following slots), and a lookup follows the same sequence until it finds the key or an empty slot.

`std::unordered_map`, the standard library’s hash table, keeps each entry in a node of its own, allocated on insertion and reached through a bucket’s pointer: one allocation per order and a pointer to follow per lookup. [Open addressing](#def-ll-the-order-book-builder-open) keeps the order references and their pool slots in two flat arrays, sized once at start-up to at least twice the largest number of live orders expected; a lookup is a multiplication, a mask and usually one [cache line](https://one-course.com/books/quant/13/en/chapter/3-memory-hierarchy-and-caches#def-ll-memory-hierarchy-and-caches-line). Deletion is the delicate part: emptying a slot would cut the probe sequences that pass through it, so the build shifts the later entries of the run back into the hole when their home slot allows it, instead of leaving a tombstone, and lookups stay as short after a day of cancels as at the open.

```cpp
    void erase(std::uint64_t ref) {
        std::size_t i = slot(ref);
        while (keys_[i] != ref) {
            if (keys_[i] == 0) return;
            i = (i + 1) & mask_;
        }
        // backward shift: move later entries of the probe run into the hole when their home slot allows it
        for (std::size_t j = (i + 1) & mask_; keys_[j] != 0; j = (j + 1) & mask_) {
            const std::size_t home = slot(keys_[j]);
            if (((j - home) & mask_) >= ((j - i) & mask_)) {
                keys_[i] = keys_[j];
                vals_[i] = vals_[j];
                i = j;
            }
        }
        keys_[i] = 0;
    }
```

***Listing 19.1.** Deletion by backward shift: the probe runs stay unbroken without tombstones. code/firm/bookbuilder/cpp/firm_bookbuilder.hpp*

The orders themselves live in a pool of fixed-size records allocated at start-up, with a [free list](https://one-course.com/books/quant/13/en/chapter/6-c-for-latency-i-memory#def-ll-cpp-for-latency-i-memory-pool) (chapter 6); the map stores a slot index, not a pointer. After start-up, applying an event allocates nothing: the build’s test counts the heap allocations while both fixtures are applied, and finds none.

## 19.4 Correctness under gaps, crosses and recovery

**Definition 19.4 (Book invariant).**

A *book invariant* is a property every correct book satisfies after every event, checked by the builder in its debug builds: each level’s quantity equals the sum of its orders’ quantities, no empty level is reported, and the best bid is below the best ask.

A book is wrong far more often because of its inputs than because of its structure. An event may name an unknown order (a reference lost in a gap), reduce an order by more than it holds, or arrive while the handler has flagged the book as stale. The build’s rules follow the [feed handler](https://one-course.com/books/quant/13/en/chapter/18-the-feed-handler#def-ll-the-feed-handler-handler) of chapter 18: during a snapshot (between its begin and end events) the book is emptied, rebuilt from the snapshot’s orders and flagged stale; an event for an unknown order is ignored and counted; a reduction larger than the order removes the order. Invariants catch the rest: the Python reference checks them after every event of both fixtures, and the C++ builder’s `check()` recomputes every level from the pool.

A crossed book deserves a word. The venue never publishes one in continuous trading, so a crossed book in the builder means a lost event or a bug, and must be treated as stale, not traded on. In auctions and in some consolidated views crosses are legitimate; the builder then reports them rather than repairing them.

The ladder has one correctness hazard of its own, recentring. When the touch leaves the middle half of the window, the builder moves the base so that the mid is at the centre and files every live order again: the only pass over all the orders, done in place.

```cpp
    // The ladder follows the touch: when a best price leaves the middle half, move the base so that the mid is at the
    // centre, and re-file every live order (the only full pass, and no allocation unless orders fall outside).
    void maybe_recentre() {
        const bool bid = bb_ >= 0, ask = ba_ < w_;
        if ((!bid || (bb_ >= w_ / 4 && bb_ < 3 * w_ / 4)) && (!ask || (ba_ >= w_ / 4 && ba_ < 3 * w_ / 4))) return;
        const std::int64_t mid = bid && ask ? (price_of(bb_) + price_of(ba_)) / 2 : price_of(bid ? bb_ : ba_);
        centre(static_cast<std::uint32_t>(mid));
        ++recentrings;
    }

    void centre(std::uint32_t mid) {
        base_ = static_cast<std::int64_t>(mid) - (w_ / 2) * tick_;
        base_ -= base_ % tick_;
        centred_ = true;
        std::fill(bids_.begin(), bids_.end(), Level{});
        std::fill(asks_.begin(), asks_.end(), Level{});
        far_bids_.clear();
        far_asks_.clear();
        bb_ = -1;
        ba_ = w_;
        if (live_ == 0) return;
        for (const auto& o : pool_)
            if (o.live) level_add(o.side, o.price, o.qty, 1);   // o.qty converts to a positive change
    }

```

***Listing 19.2.** Recentring: when a best price leaves the middle half, centre the ladder on the mid and file the live orders again. code/firm/bookbuilder/cpp/firm_bookbuilder.hpp*

How often? For a price that moves like a Brownian motion, one expected exit time answers it.

**Proposition 19.5 (Recentrings of a ladder).**

Let the price, in ticks, be a Brownian motion with standard deviation $\sigma$ per day, and let the ladder be recentred whenever the price moves $a$ ticks from the centre ($a$ is a quarter of the width). The time between recentrings has mean $a^2/\sigma^2$ days, so the long-run rate is $\sigma^2/a^2$ recentrings a day. A price that trends by $D$ ticks in a day causes about $D/a$.

**Proof.** Let $X_t$ be the move from the centre and $\tau$ the first time $|X_\tau| = a$. Since $X_t^2 - \sigma^2 t$ is a martingale and $\tau$ has finite mean, optional stopping gives $\E[X_\tau^2] = \sigma^2 \E[\tau]$, and $X_\tau^2 = a^2$, so $\E[\tau] =
a^2/\sigma^2$. The recentrings form a renewal process whose long-run rate is $1/\E[\tau]$. A steady trend travels $a$ ticks between recentrings, $D/a$ of them in $D$ ticks. ∎

A stock at 100 with a tick of $10^{-4}$ that moves 1% a day has $\sigma = 10\,000$ ticks: a ladder of 4 096 ticks ($a = 1\,024$) recentres about 95 times a day, one of 65 536 ticks about once every three days. The same stock moving thirty percent in one day travels 300 000 ticks: about 290 recentrings with the narrower ladder, and every one of them refiles every live order. [Figure 19.3](#fig-ll-the-order-book-builder-width) measures that day, on synthetic events whose mid drifts thirty percent: 256 recentrings with 4 096 ticks, fifteen with 65 536, none with a million, and a total processing time that falls from $0.7\,\mathrm{s}$ with a 256-tick ladder to $4\,\mathrm{m}\mathrm{s}$ at 65 536 ticks, then rises again as the ladder outgrows the caches.

![The day a small-tick stock moves thirty percent (100 000 synthetic events, the mid drifting 300 000 ticks): processing time of the ladder book by width, each point labelled with its number of recentrings. Measured on a laptop (Intel Core Ultra 7 155H) under WSL2, no isolated cores. Data: bench_books.py.](https://one-course.com/images/onecourse/chapters/quant-13/ll-the-order-book-builder/fig-4ef7e0873e06.svg)

***Figure 19.3.** The day a small-tick stock moves thirty percent (100 000 synthetic events, the mid drifting 300 000 ticks): processing time of the ladder book by width, each point labelled with its number of recentrings. Measured on a laptop (Intel Core Ultra 7 155H) under WSL2, no isolated cores. Data: `bench_books.py`.*

## 19.5 Testing a book

A [book builder](#def-ll-the-order-book-builder-builder) is tested against other books. The build’s Python reference, a dictionary of orders and one of levels per side with nothing clever about it, is compared event by event with the book of One Quant Book 1, chapter 28 (`firm.feed`), on its sample of order-by-order messages: the same ten levels on each side after every message. It is compared with the book behind One Quant Book 7’s feature engine (`firm.lobfeat`) on that engine’s fixture: the same best prices and sizes after every message. The C++ and Rust ladders are then compared with the Python reference on two fixtures, the simulator’s events and a synthetic small-tick stream, through a 64-bit hash of the top five levels on each side, chained over every event; the comparison runs with the ordinary ladder and with a narrow one that recentres and spills orders into its sparse map, because a structure’s rare paths are where its bugs live. And the tree and sorted-vector builders of the benchmark are checked against the ladder in the same way before any of them is timed.

## 19.6 Tutorial: three books, two regimes

**Goal.** Build the ladder book, prove it against earlier books, and time it against a tree and a sorted vector on a large-tick and a small-tick instrument. **End state:** Figures [19.2](#fig-ll-the-order-book-builder-update) and [19.3](#fig-ll-the-order-book-builder-width), and green tests in Python, C++ and Rust.

1. **The fixtures.** `make_book_fixtures.py` writes the [feed handler](https://one-course.com/books/quant/13/en/chapter/18-the-feed-handler#def-ll-the-feed-handler-handler) ’s events for the simulator’s three seconds (chapter 18) and 6 000 synthetic small-tick events, and the level-2 hashes the reference computes over them.
2. **Differential tests.** The reference against Book 1’s `firm.feed` and Book 7’s `firm.lobfeat` ; the C++ and Rust ladders against the reference (hash after every event), with widths of 4 096 and 256 ticks; the order map’s deletion on keys that collide; the invariants after every event; zero allocations after construction.
3. **Measure** with `python bench_books.py` : the three structures on the simulator’s minute and on 100 000 small-tick events, then the ladder by width on the day the mid drifts thirty percent.

**What to change next.** Replace the ladder’s scan for the next non-empty level by a bitmap of occupied levels and a count-trailing-zeros instruction, and measure the p99 on the large-tick stream again.

## 19.7 Build: the book builder

**Purpose.** The book behind every strategy of the trading system: it consumes the [feed handler](https://one-course.com/books/quant/13/en/chapter/18-the-feed-handler#def-ll-the-feed-handler-handler)’s events (chapter 18) and serves level 1 and level 2 to the strategy engine (chapter 20) and the risk gate (chapter 22).

**Interface.** Python reference `firm_bookbuilder.Book`: `apply(event)`, `best()`, `depth(side, n)`, `stale`, `check()`; `l2_hash`; `recentrings`, `expected_recentrings`. C++20 `firm::book::LadderBook(tick, width, max_orders)`: `apply`, `best`, `depth`, `check`, `stale`, `recentrings`; `OrderMap`; `l2_hash`. Rust `firm_bookbuilder::LadderBook` and `OrderMap` with the same.

**Rules.** Order lookup through [open addressing](#def-ll-the-order-book-builder-open) into a fixed pool; levels in a dense ladder with a sparse fallback; the ladder recentred when a best price leaves its middle half; the book emptied and flagged stale from a snapshot’s begin to its end; no allocation per event after construction unless an order lands outside the ladder.

**Acceptance tests.** `code/firm/bookbuilder/`: level 2 identical to Book 1’s `firm.feed` after every message of its sample and to Book 7’s `firm.lobfeat` after every message of its fixture (reference); the C++ and Rust ladders equal to the reference after every event of both fixtures, with a normal and a narrow ladder; invariants after every event; zero allocations; the order map’s backward-shift deletion; the recentring model against a simulated Brownian price.

**Stretch.** A bitmap of occupied levels for the scan; level 3 with queue positions for the firm’s own orders; a market-by-price mode; recentring in the background into a second ladder.

Sources and further reading

- Nasdaq, *TotalView-ITCH 5.0* specification, section 1.4.5 (Order Replace).
- cppreference.com, `std::map` .
- The earlier books’ order books: `firm.feed` (One Quant Book 1, chapter 28) and `firm.lobfeat` (One Quant Book 7, chapter 8).

## 19.8 Exercises

**Exercise 19.1 ★.**

A ladder of 4 096 ticks with a tick of 0.01 is centred on 50.00. What is its base price, which index holds 49.73, and where must the best bid be for the ladder to stay put?

**Solution of Exercise 19.1.**

The base is $50.00 - 2\,048 \times 0.01 = 29.52$; 49.73 sits at index $(49.73 - 29.52)/0.01 = 2\,021$. The middle half is indices 1 024 to 3 071, prices 39.76 to 60.23: the ladder stays put while both best prices remain in that range.

**Exercise 19.2 ★.**

How much memory does a ladder of 65 536 ticks take with 16 bytes per level and two sides? Does it fit the second-level cache of chapter 3?

**Solution of Exercise 19.2.**

$65\,536 \times 16 \times 2 = 2$ MiB, exactly the size of the laptop’s second-level cache (chapter 3): it fits only if nothing else does. In practice the touch and the few levels near it are what stays in cache.

**Exercise 19.3 ★.**

An order of 500 at 20.10 is replaced by one of 300 at 20.11. Which events does the book apply, and what happens to the order’s place in its queue?

**Solution of Exercise 19.3.**

The replace removes the order of 500 at 20.10 (its level loses 500) and adds a new order of 300 at 20.11 under the new reference, at the back of that level’s queue: it has lost its priority, as the specification’s new reference says.

**Exercise 19.4 ★★.**

Keys 1 024, 2 048, 3 072 hash to the same home slot 5 in a table of 16. They are inserted in that order, then 1 024 is erased. Show the table before and after the backward shift. What would a tombstone have cost instead?

**Solution of Exercise 19.4.**

Before: slot 5 holds 1 024, slot 6 2 048, slot 7 3 072. Erasing 1 024 empties slot 5; 2 048 (home 5) moves back to 5 and 3 072 (home 5) to 6; slot 7 is emptied. A tombstone would have left slot 5 marked deleted: every lookup of 2 048 and 3 072 would probe through it until the table is rebuilt, and after a day of cancels, probe runs would grow long.

**Exercise 19.5 ★★.**

A stock trades at 40 with a tick of 0.01 and a daily volatility of 2%. With a ladder of 1 024 ticks, how many recentrings per day does [Proposition 19.5](#prop-ll-the-order-book-builder-recentre) predict? And with 4 096?

**Solution of Exercise 19.5.**

$\sigma = 40 \times 0.02 / 0.01 = 80$ ticks a day. With 1 024 ticks, $a = 256$: $(80/256)^2 \approx 0.098$, about one recentring in ten days; with 4 096, $a = 1\,024$: $0.0061$, one in 160 days.

**Exercise 19.6 ★★.**

The builder receives a reduction of 300 for an order that holds 200. What does it do, and what does it tell the monitoring?

**Solution of Exercise 19.6.**

It removes the order (reducing its level by the 200 it holds) and counts the event as inconsistent: a reduction larger than the order means an event was lost or duplicated upstream, and the monitoring should raise it with the [feed handler](https://one-course.com/books/quant/13/en/chapter/18-the-feed-handler#def-ll-the-feed-handler-handler)’s gap counters.

**Exercise 19.7 ★★★.**

*Coding.* Add a bitmap of occupied levels to the C++ ladder (one bit per tick and side) and use count-trailing-zeros to find the next best level; check the fixtures’ hashes and measure the large-tick p99.

**Solution of Exercise 19.7.**

Keep, per side, an array of 64-bit words with one bit per ladder slot, set when a level becomes non-empty and cleared when it empties. The next best bid below index $i$ is found word by word with count-leading-zeros on the masked word, the next best ask with count-trailing-zeros: a few instructions per 64 empty slots instead of 64 loads. Recentring rebuilds the bitmaps with the levels.

**Exercise 19.8 ★★★.**

*Find the flaw.* “We sized the ladder at 512 ticks because it fits in the first-level cache, and our tests on a quiet day showed no recentring.”

**Solution of Exercise 19.8.**

A quiet day says nothing about the day the price moves: a 512-tick ladder ($a = 128$) recentres once per 128 ticks of travel, and on a small-tick stock a thirty percent day is hundreds of thousands of ticks, thousands of recentrings (the measurement’s 256-tick ladder needed almost twenty thousand). Size the ladder for the largest move expected, and test it on that move.

## 19.9 Problem: The Stock That Moved Thirty Percent

**Problem 19.1.**

Weekend problem — how wide a ladder

A small-tick stock trades at 100 with a tick of $10^{-4}$. On an ordinary day its volatility is 1.5%; on the day of this problem it moves thirty percent. Use [Proposition 19.5](#prop-ll-the-order-book-builder-recentre) and the measurements of [Figure 19.3](#fig-ll-the-order-book-builder-width) (`measured_width.csv`).

**Part I — The ordinary day.**

1. What is $\sigma$ in ticks per day?
2. How many recentrings a day does a ladder of 4 096 ticks expect? Of 65 536?
3. What width expects one recentring a day?
4. Why is the ordinary day a poor guide to sizing?

**Part II — The day that matters.**

5. How many ticks does the price travel, and how many recentrings does a steady trend cause with 4 096 ticks?
6. How many did the measurement count, and why fewer?
7. With 256 ticks the measurement counts far more than the trend alone predicts. Why?
8. What does one recentring cost, from the measurements at 4 096 and 65 536 ticks?

**Part III — The trade-off.**

9. Which width minimises the day’s measured total, and what does it cost?
10. Why does the total rise again beyond it?
11. How much memory does that width take for both sides?
12. What does the median update time say about the width?

**Part IV — The verdict.**

13. State the *named result* : the ladder width against the recentrings of the day and its total cost, and the width that minimises it.
14. How would you choose the width per instrument?
15. What would recentring in the background, into a second ladder, change?
16. Why must the tests include a narrow ladder?
17. How does a large-tick instrument change the answer?
18. What should the builder report to monitoring about recentrings?
19. What does the day cost with a balanced tree instead?
20. In one sentence: what does a dense ladder buy, and what must it be protected against?

**Solution of Problem 19.1.**

1. $100 \times 0.015 / 10^{-4} = 15\,000$ ticks.
2. $(15\,000/1\,024)^2 \approx 215$ a day with 4 096 ticks; $(15\,000/16\,384)^2 \approx 0.84$ with 65 536.
3. One a day when $a = \sigma$ : $4 \times 15\,000 = 60\,000$ ticks.
4. The ladder’s cost comes from the days the price travels far; an ordinary day’s rate hides them.
5. 300 000 ticks; a steady trend causes $300\,000/1\,024 \approx 293$ .
6. 256: each recentring centres the ladder on the mid, which has already passed the edge, so the next one needs more than $a$ ticks of travel.
7. The book itself is wider than the middle half of a 256-tick ladder (orders up to 300 ticks from the mid), so the best prices leave it at every jump of the touch, not only when the mid travels: 19 744 recentrings.
8. $(12.8 - 4.4)~\text{ms}/(256 - 15) \approx 35\,\text{µ}\mathrm{s}$ each: a pass over the order pool and the ladder.
9. 65 536 ticks: fifteen recentrings and about $4\,\mathrm{m}\mathrm{s}$ for the day.
10. Each centring clears the whole ladder, and a ladder of millions of ticks no longer fits any cache: the median update rises from about $29\,\mathrm{n}\mathrm{s}$ to about $135\,\mathrm{n}\mathrm{s}$ at $2^{20}$ and $2^{22}$ ticks.
11. 2 MiB.
12. It is nearly flat, about $30\,\mathrm{n}\mathrm{s}$ from 4 096 to 65 536 ticks and 36 at 262 144: within that range the width costs through recentrings, not through updates.
13. **Named result.** On a thirty-percent day of a small-tick stock (300 000 ticks), a 4 096-tick ladder recentres 256 times and costs about $13\,\mathrm{m}\mathrm{s}$ , a 65 536-tick one fifteen times and $4\,\mathrm{m}\mathrm{s}$ , the day’s minimum; a 256-tick ladder recentres almost twenty thousand times and costs $0.7\,\mathrm{s}$ .
14. From the instrument’s price, tick and the largest daily move expected (a multiple of its volatility): four times that move in ticks, capped by the memory and cache the book may use.
15. It takes recentring off the critical path: updates continue on the old ladder while the new one is filled, then the builder switches, at the price of a second ladder and a way to replay the updates made meanwhile.
16. Because a wide ladder rarely recentres or spills into its sparse map, and the tests must exercise those paths.
17. On a large-tick instrument the price travels few ticks and the book is dense near the touch: a small ladder rarely recentres, and every structure is fast.
18. The count per day and the time each took, with the instrument, so that a width that became too small shows up before it costs.
19. About $65\,\mathrm{n}\mathrm{s}$ (vector) to $72\,\mathrm{n}\mathrm{s}$ (tree) per event on the small-tick stream whatever the move: no recentring, but twice the ladder’s median every event.
20. Constant-time levels at the price of memory and recentring; it must be protected against the price travelling far, by its width and by tests on the day that matters.

## 19.10 Interview questions

**Interview question 19.1 ★ developer.**

Design an order book for a market-by-order feed. Which operations must be fast, and how fast?

**Solution of Interview question 19.1.**

Look up an order by reference, add to, reduce and remove a level, and read the best level and the first few levels: all in tens of nanoseconds, every event. Orders in a pool found by [open addressing](#def-ll-the-order-book-builder-open); levels in a dense ladder around the touch with a sparse fallback; invariants checked in debug builds.

*What the interviewer is looking for: operations, their frequency and a structure per operation.*

**Interview question 19.2 ★★ developer.**

Tree, sorted vector or array of price levels: when would you choose each?

**Solution of Interview question 19.2.**

A tree for generality (any price, any tick, no tuning) at logarithmic cost and an allocation per new level; a sorted vector when the book is shallow and changes concentrate at the touch; an array of levels when the tick is known and the price stays within a window, with recentring for when it does not. Measure on the instrument’s own data.

*What the interviewer is looking for: the tick regime and the book’s shape decide.*

**Interview question 19.3 ★★ developer.**

How would you look up orders by reference without allocating? How do you delete from an open-addressing table?

**Solution of Interview question 19.3.**

[Open addressing](#def-ll-the-order-book-builder-open) with linear probing into flat arrays sized at start-up to twice the live orders, values being slots in a preallocated pool. Delete by shifting the following entries of the probe run back into the hole when their home slot allows it, so that no tombstone lengthens later lookups.

*What the interviewer is looking for: flat arrays, a pool, and backward-shift deletion.*

**Interview question 19.4 ★★ developer.**

Your book is crossed. What could have happened, and what do you do?

**Solution of Interview question 19.4.**

A lost or duplicated event (a gap the handler did not flag, an unknown reference), a bug in the builder, or a legitimate cross (an auction). Mark the book stale, stop trading on it, check the handler’s gap counters, and resynchronise from a snapshot; investigate with the recorded events.

*What the interviewer is looking for: stale first, then cause, then recovery.*

**Interview question 19.5 ★★ developer.**

How do you test a [book builder](#def-ll-the-order-book-builder-builder) so that you trust it on the day that matters?

**Solution of Interview question 19.5.**

Compare it event by event with independent books on shared fixtures, in every language it is written in; exercise its rare paths (narrow ladders, recentring, snapshots, unknown references); check invariants after every event; replay the busiest and most volatile days recorded; count allocations.

*What the interviewer is looking for: differential testing and the rare paths.*

**Interview question 19.6 ★★★ developer, researcher.**

A dense ladder is fast until the price moves far. Quantify how far, and design around it.

**Solution of Interview question 19.6.**

With daily volatility $\sigma$ in ticks and a recentring at $a$ ticks from the centre, a Brownian price recentres $\sigma^2/a^2$ times a day and a trend of $D$ ticks $D/a$ times. Size the ladder for the largest move expected, recentre in place or in the background, keep a sparse fallback, and monitor recentrings per instrument.

*What the interviewer is looking for: the exit-time argument and a sizing rule.*