Design a Stock Exchange (Order Matching Engine)

1Clarifying the requirements#

Pin down what "exchange" means to this interviewer before drawing a single box. The word covers everything from a crypto toy to NASDAQ, and the two share almost nothing at the core.

Candidate: Are we building just the matching engine, or the whole stack including the brokerage, user accounts, and funding? Interviewer: Focus on the exchange core. Orders arrive already authenticated and risk-checked by an upstream gateway. You own order entry, matching, and the market data feed out.

Candidate: What order types do I need day one? Just limit and market, or stops, icebergs, all-or-none? Interviewer: Limit and market to start. Design so stop orders can be added later.

Candidate: How many symbols, and what latency am I held to? Interviewer: A few thousand symbols. Tail latency under 100 microseconds inside the engine is the bar. And it must be fair: equal price, earlier order wins.

Candidate: Can we lose a single acknowledged order on a crash? And do I need to support cancels and modifies? Interviewer: Zero loss of acknowledged orders. Yes to cancel and modify. Trades, once printed, are final.

What that last answer just handed me:

• "Zero loss" plus "sub-100us" means durability cannot be a database write in the request path.
• A single disk fsync is 1 to 10 ms; a cross-zone Postgres commit is tens of ms. Both are 100x to 1000x over the entire engine budget.
• So durability has to come from somewhere other than "write to the DB and wait." I defend that hard in 6.2.

Functional requirements

• Accept new orders (limit, market), cancels, and modifies per symbol.
• Match on strict price-time priority; emit fills (executions) and book updates.
• Publish a market data feed: top of book, trades, and depth.
• Replay the full day's order flow to rebuild state (audit and recovery).

Non-functional requirements

• Determinism: same input sequence produces the identical trade sequence, on any replica.
• Durability: every acknowledged order survives a process or node crash.
• Latency: p99 under 100us engine-internal; end-to-end order-to-ack a few milliseconds.
• Fairness and auditability: a regulator can reconstruct exactly why order X filled before order Y.

2Back-of-the-envelope estimation#

Get the scale in your head, because it decides the architecture. Say we are a mid-size equities venue: 2,000 symbols, 500,000 active trader sessions on a busy day.

Order rate (the number that matters).

• A normal day is maybe 300 million order events (new, cancel, modify).
• Over a 6.5 hour session that averages roughly 13,000 events/sec.
• Markets are not uniform: the open, the close, and news spikes concentrate flow.
• Plan for a peak of 1 million order events per second across the venue, with one hot symbol capable of 100,000/sec by itself.
• That burst factor of roughly 75x over the daily average is what bites you: size for the average and you brown out at 9:30am every day.

Trades.

• Trades are a fraction of orders; most orders cancel.
• Modern equities flow is market makers quoting and pulling, so the cancel-to-trade ratio runs 10:1 or worse.
• Call it 30 million trades/day.

Durability write volume.

• At 1M events/sec, each event maybe 150 bytes serialized, that is 150 MB/sec into the event log at peak.
• Over a day, the raw order log is a few terabytes.
• Compressed and tiered to object storage after the session, cheap to keep for years for audit.

Market data out (the real bandwidth hog).

• If 50,000 subscribers each want the depth feed and we push every book change, fan-out dwarfs ingest.
• One book change times 50,000 subscribers is a 50,000x amplification on the output side.
• That lives on a separate multicast and publisher tier, never the matching thread. If it ever touches the matching thread, I have already lost.

3Core APIs#

Order entry is a binary protocol in real life (FIX or a custom wire format over kernel-bypass networking). For the interview I express it as a clean request shape, but it is a framed binary message, not JSON over HTTP on the hot path.

• Call this out explicitly: draw a REST box with TLS handshakes in front of the engine and you have added milliseconds to a microsecond budget without noticing.

POST /orders

{
  "client_order_id": "c-8842-00017",
  "symbol": "ACME",
  "side": "BUY",
  "type": "LIMIT",
  "price": "101.25",
  "quantity": 500,
  "tif": "DAY"
}

