matchbox-rs

A single-instrument limit-order-book matching engine in safe Rust — the core data-structure-and-invariants problem at the heart of every exchange. Zero dependencies, zero unsafe, property- and fuzz-tested, with O(1) cancel.

This is a faithful port of my C++ engine matchbox, rebuilt in idiomatic Rust to show the same systems discipline under the borrow checker.

N 1 S LIMIT 100 10      ->  ACCEPT #1 SELL rest 10 @ 100
N 2 B LIMIT 101 4       ->  TRADE  #2 x #1 4 @ 100      (price-time priority)
N 3 B LIMIT  99 5       ->  ACCEPT #3 BUY  rest 5 @ 99
C 1                     ->  CANCEL #1 removed 6

What it does

• Price-time priority. Incoming orders match resting orders best-price first, then FIFO within a price level. Executions print at the resting (passive) order's price, so the aggressor gets price improvement.
• Order types: LIMIT (rest the remainder), MARKET (cross at any price, drop the remainder), IOC (immediate-or-cancel), FOK (fill-or-kill: all at once or reject — pre-checked against available depth).
• Cancel in O(1) via an id → slab node index.
• The book is never left crossed, quantity is conserved, and replay is deterministic — all enforced by tests (below).
• L2 depth snapshots and best-bid/ask queries.
• Events (Accept / Trade / Cancel / Unfilled / Reject) are delivered through an EventSink. It's implemented for () (discard at zero cost) and Vec<Event> (collect), so callers rarely write their own.

Design

Each side is a BTreeMap<Price, Level>, so the best level is the first entry (asks, ascending) or last entry (bids, descending). Within a level, resting orders form an intrusive doubly-linked list over a slab (Vec<Node> plus a free list): an OrderId → slab index map locates a node, and cancelling unlinks it by touching only its neighbours — O(1), with no per-order heap allocation on the hot path. Each level caches its aggregate quantity and order count for O(1) depth and fill-or-kill checks.

submit / cancel are O(log L + f) where L = distinct price levels and f = resting orders consumed by the fill. Prices are integer ticks (i64) — no floating-point money.

src/lib.rs        the engine (OrderBook, Event, matching)
src/bin/mbx.rs    stdin-driven replay/demo driver
src/bin/bench.rs  throughput + latency benchmark

The intrusive slab list is the idiomatic-Rust answer to what the C++ version got from std::list iterators: stable references and O(1) middle-erase, but with indices instead of pointers — so the whole engine is #![forbid(unsafe_code)].

Build & test

Standard Cargo; no third-party crates.

cargo test                       # unit + property tests + doctest
cargo run --release --bin bench  # benchmark
echo 'N 1 S LIMIT 100 10
N 2 B LIMIT 101 4' | cargo run --quiet --bin mbx

CI runs cargo fmt --check, cargo clippy --all-targets -D warnings, cargo test, and a release build on every push.

Tests

The suite covers each order type and the priority rules, plus two properties that catch the subtle bugs:

• Fuzz / invariants — 40k randomized submits & cancels; after every operation it asserts the book is not crossed, that level totals, order counts, the id-index, and the linked-list prev/tail links are all consistent, and that quantity is conserved (resting == accepted − traded − cancelled).
• Deterministic replay — the same input stream always produces an identical execution stream.

Benchmark

$ cargo run --release --bin bench 2000000
  throughput : ~12 M ops/s
  latency    : ~80 ns/op

Measured on an Intel Core i7-13650HX (Windows 11), single-threaded. The workload is a mixed stream — 70% limit submits (resting and crossing against a deep book), 30% cancels — around a tight price band. A couple of caveats, in the spirit of measuring honestly rather than quoting a headline:

• Numbers move ~10% run-to-run with CPU clock/thermal state; the figure above is a median of several runs.
• This is not a head-to-head with the C++ engine's "~8.6M orders/s". That number is pure single-instrument submit throughput on different hardware; this one is a submit+cancel mix. Same algorithms, different workload — so the two aren't directly comparable, and I'm not claiming Rust "beat" C++ here.

Relationship to the C++ matchbox

Same design, same invariants, same test philosophy — re-expressed in Rust: std::map → BTreeMap, std::list + iterators → a slab-backed intrusive list with index handles, virtual EventSink → an EventSink trait, exceptions in check_invariants → a Result<(), String>. The point of the port is to show the C++ systems work carries directly into safe, unsafe-free Rust.

License

MIT — see LICENSE.