Order Book Data Structures

The vocabulary, in one paragraph: a limit order rests on the book at a price. All resting orders at one price form a price level. The highest bid and the lowest ask are the best bid and best ask, together the touch or top of book; the gap between them is the spread. Levels further away are the book's depth. In a price-time priority market, an incoming order trades first against the best price, and within a price against the oldest order.

Play with the sandbox: add a few orders at several prices, cancel one from the middle of a level, and send an aggressive order through. Watch which structures each operation touches.

Prices are integers. Every venue defines a minimum price increment, the tick (a cent for most US stocks priced at $1 or more; a fixed fraction of a point for each futures contract). Store prices as a count of ticks, or as a fixed-point integer in a unit smaller than any tick, in an i64. Never f64: 0.1 + 0.2 != 0.3, equality on floats breaks map lookups, and rounding differs between code paths. The repo's types crate already wraps it as Price(i64) (and quantities as Qty(u64)); week 8 adds the validation: tick size, lot size and price bands.

Levels. Three serious designs:

• BTreeMap<Price, Level> per side. O(log n) to find or create a level, ordered iteration for depth, best price via first_key_value / last_key_value. B-tree nodes are arrays (up to 11 keys per node in the current std implementation), so it is far more cache-friendly than a red-black tree. The default choice, and a fine one.
• Sorted Vec<Level> with the best price at the end. Store bids ascending and asks descending. Most adds, cancels and fills happen near the touch, which is now near the end of the vector, so inserting or removing a level moves only a few elements. Best price is last(). Pathological when activity lands deep in a long vector, excellent otherwise.
• Dense ladder: Vec<Level> indexed by price - base. O(1) to find any level, no comparisons, perfectly predictable memory access. The costs: memory proportional to the price range rather than to the number of levels, a scan to find the next best level when the best empties, and re-centring when the market drifts outside the window. For a $100 stock with a one-cent tick, a ±10% window is about 2,000 levels per side; at 8 bytes of quantity per level that is 16 KB, which fits in L1.

Inside one level, orders must come out oldest first (time priority), which suggests a queue. But a cancel removes an order from the middle of the queue, and a VecDeque can only do that by shifting everything behind it — O(n) per cancel, on the operation that dominates the workload.

The standard answer is an intrusive doubly linked list: each order node carries prev and next links, so unlinking any node is O(1) given the node. Two changes make it fast in Rust instead of a borrow-checker fight:

• Store nodes in a slab, a Vec<Node> plus a free list of vacant slots, and link them by u32 index rather than by pointer. No allocation per order once the slab is warm, no Rc<RefCell<…>>, and a node with u32 links is small: id, quantity, prev, next fit in 24 bytes.
• Index orders by id: a map from order id to slot is what turns "cancel order 12345" into an O(1) unlink. A partial fill of the front order changes its quantity in place and keeps its position; only removal unlinks.

struct Node { id: u64, qty: u64, prev: u32, next: u32 } // 24 bytes, u32::MAX = none

use std::collections::HashMap;

pub type OrderId = u64;
const NIL: u32 = u32::MAX;

#[derive(Clone, Copy, Debug)]
struct Node {
    id: OrderId,
    qty: u64,
    prev: u32,
    next: u32,
}

/// Every resting order at one price, oldest first. Nodes live in a slab
/// (`nodes` + a `free` list of reusable slots) and link to each other by
/// index; `index` maps an order id to its slot so cancel never searches.
pub struct PriceLevel {
    nodes: Vec<Node>,
    free: Vec<u32>,
    index: HashMap<OrderId, u32>,
    head: u32,
    tail: u32,
    total_qty: u64,
}

impl PriceLevel {
    pub fn new() -> Self {
        PriceLevel { nodes: Vec::new(), free: Vec::new(), index: HashMap::new(), head: NIL, tail: NIL, total_qty: 0 }
    }

    /// Append at the back (lowest time priority). Reuse a free slot if there
    /// is one. Returns false (and changes nothing) if `id` is already here.
    pub fn push_back(&mut self, id: OrderId, qty: u64) -> bool {
        todo!()
    }

    /// Unlink `id` from wherever it sits, in O(1). Returns its remaining qty.
    pub fn cancel(&mut self, id: OrderId) -> Option<u64> {
        todo!()
    }

    /// The oldest order — the next one to trade.
    pub fn front(&self) -> Option<(OrderId, u64)> {
        todo!()
    }

    /// Trade up to `qty` against the front order (a fill). A partial fill
    /// keeps the order at the front; a full fill removes it. Returns the
    /// quantity actually filled (0 on an empty level).
    pub fn fill_front(&mut self, qty: u64) -> u64 {
        todo!()
    }

