Stock Exchange

Matching engine, sequencer and market data

Design the core of an exchange: a sequencer that puts all orders in one order, a matching engine with price-time priority, replicas that take over without losing a trade, and a feed subscribers can rebuild the book from.

Overview

An exchange takes buy and sell orders from brokers and matches them. For each symbol it keeps an order book: the resting buy orders (bids) and sell orders (asks), sorted by price. When a new order can trade against the book, the engine fills it and publishes the trade; when it cannot, the order rests in the book and waits.

The matching itself is a small algorithm. What makes the design hard is fairness and recovery. Two brokers who send orders a microsecond apart must be treated in that order, every time, and the result must be provable afterwards. If the engine's machine dies mid-morning, a replacement must continue with exactly the same book, and no trade that was reported may disappear. Thousands of subscribers must see every change, in order, and know when they missed one.

The class design of an order book (orders, levels, a brokerage's account model) is the subject of the LLD online stock brokerage topic; this page is about the system around the matching engine.

Questions to ask first

What is traded? — Stocks, about 5,000 symbols, in whole shares, prices in cents
Who connects? — Member brokers over binary order-entry sessions; no retail clients directly
Volume? — 200 million order messages a day (new, cancel, replace) in a 6.5-hour session; peaks 10 times the average
Matching rule? — Price, then time; displayed orders before hidden ones at the same price
Latency? — Tens of microseconds inside the exchange is the goal; fairness matters more than the absolute number
Recovery? — No acknowledged order or reported trade may be lost; failover in seconds

What you will be able to do

Match orders by price-time priority and handle market, limit, IOC and FOK orders, with runnable code.
Explain why the engine is single-threaded per symbol and how a sequencer and journal make it recoverable.
Design failover by replaying one ordered log into replica engines.
Design a market data feed that subscribers can rebuild the book from and recover gaps in.
Place risk checks and trading halts, and store trades for charts and audits.

Key concepts

Order book
Price-time priority
Limit and market orders
Time in force
Sequencer
Journal and replay
Deterministic state machine
Multicast market data
Gap recovery
Trading halts

Functional requirements

Accept new, cancel and replace requests for limit, market and stop orders
Support time in force: day, immediate-or-cancel (IOC), fill-or-kill (FOK)
Match by price, then display, then time; report every fill to both sides
Publish every book change and trade on a sequenced market data feed
Halt and resume trading in a symbol
Keep a complete, ordered record of every input and output for audits

Non-functional requirements

Deterministic: the same inputs in the same order always give the same trades
No acknowledged order and no published trade is ever lost
Median order-to-acknowledgment inside the exchange in the tens of microseconds (a target we chose)
Failover to a replica engine within seconds, with an identical book
Subscribers can detect and repair any missed market data message

Interview questions

Walk me through what happens to one order.
Why is the matching engine single-threaded? Isn't that slow?
How does the exchange recover when the engine crashes?
How do subscribers know they have the right book?
A broker cancels an order just as it is being filled. Who wins?
How do you scale to more symbols and more traffic?
What stops a fat-finger order or a crash in prices?
How is this different from designing a brokerage app?