View on GitHub
A limit order book matching engine in Rust. Single-writer matcher,
lock-free queues at the boundaries, write-ahead log with byte-exact
replay, machine-verified zero allocation on the hot path.
</section>
Headline numbers
End-to-end on M-series silicon, single matcher thread,
multi-tenant Hub, release build. Each number links to the bench or
test that produced it.
```mermaid
flowchart LR
subgraph gateways["tokio gateway tasks"]
c1[client A reader]
c2[client B reader]
c3[client N reader]
end
mpsc[("MPSC inbox crossbeam ArrayQueue")]
matchermatcher thread single-writer 0 alloc on hot path
subgraph fanout["per-tenant SPSC outbound"]
e1[client A writer]
e2[client B writer]
e3[client N writer]
end
wal[(WAL CRC32C frames fsync-on-commit)]
snap[(snapshot marker + book)]
c1 & c2 & c3 -->|Command| mpsc
mpsc --> matcher
matcher -->|Event| e1
matcher --> e2
matcher --> e3
matcher -.->|append + fsync| wal
wal -.->|periodic| snap
```
Code spotlight
Two pieces of code that capture the project's
flavor: the matcher's pre-acceptance gates, and the lock-free SPSC's
push with its safety proof. Both are from the actual main branch — no
pseudo-code.
Matcher pre-acceptance gates
crates/bourse-core/src/matcher.rs
```rust
// Reject upfront if the kind's precondition fails — mirrors the
// zero-qty / duplicate-id path. No `Accepted` is emitted on reject.
let opposite = order.side.opposite();
match order.kind {
OrderKind::PostOnly { price } => {
let would_cross = match opposite {
Side::Sell => self.book.best_ask()
.is_some_and(|a| a <= price),
Side::Buy => self.book.best_bid()
.is_some_and(|b| b >= price),
};
if would_cross {
out.push(Event::Done { reason: DoneReason::Rejected, /* ... */ });
return;
}
}
OrderKind::Fok { price } => {
// Bounded pre-walk: stops as soon as enough liquidity is
// found at acceptable prices.
let available = self.book.fillable_qty_at(
opposite, price, order.qty,
);
if available < order.qty {
out.push(Event::Done { reason: DoneReason::Rejected, /* ... */ });
return;
}
}
_ => {}
}
```
Lock-free SPSC push
crates/bourse-core/src/spsc.rs
```rust
pub fn try_push(&self, item: T) -> Result<(), T> {
let head = self.head.load(Ordering::Relaxed);
let next = (head + 1) & self.mask;
if next == self.cached_tail.get() {
// Cache says full; pay the cross-core load to refresh.
let real_tail = self.tail.load(Ordering::Acquire);
self.cached_tail.set(real_tail);
if next == real_tail { return Err(item); }
}
// SAFETY: head/next are bounded by mask; this slot is past the
// consumer's tail per the Acquire load above, so the cell is not
// being read concurrently. We have exclusive access to write.
unsafe { (*self.buf[head].get()).write(item); }
// Release publishes the data write to any consumer doing an
// Acquire load of head — that's the happens-before.
self.head.store(next, Ordering::Release);
Ok(())
}
```
The matching engine is single-writer on a dedicated OS thread. Lock-free queues at the boundaries; nothing shared mutable inside the matcher. Performance bottleneck shifts to memory and instructions, not coordination. Scaling out is per-symbol partitioning — not multi-threaded matching.
numerics
Fixed-point i64 prices, no floats.
Floats are non-associative; 0.1 + 0.2 != 0.3. Equality comparisons silently lie, rounding bites at boundaries, and behavior varies across architectures. i64 with 8 decimal digits is exact, deterministic, single-register, and supports saturating arithmetic — no overflow panics.
memory
Caller owns the event buffer.
Matcher::accept(order, &mut Vec<Event>) reuses a caller-owned Vec across calls — zero allocation per call in steady state. A custom GlobalAlloc harness in tests/no_alloc.rs machine-verifies 0 allocs / 1000 trades. Not "I think it doesn't allocate" — counted.
durability
fsync before ack, group-commit when batching.
WAL records are CRC32C-framed, length-prefixed, written through a BufWriter, and fsync'd before the execution report goes back to the client. Group commit batches 256 records under one fsync — 187–245× faster than per-record durability.
memory ordering
Acquire/Release pair, validated by Miri.
The SPSC's correctness rests on a single happens-before relation: producer's Release-store of head synchronizes with consumer's Acquire-load. Hand-walked the argument; each unsafe block has a // SAFETY: proof; Miri runs the unit tests in CI and catches any ordering regression.
format design
Version byte from day 0.
WAL, snapshot, and wire protocol all carry a 1-byte version from the first byte. Cost: 1 byte per record. Benefit: the slice that added wal_seq tagging to the WAL was a one-line code change. Cheap insurance pays out the first time you need it.
Snapshots with atomic temp-then-rename, wal_seq markers
Lock-free SPSC ring (Acquire/Release, Miri-validated in CI)
Lock-free MPSC Hub — one matcher across many TCP connections
Hand-rolled binary wire protocol with version byte and round-trip proptests
tokio TCP server + graceful shutdown (SIGINT / SIGTERM)
Load-gen client with HdrHistogram percentiles (3 sigfig, auto-resize)
bourse-replay recovery binary
Allocation-counting harness — 0 allocs / 1000 crosses on the hot path
WAL group-commit benchmark (187–245× speedup)
tracing instrumentation on I/O boundaries (hot path untouched)
What I learned
Memory ordering isn't intuition.
Walking through the Acquire/Release happens-before argument by hand was the first time I felt I actually understood what the C++20 memory model is doing rather than just citing it. Miri catching ordering bugs locally — before they ever became data races in production — is the strongest tooling lesson.
"Zero alloc on the hot path" needs a meter.
Argued it; didn't prove it for many slices. Eventually built the custom-allocator harness and the gap between "I think this is alloc-free" and "the steady-state cross loop is 0 / 1000" was instructive.
Property tests find real bugs.
The matcher's lifecycle proptest caught two real correctness bugs while it was being written — duplicate-id Done collisions and Book::cancel lying about leaves_qty. Both fixed in the same PR.
Benchmarks lie if you don't define them carefully.
The first TCP load-gen reported p50 = 275 ms because it was a closed-loop measurement double-counting queueing delay. The methodology post walks through what each headline number actually measures and why.
Versioning everything from day 0 is cheap.
WAL, snapshot, and wire protocol each have a version byte from the very first byte. The slice that added wal_seq tagging was a one-line code change because the version byte was already there.
</section>