Order-book labs

6.9 Lab and reading

Lab

The code is in the companion repository under ch06-book/, a single crate with four binaries, book-build, book-replay, break and rebase (the first two prefixed because Cargo reserves build as a binary name and replay would collide with the networking chapter’s); the repository holds the code and this chapter holds the reasons. As in the earlier labs, write the prediction down before each run, report p50, p99 and max and never an average, read the counter with rdtsc and subtract the cost of reading it twice back to back, run on a pinned core, and hand-write apply, with no book crates.

ch06-book/
  Cargo.toml
  src/
    lib.rs          the Book trait, the three books, the property test
    gen.rs          the generator of updates
    bin/
      build.rs      exercise 1
      replay.rs     exercise 2
      break.rs      exercise 3
      rebase.rs     exercise 4

1. Build a book. Implement apply, best_bid and best_ask on TreeBook, VecBook and ArrayBook behind the shared Book trait, the array with a 65,536-level window centred on the first mid, its cursors and its bitmaps, all allocated in new. Write one property test that feeds the same random updates to all three and asserts identical tops after every update, not only at the end; make zero quantities common enough that the best level empties and has to be found again, because the walk inward is where the three disagree first. Before you run it, write down which structure you expect to fail first and on which kind of update.
2. Replay. Write a generator of 10 million updates with a realistic shape: 95% on a level deep in the book, 4% on the best level’s quantity, and 1% moving the best price, with short walks of a few levels (or, if you did the stretch of the networking chapter, replay the feed you recorded there). Run the same stream through each structure and report updates per second and the p50, p99 and max of apply. Predict first from the ladder: a good prediction puts ArrayBook at 2–5 ns with its p99 where the 1% that move the cursor land, 5–20 ns, and TreeBook, with its two best-price walks, at 160–500 ns on an existing level and 210–700 ns on a new or emptied one. If ArrayBook’s max is far above its p99, that is the machine, not the structure; name it.
3. Break it. Drop one update from the stream and show the book diverging: after the drop the tops differ from a TreeBook that saw the whole stream. Make the dropped update the delete of the best bid, let the stream run on until an ask arrives at or below the price that should be gone, and a crossed book appears. Then move the sequence check into the feed handler that calls apply, add the Stale state, and show the resync: the gap is seen on the next update, the book goes Stale, a snapshot is fetched (simulate it taking 70 ms), the buffered deltas are replayed, the state returns to Live and the tops agree again. Report the time in each state and the updates buffered while Syncing.
4. Stretch: a price leaving the window. Make the window a ring, so that re-basing is a change of origin plus clearing the slots that change ends, and measure it against the copy re-base (a 1 MB memmove, predicted at 50–150 µs) and against a rebuild from the levels of the reference book. Measure a step of a few levels and a jump of the whole window, and predict which of the three wins at each.

Check: everyone can explain why the dense array wins and what it costs in memory. A good answer says that the array turns a price into an address by arithmetic, so an apply is an index, a load, a compare and a store at 2–5 ns with the line usually in L1, where the tree chases pointers and allocates at 100–500 ns, and that the price is 512 KB a side (1 MB for both) for a window chosen per instrument and re-based when the price leaves it, against 54 MB a side for an array over the whole range.