A limit order for 100 shares at $50.25 lands on the exchange at 9:41:07.123456. Two seconds later someone sends a market sell for 300 shares. The engine has to decide, in a few microseconds, which resting buyers get filled, in what order, and at what price, and it has to make the same decision every single time you replay that morning’s tape. That determinism is the whole game, and it’s what the interviewer is really probing when they open with “design a matching engine.”
The question shows up at exchanges like Nasdaq and CME, at crypto venues like Coinbase, at brokers like Robinhood, and at prop shops such as IMC, Optiver, and Da Vinci that run internal crossing systems. Depending on the firm it lands as a system design round, a low-level design round, or both stapled together. The domain is small enough to hold in your head, which is the good news. The trap is that candidates spend twenty minutes on the order book data structure and never reach sequencing, recovery, or the reason the thing runs on one thread.
Price-time priority, and why it comes first
Most venues match on price-time priority, also called FIFO. Sort resting orders by price, best first. Among orders at the same price, the one that arrived earlier trades first. A buyer bidding $50.26 gets filled before a buyer at $50.25. Two buyers both at $50.25 fill in the order their orders reached the book.
Say the resting bids are 200 @ 50.25 (arrived first), 100 @ 50.25 (arrived second), and 500 @ 50.24. A market sell for 400 takes the first 200 at 50.25, then the next 100 at 50.25, then 100 of the 500 at 50.24. The seller’s average fill is worse than the top of book because the order walked down two price levels. The remaining 400 @ 50.24 stays resting. Trades print at the resting (maker) price, not the incoming (taker) price, which is the detail candidates most often get backwards.
Some futures markets use pro-rata matching instead, where a large incoming order splits across resting orders at the best price in proportion to their size rather than strictly by arrival time. Mention that you know pro-rata exists and where it lives (short-dated interest rate futures, for one) and you’ve already separated yourself from the candidate who thinks FIFO is the only option. Don’t design both. Pick price-time, say why, keep going.
The data structures that make cancels O(1)
Real books cancel far more orders than they fill. Most quotes a market maker posts never trade; they get pulled and repriced as the market moves. So the structure has to make cancel and modify cheap. Matching fast isn’t enough on its own.
The shape that works: one book per side, indexed by price level. Because prices move in fixed ticks, you can index an array by tick, or use a sorted map when the price range is wide and sparse. Each price level holds a FIFO queue of orders, usually an intrusive doubly linked list so you can splice a node out in constant time. Keep a pointer to the best bid and best ask so top-of-book reads are O(1). Keep a hash map from order id to its node so a cancel is a lookup followed by an unlink, no scan.
Matching an incoming order walks price levels from the best inward, filling whole resting orders and then a partial at the boundary, stopping when the incoming quantity is exhausted or the price no longer crosses. Inserting a resting limit order appends to the FIFO queue at its level. Cancel unlinks. That is the entire hot path, and it’s why a single symbol can quote sub-ten-microsecond matching times.
| Order type | What the trader is asking for | What the engine does with the part that can’t fill now |
|---|---|---|
| Limit | Trade only at my price or better | Rest the remainder in the book at its limit price |
| Market | Trade against the best prices available right now | Fill whatever liquidity exists; cancel or reject the rest, no price protection |
| Immediate-or-cancel (IOC) | Take what fills this instant | Cancel the unfilled remainder; nothing rests |
| Fill-or-kill (FOK) | All of it now or none | Cancel the whole order if it can’t fill in full immediately |
| Post-only | Add liquidity, never take it | Reject the order if it would cross and trade on arrival |
| Stop | Stay dormant until a trigger price prints | Activate into a market or limit order, then follow that type’s rules |
Why the matching thread is single-threaded on purpose
This surprises people. You have a box with 64 cores and you run the actual matching on one of them, alone. The reason is determinism. If two threads race to touch the same price level, the order of execution depends on the scheduler, and now the same input tape can produce two different sets of fills. For a venue that has to answer “why did my order not fill” to a regulator, that is fatal.
The pattern most exchange engines borrow is LMAX’s. Gateways receive orders over FIX or a binary protocol, do the parsing and validation off the hot path, and drop each order into a lock-free ring buffer (the Disruptor). A single sequencer thread stamps every order with a monotonic sequence number, which fixes the total order of events for all time. The matching thread consumes that sequence and does nothing but match. Because it never blocks on a lock and never allocates on the hot path, its latency is the latency of one CPU doing arithmetic and chasing pointers, and its tail stays tight.
Parallelism comes from sharding, not from threading a single book. AAPL and TSLA have independent books, so they run on independent matching threads on separate cores. Hundreds of symbols spread across cores cleanly because a trade in one book never touches another. The only ordering you have to preserve is per symbol.
Sequencing, journaling, and coming back from a crash
The number the sequencer assigns is the spine of recovery. Every accepted order is written to an append-only journal in sequence order before it is matched. This is event sourcing: the journal is the source of truth, and the in-memory book is a projection you can rebuild. If the primary process dies at sequence 4,812,004, a hot standby that has replayed the same journal to the same point holds an identical book, byte for byte, because matching is a pure function of the ordered input.
Replaying from sequence zero on every restart gets slow once the journal is billions of events long, so the engine periodically snapshots the whole book to disk and records the sequence number the snapshot was taken at. Recovery loads the latest snapshot, then replays only the journal tail past that point. A snapshot plus a short replay turns a multi-hour cold start into a few seconds.
This is where interviewers push on failover. A warm standby that sits one message behind can double-fill or drop an order when it gets promoted. The clean answer is that standbys consume the same sequenced stream and apply it deterministically, so promotion means “start accepting gateway traffic,” not “reconstruct state under time pressure.”
Pre-trade checks that can’t be skipped
Before an order reaches the book it passes risk and validity gates: the price sits inside allowed bands, the size is under the fat-finger cap, the account has the buying power or position headroom for it, and self-trade prevention stops a firm from crossing its own resting order (which can look like wash trading). These run on the gateway or a dedicated risk stage, not inside the matching thread, so the hot path stays a pure matcher. Putting a credit-limit database call in the matching loop is the mistake that turns a ten-microsecond engine into a ten-millisecond one.
Market data is a second, separate problem
Every match and every book change has to reach participants. The engine publishes an incremental feed of adds, cancels, and trades, each tagged with the same sequence number so a client can detect a gap and pull a snapshot to resync. Venues offer depth at different granularities, from top-of-book to full order-by-order depth, and the feed is usually multicast so ten thousand subscribers cost about the same as one. Keeping the feed’s ordering consistent with the matching engine’s own sequence is what lets a market maker trust that the book they see is the book that filled them.
A few of the ways the question actually gets asked, so you can hear the level shift the interviewer is listening for:
- “Walk me through what happens to a marketable limit order from the socket to the fill.”
- “A market order and a cancel for the same resting order arrive in the same microsecond. Who wins?”
- “Your matching box loses power mid-session. What’s the state when it comes back, and how long does that take?”
- “How do you stop one firm’s algo from trading against its own quote?”
The strongest candidates answer the cancel-versus-market case without hedging: the sequencer already decided, by the sequence numbers it assigned, and the outcome is whatever the earlier number says. Explain why that single fact is what makes the whole system auditable and you’ve answered the question the interviewer was actually asking.
Keep sharpening your system design:
