A buy order for 10 shares at ₹102 meets three sellers. It takes 5 shares from the first person who offered ₹101, 3 from the second, and 2 at ₹102, in that order, every time, with no locks inside the matcher at all.
The order book is the heart of every exchange, and a favourite Expert-level machine-coding question: the rules fit on an index card, but the data structures decide whether the code is right and fast. The interviewer listens for three things. Do you know price-time priority cold? Can you state the complexity of each operation? And do you know why a matching engine is usually single-threaded per symbol, and why that makes it simpler, not slower?
This lesson builds it in one process: one side of the book as a hash map of price levels plus a heap, the matching loop, lazy cancels, and a matcher thread per symbol fed by a queue. Prices are integers in ticks (paise here); a float price is the first thing an interviewer will circle.
How the round runs#
"Build a matching engine for one exchange. Traders send limit and market orders and can cancel them. Match them by price-time priority and report trades. Orders can fill partially. I want to know the complexity of every operation. Many clients submit at once. Clearing, settlement, risk checks and market data feeds are out of scope."
- 0–10 min — clarify: order types, market-order leftovers, trade price, cancels
- 10–25 min —
Order,Trade, one side of the book, with complexity - 25–55 min — the matching loop: crossing, partial fills, resting the remainder
- 55–65 min — cancel in O(1), and why it's lazy
- 65–80 min — a matcher thread per symbol; a demo and an eight-thread hammer
- 80–90 min — follow-ups: IOC/FOK, modify, self-trades, recovery
Requirements and clarifying questions#
| You ask | They answer | What it changes |
|---|---|---|
| Which order types? | Limit and market. | OrderType; a market order has no price |
| What does a market order do if the book runs out? | Fill what it can; cancel the rest. | Market orders never rest in the book |
| At what price does a trade happen? | The resting order's price. | The buyer at ₹102 who meets a seller at ₹101 pays ₹101 |
| Who goes first at the same price? | Whoever arrived first. | A FIFO queue per price level |
| Can orders be cancelled? | Yes, any unfilled remainder. | An index from order id to order |
| Modify an order? | Follow-up. | Nothing now (it's cancel + new, losing time priority) |
| How many symbols? | Thousands, independent of each other. | One book and one matcher per symbol |
Price-time priority, by hand
Resting sells: S1 5 @ ₹101 (arrived first), S2 3 @ ₹101 (second), S3 10 @ ₹102. A buy limit order for 10 @ ₹102 arrives. List the trades and what's left in the book.
One strong answer
The buyer crosses everything at ₹101 and ₹102, best price first, and within a price, oldest first:
- 5 @ ₹101 with S1 (best price, earliest)
- 3 @ ₹101 with S2 (same price, later)
- 2 @ ₹102 with S3 (next price level)
The buy order is filled. S3 stays with 8 @ ₹102, keeping its place at the front. Each trade is at the resting order's price: the buyer would have paid ₹102 but paid ₹101 for eight shares.
The classes#
%% title: Order book: the classes
classDiagram
class Order {
+order_id int
+trader str
+side Side
+type OrderType
+qty int
+price int
+seq int
+filled int
+status OrderStatus
}
class Trade {
+trade_id int
+buy_order int
+sell_order int
+price int
+qty int
}
class PriceLevel {
+price int
+orders deque
+total int
}
class BookSide {
-levels dict
-heap list
+add(order)
+best() PriceLevel
+depth(n) list
}
class OrderBook {
+symbol str
+bids BookSide
+asks BookSide
-orders dict
+submit(order) list
+cancel(order_id) bool
}
class Exchange {
-inbox dict
+submit(symbol, trader, side, type, qty, price) int
+cancel(symbol, order_id)
+drain()
}
OrderBook "1" *-- "2" BookSide
BookSide "1" *-- "many" PriceLevel
PriceLevel "1" o-- "many" Order
OrderBook ..> Trade
Exchange "1" *-- "many" OrderBookOne side of the book must find the best price, find the level for a price, and keep arrival order within a level, all fast. So BookSide is three structures:
| Structure | Holds | Gives you |
|---|---|---|
dict[int, PriceLevel] |
price → level | O(1) to find or create a level |
| a heap of prices | every price that has a level (negated for bids) | O(1) to peek at the best price, O(log P) to add or drop a level |
a deque per level |
orders at that price, oldest first | O(1) append at the back, O(1) take from the front |
P is the number of distinct price levels on that side, usually far smaller than the number of orders.
The interfaces#
Orders, trades and prices as integers:
# order_book.py, part 1: orders, trades, and prices as integer ticks
from __future__ import annotations
import heapq
import itertools
import queue
import random
import threading
from collections import Counter, deque
from dataclasses import dataclass, field
from enum import Enum
class Side(Enum):
BUY = "buy"
SELL = "sell"
class OrderType(Enum):
LIMIT = "limit"
MARKET = "market"
class OrderStatus(Enum):
OPEN = "open"
PARTIAL = "partially filled"
FILLED = "filled"
CANCELLED = "cancelled"
@dataclass
class Order:
order_id: int
trader: str
side: Side
type: OrderType
qty: int
price: int | None = None # ticks (paise); None for a market order
seq: int = 0 # arrival number, set by the book: the "time" in price-time priority
filled: int = 0
status: OrderStatus = OrderStatus.OPEN
def __post_init__(self) -> None: # a bad order can't even be built, so the matcher never sees one
if self.qty <= 0:
raise ValueError("quantity must be positive")
if (self.type is OrderType.LIMIT) != (self.price is not None and self.price > 0):
raise ValueError("a limit order needs a positive price; a market order has none")
@property
def remaining(self) -> int:
return self.qty - self.filled
@dataclass(frozen=True)
class Trade:
trade_id: int
buy_order: int
sell_order: int
price: int
qty: int
def px(ticks: int) -> str:
return f"{ticks / 100:.2f}"One side of the book:
# part 2: one side of the book: a dict of price levels, a heap for the best price, a FIFO per level
@dataclass
class PriceLevel:
price: int
orders: deque[Order] = field(default_factory=deque) # oldest first
total: int = 0 # live quantity; a cancelled order stays in the deque until it reaches the front
class BookSide:
def __init__(self, side: Side) -> None:
self.side = side
self.levels: dict[int, PriceLevel] = {}
self._heap: list[int] = [] # best price on top (negated for bids); each key of levels appears once
def _key(self, price: int) -> int:
return -price if self.side is Side.BUY else price # its own inverse: _key(_key(p)) == p
def add(self, order: Order) -> None:
level = self.levels.get(order.price)
if level is None:
level = self.levels[order.price] = PriceLevel(order.price)
heapq.heappush(self._heap, self._key(order.price)) # O(log P), only for a new price
level.orders.append(order) # O(1): time priority within the price
level.total += order.remaining
def best(self) -> PriceLevel | None:
while self._heap:
level = self.levels[self._key(self._heap[0])]
if level.total > 0:
return level # O(1) when the top level is live
heapq.heappop(self._heap) # emptied by fills or cancels: drop it now, O(log P)
del self.levels[level.price]
return None
def depth(self, n: int = 5) -> list[tuple[str, int]]:
prices = sorted((p for p, lv in self.levels.items() if lv.total > 0), reverse=self.side is Side.BUY)
return [(px(p), self.levels[p].total) for p in prices[:n]] # O(P log P): for display, not the hot pathOne invariant keeps the heap and the dict in step: a price is in the heap exactly once while it has a level in the dict. A level emptied by a cancel stays (total 0) until it reaches the top, where best() removes it from both; a new order at that price reuses it.
The matching engine#
- Stamp it with the next sequence number: its place in time
- Take the best opposite level: lowest ask for a buy, highest bid for a sell
- Does it cross? Buy price ≥ ask, or sell price ≤ bid; a market order always crosses
- Trade
min(both remainders)at the resting price with the oldest order there - Repeat until filled or nothing crosses
- Leftovers: a limit order rests; a market order's remainder is cancelled
# part 3: the matching engine for one symbol. Single-threaded by design: no locks inside
class OrderBook:
def __init__(self, symbol: str) -> None:
self.symbol = symbol
self.bids, self.asks = BookSide(Side.BUY), BookSide(Side.SELL)
self.orders: dict[int, Order] = {} # resting orders by id, for O(1) cancel
self.trades: list[Trade] = []
self.processed = 0
self._seq = itertools.count(1)
self._trade_ids = itertools.count(1)
def submit(self, order: Order) -> list[Trade]:
order.seq = next(self._seq)
self.processed += 1
opposite = self.asks if order.side is Side.BUY else self.bids
trades: list[Trade] = []
while order.remaining and (level := opposite.best()) and self._crosses(order, level.price):
maker = level.orders[0]
if maker.status is OrderStatus.CANCELLED:
level.orders.popleft() # a lazily cancelled order reached the front: drop it, O(1)
continue
trades.append(self._fill(order, maker, level, min(order.remaining, maker.remaining)))
if order.remaining:
if order.type is OrderType.LIMIT:
(self.bids if order.side is Side.BUY else self.asks).add(order)
self.orders[order.order_id] = order
else:
order.status = OrderStatus.CANCELLED # a market order never rests: the unfilled part is cancelled
self.trades.extend(trades)
return trades
@staticmethod
def _crosses(order: Order, price: int) -> bool:
if order.type is OrderType.MARKET:
return True
return order.price >= price if order.side is Side.BUY else order.price <= price
def _fill(self, taker: Order, maker: Order, level: PriceLevel, qty: int) -> Trade:
for o in (taker, maker):
o.filled += qty
o.status = OrderStatus.FILLED if o.remaining == 0 else OrderStatus.PARTIAL
level.total -= qty
if maker.remaining == 0:
level.orders.popleft()
del self.orders[maker.order_id]
buy, sell = (taker, maker) if taker.side is Side.BUY else (maker, taker)
return Trade(next(self._trade_ids), buy.order_id, sell.order_id, level.price, qty) # at the resting price
def cancel(self, order_id: int) -> bool:
order = self.orders.pop(order_id, None)
if order is None:
return False # unknown, already filled, or already cancelled
order.status = OrderStatus.CANCELLED
side = self.bids if order.side is Side.BUY else self.asks
side.levels[order.price].total -= order.remaining # O(1); the order leaves the deque when it reaches the front
return TrueWhy cancel is lazy. Removing from the middle of a deque is O(n). Instead, cancel marks the order, takes its quantity off the level total and drops it from the index, all O(1); the dead order is popped when it reaches the front, also O(1). The alternative, a doubly linked list per level with the node in the index, gives O(1) cancel with no dead entries; say both and pick one.
| Operation | Cost | Why |
|---|---|---|
| Add a limit order that doesn't cross, existing price | O(1) | dict lookup + deque append |
| Add at a new price | O(log P) | one heap push |
| Cancel | O(1) | index pop + level total; the dead entry is skipped later in O(1) |
| Best bid / best ask | O(1) amortised | heap peek; each emptied level costs one O(log P) pop, once |
| Match an order that makes F fills across L levels | O(F + L log P) | each fill is O(1); each level it empties is one heap pop |
| Top-n depth for display | O(P log P) here | sorts live levels; a sorted map would make it O(n) |
The patterns, and why#
| Pattern | Where | Why it earns its place |
|---|---|---|
| Single writer | one OrderBook per symbol, touched only by its matcher |
No locks, and the same input always gives the same trades. Symbols scale out across threads. |
| Command queue | Exchange._inbox |
The only synchronised object, and the natural place to log input for replay. |
| Lazy deletion | cancelled orders, empty levels | O(1) cancels, no search through a level or the heap. |
| Value objects | Trade, integer prices |
Trades are immutable facts; ticks make equality exact. |
Concurrency and edge cases#
The book is never shared. Gateway threads validate an order, give it an id (from a counter behind a small lock) and put a command on the symbol's queue. One matcher thread per symbol runs those commands one at a time. Two symbols never interact, so they run in parallel; one symbol is sequential, which price-time priority needs anyway: someone has to decide who was first, and the queue does.
- A market order into an empty book: no trades, cancelled at once; many venues add a price-protection limit instead
- Cancel of a filled or unknown order: return
False, never raise; fills and cancels race - Cancel of a partly filled order: only the remainder leaves the level total
- Prices off the tick size: reject at the gateway, before the queue
- A trader matching their own order: allowed here; self-trade prevention is a follow-up
- The matcher thread dies: supervise it, and rebuild the book by replaying logged commands
The code#
The exchange: a queue and a matcher thread per symbol.
# part 4: one matcher thread per symbol; any number of gateway threads feed it through a queue
class Exchange:
def __init__(self, symbols: list[str]) -> None:
self.books = {s: OrderBook(s) for s in symbols}
self._inbox: dict[str, queue.Queue[tuple[str, object]]] = {s: queue.Queue() for s in symbols}
self._ids = itertools.count(1)
self._id_lock = threading.Lock() # several gateway threads issue ids
self._workers = [threading.Thread(target=self._run, args=(s,), daemon=True) for s in symbols]
for w in self._workers:
w.start()
def submit(self, symbol: str, trader: str, side: Side, type_: OrderType, qty: int, price: int | None = None) -> int:
with self._id_lock:
oid = next(self._ids)
self._inbox[symbol].put(("new", Order(oid, trader, side, type_, qty, price))) # validates on construction
return oid
def cancel(self, symbol: str, order_id: int) -> None:
self._inbox[symbol].put(("cancel", order_id))
def drain(self) -> None:
for q in self._inbox.values():
q.join() # wait until every queued command has been matched
def _run(self, symbol: str) -> None:
book, inbox = self.books[symbol], self._inbox[symbol]
while True:
kind, arg = inbox.get()
try:
if kind == "new":
book.submit(arg) # type: ignore[arg-type]
elif kind == "cancel":
book.cancel(arg) # type: ignore[arg-type]
finally:
inbox.task_done()The interviewer's sequence, then the hammer:
# part 5: the checkpoint's trades, a cancel, a market order, then eight gateway threads
if __name__ == "__main__":
book = OrderBook("ABC")
ids = itertools.count(1)
def order(trader: str, side: Side, qty: int, price: int | None = None) -> Order:
return Order(next(ids), trader, side, OrderType.LIMIT if price else OrderType.MARKET, qty, price)
s1, s2, s3 = order("s1", Side.SELL, 5, 10100), order("s2", Side.SELL, 3, 10100), order("s3", Side.SELL, 10, 10200)
for o in (s1, s2, s3, order("b1", Side.BUY, 4, 9900)):
book.submit(o)
print("asks:", book.asks.depth(), "bids:", book.bids.depth())
big = order("b2", Side.BUY, 10, 10200)
print("trades:", [(t.sell_order, t.qty, px(t.price)) for t in book.submit(big)])
print("buyer:", big.status.value, "| s3:", s3.status.value, s3.remaining, "| asks:", book.asks.depth())
print("cancel b1:", book.cancel(4), "| again:", book.cancel(4), "| bids:", book.bids.depth())
book.submit(order("b3", Side.BUY, 6, 10000))
book.submit(order("b4", Side.BUY, 2, 10000))
book.cancel(6) # b3 cancelled while it sits at the front of the 100.00 level
mkt = order("m1", Side.SELL, 20)
fills = book.submit(mkt)
print("market sell 20:", [(t.buy_order, t.qty, px(t.price)) for t in fills], "->", mkt.status.value, mkt.remaining, "unfilled")
ex = Exchange(["ABC", "XYZ"])
sent: Counter[tuple[str, Side]] = Counter() # shares sent per (symbol, side)
sent_lock = threading.Lock()
def gateway(seed: int) -> None:
rng, mine = random.Random(seed), Counter()
for _ in range(1000):
sym, side, qty = rng.choice(["ABC", "XYZ"]), rng.choice([Side.BUY, Side.SELL]), rng.randint(1, 10)
ex.submit(sym, f"t{seed}", side, OrderType.LIMIT, qty, rng.randint(9_950, 10_050))
mine[(sym, side)] += qty
with sent_lock:
sent.update(mine)
ts = [threading.Thread(target=gateway, args=(i,)) for i in range(8)]
for t in ts:
t.start()
for t in ts:
t.join()
ex.drain()
print("orders matched:", sum(b.processed for b in ex.books.values()))
for sym, b in ex.books.items():
bid, ask = b.bids.best(), b.asks.best()
traded = sum(t.qty for t in b.trades)
resting = {sd: sum(lv.total for lv in side.levels.values()) for sd, side in ((Side.BUY, b.bids), (Side.SELL, b.asks))}
conserved = all(sent[(sym, sd)] == traded + resting[sd] for sd in (Side.BUY, Side.SELL))
print(f"{sym}: crossed={bid is not None and ask is not None and bid.price >= ask.price}, every share accounted for={conserved}")asks: [('101.00', 8), ('102.00', 10)] bids: [('99.00', 4)]
trades: [(1, 5, '101.00'), (2, 3, '101.00'), (3, 2, '102.00')]
buyer: filled | s3: partially filled 8 | asks: [('102.00', 8)]
cancel b1: True | again: False | bids: []
market sell 20: [(7, 2, '100.00')] -> cancelled 18 unfilled
orders matched: 8000
ABC: crossed=False, every share accounted for=True
XYZ: crossed=False, every share accounted for=TrueThe second line is the checkpoint, computed. Cancelling b1 twice returns True, then False. The market sell meets cancelled order 6 at the front of the 100.00 level, drops it, fills order 7's 2 shares, and cancels the other 18. The hammer's 8,000 orders are all matched, neither book is crossed, and for each symbol and side the shares sent equal the shares traded plus the shares resting.
Extending it: the follow-ups#
- "Add IOC and FOK." Immediate-or-cancel is a limit order that never rests, like a market order's leftovers. Fill-or-kill first walks the levels to check the whole quantity is available, then matches or rejects. A
time_in_forcefield and a few lines insubmit. - "Let traders modify an order." Reducing quantity can keep time priority; a new price or a bigger quantity is cancel plus new, at the back of the queue. That's a fairness rule; say it.
- "Prevent self-trades." Before filling, compare traders and apply a policy (cancel the resting order, the incoming one, or both): a strategy inside the loop.
- "What if the process dies?" Log every command before matching it. Because the matcher is single-threaded and deterministic, replaying the log rebuilds the same book and trades; snapshots shorten the replay.
- "Make depth O(n)." Replace the heap with a sorted structure (a balanced tree or skip list), or, for a narrow price band, an array indexed by tick.
Common mistakes#
- Floats for prices, so 101.1 + 0.1 doesn't equal 101.2 and levels split in two
- A sorted list of all orders, re-sorted on every insert: O(n log n) where O(1) or O(log P) is available
- Trading at the incoming order's price instead of the resting order's
- Removing a cancelled order by scanning the level, which is O(n) in a busy level
- A lock around the book and many matcher threads, so the order of events depends on the scheduler
- Letting a market order rest in the book with no price
Order book
Q1/3 Asks: 5 @ 101 (first), 3 @ 101 (second), 10 @ 102. A buy limit 10 @ 102 arrives. What are the trades?
Answer & explanation
Answer: C
Price first, then time within a price, at the resting order's price. Each resting order is a separate trade.
Q2/3 Why is cancel O(1) here when removing from the middle of a deque is O(n)?
Answer & explanation
Answer: B
Lazy deletion. The order leaves the index and the level total at once, and the deque when it reaches the front, where popleft is O(1).
Q3/3 Why run one matcher thread per symbol instead of a lock and many threads?
Answer & explanation
Answer: D
Price-time priority needs one order of arrival anyway. A queue per symbol provides it, and the same input always produces the same trades, which makes replay-based recovery possible.
New lessons by email
New lessons, side quests and case files as they ship, at most once a week. No spam, unsubscribe anytime.
Discussion · …
Public: everyone reading this lesson sees comments. Be kind and keep it on the material.