Designing a Matching Engine: Determinism, Replay and Recovery

A matching engine is the one component of an exchange that cannot be eventually consistent. Every order, cancel and fill has to be applied in exactly one order, and anyone holding a copy of the input stream must be able to reproduce the same book and the same trades. If you get determinism right, replay, recovery, testing and dispute resolution follow almost for free. If you get it wrong, you will spend years patching reconciliation scripts.

This post describes the design we default to when we build trading cores: one single-threaded engine per market, a monotonically increasing sequence number on every input, an append-only log as the source of truth, periodic snapshots, and a recovery path that is nothing more than replaying the log. None of this is novel. What matters is applying it consistently and refusing the shortcuts that look harmless in the first month.

One thread per market, no shared state

The temptation is to make the engine multi-threaded because it will "need to scale". In practice a single core processing a single market with a well-designed order book handles far more messages than most venues ever see, and the cost of locks, contention and non-deterministic interleaving is enormous. We partition by market: each market gets its own engine instance with its own input queue, its own book, its own sequence counter and its own log. Markets never share mutable state. Cross-market concerns such as portfolio margin live in a separate risk service that sits in front of the engine, not inside it.

Inside the engine the rules are strict. No wall-clock reads, no random numbers, no I/O, no floating point in price or quantity arithmetic. Timestamps come in on the message; the engine records them but never branches on them. Prices and sizes are integers scaled to the market's tick and lot sizes. If a piece of logic needs "now", the gateway stamps it before the message enters the queue.

Sequence numbers are the contract

Every message admitted to a market's queue receives a sequence number assigned by the sequencer, and every output event carries both the input sequence that produced it and its own output sequence. This gives you three properties. First, clients and downstream services can detect gaps and request replay. Second, any two copies of the engine that have consumed the same inputs up to sequence N are guaranteed to have identical state. Third, every trade can be traced back to the precise input that caused it, which is what auditors and dispute teams actually need.

Sequence assignment must happen exactly once and before the message is durably logged. A common mistake is assigning it in the gateway, where retries after a network hiccup can produce duplicates. Assign it at the single point where the market's queue is written.

The append-only log is the database

The engine's only durable output is an append-only log of inputs. The order book in memory is a cache of that log. Fills, book updates and account deltas are derived events published downstream, and if they are lost they can be regenerated by replay. Treat the input log as the system of record, keep it on fast local storage with fsync semantics you have measured, and ship it to durable object storage continuously.

A useful rule: the engine acknowledges an input only after it has been appended to the log. Latency-sensitive teams sometimes flip this to acknowledge first and log asynchronously. That decision converts every crash into a potential lost order, which is a business problem you do not want to explain to a customer.

Snapshots keep replay bounded

Replaying a year of order flow to recover one market is not acceptable. Every N messages, or on a timer, the engine serialises its full state (book, open orders, sequence counters, per-order metadata) to a snapshot keyed by the sequence number it covers. Recovery means loading the latest good snapshot and replaying the log from that sequence forward. Snapshots are written by the engine thread in a way that does not block matching for long; copy-on-write structures or a fork-based approach both work.

fn recover(log: &Log, snapshots: &SnapshotStore) -> Engine {
    let snap = snapshots.latest().unwrap_or_default();
    let mut engine = Engine::from_snapshot(&snap);
    for msg in log.iter_from(snap.seq + 1) {
        // apply() must be pure with respect to msg and engine state
        engine.apply(msg);
    }
    engine
}

Recovery is replay, nothing else

Because the engine is deterministic, failover does not require special code paths. A standby engine can consume the same log in near real time and stay a few messages behind the primary. When the primary dies, the standby finishes consuming the log, confirms it has reached the last acknowledged sequence and starts accepting new inputs. There is no "reconcile the book against the database" step, no manual intervention and no divergent state.

The subtle part is output deduplication. During failover the standby will re-emit events the primary already published. Downstream consumers, including the ledger, must be idempotent on output sequence numbers. This is far easier to enforce if you design it in on day one than to retrofit after the first failover produces duplicate fills.

Testing with recorded order flow

Determinism makes the engine testable in a way most distributed systems are not. Record production input logs, strip nothing, and run them through a candidate build. The output events must match the recorded outputs byte for byte. Any difference is either a bug or an intentional rule change, and either way you want to know before deploying. We keep a corpus of recorded sessions covering opening auctions, self-trade prevention edge cases, cancel-replace storms and halts, and run it on every commit.

• Replay recorded logs against every build and diff the outputs.
• Fuzz the input stream with generated orders and assert book invariants: price-time priority, no crossed book after matching, conserved quantities.
• Run two engine instances from the same log in CI and assert identical snapshots.
• Measure snapshot and recovery time as a tracked metric, not a one-off benchmark.

Where this design ends

The matching engine is deliberately narrow. Risk checks, margin, fee calculation, settlement and account balances belong in services that consume its output stream. Keeping them out of the engine keeps the engine small enough to reason about, fast enough to matter, and pure enough that replay is trustworthy. When teams ask us to add "just one lookup" to the hot path, the answer is almost always to move the decision upstream into the sequencer's admission logic instead, where it can be applied before a sequence number is assigned and without touching the book.