Design a Stock Exchange / Order-Matching Engine

Web instincts are all wrong here

An order-matching engine is the interview where the usual web instincts (throw it in a database, shard it, scale horizontally) are all wrong, and knowing why is the whole point. The requirements are microsecond latency, perfect determinism (an audit must be able to replay every fill exactly), and strict fairness. Those force a single-writer, in-memory, event-sourced design.

Price-time priority

The matching rule is price-time priority over a limit order book: for buys, highest price first; for sells, lowest price first; and at the same price, the earliest order wins (time priority). A limit order rests in the book until matched; a market order takes the best available price immediately; a cancel removes a resting order. The book is two sorted structures (bids descending, asks ascending) grouped by price level, each level a FIFO queue of orders. Matching pops the best price levels and fills in time order.

Single-writer, single-threaded

The counterintuitive core: use a single-writer, single-threaded matching engine, not a database with locks. Why is single-threaded faster and more correct here? Because a lock per order in a general database adds milliseconds and nondeterminism (thread scheduling decides tie-breaks), and this domain needs microseconds and reproducibility. A sequencer assigns a total order to all inbound events (every order, cancel, and modify gets a monotonic sequence number), and a single thread processes them one at a time from an in-memory ring buffer (the LMAX Disruptor pattern), with no locks, cache-friendly memory access, and no cross-thread nondeterminism. Horizontal scale comes from sharding by instrument: each symbol (AAPL, TSLA) gets its own single-writer engine, and there is no cross-symbol coordination on the hot path.

Interview nuance: the signal here is explaining that single-threaded beats multi-threaded for this workload. Say: the bottleneck is not CPU throughput, it is determinism and tail latency, and a lock-free single writer over sequenced input gives both, which a sharded transactional database cannot.

The order book lives entirely in memory (arrays or intrusive structures per price level for O(1) best-price access), with no per-order database round-trip on the hot path, because a disk read would blow the microsecond budget.

Determinism and recovery

Determinism is a hard requirement, not a nice-to-have, because regulators and replay demand that the same ordered input always yields identical output. That means: no wall-clock decisions in matching logic (derive time and ids from the sequence number), no random tie-breaking, and no multi-threaded races. Given the exact same sequenced input, a replay must reproduce every fill identically.

Recovery uses event sourcing. Before the engine acts on an accepted event, append it to a durable, replicated journal (the sequenced event log). On a crash, spin up a fresh engine and replay the journal to reconstruct the exact book state; periodic snapshots bound replay time so you replay from the last snapshot forward rather than from the beginning of the day. Because matching is deterministic, replay is guaranteed to rebuild the identical book.

orders --> pre-trade risk checks --> Sequencer (assign seq #, append to journal)
   --> [single-threaded matching engine per instrument, in-memory book]
   --> fills + book deltas --> market-data bus (multicast/streaming)
Journal (replicated) --replay--> hot-standby replica (deterministic takeover)

Market-data fan-out must not slow matching: publish trades and book deltas onto a separate high-throughput multicast or streaming bus so slow subscribers cannot backpressure the matcher. Availability comes from hot-standby replicas that consume the same sequenced log and can take over deterministically, plus pre-trade risk checks in front of the matcher (credit/position limits) so bad orders never reach the book.

Recap: match by price-time priority in an in-memory order book, process a single-writer sequenced event stream single-threaded (Disruptor style) for lock-free determinism and microsecond latency, shard by instrument for scale, keep matching fully deterministic (no wall-clock, no randomness), recover by replaying a replicated event journal from snapshots, and fan out market data on a separate bus with hot standbys for availability.