Limit order book

Deep dive

How it works

In: add / cancel / reduce commands (id, side, price tick, quantity) · Out: best bid/ask, level totals, front order to match · State: levels[tick] lists of orders in a slab, id index, level bitmap · Cost: O(1) add and cancel, 2-4 cache lines

State per side: levels: [Level; ticks], a bitset with one bit per non-empty level, and the best tick. Each Level stores head, tail, total quantity and order count. Orders live in a slab (Vec<Order> with a free list); prev/next are slab indices, not pointers.

1. Add (id, side, tick, qty): allocate a slot, link it at the level's tail (time priority), add qty, set the level bit, update best if the new tick improves it, insert id → slot.
2. Cancel id: look up the slot, unlink (O(1) with prev/next), subtract qty, free the slot. If the level became empty, clear its bit; if it was the best, scan the bitset from that tick outward for the next non-empty level.
3. Reduce / execute id, n: subtract from the order and its level; at zero, cancel.
4. Match (see matching engine): repeatedly take the head of the best opposite level.

asks  tick 10052: [o7 300] -> [o9 100]          best ask = 10052
      tick 10051: (empty, bit 0)
bids  tick 10050: [o3 200] -> [o4 500] -> [o8 50]  best bid = 10050
      tick 10049: [o1 100]
index: o1→slot0, o3→slot2, ...   slab: [o1][free][o3][o4]...

Code

use std::collections::HashMap;

pub const NIL: u32 = u32::MAX;
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Side { Buy, Sell }

#[derive(Clone, Copy, Debug)]
pub struct Order { pub id: u64, pub qty: u64, pub tick: u32, prev: u32, next: u32, pub side: Side } // 32 bytes

#[derive(Clone, Copy)]
pub struct Level { pub head: u32, tail: u32, pub qty: u64, pub count: u32 }

struct Ladder { levels: Vec<Level>, bits: Vec<u64> }

impl Ladder {
    fn new(ticks: usize) -> Self {
        Ladder { levels: vec![Level { head: NIL, tail: NIL, qty: 0, count: 0 }; ticks], bits: vec![0; (ticks + 63) / 64] }
    }
    fn set(&mut self, t: u32, on: bool) {
        let (w, b) = ((t / 64) as usize, t % 64);
        if on { self.bits[w] |= 1u64 << b } else { self.bits[w] &= !(1u64 << b) }
    }
    fn lowest_at_or_above(&self, t: u32) -> Option<u32> {      // best-ask search
        let mut w = (t / 64) as usize;
        if w >= self.bits.len() { return None; }
        let mut m = self.bits[w] & (!0u64 << (t % 64));
        loop {
            if m != 0 { return Some(w as u32 * 64 + m.trailing_zeros()); }
            w += 1;
            if w == self.bits.len() { return None; }
            m = self.bits[w];
        }
    }
    fn highest_at_or_below(&self, t: u32) -> Option<u32> {     // best-bid search
        let mut w = (t / 64) as usize;
        let mut m = self.bits[w] & (!0u64 >> (63 - t % 64));  // keep bits 0..=t%64
        loop {
            if m != 0 { return Some(w as u32 * 64 + 63 - m.leading_zeros()); }
            if w == 0 { return None; }
            w -= 1;
            m = self.bits[w];
        }
    }
}

pub struct Book {
    orders: Vec<Order>, free: u32, index: HashMap<u64, u32>,
    bids: Ladder, asks: Ladder, pub best_bid: Option<u32>, pub best_ask: Option<u32>,
}

impl Book {
    pub fn new(ticks: usize, cap: usize) -> Self {
        Book { orders: Vec::with_capacity(cap), free: NIL, index: HashMap::with_capacity(cap),
               bids: Ladder::new(ticks), asks: Ladder::new(ticks), best_bid: None, best_ask: None }
    }
    fn alloc(&mut self, o: Order) -> u32 {
        if self.free != NIL {
            let s = self.free; self.free = self.orders[s as usize].next; self.orders[s as usize] = o; s
        } else { self.orders.push(o); (self.orders.len() - 1) as u32 }
    }
    pub fn add(&mut self, id: u64, side: Side, tick: u32, qty: u64) -> bool {
        if qty == 0 || self.index.contains_key(&id) { return false; }
        let slot = self.alloc(Order { id, qty, tick, prev: NIL, next: NIL, side });
        self.index.insert(id, slot);
        let lad = if side == Side::Buy { &mut self.bids } else { &mut self.asks };
        let lv = &mut lad.levels[tick as usize];
        self.orders[slot as usize].prev = lv.tail;
        if lv.tail == NIL { lv.head = slot } else { self.orders[lv.tail as usize].next = slot }
        lv.tail = slot; lv.qty += qty; lv.count += 1;
        lad.set(tick, true);
        match side {
            Side::Buy if self.best_bid.map_or(true, |b| tick > b) => self.best_bid = Some(tick),
            Side::Sell if self.best_ask.map_or(true, |a| tick < a) => self.best_ask = Some(tick),
            _ => {}
        }
        true
    }
    pub fn cancel(&mut self, id: u64) -> Option<u64> {
        let slot = self.index.remove(&id)?;
        let o = self.orders[slot as usize];
        let lad = if o.side == Side::Buy { &mut self.bids } else { &mut self.asks };
        let lv = &mut lad.levels[o.tick as usize];
        if o.prev == NIL { lv.head = o.next } else { self.orders[o.prev as usize].next = o.next }
        if o.next == NIL { lv.tail = o.prev } else { self.orders[o.next as usize].prev = o.prev }
        lv.qty -= o.qty; lv.count -= 1;
        if lv.count == 0 {
            lad.set(o.tick, false);
            if o.side == Side::Buy && self.best_bid == Some(o.tick) {
                self.best_bid = if o.tick == 0 { None } else { lad.highest_at_or_below(o.tick - 1) };
            } else if o.side == Side::Sell && self.best_ask == Some(o.tick) {
                self.best_ask = lad.lowest_at_or_above(o.tick + 1);
            }
        }
        self.orders[slot as usize].next = self.free; self.free = slot;
        Some(o.qty)
    }
    /// Execute or partially cancel `by` shares; returns remaining qty.
    pub fn reduce(&mut self, id: u64, by: u64) -> Option<u64> {
        let slot = *self.index.get(&id)?;
        let Order { qty, tick, side, .. } = self.orders[slot as usize];
        if by >= qty { self.cancel(id); return Some(0); }
        self.orders[slot as usize].qty = qty - by;
        let lad = if side == Side::Buy { &mut self.bids } else { &mut self.asks };
        lad.levels[tick as usize].qty -= by;
        Some(qty - by)
    }
    /// Oldest order at a level: the next one to fill.
    pub fn front(&self, side: Side, tick: u32) -> Option<&Order> {
        let lad = if side == Side::Buy { &self.bids } else { &self.asks };
        let h = lad.levels[tick as usize].head;
        (h != NIL).then(|| &self.orders[h as usize])
    }
}

