Courses › System Design › Question Breakdowns

Design a Stock Exchange

In-memory order books, single-threaded deterministic matching, a sequencer and replayable log, latency engineering.

Design a stock exchange (or a crypto exchange's trading core): brokers and traders submit buy and sell orders, a matching engine pairs them by price and time, and every trade is reported to both sides and to the market. It's a question about an in-memory order book, deterministic single-threaded matching, sequencing and durability without slowing the hot path, and fairness at microsecond latency — very different from typical web-scale designs.

Requirements

Functional

  • Clients can place limit and market orders, and cancel or modify open orders
  • The exchange matches buy and sell orders by price-time priority and executes trades (including partial fills)
  • Clients receive execution reports (acknowledged, filled, partially filled, cancelled)
  • The market receives market data: trades and order book changes (see Design a Market Data Feed)

Out of scope: clearing and settlement (T+1), margin and risk models beyond basic pre-trade checks, auctions at open/close (mention them).

Non-functional

  • Ultra-low latency: order-to-ack in microseconds to low milliseconds; predictable tail latency matters more than averages
  • Throughput: ~1M+ orders/second at peak across ~10k symbols; a single hot symbol can see 100k+/s
  • Correct and deterministic: the same input sequence always produces the same trades
  • Durable: an acknowledged order or trade is never lost
  • Fair: strict price-time priority; no participant gets an unfair ordering advantage

[!TIP] Don't reach for a database A matching engine for one symbol is a single-threaded, in-memory state machine fed by a sequenced log of orders. Durability comes from the log (replayable), not from writing the order book to a database. Saying this early shows you understand why exchanges look nothing like a web app.

Capacity estimates

Core Entities

  • Order — ID, client, symbol, side, type (limit / market), price, quantity, remaining, time in force, sequence number
  • Order book — per symbol: bids (descending price) and asks (ascending price), each price level a FIFO queue
  • Trade (execution) — buy order, sell order, price, quantity, sequence number, timestamp

API

Clients use the FIX protocol or a binary protocol over persistent TCP sessions, not REST:

NewOrderSingle   { clOrdId, symbol: "AAPL", side: BUY, type: LIMIT, price: 189.50, qty: 300, tif: DAY }
OrderCancelRequest { origClOrdId, symbol }
ExecutionReport  { clOrdId, execType: PARTIAL_FILL, lastQty: 100, lastPx: 189.50, leavesQty: 200 }

High-Level Design

c = client "Brokers / Traders" @0,1
gw = service "Order Gateways\n(FIX sessions)" @1,1
risk = service "Pre-trade Risk" @2,1
seq = service "Sequencer" @3,1
log = store "Replicated\nOrder Log" @3,0
me = service "Matching Engine\n(symbols A–M)" @4,0
me2 = service "Matching Engine\n(symbols N–Z)" @4,2
md = service "Market Data\nPublisher" @5,1
rep = service "Execution\nReports" @2,2
c -> gw
gw -> risk
risk -> seq
seq -> log : append
seq -> me
seq -> me2
me -> md
me2 -> md
me -> rep
rep -> gw
  • Gateways terminate client sessions, authenticate, validate messages, and enforce per-client rate limits.
  • Pre-trade risk checks order size, price bands and buying power/position limits.
  • The sequencer stamps every inbound event with a global, monotonically increasing sequence number and writes it to a replicated log.
  • Matching engines (one per symbol, grouped into shards) consume the sequenced stream, update the in-memory book, and emit trades and book updates.
  • Execution reports go back to the clients; market data goes to everyone.

Deep Dives

1. The order book and matching

For each symbol keep two sides; each price level holds a FIFO queue of orders:

  • Best bid/ask lookup in O(1); insert at a price level in O(log P) (a tree or, since prices are discrete ticks, an array indexed by tick) and O(1) append within the level.
  • A hash map orderId → order node makes cancel O(1) — important, since most orders are cancelled.
  • Matching: an incoming buy at 189.50 matches resting asks at ≤ 189.50, best price first, oldest first within a price, producing trades until filled or no match; any remainder rests in the book (limit) or is cancelled (market/IOC).

2. Why single-threaded per symbol

Matching for one symbol is inherently sequential: price-time priority depends on exact order. One thread per symbol (or per shard of symbols) with no locks gives deterministic results and microsecond latency; parallelism comes from running many symbols on many cores. Hot symbols get their own core.

3. Sequencing and durability

Everything that changes state is an input event in the log: new orders, cancels, even timer events. Because the engine is deterministic:

  • Recovery = load the last snapshot of the book and replay the log from its sequence number.
  • Hot standby: a replica engine consumes the same sequenced log and holds identical state, ready to take over instantly.
  • The sequencer writes to a replicated log (memory replication across machines, then disk) before the event reaches the engine, so an acknowledged order survives any single failure.

[!WARNING] Determinism is easy to break Reading the wall clock, iterating a hash map in random order, or depending on thread scheduling inside the engine makes replicas diverge. Take timestamps from the sequencer, use ordered structures, and keep the engine single-threaded.

4. Latency engineering

  • Keep everything in memory; preallocate objects (no GC pauses — C++/Rust or tuned Java with object pools).
  • Pin threads to cores, use lock-free ring buffers between stages (the LMAX Disruptor pattern), and kernel-bypass networking for the hottest paths.
  • Co-location: members' servers sit in the same data center, often with equal-length cables, for fairness.

5. Pre-trade risk without slowing everyone

Risk checks (price bands, max order size, credit limits) must run on every order. Keep each client's limits and running exposure in memory in the risk stage, partitioned by client, updated from execution reports. Bad orders are rejected before sequencing so they never touch the book.

6. Crypto exchange and retail broker variants

  • A crypto exchange (Coinbase) adds custody: balances must be reserved when an order is placed (no double spending across open orders) and settled into the ledger after each trade — the matching engine's output feeds a ledger, not a clearing house.
  • A retail broker (Robinhood) usually doesn't run a matching engine; it routes orders to market makers/exchanges and focuses on order state, buying power and real-time positions.

What's expected at each level

  • Mid-level: an order book with bids and asks, price-time matching, partial fills, execution reports.
  • Senior: in-memory single-threaded matching per symbol, a sequencer and replayable log for durability, O(1) cancels, pre-trade risk.
  • Staff: determinism and hot standbys, latency engineering (Disruptor, core pinning), fairness, and how the design changes for crypto custody or a retail broker.