POST /orders/cancel

{ "client_order_id": "c-8842-00017", "symbol": "ACME" }

Two things worth defending:

• The client_order_id is the idempotency key. If the gateway retries a send after a timeout, the engine must dedup on it. Otherwise one retry becomes a double buy, which in dollar terms is a real loss and a real incident.
• Market data is a subscribe, not a request. The engine emits a stream; subscribers tap it off a separate tier.

GET /marketdata/subscribe?symbol=ACME&depth=10

What the engine emits back:

• ACK (accepted, with an exchange-assigned sequence number and order id).
• REJECT (with reason), FILL, and BOOK_UPDATE.
• The ack carries the exchange sequence number, not just "ok." That number is the receipt the trader (and later a regulator) uses to reason about ordering.

4High-level design#

The spine is a classic LMAX-style pattern, so draw it fast:

• Everything that touches an order first becomes an immutable, numbered event.
• A new order lands at the gateway, gets authenticated and risk-checked (buying power, fat-finger limits), then goes to the sequencer.
• The sequencer stamps a monotonic sequence number, writes to the replicated event log, and only then feeds the engine.
• The engine mutates the in-memory book, produces fills, and hands results to the publisher.
• The publisher sends the private fill back to the trader and the public print to the market data feed.

Write path and read path are deliberately split.

• The matching engine never serves a query. It only consumes sequenced events and emits result events.
• All reads (your open orders, the depth book, trade history) come from downstream consumers that replay the same log into their own query-optimized stores.
• That separation is what lets the core stay single-threaded and insanely fast.
• It is CQRS taken to its logical extreme: the write model is one in-memory book, every read model is a projection of the event log.

Why single-threaded.

• A lock-free structure on one thread, pinned to one core, with the book sized to fit L2/L3 cache, beats any multi-threaded design that needs locks for price-time correctness.
• A main-memory read is around 100 ns; an L2 hit is a few ns; an uncontended lock plus the cache-line bouncing it causes can cost hundreds of ns and wrecks predictability.
• Contention is the enemy. We remove it by removing the concurrency.

5Data model#

Use a few stores, each shaped for its own access pattern. The hot path has no SQL, but we still model the persisted log and the downstream query stores, because the interviewer will ask "where does the data actually live" and "what is your SQL vs NoSQL call."

The in-memory book (a pair of structures per symbol):

• Price levels use an order-statistics structure (a sorted map or a radix tree over tick-sized prices) so "best price" is O(1) and inserting a new level is O(log n).
• Within a level, a linked list preserves arrival order. Cancel is O(1): the order index hands you the exact node, you unlink it.
• I like the radix tree over tick prices: valid prices are a bounded, dense integer space (every penny from the floor to the ceiling), so you get array-like access instead of pointer chasing through a tree.

The durable event log (the source of truth):

• The log turns the SQL-vs-NoSQL question on its head: it is an append-only, immutable, ordered log, which is neither.
• Downstream, order history and account positions land in a relational store (strong consistency, you need accurate balances and reporting).
• The market data depth cache is served from an in-memory read store rebuilt from the log.
• Trade history for audit goes to columnar object storage, partitioned by day and symbol, because it is write-once and queried by analysts in big scans.
• Three stores, one source of truth, each shaped for its own access pattern.

6Deep dives#

6.1 The matching engine and price-time priority (the signature hard part)#

This is the core, and the determinism story lives here. Walk through a buy limit arriving at price P:

• I walk the ask side from the best (lowest) price up.
• For every resting ask at price <= P, I match against orders in that level in FIFO order until my incoming order is filled or the price no longer crosses.
• Whatever remains rests on the bid book at its limit price, at the back of that level's queue.
• A market order is the same walk with no price limit: it sweeps levels until filled or the book runs dry.

Price-time priority is two tiebreaks, in order.

