Designing a Matching Engine in Rust: Price-Time Priority Without GC Pauses

A spot exchange matching engine has a narrow job. It takes an ordered stream of commands - new order, cancel, replace - applies them to an order book under price-time priority, and emits an ordered stream of events: trades, book updates, rejects, acknowledgements.

Everything hard about it comes from three constraints stacked on top of that job: the result must be identical on every replay of the same input, the remainder of a partially filled order must keep its place in the queue, and the latency tail must not move when a burst arrives.

The order book is a sorted index of price levels over FIFO queues

The book is two sides, each a price-ordered collection of levels. A level is not a number - it is a queue of resting orders at that price, in arrival order. Matching touches the best level constantly and the deep levels rarely, so the structure is chosen for that access pattern rather than for elegance.

• Prices are integers in ticks, never floating point - a tick is the unit of the instrument, and comparison and arithmetic on integers are exact
• Each side keeps its levels in price order, with the best price reachable without a search - the top of book is read on every single command
• A level holds a FIFO queue of resting orders, plus the aggregated resting quantity, so the aggregate does not have to be recomputed by walking the queue
• Orders are held in a preallocated slab and referenced by index handles, and the queue is intrusive: the next and previous links live inside the order record itself
• A separate map from client order id to slab handle makes cancel and replace a direct lookup, so a cancel never scans the book
• Removal from a queue is by handle, not by search - a cancel of a deep resting order costs the same as a cancel at the top of book

The consequence of intrusive queues and index handles is that a resting order never moves in memory while it lives. Its queue position is a property of its links, not of where it happens to sit, which is what makes partial fills cheap later on.

Price-time priority is a loop over levels, then over a queue

An incoming aggressive order walks the opposite side from the best price inward. At each level it walks the FIFO queue from the front. It stops when the level price is no longer acceptable to the incoming order or when the incoming quantity reaches zero.

• Take the best opposite level; if its price does not cross the incoming limit price, stop
• Take the front order of that level queue - it is the oldest at that price, and time priority means it fills first
• The traded quantity is the smaller of the two remaining quantities; the trade price is the resting order price, because the resting order set the terms
• Decrement both remainders, emit the trade event, and decrement the level aggregate
• If the resting order remainder reaches zero, unlink it from the queue and return its slab slot; if the level becomes empty, remove the level
• Repeat until the incoming quantity is zero or no acceptable level remains

Order type semantics are decisions taken at the boundary of this loop, not inside it. Immediate-or-cancel drops the remainder instead of resting it. Fill-or-kill runs a dry pass first and either executes whole or rejects. Post-only rejects if the order would cross on arrival. Keeping these outside the loop means the loop stays the only place where book state changes.

Self-trade prevention, minimum quantities, and tick and lot validation belong before the loop as well. An order that reaches matching has already been proven well formed, so the loop has no error branches to slow it down or to disagree about.

Determinism is what makes the tail predictable, and allocation is what breaks it

Average latency is rarely the problem. The problem is the worst observation during a burst, which is when the engine matters most and when a stop-the-world pause is most likely to land. Under a managed runtime with a garbage collector, that pause is scheduled by the collector rather than by you, and it lands in the middle of the burst that produced the garbage.

Manual allocation is a smaller version of the same problem. A general purpose allocator can walk free lists, take a lock, or ask the kernel for more memory, and the call that does so is the call that shows up in the tail. The fix is the same in either case: do not allocate on the hot path at all.

• Order records, level records and event buffers come from arenas sized at startup - steady state allocation count on the matching path is zero
• Freed slots return to a free list inside the arena, so a busy instrument recycles the same memory all session
• Structures are fixed shape and fixed size, with capacity limits enforced as a rejection rather than as a growth event
• Outbound events are written into a preallocated ring buffer that another thread drains - the matching thread never blocks on a consumer
• The matching thread is a single writer over the book, so there is no lock on book state and no ordering ambiguity to resolve
• Inputs are sequenced before they reach the engine, and the sequence number, not the arrival time, decides order

