Matching engine, Rust
Shadowbook
A price-time priority matching engine for a single instrument, written in Rust with nothing allocating on the hot path. Resting orders live in intrusive lists indexed by a flat price array, so cancel and amend are constant time once the order id resolves. Correctness is not asserted, it is differentially fuzzed: the same random order flow drives both this engine and a deliberately naive reference model, and every trade and every book state has to match.
The engine
A single instrument, price-time priority, limit and market orders with cancel and amend. Resting orders are held in intrusive doubly linked lists, one per price level, and the levels themselves sit in a flat array indexed by ticks from a fixed reference price. That trades memory for the absence of a tree walk on every operation.
Order ids resolve through an open addressing table to a raw pointer into the arena, so cancelling an order in the middle of a deep queue does not touch the level above it. Nothing on the hot path allocates. The arena is sized up front and a run that would exceed it fails loudly at startup rather than quietly at the worst moment.
The adversary
The reference model is intentionally slow and obviously correct: a sorted vector per side, rebuilt whenever it is touched, written so a reader can check it against the spec by eye. It exists to disagree with the fast engine.
The fuzzer generates order flow, feeds the identical stream to both, and compares the full trade sequence and the complete book state after every single operation, not just at the end. A divergence is minimised down to the shortest reproducing sequence and written out as a seed. Every seed that has ever failed stays in the corpus and runs on every build afterwards.
What it cost
The first divergence took four hours to find and twenty minutes to fix. It was an amend that changed quantity downward, which should hold queue position, and did not, because the level bookkeeping updated the aggregate before the list. That bug is invisible to unit tests written by the person who wrote the bug.