Cruxly › System design › Design Exercises

Order Matching Engine

determinism first, and the fastest correct thing is one thread

Prompt: design the matching engine of an exchange. Accept buy and sell orders for an instrument, match them by price-time priority, publish the resulting trades and the order book. Latency matters in microseconds, and the book must be reproducible exactly from the input sequence.

40 minutes first. Almost every instinct from the other exercises in this track is wrong here.

Applying the four moves: Scope — accept orders, match by price-time priority, publish trades and book state, reproducible from input; clearing and settlement out. Estimate — latency in microseconds, which rules out network hops and disk on the hot path; throughput per instrument is high but each instrument is independent. Sketch — a single-threaded matching engine per instrument holding the book in memory, fed by a sequenced input log. Deep dive — the usual playbook (replicate, shard, cache) is wrong here: one thread per book is what makes matching deterministic, and determinism is what makes the input log a complete, replayable recovery mechanism.

Why the usual playbook is wrong here

Every other exercise in this track scales out: shard it, replicate it, make it eventually consistent. Here that instinct produces a worse system, and being able to say why is the whole exercise.

Scale first, so the claim is grounded. A busy instrument might see 100,000 orders/s at peak. That is a genuinely large number for one thread — and completely unremarkable for a modern CPU doing in-memory work with no I/O on the path. The data is small: an order book is a few hundred thousand resting orders, tens of megabytes.

Requirement 1: determinism. Replaying the same input sequence must reproduce the same book and the same trades, exactly. This is not a nice-to-have — it is how you recover from a crash, how you run a hot standby, how you settle a dispute, and in most jurisdictions a regulatory obligation. Concurrency is the enemy of determinism: two threads touching one book interleave differently on each run, so the same inputs stop producing the same outputs.

Requirement 2: fairness. Price-time priority means the earliest order at the best price trades first. "Earliest" has to mean something precise, and across several machines with skewed clocks it does not.

Both requirements resolve to the same answer: impose a total order on inputs, then apply them one at a time. Once you have done that, a second thread on the matching core buys you nothing — the order is already fixed — while costing determinism and adding lock contention to a path measured in microseconds.

:::key The counter-intuitive core of this problem Single-threaded is not a limitation you accept here; it is the design. The work is arranging everything else — parsing, risk checks, persistence, market-data publishing — so that the one thread that matches never waits for any of it. :::

Concurrency doesn't just risk a race here — it destroys the one property (exact replayability) that recovery, failover and regulation all depend on.

The architecture: sequencer, matcher, and everything off the hot path

The sequencer creates the total order; the matcher applies it alone. Everything else is a downstream consumer of the identical sequence, so nothing downstream can ever slow the matching thread.

Gateways handle protocol parsing, authentication and pre-trade risk checks (does this account have the margin, is the price within limits). All of it happens before sequencing, because it is per-order work that parallelises freely — and because rejecting a bad order should never consume a sequence number.

The sequencer is the only coordination point: it stamps each accepted order with a monotonically increasing sequence number and appends it to a log. That number, not a wall clock, defines "earliest" — which sidesteps clock skew across gateways entirely. This is the one component that must not be scaled out, because being the single authority is its function.

The matcher consumes the log strictly in sequence order, holds the book in memory, and does nothing else. No database calls, no network calls, no allocation on the hot path if you can avoid it. One thread, one instrument (or a small group), no locks — because there is nothing to contend with.

Everything else consumes the same log downstream. The journal writes it durably for replay. Market data publishes book updates. The hot standby applies the identical sequence to its own copy of the book, so it is always one moment behind and ready to take over. None of these can block the matcher, because none of them is on its path.

The order book, and why it is an unusual data structure

A price-time priority book needs, on every incoming order: the best price on the opposite side (constantly), all orders at a price in arrival order (to match), and removal of an arbitrary order by ID (cancels are the majority of messages on a real venue).

book
├── bids: price → FIFO queue of resting orders   (descending)
└── asks: price → FIFO queue of resting orders   (ascending)

