High-Performance Order Book Maintenance: Incremental Sync, Data Structures & Benchmarks
This article details local order book maintenance covering incremental WebSocket depth updates, REST snapshot alignment, price quantization to integers, and compares BTreeMap, sorted Vec, flat arrays with bitmap indexing, and RingBuffer implementations with benchmark results on Apple M4 Pro showing array-based structures achieve 4-5ns updates vs 34ns for BTreeMap.
1. Incremental Depth Update Basics
1.1 A Single Incremental Message
After subscribing to <symbol>@depth, each depthUpdate message looks like:
b: [["1851.28","0.007"], ["1856.58","8.872"], ["1856.96","0"]]
a: [["1857.70","1.003"], ["1857.71","0.000"]]
U: 2720900344864 ← first update ID in this batch
u: 2720900347289 ← last update ID in this batch
pu: 2720900342967 ← previous message's ubis bids, a is asks, each entry is [price, quantity].
Quantity is an overwrite value : the total quantity at price 1851.28 becomes 0.007, not an increment of 0.007.
Quantity 0 means delete the level : price 1856.96 is fully filled or cancelled, remove from book.
Missing prices stay unchanged : message only contains changed levels, could be 2 or 200 levels, independent of how many levels you track. Changes far from the top of book are also pushed.
Core local maintenance operation:
for (price, qty) in levels {
if qty == 0.0 {
side.remove(price);
} else {
side.set(price, qty);
}
}1.2 Snapshot and Incremental Alignment
Incremental stream only gives changes, not the starting point. Starting point comes from REST depth snapshot returning current bid/ask levels (e.g., 1000 each) plus a lastUpdateId indicating the update ID up to which the snapshot applies.
Standard alignment flow:
Subscribe WebSocket @depth first, buffer incoming messages.
Fetch REST snapshot, record lastUpdateId.
Discard buffered messages with u < lastUpdateId (occurred before snapshot).
First remaining message must satisfy U <= lastUpdateId <= u, meaning it covers the snapshot's point in time; apply from there.
Each subsequent message check pu == previous u; if continuous apply, if broken go back to step 2.
If step 4 fails (first message's U already > lastUpdateId), snapshot and incremental have a gap, re-fetch snapshot.
Snapshot only has top N levels, incremental covers all prices. Local book outside snapshot depth is incomplete: far prices only appear if they changed after snapshot. Deleting a non-existent local level in incremental is normal, just ignore.
1.3 Convert Price to Integer
Price should not be stored as f64: f64 doesn't implement Ord, can't be BTreeMap key; floating-point errors like 0.1 + 0.2 != 0.3 cause same price to map to different keys.
Exchange prices are integer multiples of tick size (minimum price increment). Parse string directly to integer without floating-point. E.g., tick size 0.01, "1851.28" → 185128.
If tick size not power of 10 (e.g., 0.5), divide by corresponding integer.
Quantities are values, not sorted, f64 fine. Incremental quantities are overwrite values, full replacement each time, no accumulation error; "0" and "0.000" both parse to exact 0.0, deletion check qty == 0.0 safe. For summing multiple levels or reconciling with own orders, convert to integer via step size (minimum quantity increment).
2. BTreeMap
2.1 Usage
Order book needs two operations: high-frequency modify/delete by price; anytime get best price and top N levels. Former needs fast lookup, latter needs ordering. HashMap only satisfies former, getting best price requires full scan, so default choice is ordered BTreeMap:
use std::collections::BTreeMap;
type Tick = i64;
type Qty = f64;
struct OrderBook {
bids: BTreeMap<Tick, Qty>,
asks: BTreeMap<Tick, Qty>,
}Both sides stored ascending by price, no need for separate descending for bids:
let best_bid = book.bids.last_key_value(); // highest bid
let best_ask = book.asks.first_key_value(); // lowest ask
let top_bids = book.bids.iter().rev().take(20);
let top_asks = book.asks.iter().take(20);2.2 B-Tree Structure
Binary search trees (e.g., red-black) store one key per node, lookup traverses log₂ n levels, each level potential cache miss. B-tree packs many keys per node, tree becomes shorter and wider, far fewer pointer hops.
In Rust's BTreeMap, node capacity determined by constant B:
const B: usize = 6;
pub(super) const CAPACITY: usize = 2 * B - 1; // max 11 keys per node
struct LeafNode<K, V> {
parent: Option<NonNull<InternalNode<K, V>>>,
parent_idx: MaybeUninit<u16>,
len: u16,
keys: [MaybeUninit<K>; CAPACITY],
vals: [MaybeUninit<V>; CAPACITY],
}
struct InternalNode<K, V> {
data: LeafNode<K, V>,
edges: [MaybeUninit<BoxedNode<K, V>>; 2 * B], // max 12 children
}Keys and values each in contiguous arrays, sorted within node. Except root, each node has at least 5 keys.
Node-internal search is linear left-to-right, not binary:
for (offset, k) in unsafe { keys.get_unchecked(start_index..) }.iter().enumerate() {
match key.cmp(k.borrow()) {
Ordering::Greater => {}
Ordering::Equal => return IndexResult::KV(start_index + offset),
Ordering::Less => return IndexResult::Edge(start_index + offset),
}
}Max 11 keys per node, keys in contiguous memory, linear scan overhead small.
For order book scale: K is i64, V is f64, leaf node 192 bytes, internal node 288 bytes, node spans multiple cache lines. One side ~1700 levels, leaf nodes hold 5-11 keys each, ~150-340 leaf nodes plus a few internal levels. Lookup walks from root down, each level accesses one node, does several comparisons.
Insert new price: shift subsequent elements in node; if node full, split, allocate new node. Delete price: shift elements forward; if node too empty, borrow from sibling or merge, merge frees node. Order book updates frequently add and remove price levels.
3. Sorted Vec
3.1 Best Price at End
Each side uses a price-sorted Vec<(Tick, Qty)>, all levels in one contiguous memory block.
Like BTreeMap, only stores prices with orders, memory proportional to level count, not price range. Ordering puts best price at end: bids ascending, asks descending. Insert/delete only moves elements after insertion point; updates near top of book move fewest elements.
Store asks with negative price, both sides ascending, share code:
struct SortedVecBook {
bids: Vec<(Tick, Qty)>, // ascending, best bid at end
asks: Vec<(Tick, Qty)>, // store -tick, ascending, best ask at end
}Update: find price position; if exists, update qty or delete; if not exists and qty non-zero, insert. Best price is last element, top N levels are last N elements read in reverse.
Two search methods: linear scan from end, or partition_point binary search. Linear search fast for near-top prices, slower further away; binary search distance-independent but each comparison unpredictable, branch prediction fails.
4. Flat Array
4.1 Price as Direct Index
Since price is integer tick, use directly as array index:
index = tick - base
levels[index] = qtyLookup and modify are single array access, no tree traversal, no node splits/merges, no allocations. qty == 0.0 slot means no order at that price. Cost: best price no longer "naturally ordered", must maintain manually:
struct VecBook {
base: Tick,
bids: Vec<Qty>,
asks: Vec<Qty>,
best_bid: Option<usize>,
best_ask: Option<usize>,
}
// Bid side update
self.bids[i] = qty;
if qty != 0.0 {
if self.best_bid.map_or(true, |b| i > b) {
self.best_bid = Some(i);
}
} else if self.best_bid == Some(i) {
// Best level deleted, scan down to next non-zero level
self.best_bid = self.bids[..i].iter().rposition(|&q| q != 0.0);
}New price better than best replaces directly; best level deleted, linear scan away from book to find next non-zero. Near top of book prices dense, usually few slots. Top N levels similarly scan from best outward, skipping empty slots.
4.2 Bitmap for Next Level
Linear scan after deleting best level costs proportional to distance to next level. Sparse book (illiquid symbols, or large order sweeps dozens of levels) can scan hundreds of empty slots.
Bitmap uses 0/1 bits to record "has order at this position". One bit per position, 1 = has order, 0 = empty.
Applied to order book, each tick maps to one bit:
tick: 100 101 102 103 104 105 106 107
qty: 3.0 0 0 1.5 0 0 0 2.0
bitmap: 1 0 0 1 0 0 0 1Bitmap only records presence.
Add hierarchical bitmap to array, each tick one bit, 1 = has order:
L0: one bit per tick, 262144 ticks = 4096 u64 s.
L1: each bit indicates if an L0 u64 is non-zero, 64 u64 s.
L2: each bit indicates if an L1 u64 is non-zero, single u64.
struct Bitmap {
l0: Vec<u64>,
l1: Vec<u64>,
l2: u64,
}
impl Bitmap {
fn set(&mut self, i: usize) {
self.l0[i >> 6] |= 1 << (i & 63);
self.l1[i >> 12] |= 1 << ((i >> 6) & 63);
self.l2 |= 1 << (i >> 12);
}
fn clear(&mut self, i: usize) {
let w = i >> 6;
self.l0[w] &= !(1 << (i & 63));
if self.l0[w] == 0 {
self.l1[w >> 6] &= !(1 << (w & 63));
if self.l1[w >> 6] == 0 {
self.l2 &= !(1 << (w >> 6));
}
}
}
/// Highest set bit < i, i.e., bid side next level
fn prev(&self, i: usize) -> Option<usize> {
let hi = |x: u64| 63 - x.leading_zeros() as usize;
// L0: lower bits in same word
let w = i >> 6;
let m = self.l0[w] & ((1u64 << (i & 63)) - 1);
if m != 0 {
return Some((w << 6) + hi(m));
}
// L1: lower non-zero word in same group
let w1 = w >> 6;
let m1 = self.l1[w1] & ((1u64 << (w & 63)) - 1);
let w0 = if m1 != 0 {
(w1 << 6) + hi(m1)
} else {
// L2: lower non-zero group
let m2 = self.l2 & ((1u64 << w1) - 1);
if m2 == 0 {
return None;
}
let w1 = hi(m2);
(w1 << 6) + hi(self.l1[w1])
};
Some((w0 << 6) + hi(self.l0[w0]))
}
}Each level examines one u64, uses leading_zeros (CPU single instruction) to locate highest set bit. Regardless of distance, lookup reads at most one word from L0, L1, L2 each, then two more words. Ask side next level is "lowest set bit > i", symmetric using trailing_zeros.
Array updates maintain bitmap synchronously: qty non-zero → set, zero → clear; when best level deleted use prev / next instead of linear scan.
4.3 Problem: Price Space
Array length must cover entire possible price range. Price can move tens of percent in a day, tick size fine, allocating full price space wastes memory and cache, and still can't guarantee price never overflows.
Real systems use a finite window centered on current price, window moves with price.
5. RingBuffer & Dual Structure
5.1 Index Mapping
If window moves and index remains tick - base, must copy entire array. Switch to modulo mapping, physical array static, only logical window moves — RingBuffer (circular array):
#[derive(Clone, Copy, Default)]
struct Level {
tick: Tick, // which price this slot currently belongs to
qty: Qty,
}
struct Ladder {
levels: Vec<Level>,
mask: usize,
min: Tick, // window [min, max)
max: Tick,
}
impl Ladder {
#[inline]
fn idx(&self, tick: Tick) -> usize {
(tick as usize) & self.mask // capacity power of 2, modulo becomes bitwise AND
}
#[inline]
fn contains(&self, tick: Tick) -> bool {
tick >= self.min && tick < self.max
}
#[inline]
fn set(&mut self, tick: Tick, qty: Qty) {
let i = self.idx(tick);
self.levels[i] = Level { tick, qty };
}
#[inline]
fn get(&self, tick: Tick) -> Qty {
let l = &self.levels[self.idx(tick)];
if l.tick == tick { l.qty } else { 0.0 }
}
}Capacity 4096, 250000 and 254096 map to same slot. Each slot stores its price, read verifies tick, mismatch treated as empty.
Best price maintenance same as flat array.
Window recenter trigger: when best bid near window lower bound or best ask near upper bound within 1/8 capacity, recenter window on current mid-price.
5.2 Levels Outside Window
Incremental updates outside window cannot be dropped. E.g., price at 2500, window covers ±20.48, far price 2530 changes; if dropped, when price reaches 2530 and window moves, that level is wrong.
Two common approaches for out-of-window data:
Dual-write : BTreeMap stores complete book, RingBuffer caches only in-window prices. Every update writes both; window move backfills new in-window prices from BTreeMap.
Separate storage : In-window prices only in RingBuffer, out-of-window far levels in BTreeMap. Each update writes to one based on price; window move shifts leaving prices into BTreeMap, entering prices from BTreeMap into RingBuffer.
5.3 Stale Data on Window Move
After window move, slots may retain previous window data. tick verification catches most: old slot's price mismatches new price, read returns empty.
But one case slips through when window moves back and forth. Capacity 4096, mid-price 2500.00:
Window contains 250000, qty 5, slot stores {250000, 5}.
Price rises 30, window shifts up, 250000 leaves window. Same slot now maps to 254096, but 254096 never had orders, slot unchanged, still {250000, 5}.
During this, 250000 cancelled, incremental sends qty = 0, but it's outside window, RingBuffer ignores.
Price falls, window shifts down, 250000 re-enters. Read slot, tick matches, returns qty 5, actual should be 0.
So on window move, newly entering slots must be cleared first (write new tick and qty 0), then backfill from BTreeMap. Separate-storage approach core logic:
fn recenter(&mut self, center: Tick) {
for (side, far) in [(&mut self.bids, &mut self.far_bids), (&mut self.asks, &mut self.far_asks)] {
let l = &mut side.ladder;
let (old_min, old_max) = (l.min, l.max);
l.set_window(center);
let (min, max) = (l.min, l.max);
// First move leaving prices into BTreeMap (slots about to be reused)
for (lo, hi) in [(old_min, min.min(old_max)), (max.max(old_min), old_max)] {
for t in lo..hi {
let q = l.get(t);
if q != 0.0 {
far.insert(t, q);
}
}
}
// Then handle entering prices: clear, then move back from BTreeMap
for (lo, hi) in [(min, old_min.min(max)), (old_max.max(min), max)] {
if lo >= hi { continue; }
for t in lo..hi {
l.set(t, 0.0);
}
let mut moved = far.split_off(&lo);
let mut rest = moved.split_off(&hi);
far.append(&mut rest);
for (t, q) in moved {
l.set(t, q);
}
}
side.rescan(if side.is_bid { max } else { min - 1 });
}
}Leaving slots must be read out before handling entering slots, because they may be the same physical slots.
6. Benchmark Comparison
6.1 Test Method
Test machine: Apple M4 Pro, criterion with synthetic market data:
Price near 2500.00, tick size 0.01; snapshot 1000 levels each side.
200k incremental messages, ~2.13M level updates; 1-20 levels per message.
85% updates near top of book (distance exponential distribution mean 15 ticks), 15% uniform within 2000 ticks; 30% are deletions.
Price random walk, crossed levels deleted by feed, no crossed book.
After each message, read best bid/ask once.
Plus a spike scenario:
Every 2000 messages, mid-price jumps 3000 ticks (~1.2%) in one message, alternating up/down.
Crossed levels pushed as deletions in same message; window moved 92 times total.
Flat array length 2¹⁸ = 262144 ticks, 2 MiB per side, covers 2500.00 ± ~1310, entire test within range. RingBuffer capacity 4096.
6.2 Updates
Average per-level update latency: BTreeMap: Normal Market 34.2 ns, Spike Market 36.6 ns
Sorted Vec, linear search: Normal Market 51.2 ns, Spike Market 43.0 ns
Sorted Vec, binary search: Normal Market 29.8 ns, Spike Market 30.8 ns
Flat Array: Normal Market 4.7 ns, Spike Market 4.9 ns
Flat Array + Bitmap: Normal Market 5.3 ns, Spike Market 5.3 ns
Dual-write: BTreeMap + RingBuffer: Normal Market 33.9 ns, Spike Market 35.8 ns
Separate: RingBuffer + far BTreeMap: Normal Market 3.9 ns, Spike Market 7.2 ns
Interpretation:
Flat array update ~1/7 of BTreeMap. Bitmap adds 0.6 ns (maintaining a few bits per update).
In this test, sorted Vec linear search slower than binary. 15% updates uniform within 2000 ticks, scanning hundreds of elements.
When updates concentrated near top of book, linear faster. Restricting to within 200 ticks: linear 16.7 ns, binary 22.7 ns, BTreeMap 32.8 ns.
Dual-write update latency matches standalone BTreeMap. Still writes BTreeMap every update, RingBuffer only speeds reads.
Separate storage update latency near flat array. Near-top updates only write array, only far levels hit BTreeMap.
6.3 Reads
End-of-test book state, ~1700 bid levels: BTreeMap: Best Bid 2.0 ns, Top 20 Levels 24.9 ns
Sorted Vec: Best Bid 1.3 ns, Top 20 Levels 4.6 ns
Flat Array: Best Bid 1.3 ns, Top 20 Levels 20.2 ns
Flat Array + Bitmap: Best Bid 1.3 ns, Top 20 Levels 29.5 ns
RingBuffer: Best Bid 1.2 ns, Top 20 Levels 24.5 ns
Interpretation:
Best bid read similar across structures, ~2 ns.
Top 20 fastest with sorted Vec — data is last 20 contiguous elements.
Bitmap slows top 20: must call bitmap lookup per level, 20.2 ns → 29.5 ns. RingBuffer verifies tick per level, also slower than flat array.
6.4 Sparse Book
Bid side one level every fixed distance, each round delete best then re-add, each deletion must find next level. Per-round delete+re-add latency:
Next Level Distance 16 ticks: Linear Scan 7.0 ns, Bitmap 4.2 ns
Next Level Distance 512 ticks: Linear Scan 140.2 ns, Bitmap 4.4 ns
Bitmap keeps delete-best latency stable when book sparse. Next level 512 ticks away: linear 140.2 ns, bitmap 4.4 ns. No benefit when book dense.
6.5 Window Move
Single window move latency:
Dual-write: Move 256 ticks 0.31 µs, Move 3000 ticks 2.9 µs
Separate storage: Move 256 ticks 4.2 µs, Move 3000 ticks 33.7 µs
Separate storage cost shows in window moves. 3000-tick jump: single move 33.7 µs, mainly inserting thousands of leaving prices into BTreeMap one by one. That message processing spikes tens of microseconds.
Out-of-window levels unreadable. In spike test, 277 of 200k messages couldn't fill top 20 bids from window alone. Test read interface only reads in-window; deeper levels need fallback to read from far BTreeMap.
6.6 Structure Selection
If strategy only reads best price and top few dozen levels, BTreeMap read already fast enough, bottleneck is updates. Dual-write doesn't improve updates, limited value here.
Strategies reading top dozens every message to compute factors (signals), wanting full book like BTreeMap without price range handling, can replace BTreeMap with sorted Vec: top N ~5x faster than BTreeMap; binary search slightly faster updates, linear search faster when updates concentrated near top. Pure speed: array structures update much faster, even with top 20 read each message total latency still lower.
When updates truly bottleneck, consider separate storage, trading off window-move latency spikes and more correctness-critical code: best price maintenance, window move, stale slot cleanup.
7. Gap Handling
7.1 Gap Meaning
Running receives message where pu!= previous u, meaning at least one message lost. Lost message's price changes unknown, local book diverges from exchange from this point.
Standard flow: re-fetch snapshot, re-align. During re-sync wait for REST response, book unavailable.
7.2 Common Approaches
Real systems handle gaps differently, roughly three categories.
Strict verification: gap triggers re-sync : Every message checks pu, on gap re-fetch snapshot, some implementations tear down stream, reconnect WebSocket, re-sync from scratch. Local book always consistent with exchange, cost: every gap causes downtime. Frequent gaps → frequent brief unavailability.
Only re-sync on WebSocket disconnect : Verify only during snapshot alignment, or not at all. Only fetch snapshot on subscribe and WebSocket reconnect. Some retry alignment gaps a few times, then just log error and continue. Simple, book always available; but if messages truly lost, local book carries wrong levels until next reconnect. Strategy must tolerate this, and should receive notification on gap.
Relaxed verification : pu > previous u: gap in middle, treat as gap, re-sync. pu <= previous u: overlap with already applied, allow continue applying.
Overlap allowed because quantities are overwrite values: a message carries all changed prices in (pu, u] at time u. As long as u newer than local, re-writing overlap yields correct result. u <= previous u means entire message is stale, must discard, else reverts prices to old values.
Slightly deviates from standard flow, but only re-syncs on actual missing messages, reducing unnecessary downtime.
7.3 Book During Invalid Period
Between gap detection and re-sync completion, two options:
Clear : Book emptied, mark is_valid = false, strategy sees no levels.
Retain but mark invalid : Book unchanged, is_valid = false, strategy decides whether/how to use.
Retained book has little value. It's the state at gap moment, strategy already received it in last callback; if needed, strategy can cache last computed factor, doesn't need framework to keep raw book.
Impact minimal, both switchable. is_valid reflects book trustworthiness, strategy decides usage.
7.4 Current Choice
Standard flow requires re-sync on any discontinuity. Our choice:
Strict pu verification, gap triggers re-sync.
During re-sync is_valid = false, whether book cleared not critical, strategy only checks is_valid.
If production gaps frequent and re-sync downtime hurts strategy, consider relaxing verification to allow overlap intervals.
Conclusion
Order book structure choice depends on where bottleneck is: start with BTreeMap to get flow working, measure real update vs read ratio with live data, then decide whether to switch and to what based on business needs.
Signed-in readers can open the original source through BestHub's protected redirect.
This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactand we will review it promptly.
How this landed with the community
Was this worth your time?
0 Comments
Thoughtful readers leave field notes, pushback, and hard-won operational detail here.