Complexity and constants

• Add, cancel, reduce, front: O(1), about 2-4 cache lines touched (index bucket, order slot, level, neighbour order).
• Best after the top level empties: O(gap/64) words; a two-level bitmap (one summary bit per 64-bit word) bounds it to 2-3 word reads for 4,096 ticks and stays cheap far beyond.
• Memory: 32 B/order, 24 B/level. 65,536 ticks × 2 sides × 24 B ≈ 3 MB, beyond L2, but only the few lines near the touch are hot.
• A feed-handler book update is order of 50-200 ns in software, dominated by the id lookup cache miss.

Efficiency

Cost: the bound is memory latency (cache misses), not arithmetic. An update touches about 2-4 cache lines; a feed-handler book update is order of 50-200 ns in software, dominated by the order-id lookup miss. Memory: 32 B per order, 24 B per level; 65,536 ticks × 2 sides × 24 B is about 3 MB.

Levers

• Array-indexed ticks plus two-level bitmap — best price from 1-3 word reads instead of an O(log L) tree walk — bounded price window.
• Slab with u32 indices, 32 B orders — two per cache line, no malloc per add — preallocate for the day's peak.
• Dense Vec by id - base_id or a fast-hash Swiss table — removes SipHash cost and probe misses — id lookup dominates.
• Incremental qty/count per level — L2 snapshots never walk orders.

Naive → standard → state of the art

• Naive: sorted vector of orders · O(n) insert and cancel
• Standard: BTreeMap of levels + id map · O(log L), no band limit
• State of the art: array ticks + bitmap + intrusive lists in a slab · O(1), order of 50-200 ns per update

Implementation notes

• Prices: integer ticks, tick = (price - base) / tick_size, never floats. Reject (or route to a fallback map) prices outside the band.
• Order id index: Rust's default SipHash is slow; use a fast hasher (fast hash functions) in a Swiss table. When ids are dense and increasing (exchanges usually assign them that way), index a Vec by id - base_id instead of hashing.
• Use slab indices (u32) instead of pointers: half the size, no lifetime fights, trivially relocatable for snapshots.
• Preallocate the slab and index for the day's peak; growth means reallocation and a latency spike (slab allocator).
• One book per symbol, all owned by one thread; index books by a dense symbol number (ITCH's per-day stock locate code) rather than by ticker string.
• Keep aggregated qty/count per level updated incrementally; L2 snapshots then never walk orders.

Pitfalls

• Recomputing best by scanning all levels on every cancel: fine in tests, O(ticks) in production at the open.
• Modify semantics: a quantity decrease keeps time priority; a price change or quantity increase loses it (cancel + re-add at the tail). Exchanges define this; follow their rules.
• Forgetting qty == 0 and duplicate-id checks: zero-qty orders leave phantom levels with count > 0.
• Overflow of level quantity with u32 shares on busy instruments; use u64.
• Pointer-based lists with a general-purpose allocator: fragmentation and malloc latency on every add.

Variants and alternatives

In production

Exchange matching engines and every market-by-order feed handler (Nasdaq TotalView-ITCH, Cboe PITCH, CME MDP 3.0 market-by-order) rebuild this structure; open source example: liquibook (C++).

Implementations

Sources

• Larry Harris, Trading and Exchanges: Market Microstructure for Practitioners, Oxford University Press, 2003.
• Nasdaq, Nasdaq TotalView-ITCH 5.0 specification. spec
• SEC, Regulation NMS, Rule 612 (Minimum Pricing Increment), 17 CFR 242.612. rule
• Martin D. Gould, Mason A. Porter, Stacy Williams, Mark McDonald, Daniel J. Fenn, Sam D. Howison, Limit order books, Quantitative Finance, 2013. paper · arXiv