• Better price always wins.
• At equal price, the order that arrived first (lower sequence number) fills first.
• That is why the per-level structure is a FIFO queue, and why the sequencer assigns time, not the wall clock.
• Two orders in the same microsecond are ordered by sequence number, full stop. Never by a timestamp two machines might disagree on. NTP leaves clocks milliseconds apart, and a millisecond is an eternity here.

Determinism is non-negotiable.

• We run a hot replica that consumes the identical sequenced stream. If primary and replica ever diverge on a single fill, the replica is useless as a standby.
• So the engine must be a pure function of the event sequence. That bans wall-clock reads, random numbers, hash-map iteration order, and any floating point in price math.
• We use integer ticks (price in whole cents or finer), fixed-point everywhere.
• I have watched a design collapse in an interview because the candidate used a double for price and could not explain the drift: 0.1 + 0.2 is not 0.3 in IEEE 754, and if rounding goes one way on one CPU and another way after a compiler reorders an operation, your two "identical" engines print different trades.
• Integers make the engine bit-reproducible by construction.

Trade-off: one symbol cannot borrow a neighbor's core.

• Single-threaded means a hot streak on one name saturates one thread.
• We shard symbols across engine instances (A-F on engine 1, G-M on engine 2), so each engine is single-threaded but we scale horizontally by symbol.
• The cost: a strategy trading a pair across two symbols on two engines has no atomic cross-symbol view.
• We accept that. Equities match per symbol anyway, and no real equities venue promises cross-symbol atomicity.

6.2 Durability without killing latency#

Here is the tension the requirements set up: zero loss of acknowledged orders, but no synchronous database write in a 10us budget. The resolution:

• We do not ack the trader until the event is durable.
• "Durable" means replicated in memory to a quorum, not fsync'd to disk on the critical path.

How it works.

• The sequencer writes each event to an append-only log replicated to a small set of nodes (say three) over the local network.
• We ack the order the instant a majority has the event in their log buffer.
• Those nodes fsync to NVMe asynchronously in batches.
• Because the event is already on three machines' memory, a single node crash loses nothing: two copies remain, and the engine can replay from any of them.
• A local network round trip is a handful of microseconds on good hardware, which fits the budget; a disk fsync at 1 to 10 ms does not, so it comes off the critical path entirely.

Recovery is pure replay.

• A new engine process spins up, reads the event log from sequence 0 (or the last snapshot), and replays every event through the identical matching logic.
• Because matching is deterministic, replay reconstructs the exact book, down to queue positions.
• We snapshot the in-memory book every few minutes so replay does not start from the market open.
• Replay resumes from "snapshot at seq N" and applies N+1 onward.
• Without snapshots, recovering a 3pm crash means replaying 300 million events, which blows your recovery time. With a snapshot every few minutes you replay at most a few million.

Trade-off: in-memory quorum over synchronous fsync.

• A simultaneous power loss of all three log nodes before any fsync could theoretically lose the last few milliseconds of events.
• We make that acceptable by putting the log nodes in different racks with independent power, so correlated loss of all three is astronomically unlikely.
• This is a consistency call made on purpose: we trade a sliver of theoretical durability for a 100x latency win, and we document exactly what the failure window is.
• When the interviewer pushes on "but you said zero loss," the honest answer is: zero loss under any single-node failure, and a named, bounded, rack-isolated window for the three-way correlated failure.

6.3 Idempotency and the cancel/modify race#

Cancels and modifies are where correctness quietly breaks. The race resolution is in 6.1: whichever event got the lower sequence number wins, because the sequencer is the one serialization point. This is why I fought so hard for a single writer. Now the send side:

• The gateway may time out waiting for an ack and resend the same new order.
• Process both naively and the trader buys twice.
• So the engine keeps a seen-set of client_order_id per session (a rolling window, since ids are monotonic per client).
• A duplicate returns the original ack, never a second order.
• The seen-set is itself rebuilt on replay from the log, so it survives crashes: the dedup state is not a side table we could lose, it is a projection of the same event stream everything else derives from.

