From sequence check to top-of-book change

The sequence check

The sequence number is the venue’s running count of updates, one more for each. The feed handler remembers the last one it applied and compares each new one with the next it expects:

use std::cmp::Ordering;

pub enum Seq { Next, Seen, Gap { expected: u64, got: u64 } }

pub fn check_seq(last: u64, seq: u64) -> Seq {
    match seq.cmp(&(last + 1)) {
        Ordering::Equal   => Seq::Next,
        Ordering::Less    => Seq::Seen,
        Ordering::Greater => Seq::Gap { expected: last + 1, got: seq },
    }
}

Equal is the common case: apply it. Greater is a gap, at least one update never seen: the copy is missing a change and cannot be trusted, so the handler stops and hands over to recovery, which fetches a fresh snapshot and replays what arrived meanwhile. Less means already applied, a duplicate after a reconnect or a copy from a second feed; it is dropped, because an old quantity written over a newer one silently undoes a change. This example assumes one consecutive sequence number per complete event. Binance adapters must retain the event ranges and follow the venue’s documented checks, including pu on the futures feed; flattening several level changes into independent consecutive sequence numbers would lose that information. The check is one compare, about 1 ns, its branch almost always predicted.

Find the level

Finding the level means turning a price into the place its quantity lives. The array subtracts the window’s base, the lowest price it covers, from the price in ticks, and the difference is the index: no search, about 1 ns. The Vec binary-searches its occupied prices, about ten compares for 1,000 levels; the tree descends about three nodes from its root; a HashMap hashes the price and probes. A price outside the array’s window has no slot: far from the top it is ignored, and near the top it means a re-base, moving the window.

Set the quantity

An update carries the new absolute quantity at its price, not a change to it: “512 lots are now bid at $68,123.45”, never “12 more than before”. So the store is one write. On the array, zero clears the level: the slot becomes 0 and its bit in the bitmap of occupied levels is cleared; a level that was empty and now holds something sets its bit. The array never allocates; every slot in the window has existed since startup. The others pay here when a level appears or disappears: the Vec shifts every level behind it, and the tree may split a full node, allocating one, or merge two thin ones, freeing one.

Maintain the best-price cursor

The best-price cursor is the array’s stored index of the best occupied level on one side, the highest bid or the lowest ask, so that best_bid and best_ask are one load each, not a search. Outward means towards the spread, the gap between best bid and best ask; inward means away from it, deeper into the book. Every update leaves the cursor in one of three cases. In the first, the update puts quantity at a price better than the cursor, above the best bid or below the best ask: that is the new best, and the cursor moves out to it, one compare and one store. In the second, the update empties the level under the cursor, and the cursor must walk inward, stepping deeper until it finds an occupied level. With the bitmap, the walk masks off the bits from the old best outward in the current 64-bit word and finds the nearest set bit with leading_zeros or trailing_zeros, going to the next word only if this one is empty: 5–20 ns. Without it, the walk reads slot after slot at about 1 ns a level in L1: nothing for three levels, a fifth of a budget for the two hundred levels one large order can empty. In the third case, most updates, neither happens: the change is deeper, or a new quantity at the best itself, and the cursor stays. The Vec needs no cursor, its best always at index 0 with bids stored highest first; the tree keeps none and walks to its last leaf, 30–100 ns, whenever asked.

Decide what the strategy needs

The strategy does not want the book; it wants to know when the part it acts on has changed. It cares about the best bid and ask and their quantities; a change ten ticks deep alters nothing it would do. So apply returns one bit, the top-changed flag: true when the side the update touched has a different best price, or a different quantity at the best, than before. On the array the old top is the cursor and the quantity under it, read before the write, and the new top the same two read after: a compare of 1–2 ns. Most updates are deep and leave the flag false.