use std::collections::{BTreeMap, HashMap, VecDeque};
use std::fmt;
use serde::{Deserialize, Serialize};
use crate::book::{BookSnapshot, L2Book};
use crate::clock::{Stamp, Timestamps};
use crate::fixed::Fixed;
use crate::types::{Side, Symbol};
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
pub struct OrderId(pub String);
impl OrderId {
pub fn new(id: impl Into<String>) -> Self {
OrderId(id.into())
}
pub fn as_str(&self) -> &str {
&self.0
}
}
impl fmt::Display for OrderId {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(&self.0)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "lowercase")]
pub enum OrderAction {
Add,
Modify,
Cancel,
Execute,
}
impl OrderAction {
pub const fn as_str(self) -> &'static str {
match self {
OrderAction::Add => "add",
OrderAction::Modify => "modify",
OrderAction::Cancel => "cancel",
OrderAction::Execute => "execute",
}
}
pub const fn removes(self) -> bool {
matches!(self, OrderAction::Cancel | OrderAction::Execute)
}
}
impl fmt::Display for OrderAction {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(self.as_str())
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct OrderEvent {
pub symbol: Symbol,
pub order_id: OrderId,
pub action: OrderAction,
pub side: Side,
pub price: Fixed,
pub qty: Fixed,
pub original_qty: Option<Fixed>,
pub executed_qty: Option<Fixed>,
pub stamps: Timestamps,
pub event_token: Option<u128>,
pub prev_event_token: Option<u128>,
pub size_change_explained: bool,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum QueueCertainty {
Observed,
Seeded,
Unknown,
}
impl QueueCertainty {
pub const fn is_observed(self) -> bool {
matches!(self, QueueCertainty::Observed)
}
pub const fn as_str(self) -> &'static str {
match self {
QueueCertainty::Observed => "observed",
QueueCertainty::Seeded => "seeded",
QueueCertainty::Unknown => "unknown",
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Order {
pub id: OrderId,
pub side: Side,
pub price: Fixed,
pub qty: Fixed,
pub original_qty: Option<Fixed>,
pub executed_qty: Option<Fixed>,
pub arrived: Stamp,
pub certainty: QueueCertainty,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct QueuePosition {
pub index: usize,
pub qty_ahead: Fixed,
pub certainty: QueueCertainty,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum L3Anomaly {
UnknownOrder { id: OrderId, action: OrderAction },
DuplicateAdd { id: OrderId },
PriceMoved { id: OrderId, from: Fixed, to: Fixed },
NegativeQty { id: OrderId, qty: Fixed },
Crossed { best_bid: Fixed, best_ask: Fixed },
}
impl fmt::Display for L3Anomaly {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
L3Anomaly::UnknownOrder { id, action } => {
write!(f, "{action} for unknown order {id}")
}
L3Anomaly::DuplicateAdd { id } => write!(f, "order {id} added twice"),
L3Anomaly::PriceMoved { id, from, to } => {
write!(f, "order {id} moved from {from} to {to}")
}
L3Anomaly::NegativeQty { id, qty } => {
write!(f, "order {id} has negative quantity {qty}")
}
L3Anomaly::Crossed { best_bid, best_ask } => {
write!(f, "crossed book: bid {best_bid} above ask {best_ask}")
}
}
}
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct L3Stats {
pub added: u64,
pub modified: u64,
pub cancelled: u64,
pub executed: u64,
pub unknown_orders: u64,
pub unexplained_size_changes: u64,
pub peak_open_orders: u64,
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct L3Outcome {
pub applied: bool,
pub anomalies: Vec<L3Anomaly>,
pub traded_qty: Option<Fixed>,
}
impl L3Outcome {
pub fn is_clean(&self) -> bool {
self.anomalies.is_empty()
}
}
#[derive(Debug, Clone)]
pub struct L3Book {
symbol: Symbol,
orders: HashMap<OrderId, Order>,
bids: BTreeMap<Fixed, VecDeque<OrderId>>,
asks: BTreeMap<Fixed, VecDeque<OrderId>>,
incomplete: std::collections::HashSet<(Side, Fixed)>,
stats: L3Stats,
}
impl L3Book {
pub fn new(symbol: Symbol) -> Self {
L3Book {
symbol,
orders: HashMap::new(),
bids: BTreeMap::new(),
asks: BTreeMap::new(),
incomplete: std::collections::HashSet::new(),
stats: L3Stats::default(),
}
}
pub fn symbol(&self) -> &Symbol {
&self.symbol
}
pub fn stats(&self) -> L3Stats {
self.stats
}
pub fn open_orders(&self) -> usize {
self.orders.len()
}
pub fn incomplete_levels(&self) -> usize {
self.incomplete.len()
}
pub fn level_is_incomplete(&self, side: Side, price: Fixed) -> bool {
self.incomplete.contains(&(side, price))
}
pub fn order(&self, id: &OrderId) -> Option<&Order> {
self.orders.get(id)
}
pub fn is_empty(&self) -> bool {
self.orders.is_empty()
}
fn levels(&self, side: Side) -> &BTreeMap<Fixed, VecDeque<OrderId>> {
match side {
Side::Bid => &self.bids,
Side::Ask => &self.asks,
}
}
fn levels_mut(&mut self, side: Side) -> &mut BTreeMap<Fixed, VecDeque<OrderId>> {
match side {
Side::Bid => &mut self.bids,
Side::Ask => &mut self.asks,
}
}
pub fn best_bid(&self) -> Option<Fixed> {
self.bids.keys().next_back().copied()
}
pub fn best_ask(&self) -> Option<Fixed> {
self.asks.keys().next().copied()
}
pub fn is_crossed(&self) -> bool {
matches!((self.best_bid(), self.best_ask()), (Some(b), Some(a)) if b > a)
}
pub fn queue_at(&self, side: Side, price: Fixed) -> Vec<&Order> {
self.levels(side)
.get(&price)
.map(|queue| queue.iter().filter_map(|id| self.orders.get(id)).collect())
.unwrap_or_default()
}
pub fn queue_position(&self, id: &OrderId) -> Option<QueuePosition> {
let order = self.orders.get(id)?;
let queue = self.levels(order.side).get(&order.price)?;
let mut qty_ahead = Fixed::ZERO;
let mut certainty = order.certainty;
if self.level_is_incomplete(order.side, order.price) {
certainty = QueueCertainty::Unknown;
}
for (index, ahead) in queue.iter().enumerate() {
if ahead == id {
return Some(QueuePosition {
index,
qty_ahead,
certainty,
});
}
if let Some(other) = self.orders.get(ahead) {
qty_ahead = qty_ahead.checked_add(other.qty).unwrap_or(Fixed::MAX);
if !other.certainty.is_observed() {
certainty = match certainty {
QueueCertainty::Unknown => QueueCertainty::Unknown,
_ => other.certainty,
};
}
}
}
None
}
pub fn seed(
&mut self,
orders: impl IntoIterator<Item = (OrderId, Side, Fixed, Fixed)>,
at: Stamp,
) {
self.orders.clear();
self.bids.clear();
self.asks.clear();
for (id, side, price, qty) in orders {
if qty.is_zero() || qty.is_negative() {
continue;
}
self.levels_mut(side)
.entry(price)
.or_default()
.push_back(id.clone());
self.orders.insert(
id.clone(),
Order {
id,
side,
price,
qty,
original_qty: Some(qty),
executed_qty: None,
arrived: at,
certainty: QueueCertainty::Seeded,
},
);
}
self.stats.peak_open_orders = self.stats.peak_open_orders.max(self.orders.len() as u64);
}
pub fn apply(&mut self, event: &OrderEvent) -> L3Outcome {
let mut outcome = L3Outcome::default();
if !event.size_change_explained {
self.stats.unexplained_size_changes += 1;
}
if event.qty.is_negative() {
outcome.anomalies.push(L3Anomaly::NegativeQty {
id: event.order_id.clone(),
qty: event.qty,
});
return outcome;
}
match event.action {
OrderAction::Add => self.add(event, &mut outcome),
OrderAction::Modify => self.modify(event, &mut outcome),
OrderAction::Cancel | OrderAction::Execute => self.remove(event, &mut outcome),
}
if let (Some(bid), Some(ask)) = (self.best_bid(), self.best_ask())
&& bid > ask
{
outcome.anomalies.push(L3Anomaly::Crossed {
best_bid: bid,
best_ask: ask,
});
}
self.stats.peak_open_orders = self.stats.peak_open_orders.max(self.orders.len() as u64);
outcome
}
fn add(&mut self, event: &OrderEvent, outcome: &mut L3Outcome) {
if self.orders.contains_key(&event.order_id) {
outcome.anomalies.push(L3Anomaly::DuplicateAdd {
id: event.order_id.clone(),
});
return;
}
if event.qty.is_zero() {
return;
}
self.levels_mut(event.side)
.entry(event.price)
.or_default()
.push_back(event.order_id.clone());
self.orders.insert(
event.order_id.clone(),
Order {
id: event.order_id.clone(),
side: event.side,
price: event.price,
qty: event.qty,
original_qty: event.original_qty,
executed_qty: event.executed_qty,
arrived: event.stamps.recv,
certainty: QueueCertainty::Observed,
},
);
self.stats.added += 1;
outcome.applied = true;
}
fn modify(&mut self, event: &OrderEvent, outcome: &mut L3Outcome) {
let Some(existing) = self.orders.get(&event.order_id).cloned() else {
outcome.anomalies.push(L3Anomaly::UnknownOrder {
id: event.order_id.clone(),
action: event.action,
});
self.stats.unknown_orders += 1;
self.incomplete.insert((event.side, event.price));
return;
};
if existing.price != event.price {
outcome.anomalies.push(L3Anomaly::PriceMoved {
id: event.order_id.clone(),
from: existing.price,
to: event.price,
});
self.detach(&existing);
self.levels_mut(event.side)
.entry(event.price)
.or_default()
.push_back(event.order_id.clone());
} else if event.qty > existing.qty {
self.detach(&existing);
self.levels_mut(event.side)
.entry(event.price)
.or_default()
.push_back(event.order_id.clone());
if let Some(order) = self.orders.get_mut(&event.order_id) {
order.certainty = QueueCertainty::Unknown;
}
}
if let Some(order) = self.orders.get_mut(&event.order_id) {
order.price = event.price;
order.side = event.side;
order.qty = event.qty;
order.executed_qty = event.executed_qty.or(order.executed_qty);
order.original_qty = order.original_qty.or(event.original_qty);
}
self.stats.modified += 1;
outcome.applied = true;
let filled = traded_since(&existing, event);
if !filled.is_zero() {
outcome.traded_qty = Some(filled);
}
if event.qty.is_zero() {
let order = self.orders.get(&event.order_id).cloned();
if let Some(order) = order {
self.detach(&order);
self.orders.remove(&event.order_id);
}
}
}
fn remove(&mut self, event: &OrderEvent, outcome: &mut L3Outcome) {
let Some(existing) = self.orders.remove(&event.order_id) else {
outcome.anomalies.push(L3Anomaly::UnknownOrder {
id: event.order_id.clone(),
action: event.action,
});
self.stats.unknown_orders += 1;
self.incomplete.insert((event.side, event.price));
return;
};
self.detach(&existing);
match event.action {
OrderAction::Execute => {
self.stats.executed += 1;
outcome.traded_qty = Some(traded_since(&existing, event));
}
_ => self.stats.cancelled += 1,
}
outcome.applied = true;
}
}
fn traded_since(existing: &Order, event: &OrderEvent) -> Fixed {
match (event.executed_qty, existing.executed_qty) {
(Some(now), Some(before)) => now
.checked_sub(before)
.unwrap_or(Fixed::ZERO)
.max(Fixed::ZERO),
(Some(now), None) => now.min(existing.qty),
(None, _) if event.action == OrderAction::Execute => existing.qty,
(None, _) => Fixed::ZERO,
}
}
impl L3Book {
fn detach(&mut self, order: &Order) {
let levels = self.levels_mut(order.side);
if let Some(queue) = levels.get_mut(&order.price) {
queue.retain(|id| id != &order.id);
if queue.is_empty() {
levels.remove(&order.price);
self.incomplete.remove(&(order.side, order.price));
}
}
}
pub fn prune_crossed_seeded(&mut self) -> usize {
let mut pruned = 0;
loop {
let (Some(bid), Some(ask)) = (self.best_bid(), self.best_ask()) else {
return pruned;
};
if bid <= ask {
return pruned;
}
let bid_seeded = self.level_is_seeded(Side::Bid, bid);
let ask_seeded = self.level_is_seeded(Side::Ask, ask);
let side = match (bid_seeded, ask_seeded) {
(true, _) => Side::Bid,
(false, true) => Side::Ask,
(false, false) => return pruned,
};
let price = if side == Side::Bid { bid } else { ask };
let ids: Vec<OrderId> = self
.levels(side)
.get(&price)
.map(|q| q.iter().cloned().collect())
.unwrap_or_default();
for id in ids {
if let Some(order) = self.orders.get(&id).cloned()
&& order.certainty == QueueCertainty::Seeded
{
self.orders.remove(&id);
self.detach(&order);
pruned += 1;
}
}
if self.levels(side).contains_key(&price) {
return pruned;
}
}
}
fn level_is_seeded(&self, side: Side, price: Fixed) -> bool {
self.levels(side)
.get(&price)
.map(|q| {
q.iter().any(|id| {
self.orders
.get(id)
.map(|o| o.certainty == QueueCertainty::Seeded)
.unwrap_or(false)
})
})
.unwrap_or(false)
}
pub fn to_l2(&self, at: Timestamps) -> L2Book {
let mut book = L2Book::new(self.symbol.clone());
let aggregate = |levels: &BTreeMap<Fixed, VecDeque<OrderId>>,
orders: &HashMap<OrderId, Order>| {
levels
.iter()
.filter_map(|(price, queue)| {
let total = queue
.iter()
.filter_map(|id| orders.get(id))
.fold(Fixed::ZERO, |acc, o| {
acc.checked_add(o.qty).unwrap_or(Fixed::MAX)
});
(!total.is_zero()).then_some((*price, total))
})
.collect::<Vec<_>>()
};
book.reset_from_snapshot(&BookSnapshot {
symbol: self.symbol.clone(),
bids: aggregate(&self.bids, &self.orders),
asks: aggregate(&self.asks, &self.orders),
seq: None,
checksum: None,
stamps: at,
});
book
}
}
#[cfg(test)]
mod tests {
use super::*;
fn f(s: &str) -> Fixed {
Fixed::from_decimal_str(s).unwrap()
}
fn sym() -> Symbol {
Symbol::new("BTC", "USD")
}
fn at(n: u64) -> Stamp {
Stamp {
mono_nanos: n,
wall_nanos: n as i64,
}
}
fn event(
id: &str,
action: OrderAction,
side: Side,
price: &str,
qty: &str,
n: u64,
) -> OrderEvent {
OrderEvent {
symbol: sym(),
order_id: OrderId::new(id),
action,
side,
price: f(price),
qty: f(qty),
original_qty: Some(f(qty)),
executed_qty: None,
stamps: Timestamps::recv_only(at(n)),
event_token: Some(n as u128),
prev_event_token: (n > 0).then_some(n as u128 - 1),
size_change_explained: true,
}
}
fn seeded_book() -> L3Book {
let mut book = L3Book::new(sym());
book.apply(&event("a", OrderAction::Add, Side::Bid, "100", "1", 1));
book.apply(&event("b", OrderAction::Add, Side::Bid, "100", "2", 2));
book.apply(&event("c", OrderAction::Add, Side::Bid, "100", "3", 3));
book.apply(&event("d", OrderAction::Add, Side::Ask, "101", "1", 4));
book
}
#[test]
fn orders_queue_in_the_order_they_arrived() {
let book = seeded_book();
let queue: Vec<&str> = book
.queue_at(Side::Bid, f("100"))
.iter()
.map(|o| o.id.as_str())
.collect();
assert_eq!(queue, vec!["a", "b", "c"]);
}
#[test]
fn queue_position_counts_the_quantity_that_must_trade_first() {
let book = seeded_book();
let pos = book.queue_position(&OrderId::new("c")).unwrap();
assert_eq!(pos.index, 2);
assert_eq!(pos.qty_ahead, f("3"));
assert_eq!(pos.certainty, QueueCertainty::Observed);
let front = book.queue_position(&OrderId::new("a")).unwrap();
assert_eq!(front.index, 0);
assert_eq!(front.qty_ahead, Fixed::ZERO);
}
#[test]
fn removing_an_order_promotes_everything_behind_it() {
let mut book = seeded_book();
book.apply(&event("a", OrderAction::Execute, Side::Bid, "100", "0", 5));
let pos = book.queue_position(&OrderId::new("c")).unwrap();
assert_eq!(pos.index, 1);
assert_eq!(pos.qty_ahead, f("2"));
assert_eq!(book.stats().executed, 1);
}
#[test]
fn a_seeded_order_never_claims_an_observed_position() {
let mut book = L3Book::new(sym());
book.seed(
[
(OrderId::new("x"), Side::Bid, f("100"), f("1")),
(OrderId::new("y"), Side::Bid, f("100"), f("2")),
],
at(0),
);
let pos = book.queue_position(&OrderId::new("y")).unwrap();
assert_eq!(pos.index, 1);
assert_eq!(pos.certainty, QueueCertainty::Seeded);
assert!(!pos.certainty.is_observed());
}
#[test]
fn an_observed_order_behind_a_seeded_one_inherits_the_weaker_certainty() {
let mut book = L3Book::new(sym());
book.seed([(OrderId::new("old"), Side::Bid, f("100"), f("5"))], at(0));
book.apply(&event("new", OrderAction::Add, Side::Bid, "100", "1", 1));
let new = book.queue_position(&OrderId::new("new")).unwrap();
assert_eq!(new.index, 1);
assert_eq!(new.qty_ahead, f("5"));
assert_eq!(
new.certainty,
QueueCertainty::Seeded,
"its own arrival was observed, but what is ahead of it was not"
);
}
#[test]
fn raising_size_forfeits_the_position_and_says_so() {
let mut book = seeded_book();
let mut grow = event("a", OrderAction::Modify, Side::Bid, "100", "5", 5);
grow.original_qty = Some(f("1"));
book.apply(&grow);
let queue: Vec<&str> = book
.queue_at(Side::Bid, f("100"))
.iter()
.map(|o| o.id.as_str())
.collect();
assert_eq!(queue, vec!["b", "c", "a"], "a must lose its place");
let pos = book.queue_position(&OrderId::new("a")).unwrap();
assert_eq!(
pos.certainty,
QueueCertainty::Unknown,
"where a re-sized order lands is not something the feed says"
);
}
#[test]
fn shrinking_an_order_keeps_its_place() {
let mut book = seeded_book();
let shrink = event("b", OrderAction::Modify, Side::Bid, "100", "1", 5);
book.apply(&shrink);
let queue: Vec<&str> = book
.queue_at(Side::Bid, f("100"))
.iter()
.map(|o| o.id.as_str())
.collect();
assert_eq!(queue, vec!["a", "b", "c"]);
let pos = book.queue_position(&OrderId::new("b")).unwrap();
assert_eq!(pos.certainty, QueueCertainty::Observed);
assert_eq!(book.order(&OrderId::new("b")).unwrap().qty, f("1"));
}
#[test]
fn an_event_for_an_unknown_order_is_flagged_not_ignored() {
let mut book = L3Book::new(sym());
let outcome = book.apply(&event(
"ghost",
OrderAction::Cancel,
Side::Bid,
"100",
"0",
1,
));
assert_eq!(
outcome.anomalies,
vec![L3Anomaly::UnknownOrder {
id: OrderId::new("ghost"),
action: OrderAction::Cancel
}]
);
assert_eq!(book.stats().unknown_orders, 1);
assert!(book.is_empty());
}
#[test]
fn adding_the_same_order_twice_is_flagged() {
let mut book = seeded_book();
let outcome = book.apply(&event("a", OrderAction::Add, Side::Bid, "100", "1", 9));
assert_eq!(
outcome.anomalies,
vec![L3Anomaly::DuplicateAdd {
id: OrderId::new("a")
}]
);
assert_eq!(book.queue_at(Side::Bid, f("100")).len(), 3);
}
#[test]
fn a_price_change_moves_the_order_and_is_flagged() {
let mut book = seeded_book();
let outcome = book.apply(&event("a", OrderAction::Modify, Side::Bid, "99", "1", 5));
assert!(matches!(
outcome.anomalies.as_slice(),
[L3Anomaly::PriceMoved { .. }]
));
assert_eq!(book.queue_at(Side::Bid, f("100")).len(), 2);
assert_eq!(book.queue_at(Side::Bid, f("99")).len(), 1);
}
#[test]
fn a_crossed_book_is_flagged() {
let mut book = seeded_book();
let outcome = book.apply(&event("z", OrderAction::Add, Side::Bid, "102", "1", 6));
assert!(
outcome
.anomalies
.iter()
.any(|a| matches!(a, L3Anomaly::Crossed { .. }))
);
assert!(book.is_crossed());
}
#[test]
fn the_l2_view_aggregates_the_queue() {
let book = seeded_book();
let l2 = book.to_l2(Timestamps::recv_only(at(9)));
assert_eq!(l2.best_bid(), Some((f("100"), f("6"))));
assert_eq!(l2.best_ask(), Some((f("101"), f("1"))));
assert_eq!(l2.level_count(Side::Bid), 1);
}
#[test]
fn the_l2_view_tracks_removals() {
let mut book = seeded_book();
book.apply(&event("a", OrderAction::Cancel, Side::Bid, "100", "0", 5));
book.apply(&event("d", OrderAction::Cancel, Side::Ask, "101", "0", 6));
let l2 = book.to_l2(Timestamps::recv_only(at(9)));
assert_eq!(l2.best_bid(), Some((f("100"), f("5"))));
assert_eq!(l2.best_ask(), None, "the only ask left the book");
}
#[test]
fn an_empty_level_disappears_rather_than_lingering_at_zero() {
let mut book = seeded_book();
for id in ["a", "b", "c"] {
book.apply(&event(id, OrderAction::Cancel, Side::Bid, "100", "0", 7));
}
assert_eq!(book.best_bid(), None);
assert!(book.queue_at(Side::Bid, f("100")).is_empty());
assert_eq!(
book.to_l2(Timestamps::recv_only(at(9)))
.level_count(Side::Bid),
0
);
}
#[test]
fn unexplained_size_changes_are_counted() {
let mut book = seeded_book();
let mut odd = event("b", OrderAction::Modify, Side::Bid, "100", "1", 5);
odd.size_change_explained = false;
book.apply(&odd);
assert_eq!(book.stats().unexplained_size_changes, 1);
}
#[test]
fn a_modify_to_zero_removes_the_order() {
let mut book = seeded_book();
book.apply(&event("b", OrderAction::Modify, Side::Bid, "100", "0", 5));
assert!(book.order(&OrderId::new("b")).is_none());
let queue: Vec<&str> = book
.queue_at(Side::Bid, f("100"))
.iter()
.map(|o| o.id.as_str())
.collect();
assert_eq!(queue, vec!["a", "c"]);
}
#[test]
fn peak_open_orders_is_tracked_for_the_load_report() {
let mut book = seeded_book();
assert_eq!(book.stats().peak_open_orders, 4);
for id in ["a", "b", "c", "d"] {
book.apply(&event(id, OrderAction::Cancel, Side::Bid, "100", "0", 8));
}
assert_eq!(book.stats().peak_open_orders, 4, "peak, not current");
}
}