An engine is deterministic when the same input sequence produces the same output sequence, byte for byte, on a different machine and a year later. Anything that reads wall clock time, thread scheduling or hash iteration order inside the matching path breaks that property.

Timestamps are therefore an input, not something the engine reads for itself. The sequencer stamps a command when it accepts it, and the matching loop treats the stamp as data. Randomness, if any is needed, comes from a seeded generator whose seed is part of the journal.

The journal is the engine state, and the book is a cache of it

Recovery is not a feature bolted on after matching works. The engine writes an append-only journal of accepted commands in sequence order, and the in-memory book is nothing more than the result of folding that journal. Rebuilding after a crash means replaying it.

• A command is journaled and durable before it is matched, so an accepted order cannot be lost by a crash between acknowledgement and execution
• The journal is the input sequence, not the output - outputs are derived, and re-deriving them is exactly what replay does
• Periodic snapshots of the book carry the sequence number they were taken at, so recovery loads a snapshot and replays only the tail of the journal
• Snapshot and replay agreement is checked rather than assumed: replaying from the previous snapshot must reproduce the next one
• The event stream carries the same sequence numbers, so downstream consumers - risk, settlement, market data - can be resumed from a known point instead of resynchronised by hand

The engine writes the journal, but durability is a property of the storage path and of how many machines have the record before the acknowledgement goes out. That is a replication and hardware decision, and it is where recovery time is actually won or lost.

Testing is deterministic replay plus invariants that must always hold

Determinism is what makes the engine testable. Because the same input gives the same output, a captured session is a regression test, and a failure found once can be reproduced exactly instead of chased.

• Replay harness: feed a recorded command sequence, compare the emitted event stream against the stored one, and fail on the first divergence with the sequence number
• Invariant checks after every command in test builds - queues sorted by arrival, level aggregates equal to the sum of their queue, no crossed book, total quantity conserved across every trade
• Property based tests that generate random but well formed command sequences and assert the invariants rather than specific outcomes
• A differential reference model: a slow, obviously correct implementation with naive data structures, run against the same input, with any disagreement treated as a bug in the fast one
• Fuzzing at the decoder boundary, where malformed input arrives from outside and where a panic would take the matching thread down
• Latency measurement under the burst shape that worries you, recording the distribution rather than an average, since the tail is the number that decides the design

What Rust gives you here, and what it does not

Rust removes a category of problem rather than making the loop faster by itself. There is no garbage collector, so no pause is scheduled behind your back. Ownership makes the single-writer discipline something the compiler enforces instead of something a code review has to notice. Slab handles and intrusive links, which are error prone in a language without lifetimes, are checkable here. Panics on integer overflow in debug builds catch a class of bug that silently corrupts a book.

The honest boundary is that most of what determines tail latency is not the language:

• Kernel scheduling, interrupt handling, CPU pinning and power management move the tail more than the matching code does
• Network interface, kernel bypass or its absence, and the physical path to the venue set a floor the engine cannot go below
• Serialisation and the wire protocol at the boundary are frequently the dominant cost, not the match itself
• Matching semantics, order types, fee and rebate rules and market phases are business decisions - a wrong rule implemented quickly is still wrong
• Risk checks, position limits and the settlement path live outside the engine and have their own latency and their own failure modes
• Operations - deployment, monitoring, the runbook for a failed replay - decide whether the guarantees survive contact with a production incident

Rust also costs something. The borrow checker slows down the first weeks of a design that is still moving, the ecosystem for exchange specific protocols is thinner than in older languages, and unsafe blocks around lock-free structures need the same review discipline as the equivalent code anywhere else. Choosing it is a decision about the latency tail and about memory safety in a single-writer core, not a decision about developer comfort.

amBrain has built trading infrastructure in Yerevan, Armenia since 2019, with hot paths in Rust - market data delivered in under 5 ms, pre-trade risk checks in under 1 ms. If you are designing a matching engine and want to walk through the book structure, the journal format or the replay harness, that conversation is worth having before the first line of the hot path is written.