Design a Stock Exchange

The exchange question is unusual and worth learning for that reason: almost every instinct from web-scale design — shard it, make it eventually consistent, scale horizontally — is

wrong here. Correctness, determinism and microsecond latency dominate.

Requirements

Functional

Place, modify and cancel orders (market, limit, stop).
Match buyers to sellers by price-time priority.
Publish market data: order book depth and the trade tape.
Settle and report trades.

Non-functional

Latency in microseconds, and predictable — tail latency matters more than the mean.
Fairness: identical orders must be processed in arrival order.
Zero tolerance for lost or duplicated orders.
Full auditability: every event reconstructible.

NYSE-scale: millions of orders/second at peak across symbols
Order book depth: thousands of price levels per symbol
Latency budget: single-digit microseconds inside the matching engine

The order book

Per symbol, two sorted structures:

Each price level is a FIFO queue of orders — which is how time priority is implemented. Price first, then arrival time.

Each price level is a FIFO queue of orders, which is what implements time priority. The data structure is a price-indexed array or map of levels, each holding an intrusive linked list — chosen so that adding to a level, cancelling from the middle, and reading the best price are all O(1). Cancellations vastly outnumber trades in real markets, so O(1) cancellation is a first-order concern, not a detail.

Matching: price-time priority

Incoming BUY limit 101.00 × 400

1. Best ask is 101.00 ≤ 101.00 → it crosses
2. Match against the FIFO queue at 101.00, earliest order first
3. 200 available → trade 200, remove that resting order
4. 200 remain unfilled; next ask is 101.25 > 101.00 → stop
5. Rest the remaining 200 as a new bid at 101.00

Price first, then time. A market order simply crosses until filled or the book is exhausted. The algorithm is not the hard part — making it deterministic and fast is.

The single-threaded matching engine

The counter-intuitive core of the answer: **the matching engine is one thread per symbol, in memory, with no locks.**

Why not parallelise? Because matching must be deterministic and fair, and any concurrency introduces ordering non-determinism that would let two identical orders be matched in an order that depends on thread scheduling. A single thread over an in-memory book handles millions of orders per second, and lock contention would cost more than it saves.

Scaling is therefore by symbol, not within a symbol: each symbol's book runs on its own core, and symbols are independent because an order only ever touches one book.

The techniques that make this fast, worth naming: pre-allocated object pools with no allocation on the hot path (garbage collection pauses are unacceptable), mechanical sympathy — cache-friendly layouts, avoiding pointer chasing — busy-spinning rather than blocking, CPU pinning and kernel bypass networking. LMAX Disruptor is the canonical open-source example.

Sequencing and replication

Gateways → SEQUENCER → matching engine (primary)
              │              │
              │              └→ market data publisher
              └→ replicated event log → hot standby engines

The sequencer stamps every inbound order with a global sequence number before it reaches the engine. That single step gives you everything:

A total order, so fairness is defined and provable.
Deterministic replay: replaying the sequenced input reproduces the exact book state.
Replication without consensus in the hot path — standbys consume the same log and stay

bit-identical.

A complete audit trail, which regulators require.

Determinism is the substitute for distributed consensus here. Because the engine is a

deterministic state machine over an ordered input log, a standby that has consumed the same log is guaranteed to be in the same state, and failover is instant.

Market data

Fanning out to thousands of subscribers is a separate concern from matching, and must never slow it down.

Matching engine → event stream ┬→ full depth feed (every book change)
                               ├→ top-of-book feed (best bid/ask only)
                               └→ trade tape (executions)

Multicast is the usual transport within a data centre, since one packet serves every subscriber. A slow subscriber must never apply backpressure to the engine — drop or snapshot them instead, and provide periodic snapshots so a client that falls behind can resynchronise rather than replaying from the beginning.

Risk and settlement

Pre-trade risk checks — sufficient funds, position limits, price collars — must run

before the order reaches the book, and they are on the latency budget. Post-trade

settlement (T+1 or T+2), clearing and reporting are asynchronous and are ordinary distributed-systems work by comparison.

Follow-ups to expect

Order types — stop, iceberg, fill-or-kill, good-till-cancelled; each is a rule layered

over the same matching core.

Circuit breakers — halting a symbol after an extreme move.
Auctions — opening and closing crosses use a different algorithm that maximises

matched volume at a single price.

Fairness and co-location — physically equal cable lengths to every rack, because

microseconds are commercially meaningful.

Testing — deterministic replay of production input as the primary correctness tool.

Track this problem on the System Design sheet.

Frequently asked

Why is a matching engine single-threaded?

Because matching must be deterministic and provably fair. Any concurrency within a symbol makes execution order depend on thread scheduling, which breaks time priority and makes replay-based recovery and auditing impossible. A single thread over an in-memory book handles millions of orders per second, and scaling is done by running each symbol's book on its own core.

What is price-time priority?

The matching rule: orders at a better price execute first, and among orders at the same price the one that arrived earliest executes first. It is implemented as a price-indexed structure of levels, each holding a FIFO queue of resting orders, so the best price is O(1) to read and time priority is inherent in the queue.

How does an exchange achieve fault tolerance without slowing down?

By making the engine a deterministic state machine over a sequenced input log. A sequencer assigns a global order number to every inbound order before it reaches the engine, so hot standbys that consume the same log arrive at bit-identical state with no consensus protocol in the hot path — and the same log provides replay, recovery and the regulatory audit trail.