Design a Stock Exchange: Order Books, Matching Engines and Deterministic Replay

Listen

Clarify scope. Brokers send limit and market orders, cancels and replaces. The exchange matches them by best price first, then by arrival time, sends execution reports back, and publishes a public feed of prices and trades. Non-functional needs are extreme: matching in microseconds, never losing an order once it is acknowledged, identical results if you replay the same inputs, and equal treatment for everyone. Clearing and settlement happen downstream, and we will only connect to them.

Ask scale

Assume five thousand symbols and half a billion order messages a day, most of them cancels and replaces from algorithms. Squeezed into a six and a half hour session, that averages about twenty thousand messages a second, but the opening and closing minutes can be fifty times busier, around a million a second. The journal grows by about fifty gigabytes a day. The latency target is the unusual part: acknowledgements in under a hundred microseconds, p ninety-nine within a millisecond.

5,000 listed symbols
500M order messages/day
  (new + cancel + replace)
trading day 6.5 h = 23,400 s
  avg = about 21,000 msgs/s
  open/close burst x50 = 1M msgs/s
20M trades/day

journal: 500M x 100 B = 50 GB/day
latency: ack under 100 us, p99 1 ms

Define API

There is no REST here. Brokers keep long-lived TCP sessions using the FIX protocol or a faster binary format. A new order carries the broker's own order id, symbol, side, type, price, quantity and time in force. Cancel and replace refer to the original id. The exchange answers with execution reports: acknowledged, partially filled, filled, cancelled or rejected, with the fill price, quantity and what is left. The public feed carries book updates and trades, each with a sequence number.

NewOrder { cl_ord_id, symbol, side,
  type: LIMIT, price: 101.25,
  qty: 300, tif: DAY }
Cancel  { cl_ord_id, orig_cl_ord_id }
Replace { orig_cl_ord_id, price, qty }

ExecReport { ACK | PARTIAL_FILL |
  FILL | CANCELLED | REJECTED,
  exec_id, last_px, last_qty, leaves }
feed: BookUpdate, Trade (seq numbered)

Data model

The central data structure is the order book, one per symbol, held in memory. It has two sides: bids sorted from highest price down and asks from lowest up. Each price level is a first-in, first-out queue of orders, which is exactly what time priority means. A hash map from order id to its queue node makes cancels instant. What is durable is not the book, it is the journal: every sequenced input message, from which the book can always be rebuilt.

per symbol, two sides:
  bids: price levels high -> low
  asks: price levels low -> high
  level = FIFO queue of orders
order_id -> node (for O(1) cancel)

durable:
  journal of sequenced input messages
  trades -> trade store (off hot path)
  end-of-day snapshot of open orders

High-level design

Trace an order. The broker's message reaches a gateway, which authenticates the session, validates fields and throttles abusive senders. Pre-trade risk checks the member's limits. The sequencer stamps the message with a global sequence number and appends it to the replicated journal. Then the matching engine applies it to the book, producing fills, and the results flow back to the broker and out on the market data feed.

Deep dive: matching

Matching follows price-time priority. An incoming buy for three hundred at up to one oh one point two five looks at the asks. The best price is one oh one point two, where seller A has two hundred, so that fills first at A's price. Next is one oh one point two five, where B arrived before C, so B's hundred fills. The order is complete; C keeps its place in line. Notice the trade happens at the resting order's price, so the buyer gets the better price.

Choose structures so every common operation is constant time. Because prices move in fixed ticks within a daily band, the price levels can be a plain array indexed by tick, or a balanced tree if the range is wide. Each level is a doubly linked list, so adding to the back and removing from the middle are both instant. Keep the best bid and ask cached. And preallocate order objects, because allocating memory or pausing for garbage collection costs more than the matching itself.

asks:  101.20  x 200  (A, 09:15:01)
       101.25  x 100  (B, 09:15:02)
       101.25  x 400  (C, 09:15:04)

in: BUY 300 LIMIT 101.25
  fill 200 @ 101.20 with A
  fill 100 @ 101.25 with B
  done. C keeps its place in line

