wickra_exchange_core/
orderbook.rs

1//! A locally maintained level-2 order book.
2//!
3//! Streaming depth arrives as a snapshot followed by incremental diffs. Keeping
4//! a correct local book is its own fiddly problem: diffs must be applied in
5//! sequence, stale diffs (already covered by the snapshot) dropped, and a
6//! **sequence gap** — a missing diff — detected so the book can be re-synced
7//! from a fresh snapshot rather than silently drifting. [`OrderBookBuilder`]
8//! does exactly that, following the canonical depth-management algorithm.
9
10use crate::events::{BookDelta, BookLevel, OrderBookSnapshot};
11use crate::symbol::Symbol;
12use rust_decimal::Decimal;
13use std::collections::BTreeMap;
14
15/// The outcome of applying a [`BookDelta`].
16#[derive(Debug, Clone, Copy, PartialEq, Eq)]
17pub enum BookUpdate {
18    /// The diff was applied and advanced the book.
19    Applied,
20    /// The diff is older than the current state and was ignored.
21    Stale,
22    /// A sequence gap was detected: a diff is missing. The book is now marked
23    /// uninitialized and must be re-synced from a fresh snapshot.
24    Gap,
25    /// No snapshot has been applied yet; the diff cannot be used.
26    Uninitialized,
27}
28
29/// A local L2 book built from a snapshot and a stream of diffs.
30#[derive(Debug)]
31pub struct OrderBookBuilder {
32    symbol: Symbol,
33    bids: BTreeMap<Decimal, Decimal>,
34    asks: BTreeMap<Decimal, Decimal>,
35    last_update_id: u64,
36    /// The venue stamp of the most recent frame folded in, so a snapshot taken
37    /// from the builder reports how fresh the book actually is rather than when
38    /// it happened to be read.
39    timestamp: i64,
40    initialized: bool,
41}
42
43impl OrderBookBuilder {
44    /// A new, uninitialized builder for `symbol`.
45    #[must_use]
46    pub fn new(symbol: Symbol) -> Self {
47        Self {
48            symbol,
49            bids: BTreeMap::new(),
50            asks: BTreeMap::new(),
51            last_update_id: 0,
52            timestamp: 0,
53            initialized: false,
54        }
55    }
56
57    /// The market this book tracks.
58    #[must_use]
59    pub fn symbol(&self) -> &Symbol {
60        &self.symbol
61    }
62
63    /// Whether a snapshot has been applied and no unresolved gap exists.
64    #[must_use]
65    pub fn is_initialized(&self) -> bool {
66        self.initialized
67    }
68
69    /// The last sequence id the book has incorporated.
70    #[must_use]
71    pub fn last_update_id(&self) -> u64 {
72        self.last_update_id
73    }
74
75    /// Reset the book from a full snapshot, marking it initialized.
76    pub fn apply_snapshot(&mut self, snapshot: &OrderBookSnapshot) {
77        self.bids = snapshot
78            .bids
79            .iter()
80            .filter(|l| l.quantity > Decimal::ZERO)
81            .map(|l| (l.price, l.quantity))
82            .collect();
83        self.asks = snapshot
84            .asks
85            .iter()
86            .filter(|l| l.quantity > Decimal::ZERO)
87            .map(|l| (l.price, l.quantity))
88            .collect();
89        self.last_update_id = snapshot.last_update_id;
90        self.timestamp = snapshot.timestamp;
91        self.initialized = true;
92    }
93
94    /// Apply an incremental diff, returning how it was handled.
95    ///
96    /// Stale diffs are ignored; a gap marks the book uninitialized (the caller
97    /// should re-fetch a snapshot and call [`apply_snapshot`](Self::apply_snapshot)).
98    pub fn apply_delta(&mut self, delta: &BookDelta) -> BookUpdate {
99        if !self.initialized {
100            return BookUpdate::Uninitialized;
101        }
102        // Entirely before our state: already covered by the snapshot.
103        if delta.final_update_id <= self.last_update_id {
104            return BookUpdate::Stale;
105        }
106        // A missing diff: the next expected id is last_update_id + 1.
107        if delta.first_update_id > self.last_update_id + 1 {
108            self.initialized = false;
109            return BookUpdate::Gap;
110        }
111        for level in &delta.bids {
112            apply_level(&mut self.bids, level);
113        }
114        for level in &delta.asks {
115            apply_level(&mut self.asks, level);
116        }
117        self.last_update_id = delta.final_update_id;
118        self.timestamp = delta.timestamp;
119        BookUpdate::Applied
120    }
121
122    /// The best (highest-price) bid as `(price, quantity)`.
123    #[must_use]
124    pub fn best_bid(&self) -> Option<(Decimal, Decimal)> {
125        self.bids.iter().next_back().map(|(&p, &q)| (p, q))
126    }
127
128    /// The best (lowest-price) ask as `(price, quantity)`.
129    #[must_use]
130    pub fn best_ask(&self) -> Option<(Decimal, Decimal)> {
131        self.asks.iter().next().map(|(&p, &q)| (p, q))
132    }
133
134    /// The mid price `(best_bid + best_ask) / 2`, or `None` if either side is empty.
135    #[must_use]
136    pub fn mid_price(&self) -> Option<Decimal> {
137        match (self.best_bid(), self.best_ask()) {
138            (Some((bid, _)), Some((ask, _))) => Some((bid + ask) / Decimal::from(2)),
139            _ => None,
140        }
141    }
142
143    /// The spread `best_ask - best_bid`, or `None` if either side is empty.
144    #[must_use]
145    pub fn spread(&self) -> Option<Decimal> {
146        match (self.best_bid(), self.best_ask()) {
147            (Some((bid, _)), Some((ask, _))) => Some(ask - bid),
148            _ => None,
149        }
150    }
151
152    /// Export the top `depth` levels per side as a snapshot, best-first.
153    #[must_use]
154    pub fn to_snapshot(&self, depth: usize) -> OrderBookSnapshot {
155        let bids = self
156            .bids
157            .iter()
158            .rev()
159            .take(depth)
160            .map(|(&price, &quantity)| BookLevel { price, quantity })
161            .collect();
162        let asks = self
163            .asks
164            .iter()
165            .take(depth)
166            .map(|(&price, &quantity)| BookLevel { price, quantity })
167            .collect();
168        OrderBookSnapshot {
169            symbol: self.symbol.clone(),
170            last_update_id: self.last_update_id,
171            bids,
172            asks,
173            // The builder folds deltas into a book; the freshest thing it knows
174            // is the stamp on the last delta it applied.
175            timestamp: self.timestamp,
176        }
177    }
178}
179
180/// Insert/update a level; a zero (or negative) quantity removes it.
181fn apply_level(side: &mut BTreeMap<Decimal, Decimal>, level: &BookLevel) {
182    if level.quantity <= Decimal::ZERO {
183        side.remove(&level.price);
184    } else {
185        side.insert(level.price, level.quantity);
186    }
187}
188
189#[cfg(test)]
190mod tests {
191    use super::*;
192    use rust_decimal_macros::dec;
193
194    fn symbol() -> Symbol {
195        Symbol::new("BTC", "USDT")
196    }
197
198    fn snapshot(id: u64) -> OrderBookSnapshot {
199        OrderBookSnapshot {
200            symbol: symbol(),
201            last_update_id: id,
202            bids: vec![
203                BookLevel::new(dec!(100), dec!(1)),
204                BookLevel::new(dec!(99), dec!(2)),
205            ],
206            asks: vec![
207                BookLevel::new(dec!(101), dec!(1)),
208                BookLevel::new(dec!(102), dec!(3)),
209            ],
210            timestamp: 0,
211        }
212    }
213
214    #[test]
215    fn diff_before_snapshot_is_uninitialized() {
216        let mut book = OrderBookBuilder::new(symbol());
217        assert!(!book.is_initialized());
218        let delta = BookDelta {
219            symbol: symbol(),
220            first_update_id: 1,
221            final_update_id: 2,
222            bids: vec![],
223            asks: vec![],
224            timestamp: 0,
225        };
226        assert_eq!(book.apply_delta(&delta), BookUpdate::Uninitialized);
227    }
228
229    #[test]
230    fn snapshot_then_best_levels() {
231        let mut book = OrderBookBuilder::new(symbol());
232        book.apply_snapshot(&snapshot(10));
233        assert!(book.is_initialized());
234        assert_eq!(book.last_update_id(), 10);
235        assert_eq!(book.symbol(), &symbol());
236        assert_eq!(book.best_bid(), Some((dec!(100), dec!(1))));
237        assert_eq!(book.best_ask(), Some((dec!(101), dec!(1))));
238        assert_eq!(book.mid_price(), Some(dec!(100.5)));
239        assert_eq!(book.spread(), Some(dec!(1)));
240    }
241
242    #[test]
243    fn contiguous_diff_applies_and_advances() {
244        let mut book = OrderBookBuilder::new(symbol());
245        book.apply_snapshot(&snapshot(10));
246        let delta = BookDelta {
247            symbol: symbol(),
248            first_update_id: 11,
249            final_update_id: 12,
250            // Improve the bid, remove the top ask.
251            bids: vec![BookLevel::new(dec!(100.5), dec!(5))],
252            asks: vec![BookLevel::new(dec!(101), dec!(0))],
253            timestamp: 0,
254        };
255        assert_eq!(book.apply_delta(&delta), BookUpdate::Applied);
256        assert_eq!(book.last_update_id(), 12);
257        assert_eq!(book.best_bid(), Some((dec!(100.5), dec!(5))));
258        assert_eq!(book.best_ask(), Some((dec!(102), dec!(3))));
259    }
260
261    #[test]
262    fn stale_diff_is_ignored() {
263        let mut book = OrderBookBuilder::new(symbol());
264        book.apply_snapshot(&snapshot(10));
265        let delta = BookDelta {
266            symbol: symbol(),
267            first_update_id: 5,
268            final_update_id: 9,
269            bids: vec![BookLevel::new(dec!(100), dec!(99))],
270            asks: vec![],
271            timestamp: 0,
272        };
273        assert_eq!(book.apply_delta(&delta), BookUpdate::Stale);
274        // Unchanged.
275        assert_eq!(book.best_bid(), Some((dec!(100), dec!(1))));
276        assert_eq!(book.last_update_id(), 10);
277    }
278
279    #[test]
280    fn gap_marks_uninitialized_for_resync() {
281        let mut book = OrderBookBuilder::new(symbol());
282        book.apply_snapshot(&snapshot(10));
283        // Expected next first id is 11; jumping to 13 is a gap.
284        let delta = BookDelta {
285            symbol: symbol(),
286            first_update_id: 13,
287            final_update_id: 14,
288            bids: vec![],
289            asks: vec![],
290            timestamp: 0,
291        };
292        assert_eq!(book.apply_delta(&delta), BookUpdate::Gap);
293        assert!(!book.is_initialized());
294
295        // Re-syncing from a fresh snapshot recovers.
296        book.apply_snapshot(&snapshot(14));
297        assert!(book.is_initialized());
298        assert_eq!(book.last_update_id(), 14);
299    }
300
301    #[test]
302    fn snapshot_drops_zero_quantity_levels() {
303        let mut book = OrderBookBuilder::new(symbol());
304        let mut snap = snapshot(10);
305        snap.bids.push(BookLevel::new(dec!(98), dec!(0)));
306        book.apply_snapshot(&snap);
307        // The zero-quantity bid is not retained.
308        let exported = book.to_snapshot(10);
309        assert!(exported.bids.iter().all(|l| l.quantity > dec!(0)));
310    }
311
312    #[test]
313    fn to_snapshot_limits_depth_and_orders_best_first() {
314        let mut book = OrderBookBuilder::new(symbol());
315        book.apply_snapshot(&snapshot(10));
316        let snap = book.to_snapshot(1);
317        assert_eq!(snap.bids.len(), 1);
318        assert_eq!(snap.asks.len(), 1);
319        assert_eq!(snap.bids[0].price, dec!(100));
320        assert_eq!(snap.asks[0].price, dec!(101));
321        assert_eq!(snap.last_update_id, 10);
322    }
323
324    #[test]
325    fn empty_book_has_no_mid_or_spread() {
326        let book = OrderBookBuilder::new(symbol());
327        assert!(book.best_bid().is_none());
328        assert!(book.best_ask().is_none());
329        assert!(book.mid_price().is_none());
330        assert!(book.spread().is_none());
331    }
332}
wickra_exchange_core/orderbook.rs

wickra_exchange_core/
orderbook.rs