    pub fn len(&self) -> usize {
        self.index.len()
    }

    pub fn total_qty(&self) -> u64 {
        self.total_qty
    }

    /// Slots ever allocated in the slab — freed slots must be reused.
    pub fn slots_allocated(&self) -> usize {
        self.nodes.len()
    }

    /// Order ids from oldest to newest (for tests; O(n) is fine here).
    pub fn ids(&self) -> Vec<OrderId> {
        todo!()
    }
}

The last case cancels 50,000 orders out of 100,000 in random order and compares your per-cancel time with a plain HashMap remove measured in the same run. An implementation that walks the list to find the order fails it by two orders of magnitude.

Reading the best price must be O(1) because the engine does it on every order. Writes are where the work is:

• An add can only improve the best: compare and maybe replace. O(1).
• A cancel or fill that leaves the best level non-empty changes nothing. O(1).
• A cancel or fill that empties the best level is the one case that needs work: find the next non-empty level. In a BTreeMap that is the next key; on a ladder it is a scan away from the touch.

Today's drill is the ladder version, because it forces you to handle the edges: a level at index 0, a side that empties completely, an add after a side was empty. The harness runs 20,000 random operations and compares your best bid and ask with a BTreeMap model after every one.

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Side {
    Bid,
    Ask,
}

/// Aggregate quantity per price on a dense ladder of `levels` ticks:
/// index i ↔ price `min_price + i` (prices are integer ticks).
pub struct Ladder {
    min_price: i64,
    bids: Vec<u64>,
    asks: Vec<u64>,
    /// Index of the highest non-empty bid level.
    best_bid: Option<usize>,
    /// Index of the lowest non-empty ask level.
    best_ask: Option<usize>,
}

impl Ladder {
    pub fn new(min_price: i64, levels: usize) -> Self {
        Ladder { min_price, bids: vec![0; levels], asks: vec![0; levels], best_bid: None, best_ask: None }
    }

    /// Add `qty` at `price` (always inside the ladder). O(1).
    pub fn add(&mut self, side: Side, price: i64, qty: u64) {
        todo!()
    }

    /// Remove `qty` at `price` — a cancel or a fill; never more than the
    /// level holds. O(1), except when the best level empties: then walk
    /// away from the touch to the next non-empty level (or None).
    pub fn remove(&mut self, side: Side, price: i64, qty: u64) {
        todo!()
    }

    /// (price, aggregate qty) of the best bid. O(1): no scanning here.
    pub fn best_bid(&self) -> Option<(i64, u64)> {
        todo!()
    }

    /// (price, aggregate qty) of the best ask. O(1).
    pub fn best_ask(&self) -> Option<(i64, u64)> {
        todo!()
    }

    pub fn qty_at(&self, side: Side, price: i64) -> u64 {
        todo!()
    }
}

The order index maps an id to the order's location: its side, its price level and its slot. Three options, from general to specialized:

• HashMap<OrderId, Handle> with the default hasher. Correct and DoS-resistant, but SipHash costs a noticeable fraction of your cancel budget for a single u64 key.
• The same map with a fast non-cryptographic hasher (FxHash and friends). Several times cheaper per lookup. Safe here because the keys are not attacker-controlled: see the next point.
• Dense, exchange-assigned ids. The exchange assigns order ids, so it can make them dense (a sequence number), or embed the slab slot in the id itself (slot in the low 32 bits, a generation counter in the high bits to catch stale ids). Lookup becomes an array index. The client's own order id (FIX ClOrdID) is mapped to the exchange id at the gateway, outside the engine's hot path.

Modify semantics decide what the book must support. The common rule across venues: reducing quantity keeps the order's time priority (it is in place, and it only hurts the person doing it), while increasing quantity or changing price loses priority — it is treated as a cancel and a new order at the back of the queue. Otherwise a trader could join a queue with 1 lot and grow to 10,000 while keeping a place they never paid for.

Put the drills together into one structure per instrument:

• two level structures (bids and asks), each mapping a price to a level that holds the aggregate quantity, the order count and the head and tail of its FIFO;
• one slab of order nodes shared by all levels;
• one order index from id to slot (the node itself records side and price, so it can find its level);
• the cached best bid and best ask.

Keep the public surface small. In the repo it is given: the OrderBook trait in crates/book/src/lib.rs (add, cancel, reduce, lookup by id, best level, the front order and fill_front for matching, and visitors for depth), which your concrete Book implements. The engine is generic over that trait, so week 27 and week 28 can drop in a slab book and a ladder book behind the same interface and benchmark them against yours.