Trade-off: the seen-set costs memory per active session.

• We bound it with a sliding window and reject very old duplicate ids outright rather than remembering forever.
• The risk is a very delayed retry (seconds late) getting re-processed.
• That is acceptable because the gateway's own retry timeout is far shorter than the window.

7Bottlenecks and trade-offs#

What breaks first: the single hot symbol.

• If one name goes vertical on news, its engine thread saturates one core.
• We cannot shard a single symbol's book across cores without reintroducing the locking we fought to remove, since price-time priority is inherently a total order on that one book.
• Mitigation is vertical: fastest possible core, book pinned in cache, zero allocation on the hot path (pre-allocated order node pools, no garbage collector pauses, which is why these engines are C++ or Rust or very carefully tuned Java with object pooling).
• A single GC pause of even 5 ms is 500 events of backlog on a 100,000/sec symbol, so "no allocation on the hot path" is not a nicety, it is a hard requirement.
• We also throttle at the gateway: a client flooding one symbol gets rate-limited before it reaches the sequencer.

The SPOF: the sequencer.

• It is the one total-ordering point, so by definition a single active writer.
• We do not make it multi-master; that would destroy the total order.
• Instead it is a leader with hot standbys and fast failover. If the leader dies, a standby holding the full replicated log is promoted and continues sequencing from the last committed number.
• Failover is the scary window: during it, order entry stalls for a few hundred milliseconds.
• We accept a brief halt over ever producing two conflicting sequences. In an exchange a short pause is fine; a mismatched trade print is a regulatory incident.
• This is a deliberate CP over AP choice at the sequencer: when the network partitions, we stop taking orders rather than risk two leaders each stamping seq 90412 onto different events.

The consistency call.

• The matching core is strongly consistent and linearizable by construction (one writer, one order).
• The read side is eventually consistent. Your "open orders" view served from a downstream store might lag the true book by a millisecond. That is deliberate.
• We never let a read-side lag affect matching; the engine's in-memory book is the only authority for what fills.
• A stale read can cost a trader a slightly outdated screen; a stale write would cost someone money and the venue its license.

Market data fan-out is a separate scaling axis entirely.

• We never let 50,000 subscribers touch the matching thread.
• The engine emits one stream of book updates; a tree of publisher nodes fans it out, often over multicast on the private network and over WebSocket conflated snapshots to retail.
• Slow subscribers get conflated updates (latest state) rather than every tick, so one slow consumer cannot back-pressure the core.
• Conflation is the key trick: a retail phone on 4G gets "here is the current top of book" at 10 updates/sec, while a colocated market maker gets every single tick over multicast, and neither can slow the other down or reach the engine.

Fairness and sub-100us latency demand a single writer. Build durability around that constraint, not against it.

8Summary#

The decisions that matter:

• Single writer per symbol, in memory. Price-time priority is a total order on one book, so one thread on one core beats any locked design. Contention is the enemy; we delete it by deleting the concurrency.
• One sequencer, total order. Every event is numbered before it reaches the engine, which makes the cancel/fill race unexpressible and every ordering decision explainable to a regulator.
• Durability from in-memory quorum replication, not a synchronous disk write, with a named, rack-isolated failure window instead of a hand-wave.
• Determinism enforced with integer price math and zero wall-clock or random dependence, so a hot replica stays bit-identical and recovery is pure log replay from the last snapshot.
• Idempotency on client_order_id to survive gateway retries, rebuilt on replay like every other projection.
• Reads are projections of the log, so the core never serves a query and stays single-threaded and fast.
• Out of scope by choice: stop-order activation (a conditional queue that injects a deterministic market order on a trigger print), the open and close auctions (a batch cross at a single clearing price, a different algorithm from continuous matching), and kernel-bypass networking plus NUMA pinning. Naming them keeps me honest about what the time covered.

For a payments-flavored take on atomicity and idempotency under money movement, see our UPI and digital wallet design guide.