How Would You Design a Stock Exchange Matching Engine?
Learn how to design a stock exchange matching engine with price-time priority, order books, and deterministic replay for interviews.
Expected Interview Answer
A stock exchange is designed around a single-threaded, in-memory matching engine per symbol that maintains a price-time-priority order book, sequences every incoming order deterministically, and matches buy and sell orders while streaming trade confirmations and market data out asynchronously.
Each symbol’s order book is owned by exactly one matching engine instance to avoid distributed locking on the hottest, latency-critical path; orders for a symbol are appended to a durable, sequenced log (similar to Kafka) so the engine can replay and recover deterministically after a crash. The book is typically two sorted structures (bids and asks) ordered by price then arrival time, and a new order is matched against the opposite side as far as price allows before resting the remainder in the book. Because correctness and ordering matter more than raw throughput per se, the engine processes orders strictly sequentially in memory, achieving very low latency by avoiding locks, and horizontal scale comes from sharding by symbol across many such engines rather than parallelizing within one book. Trade executions are pushed out via a separate, decoupled market-data feed and to a downstream clearing/settlement system, keeping the matching path itself minimal and fast.
- Single-threaded, in-memory matching per symbol removes locking and guarantees deterministic ordering
- A durable sequenced log allows exact replay for crash recovery and auditability
- Price-time priority ensures fair, predictable matching that regulators and traders can verify
- Sharding by symbol scales the exchange horizontally without touching the hot matching path
AI Mentor Explanation
A stock exchange matching engine is like a single official scorer who is the sole authority processing every ball bowled in strict order, never letting two events be recorded out of sequence, which is what keeps the scorecard trustworthy. Buy and sell orders are like batters and bowlers being paired by a strict queue — the earliest-arrived, best-priced request at the crease gets matched first, and unmatched requests wait in an ordered list. If the scorer’s system crashes, replaying the exact sequence of balls bowled from the recorded log reconstructs the identical scorecard. That single authoritative sequencer with a durable, replayable log is exactly how a matching engine guarantees fair, deterministic order matching.
Step-by-Step Explanation
Step 1
Sequence the order into a durable log
Every incoming order for a symbol is appended to an ordered, persisted log before processing, enabling deterministic replay.
Step 2
Feed the single-threaded matching engine
Exactly one in-memory process owns that symbol’s order book, applying orders strictly in log order with no locking needed.
Step 3
Match by price-time priority
An incoming order matches against the best-priced resting orders on the opposite side, oldest first at each price level, until exhausted or fully filled.
Step 4
Publish trades and market data asynchronously
Confirmed trades stream out to clearing/settlement and a public market-data feed, decoupled from the hot matching path.
What Interviewer Expects
- Explains why matching per symbol is single-threaded/in-memory rather than distributed-locked for low latency
- Describes price-time priority and the order book as two sorted sides (bids/asks)
- Uses a durable, sequenced log for deterministic crash recovery/replay
- Scales via sharding by symbol, not by parallelizing within a single order book
Common Mistakes
- Proposing a distributed lock or multi-writer design for a single order book, which destroys determinism and adds latency
- Forgetting price-time priority and treating matching as arbitrary or random
- Not separating the low-latency matching path from slower downstream concerns like market data and clearing
- Ignoring crash recovery — no durable log means the book cannot be reconstructed after a failure
Best Answer (HR Friendly)
“I would design the exchange so that each stock has exactly one process responsible for matching its buy and sell orders, processing them one at a time in the exact order they arrived, which keeps everything fast and completely predictable. Every order gets written to a durable log first, so if that process ever crashes, we can replay the log and end up in the exact same state. Once trades are matched, we publish the results out to other systems like market data and settlement separately, so that reporting work never slows down the actual matching.”
Code Example
import heapq
class OrderBook:
def __init__(self):
self.bids = [] # max-heap via negative price, then arrival seq
self.asks = [] # min-heap by price, then arrival seq
self.seq = 0
def add_order(self, side, price, quantity):
self.seq += 1
trades = []
if side == "buy":
while quantity > 0 and self.asks and self.asks[0][0] <= price:
ask_price, ask_seq, ask_qty, ask_id = heapq.heappop(self.asks)
fill = min(quantity, ask_qty)
trades.append((ask_id, fill, ask_price))
quantity -= fill
if ask_qty > fill:
heapq.heappush(self.asks, (ask_price, ask_seq, ask_qty - fill, ask_id))
if quantity > 0:
heapq.heappush(self.bids, (-price, self.seq, quantity, self.seq))
else:
while quantity > 0 and self.bids and -self.bids[0][0] >= price:
bid_price, bid_seq, bid_qty, bid_id = heapq.heappop(self.bids)
fill = min(quantity, bid_qty)
trades.append((bid_id, fill, -bid_price))
quantity -= fill
if bid_qty > fill:
heapq.heappush(self.bids, (bid_price, bid_seq, bid_qty - fill, bid_id))
if quantity > 0:
heapq.heappush(self.asks, (price, self.seq, quantity, self.seq))
return tradesFollow-up Questions
- Why does price-time priority matter for fairness, and how do you enforce arrival order precisely?
- How would you shard the exchange across thousands of symbols while keeping each book single-threaded?
- How does the engine recover deterministically after a crash using the sequenced log?
- How would you handle a market-wide circuit breaker that must halt trading across all symbols simultaneously?
MCQ Practice
1. Why is a single symbol’s order book typically owned by exactly one in-memory process?
A single owner per symbol removes the need for distributed locks, keeping matching latency low and the match order strictly deterministic.
2. What does price-time priority mean in an order book?
Price-time priority matches the best available price first, breaking ties by which order arrived earliest at that price.
3. Why does the matching engine append every order to a durable sequenced log before processing it?
A durable, ordered log lets the engine replay exactly what happened to reconstruct the identical order book state after a failure.
Flash Cards
Why is matching single-threaded per symbol? — To avoid distributed locks and guarantee deterministic, low-latency order matching.
What is price-time priority? — Best price matches first; ties broken by earliest arrival time at that price.
How does the engine recover after a crash? — By replaying the durable, sequenced order log to deterministically reconstruct the order book.
How does an exchange scale horizontally? — By sharding matching engines per symbol, not by parallelizing within a single order book.