pub mod checksum;
pub mod l3;
pub mod replay;
use std::collections::BTreeMap;
use std::fmt;
use serde::{Deserialize, Serialize};
use crate::clock::Timestamps;
use crate::fixed::Fixed;
use crate::types::{Side, Symbol};
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub struct LevelChange {
pub side: Side,
pub price: Fixed,
pub qty: Fixed,
}
impl LevelChange {
pub fn new(side: Side, price: Fixed, qty: Fixed) -> Self {
LevelChange { side, price, qty }
}
pub fn is_removal(&self) -> bool {
self.qty.is_zero()
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct BookSnapshot {
pub symbol: Symbol,
pub bids: Vec<(Fixed, Fixed)>,
pub asks: Vec<(Fixed, Fixed)>,
pub seq: Option<u64>,
pub checksum: Option<u32>,
pub stamps: Timestamps,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct BookDelta {
pub symbol: Symbol,
pub changes: Vec<LevelChange>,
pub seq: Option<u64>,
pub checksum: Option<u32>,
pub stamps: Timestamps,
pub prev_seq: Option<u64>,
pub first_seq: Option<u64>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub enum BookAnomaly {
Crossed { best_bid: Fixed, best_ask: Fixed },
Locked { price: Fixed },
NegativeQty {
side: Side,
price: Fixed,
qty: Fixed,
},
RemovedMissingLevel { side: Side, price: Fixed },
}
impl BookAnomaly {
pub fn corrupts_book(&self) -> bool {
matches!(
self,
BookAnomaly::Crossed { .. }
| BookAnomaly::NegativeQty { .. }
| BookAnomaly::RemovedMissingLevel { .. }
)
}
}
impl fmt::Display for BookAnomaly {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
BookAnomaly::Crossed { best_bid, best_ask } => {
write!(f, "crossed book: bid {best_bid} above ask {best_ask}")
}
BookAnomaly::Locked { price } => write!(f, "locked book at {price}"),
BookAnomaly::NegativeQty { side, price, qty } => {
write!(f, "negative quantity {qty} on {side} at {price}")
}
BookAnomaly::RemovedMissingLevel { side, price } => {
write!(f, "delete for absent {side} level at {price}")
}
}
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct ApplyOutcome {
pub applied: usize,
pub removed: usize,
pub truncated: usize,
pub anomalies: Vec<BookAnomaly>,
}
impl ApplyOutcome {
pub fn is_clean(&self) -> bool {
self.anomalies.is_empty()
}
pub fn corrupted(&self) -> bool {
self.anomalies.iter().any(BookAnomaly::corrupts_book)
}
}
#[derive(Debug, Clone)]
pub struct L2Book {
symbol: Symbol,
bids: BTreeMap<Fixed, Fixed>,
asks: BTreeMap<Fixed, Fixed>,
depth_limit: Option<usize>,
last_stamps: Option<Timestamps>,
updates_applied: u64,
}
impl L2Book {
pub fn new(symbol: Symbol) -> Self {
L2Book {
symbol,
bids: BTreeMap::new(),
asks: BTreeMap::new(),
depth_limit: None,
last_stamps: None,
updates_applied: 0,
}
}
pub fn with_depth_limit(symbol: Symbol, depth: usize) -> Self {
L2Book {
depth_limit: Some(depth),
..L2Book::new(symbol)
}
}
pub fn symbol(&self) -> &Symbol {
&self.symbol
}
pub fn depth_limit(&self) -> Option<usize> {
self.depth_limit
}
pub fn updates_applied(&self) -> u64 {
self.updates_applied
}
pub fn last_stamps(&self) -> Option<Timestamps> {
self.last_stamps
}
pub fn is_empty(&self) -> bool {
self.bids.is_empty() && self.asks.is_empty()
}
pub fn level_count(&self, side: Side) -> usize {
self.side(side).len()
}
fn side(&self, side: Side) -> &BTreeMap<Fixed, Fixed> {
match side {
Side::Bid => &self.bids,
Side::Ask => &self.asks,
}
}
fn side_mut(&mut self, side: Side) -> &mut BTreeMap<Fixed, Fixed> {
match side {
Side::Bid => &mut self.bids,
Side::Ask => &mut self.asks,
}
}
pub fn best_bid(&self) -> Option<(Fixed, Fixed)> {
self.bids.iter().next_back().map(|(p, q)| (*p, *q))
}
pub fn best_ask(&self) -> Option<(Fixed, Fixed)> {
self.asks.iter().next().map(|(p, q)| (*p, *q))
}
pub fn spread(&self) -> Option<Fixed> {
match (self.best_bid(), self.best_ask()) {
(Some((b, _)), Some((a, _))) => a.checked_sub(b),
_ => None,
}
}
pub fn qty_at(&self, side: Side, price: Fixed) -> Option<Fixed> {
self.side(side).get(&price).copied()
}
pub fn top(&self, side: Side, n: usize) -> Vec<(Fixed, Fixed)> {
match side {
Side::Bid => self
.bids
.iter()
.rev()
.take(n)
.map(|(p, q)| (*p, *q))
.collect(),
Side::Ask => self.asks.iter().take(n).map(|(p, q)| (*p, *q)).collect(),
}
}
pub fn reset_from_snapshot(&mut self, snapshot: &BookSnapshot) -> ApplyOutcome {
self.bids.clear();
self.asks.clear();
self.updates_applied = 0;
let mut outcome = ApplyOutcome::default();
for (price, qty) in &snapshot.bids {
self.insert_checked(Side::Bid, *price, *qty, &mut outcome);
}
for (price, qty) in &snapshot.asks {
self.insert_checked(Side::Ask, *price, *qty, &mut outcome);
}
self.truncate_to_depth(&mut outcome);
self.check_cross(&mut outcome);
self.last_stamps = Some(snapshot.stamps);
outcome
}
pub fn apply_delta(&mut self, delta: &BookDelta) -> ApplyOutcome {
let mut outcome = ApplyOutcome::default();
for change in &delta.changes {
self.apply_change(*change, &mut outcome);
}
self.truncate_to_depth(&mut outcome);
self.check_cross(&mut outcome);
self.last_stamps = Some(delta.stamps);
self.updates_applied += 1;
outcome
}
pub fn apply_change(&mut self, change: LevelChange, outcome: &mut ApplyOutcome) {
if change.qty.is_negative() {
outcome.anomalies.push(BookAnomaly::NegativeQty {
side: change.side,
price: change.price,
qty: change.qty,
});
return;
}
if change.is_removal() {
if self.side_mut(change.side).remove(&change.price).is_some() {
outcome.removed += 1;
} else {
outcome.anomalies.push(BookAnomaly::RemovedMissingLevel {
side: change.side,
price: change.price,
});
}
} else {
self.side_mut(change.side).insert(change.price, change.qty);
outcome.applied += 1;
}
}
fn insert_checked(&mut self, side: Side, price: Fixed, qty: Fixed, outcome: &mut ApplyOutcome) {
if qty.is_negative() {
outcome
.anomalies
.push(BookAnomaly::NegativeQty { side, price, qty });
return;
}
if qty.is_zero() {
return;
}
self.side_mut(side).insert(price, qty);
outcome.applied += 1;
}
fn truncate_to_depth(&mut self, outcome: &mut ApplyOutcome) {
let Some(limit) = self.depth_limit else {
return;
};
while self.bids.len() > limit {
if let Some((&price, _)) = self.bids.iter().next() {
self.bids.remove(&price);
outcome.truncated += 1;
}
}
while self.asks.len() > limit {
if let Some((&price, _)) = self.asks.iter().next_back() {
self.asks.remove(&price);
outcome.truncated += 1;
}
}
}
fn check_cross(&self, outcome: &mut ApplyOutcome) {
if let (Some((bid, _)), Some((ask, _))) = (self.best_bid(), self.best_ask()) {
if bid > ask {
outcome.anomalies.push(BookAnomaly::Crossed {
best_bid: bid,
best_ask: ask,
});
} else if bid == ask {
outcome.anomalies.push(BookAnomaly::Locked { price: bid });
}
}
}
pub fn is_crossed(&self) -> bool {
matches!(
(self.best_bid(), self.best_ask()),
(Some((b, _)), Some((a, _))) if b > a
)
}
pub fn digest(&self) -> u32 {
checksum::book_digest(self)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::clock::Stamp;
fn f(s: &str) -> Fixed {
Fixed::from_decimal_str(s).unwrap()
}
fn sym() -> Symbol {
Symbol::new("BTC", "USD")
}
fn stamps() -> Timestamps {
Timestamps::recv_only(Stamp {
mono_nanos: 1,
wall_nanos: 1,
})
}
fn delta(changes: Vec<LevelChange>) -> BookDelta {
BookDelta {
symbol: sym(),
changes,
seq: None,
checksum: None,
stamps: stamps(),
prev_seq: None,
first_seq: None,
}
}
fn seeded() -> L2Book {
let mut book = L2Book::new(sym());
let snap = BookSnapshot {
symbol: sym(),
bids: vec![(f("99"), f("1")), (f("98"), f("2")), (f("97"), f("3"))],
asks: vec![(f("101"), f("1")), (f("102"), f("2")), (f("103"), f("3"))],
seq: Some(10),
checksum: None,
stamps: stamps(),
};
let outcome = book.reset_from_snapshot(&snap);
assert!(outcome.is_clean(), "{outcome:?}");
book
}
#[test]
fn best_prices_come_from_the_right_end_of_each_side() {
let book = seeded();
assert_eq!(book.best_bid(), Some((f("99"), f("1"))));
assert_eq!(book.best_ask(), Some((f("101"), f("1"))));
assert_eq!(book.spread(), Some(f("2")));
}
#[test]
fn top_n_is_ordered_best_first_on_both_sides() {
let book = seeded();
assert_eq!(
book.top(Side::Bid, 2),
vec![(f("99"), f("1")), (f("98"), f("2"))]
);
assert_eq!(
book.top(Side::Ask, 2),
vec![(f("101"), f("1")), (f("102"), f("2"))]
);
assert_eq!(book.top(Side::Bid, 99).len(), 3);
}
#[test]
fn zero_quantity_removes_a_level() {
let mut book = seeded();
let out = book.apply_delta(&delta(vec![LevelChange::new(Side::Bid, f("99"), f("0"))]));
assert_eq!(out.removed, 1);
assert!(out.is_clean(), "{out:?}");
assert_eq!(book.best_bid(), Some((f("98"), f("2"))));
}
#[test]
fn deleting_an_absent_level_is_flagged_not_ignored() {
let mut book = seeded();
let out = book.apply_delta(&delta(vec![LevelChange::new(Side::Bid, f("50"), f("0"))]));
assert_eq!(
out.anomalies,
vec![BookAnomaly::RemovedMissingLevel {
side: Side::Bid,
price: f("50")
}]
);
assert!(out.corrupted());
}
#[test]
fn crossed_book_is_always_flagged() {
let mut book = seeded();
let out = book.apply_delta(&delta(vec![LevelChange::new(Side::Bid, f("105"), f("1"))]));
assert_eq!(
out.anomalies,
vec![BookAnomaly::Crossed {
best_bid: f("105"),
best_ask: f("101")
}]
);
assert!(book.is_crossed());
}
#[test]
fn locked_book_is_reported_separately_from_crossed() {
let mut book = seeded();
let out = book.apply_delta(&delta(vec![LevelChange::new(Side::Bid, f("101"), f("1"))]));
assert_eq!(out.anomalies, vec![BookAnomaly::Locked { price: f("101") }]);
assert!(!book.is_crossed());
assert!(!out.corrupted(), "a locked book is unusual, not corrupt");
}
#[test]
fn a_batch_that_moves_both_sides_is_not_transiently_flagged() {
let mut book = seeded();
let out = book.apply_delta(&delta(vec![
LevelChange::new(Side::Bid, f("104"), f("1")),
LevelChange::new(Side::Ask, f("101"), f("0")),
LevelChange::new(Side::Ask, f("102"), f("0")),
LevelChange::new(Side::Ask, f("103"), f("0")),
LevelChange::new(Side::Ask, f("106"), f("1")),
]));
assert!(out.is_clean(), "{out:?}");
assert_eq!(book.best_bid(), Some((f("104"), f("1"))));
assert_eq!(book.best_ask(), Some((f("106"), f("1"))));
}
#[test]
fn negative_quantity_is_rejected_without_touching_the_book() {
let mut book = seeded();
let out = book.apply_delta(&delta(vec![LevelChange::new(Side::Bid, f("99"), f("-1"))]));
assert!(matches!(
out.anomalies.as_slice(),
[BookAnomaly::NegativeQty { .. }]
));
assert_eq!(book.qty_at(Side::Bid, f("99")), Some(f("1")));
}
#[test]
fn depth_limited_book_truncates_the_worst_levels_on_each_side() {
let mut book = L2Book::with_depth_limit(sym(), 2);
let out = book.reset_from_snapshot(&BookSnapshot {
symbol: sym(),
bids: vec![(f("99"), f("1")), (f("98"), f("2")), (f("97"), f("3"))],
asks: vec![(f("101"), f("1")), (f("102"), f("2")), (f("103"), f("3"))],
seq: None,
checksum: None,
stamps: stamps(),
});
assert_eq!(out.truncated, 2);
assert_eq!(book.level_count(Side::Bid), 2);
assert_eq!(book.level_count(Side::Ask), 2);
assert_eq!(book.qty_at(Side::Bid, f("97")), None);
assert_eq!(book.qty_at(Side::Ask, f("103")), None);
assert_eq!(book.best_bid(), Some((f("99"), f("1"))));
}
#[test]
fn a_new_best_level_pushes_the_worst_one_out_of_the_window() {
let mut book = L2Book::with_depth_limit(sym(), 2);
book.reset_from_snapshot(&BookSnapshot {
symbol: sym(),
bids: vec![(f("99"), f("1")), (f("98"), f("2"))],
asks: vec![(f("101"), f("1")), (f("102"), f("2"))],
seq: None,
checksum: None,
stamps: stamps(),
});
let out = book.apply_delta(&delta(vec![LevelChange::new(Side::Bid, f("99.5"), f("4"))]));
assert_eq!(out.truncated, 1);
assert_eq!(
book.top(Side::Bid, 5),
vec![(f("99.5"), f("4")), (f("99"), f("1"))]
);
}
#[test]
fn snapshot_reset_discards_prior_state_entirely() {
let mut book = seeded();
book.apply_delta(&delta(vec![LevelChange::new(Side::Bid, f("1"), f("9"))]));
book.reset_from_snapshot(&BookSnapshot {
symbol: sym(),
bids: vec![(f("10"), f("1"))],
asks: vec![(f("11"), f("1"))],
seq: Some(99),
checksum: None,
stamps: stamps(),
});
assert_eq!(book.level_count(Side::Bid), 1);
assert_eq!(book.qty_at(Side::Bid, f("1")), None);
assert_eq!(book.updates_applied(), 0);
}
#[test]
fn identical_message_orders_give_identical_digests() {
let a = seeded();
let b = seeded();
assert_eq!(a.digest(), b.digest());
let mut c = seeded();
c.apply_delta(&delta(vec![LevelChange::new(Side::Bid, f("99"), f("5"))]));
assert_ne!(a.digest(), c.digest());
}
}