trade price = the resting order price

price levels: array indexed by tick
  (price bands keep it bounded)
  or a balanced tree of levels
level: doubly linked list of orders
best bid/ask: cached index

add at existing level  O(1)
cancel via id map      O(1)
match from the top     O(1) per fill
no allocation on the hot path

Deep dive: one thread

Why one thread? A busy order book is touched by every message, so locks would add contention and unpredictable delays. A single thread that owns the book needs no locks, stays in the processor's cache, and is fully deterministic: the same inputs in the same order always produce the same outputs. To scale, partition symbols across engines, since an order only ever touches one symbol. The sequencer gives each engine a single, journaled order of inputs.

Deep dive: never lose

How do you never lose an order with no database on the hot path? Journal the inputs. Each sequenced message is appended to the journal and copied to a hot standby before the broker gets an acknowledgement. The standby runs the identical engine on the identical inputs, and because matching is deterministic, it holds exactly the same book. If the primary dies, the standby is already current and takes over within milliseconds. A cold restart loads a snapshot and replays the journal from there.

Replay only works if the engine is perfectly deterministic, and that takes discipline. The engine never reads the wall clock; timestamps come from the sequencer inside each message. No random numbers, and no reliance on hash map iteration order. No calls to outside systems from inside the engine. Run the same binary and config on primary and standby. Every output carries its input's sequence number, so after a failover anyone can spot and discard a duplicate.

Deep dive: risk

Before an order reaches the book, cheap in-memory checks catch mistakes. A price band rejects orders far from the last trade, which stops a misplaced decimal point. Limits on order size, value, and each member's credit and position stop runaway algorithms. Throttles cap messages per session. A kill switch cancels all of one member's orders at once. And market-wide circuit breakers halt trading after extreme moves. All of this must cost only microseconds.

Deep dive: market data

Market data must reach everyone fast and at the same moment. The engine emits incremental updates, like a price level changed or a trade printed, each with a sequence number. Inside a data center, UDP multicast sends one packet that all subscribers receive together, which is fairer than looping over connections. If a subscriber sees a gap in sequence numbers, it asks a retransmit service for the missing packets, or loads a fresh snapshot and continues from there.

Deep dive: post-trade

Everything that needs a database sits downstream. Trades stream asynchronously into a trade store, ordered by sequence number. Brokers receive drop copies of their own fills for their records. At the end of the day, trades go to the clearing house, which nets positions and settles them, often the next business day. Market surveillance reads the same stream looking for manipulation. And because the journal is complete, auditors can replay any second of any day.

Interviewers may ask how real exchanges get so fast. Brokers co-locate their servers in the exchange's data center, often with equal cable lengths so nobody gains a physical edge. Networking bypasses the operating system kernel. Engine threads are pinned to dedicated cores and spin instead of sleeping. Protocols are binary, so there is no text parsing on the hot path. And the team watches p ninety-nine and p ninety-nine point nine, never the average.

Trade-offs

Trade-offs. The single-threaded engine is simple, fast and deterministic, but one symbol can never use more than one core, which is fine because a core handles millions of operations a second. Replicating to the standby before the acknowledgement costs a few microseconds and buys durability. If a gateway dies, brokers reconnect to another and resend using their own order ids, which the engine deduplicates. If something looks wrong in matching, halt that symbol rather than guess.

Monitor acknowledgement latency at p ninety-nine and p ninety-nine point nine, journal replication lag, and how far the standby's sequence number trails the primary's. Watch feed gaps per subscriber and rejects by reason, since a spike in price band rejects can mean a broker's algorithm has gone wrong. At ten times the messages, add engine partitions and rebalance symbols. A new asset class uses the same engine shape with new risk rules.

Interview summary

In the interview: bursts of a million messages a second with microsecond latency. An in-memory order book per symbol, made of price levels with first-in first-out queues, matched by price then time. Gateway, risk checks and a sequencer in front. A single-threaded engine per symbol partition. Inputs journaled and replicated to a hot standby that replays them deterministically. A sequenced multicast feed, and databases only downstream.