Why not a heap. A heap gives the best price in O(1) but cannot remove an arbitrary order by ID without a linear scan — and cancels dominate. Most real engines use price levels in a sorted structure (or, since instrument prices sit in a narrow band, a direct-indexed array of price levels, which makes "best price" a short walk and any price level an O(1) array index), plus a hash map from order ID to its node for O(1) cancel.

Matching is then mechanical:

on incoming BUY at price P, quantity Q:
    while Q > 0 and best_ask <= P:
        resting = front of queue at best_ask
        traded  = min(Q, resting.remaining)
        emit Trade(resting.id, incoming.id, best_ask, traded)
        Q -= traded;  resting.remaining -= traded
        if resting.remaining == 0: pop it from the queue
    if Q > 0: rest the remainder at price P   (or cancel it, if IOC)

Note the price: a trade executes at the resting order's price, not the incoming one. The resting order was there first and set the terms — that rule is the reason price-time priority is a fairness guarantee rather than just an ordering convention, and getting it backwards is a subtle, expensive bug.

Integer ticks, never floating point. Prices are integer multiples of a tick size, exactly as money is integer minor units in the ledger exercise. A book that accumulates floating-point error is one that eventually disagrees with itself about whether two prices are equal.

The heap's classic strength — instant access to the extreme value — is exactly the wrong optimization target here, since the operation that actually dominates traffic is cancellation, not peeking.

Recovery, failover, and the latency work

Recovery is replay. The book is in memory and vanishes on crash. Restart, read the journal from the last snapshot, reapply every sequenced message in order, and you are in exactly the state you were in — because the matcher is deterministic. Periodic snapshots bound how much replay is needed. This is the payoff for the determinism requirement: recovery needs no reconciliation, only repetition.

Failover. The hot standby has been applying the same sequence all along. Promotion means confirming the primary is truly dead (a split brain with two matchers is catastrophic — both would emit conflicting trades) and pointing gateways at the standby. Fencing matters more here than almost anywhere: use a sequence-number-based fence so a resurrected old primary cannot append after the standby has taken over.

Where the microseconds actually go, worth naming because it separates people who have built one of these from people who have read about them:

Allocation and garbage collection. A GC pause is an eternity at this scale. Pre-allocate objects, reuse them, avoid anything that allocates per message.
Kernel network stack. Kernel bypass (DPDK, or hardware timestamping on the NIC) removes a large fraction of end-to-end latency, and it is a real answer to "how do you go faster" once the algorithm is already right.
Cache locality. The book should fit in CPU cache where possible; an array-of-price-levels layout is chosen partly for this reason, not just for O(1) indexing.
Do not log synchronously on the hot path. Hand the message to a journaling thread through a wait-free ring buffer and move on.

The question to ask before any of that: what actually needs to be fast? The matching thread. Not the risk checks (already parallel, before sequencing), not the market data publish (downstream), not the journal (async). Most latency work fails by optimising a component that was never on the critical path.

:::warn What not to propose here Eventual consistency, sharding one instrument's book across machines, or a distributed lock around matching. All three break determinism or add coordination to a path whose entire budget is a few microseconds. Sharding across instruments is fine and standard — each instrument gets its own single-threaded matcher — but one book stays on one thread. :::

How to say it in the interview

"This is the one system where I do not want to distribute the hot path. Determinism and microsecond latency both point the same way — a single-threaded matching core fed by an ordered log, with everything else kept off that thread."

Checklist

Said explicitly why the scale-out instinct is wrong here, rather than just not using it
Named determinism as a hard requirement with concrete consequences
Used a sequencer to impose total order instead of relying on wall-clock timestamps
Put risk checks and parsing before sequencing so they parallelise freely
Kept journal, market data and standby as downstream consumers of the same log
Rejected a heap for the book because cancels dominate and need O(1) removal by ID
Executed trades at the resting order's price, not the incoming order's
Used integer ticks rather than floating point for prices
Made recovery a deterministic replay from snapshot plus journal
Fenced failover by sequence number so a resurrected primary cannot append
Named GC pauses, kernel bypass and cache locality as where the microseconds go
Sharded across instruments but never within one book

Practice this interactively