Design an order-matching engine (stock exchange)
Design the core of a stock exchange: an order book that matches buy and sell orders.
Why interviewers ask it
It tests data structures (heaps and queues), fairness rules, and why a single-threaded design can be both the fastest and the safest.
Functional requirements
- Place limit orders (buy or sell at a price or better).
- Match orders by price, then time; allow partial fills.
- Cancel orders; publish trades.
Non-functional requirements
- Very low latency; fair and deterministic ordering.
- Never lose an order or fill it twice.
From version 1 to the final design
- Version 1: one list of orders, scanned for a match every time (slow).
- Version 2: buy and sell heaps ordered by price, first in first out at each price.
- Version 3: partial fills, cancels and market orders.
- Version 4: one single-threaded engine per stock, fed by a queue, with an event log for replay.
The design, step by step
- An incoming buy order fills against the cheapest sell orders while their price is at or below the buy price, oldest first at each price.
- Any quantity left over rests in the book.
- Each stock's book is processed by one thread, in sequence, fed by a queue, so no locks are needed inside the book.
Deep dives
- Price-time priority: better price first; at the same price, the earliest order first.
- One thread per stock gives determinism and avoids locks; parallelism comes from different stocks.
- Log every order before processing it, so the book can be rebuilt by replay after a crash.
Common mistakes
- Ignoring time priority at the same price.
- Using locks inside the matching loop instead of processing in sequence.
- Storing prices as floats: rounding makes equal prices compare as different. Use integers, such as whole pence.
Not true: Several threads on one stock: a faster engine that gives the same results.
In fact: Matching depends on order, so threads on one stock need locks and can give different results on each run. One thread per stock stays deterministic.
In the interview
Each stock has an order book with bids in a max-heap and asks in a min-heap, first in first out within a price. A matching engine processes one stock's orders in sequence on a single thread: an incoming order fills against the best opposite prices while they cross, and any remainder rests in the book. Every order is logged first, so the book can be rebuilt.
Part of Unit 7: Low-level design questions in the free System Design course.