Match buy and sell orders

The matching engine is the exchange's kernel: a tiny, single-threaded state machine whose only job is to decide — for a stream of orders — exactly which trades happen, in exactly what order, every single time you replay the tape. Correctness is the product. Speed is a constraint.

The hinge: matching is a deterministic state machine, not a database query

Notice what this rules out. The engine cannot consult wall-clock time mid-match (two replays would diverge), cannot read a shared cache (stale reads differ), cannot run the matching loop on multiple threads racing for the same price level (interleavings differ), and cannot let floating-point summation reorder. The forcing constraint is reproducibility under replay, and it pushes the design toward something that feels almost retro: a single thread, all state in memory, fed by one totally-ordered input log. This is DDIA Ch. 7's deepest insight made literal — the strongest isolation level, serializability, is defined as "as if executed serially, one at a time," and the matching engine simply is a single-threaded serial executor. There is no isolation anomaly because there is no concurrency.

1. Clarify the contract — and what it is NOT

Treat the prompt as a product contract before a box diagram. The kernel must:

• Maintain a bid book (buyers, sorted by price descending) and an ask book (sellers, price ascending).
• Match incoming marketable orders by price-time priority: best price first; ties broken by earliest arrival (FIFO within a level).
• Support limit, market, cancel, and replace; emit partial fills.
• Produce a deterministic trade stream plus the resting-order residual, and a book snapshot on demand.
• Replay deterministically from the input command log — bit-for-bit identical fills.

And explicitly what it need not do, because these belong to C37's surrounding system, not the kernel: it does not persist to a database on the hot path (durability comes from the sequenced input log, replayed into a hot standby — see below), does not do auth, risk-limit, or balance checks (the gateway does pre-trade risk before the sequencer), does not handle multi-symbol sharding policy (C37: one symbol → one kernel instance), and does not own the wire latency budget (C38). Keeping the kernel this small is what lets it stay a few thousand lines of branch-predictable, allocation-free code.

2. Put numbers on the data structure — array of price levels vs tree map

The single most consequential kernel decision is how to store price levels. The matching loop does one thing constantly: find the best (top-of-book) price, repeatedly. So the question is "what is the cost of `best_bid()` / `best_ask()`, and of insert/cancel?" Two candidates:

Now do the arithmetic that decides it. Take an instrument with a bounded, regulated tick grid: price range $0.01 to $1000 at a $0.01 tick. The number of representable price levels is

L_max = (1000 − 0.01) / 0.01 ≈ 100,000 levels

Pre-allocate an array of 100,000 slots, each a small struct (head/tail pointer into a FIFO queue + aggregate qty), say ~32 bytes. That is 100,000 · 32 = 3.2 MB per side, ~6.4 MB for the full book — trivially L1/L2-adjacent, cache-friendly, and never touches the allocator after startup. In exchange for that fixed memory you get O(1) access to any price level by direct indexing and an O(1) best-price read by advancing a single "best level" cursor. Compare the tree map: it only stores the handful of active levels (maybe a few hundred), so its memory is smaller, but every best-price read pays O(log L) ≈ log₂(100,000) ≈ 17 pointer-chasing, cache-missing comparisons — and you do this on the hottest line of the hottest loop in the building.

3. The cancel-rate fact that drives the queue design

One operational number dominates the data-structure choice for within a price level: in modern markets, roughly 90% of submitted orders are cancelled before they ever fill. The order-to-trade ratio at high-frequency venues runs well above 10:1. So cancel is not a rare path — it is the dominant path. That changes the math entirely.

If you model each price level's FIFO as a doubly-linked list and store, in an order-ID → node hash map, a direct pointer to each resting order, then both insert and cancel are O(1). But a true node removal on cancel costs you the pointer surgery plus map deletion plus potential allocator churn — and you pay it on 90% of orders. The cheaper alternative is a tombstone: on cancel, flip a `cancelled` flag on the node and leave it in the queue; the matching loop skips tombstoned nodes lazily when it walks the level, and a background compaction reclaims them. Tombstoning makes cancel a single branch-free store, at the cost of queues that bloat with dead nodes between compactions. Given a 90% cancel rate, the tombstone's "do almost nothing on the hot cancel path, clean up in bulk later" is usually the right trade — it is the same LSM-tree intuition from DDIA Ch. 3 (cheap deletes via markers, amortised compaction) applied to an in-memory queue.

4. Data model & API

Keep the surface minimal; the kernel speaks in commands, not internal layout.

The core records: a price level (FIFO queue head/tail + aggregate qty), an order (id, side, price, remaining qty, queue node), an order-ID map (id → node, for O(1) cancel), a trade (maker id, taker id, price, qty, seq), and the sequence number stamped by the sequencer on every command.

5. Linearized design — follow one aggressive order

1. Sequence first. Every accepted command passes through the C37 sequencer, which stamps a monotonic sequence number. This is the total order; the kernel only ever sees commands in this order. (DDIA Ch. 9: total order broadcast.)
2. Read the opposite top-of-book. For a buy, look at the best ask via the O(1) best-price cursor.
3. Cross test. If the buy's limit price ≥ best ask, it is marketable — match. Otherwise rest it.
4. Walk FIFO within the level. Fill against the oldest resting order at that price first, then the next, emitting a trade per fill, decrementing both quantities. Skip tombstoned nodes.
5. Sweep levels. If the order still has quantity and the next price level is still marketable, advance the best cursor and repeat (this is how a large/market order "walks the book").
6. Rest the residual. Any unfilled limit quantity is inserted at the back of its own price level (FIFO tail); a market/IOC residual is cancelled.
7. Append outputs to the log. Commands in, trades out — both appended to the sequenced log that feeds the hot standby and the audit trail.

6. Deep dives

(a) Price-time priority and why the structure follows the rule

The rule is two-level: price priority (a better price always trades first) then time priority (at equal price, the order that arrived earlier trades first). The data structure is just this rule made physical. Price priority is why levels are sorted and why best-price must be cheap — you always touch the top of the book first. Time priority is why each level is a FIFO queue and why every command carries a monotonic sequence number: "earlier" is defined by sequence position, not wall clock. Get those two structures right and the matching loop is almost trivial — "while marketable, fill the front of the best opposite level." Note the fairness corollary mentioned above: changing an order's price moves it to the back of the new level, because otherwise you could jump the queue for free.

(b) Deterministic replay = state-machine replication

Durability here does not come from writing the book to a database on each trade — that would put a disk round-trip in the microsecond hot path. Instead: persist only the sequenced input log, and recover the book by replaying it through the same deterministic kernel. This is exactly DDIA Ch. 9's state-machine replication and Ch. 11's event sourcing: the log of commands is the source of truth; the order book is a derived view, a fold over the log. A hot standby runs the identical kernel against the identical sequenced stream and stays bit-for-bit in lockstep, ready to take over with zero divergence. The auditor can reconstruct any trade from three years ago by replaying the tape. None of this works unless the kernel is a pure deterministic function — which is why the "no wall clock, no shared cache, single thread, no FP reordering" rules from the hinge are non-negotiable. The sequencer providing the total order (Ch. 9, total order broadcast — itself a consensus problem, foundation lesson 10) is the keystone: one agreed input order makes one reproducible output.

(c) Tombstone vs node removal under 90% cancels; market vs limit

Covered numerically in §3: with ~90% of orders cancelled, the cancel path is the hot path, so a tombstone (flag-and-skip, bulk-compact later) usually beats true node removal (pointer surgery + map delete + allocator churn) on the hot path, at the cost of dead-node bloat between compactions. Choose true removal only if memory pressure or queue-walk overhead from tombstones measurably dominates — i.e. when cancels are rare, which is the opposite of these markets.

On market vs limit: a market order has no price bound, so it walks the book sweeping every level until filled — which means in a thin book it can fill at a far worse price than the top, the slippage risk. Limit-only venues never slip past the limit but can leave orders unfilled. Retail-facing venues offer market orders for simplicity and bolt on protection — price collars / banding that reject or convert a market order if it would walk too far from the reference price. The kernel stays deterministic either way; the collar is just another deterministic check on the sequenced command.

7. Trade-offs

The sharpest of these is the last: putting the book only in memory feels reckless until you internalise that the sequenced log is the durable truth and the book is a replayable derivation (DDIA Ch. 11). A database-backed book would be durable but would add a disk write to a path measured in nanoseconds — and would still not give you deterministic replay for audit. The in-memory-plus-log design gets both microsecond latency and stronger auditability, precisely because it inverts the usual "the database is the source of truth" instinct.

8. Failure modes

9. Interview Q&A

Related lessons

Read C37 first — it is the exchange overview anchor (sequencer, fan-out, durability, symbol sharding) that this kernel plugs into. C38 owns the microsecond latency budget that this single-threaded kernel must hit. Foundation lesson 10 (consensus & coordination) is where the sequencer's total order ultimately comes from, and 09 (consistency & CAP) frames why a strongly-ordered single writer is the right consistency model for a fair market.