Courses › Low-Level Design › Problem Walkthroughs

Design a Stock Order Book

Price-time priority, partial fills, lazy cancels and the invariants trading firms check.

"Design a stock exchange order book" is a common LLD question at trading firms, fintech companies and some big tech teams. It tests choosing the right data structures (fast access to the best price, and first come, first served within a price), precise matching rules, and careful handling of partial fills and cancels. It's a compact problem with very little room for sloppiness.

Requirements

  • Accept limit orders: buy or sell, a price, a quantity, and an order ID.
  • Match an incoming order against the opposite side at the best prices, following price-time priority: a better price matches first, and at the same price, the earlier order matches first.
  • Support partial fills. Whatever's left of an order rests on the book.
  • Cancel an order by ID.
  • Report the trades, and the best bid and best ask.
  • Extras: market orders, modify (cancel and replace), immediate-or-cancel orders.

Choosing the data structures

Side (Enum)        BUY, SELL
Order              id, side, price, qty (remaining), seq
Trade              buy_id, sell_id, price, qty
PriceLevel         price, deque of orders
OrderBook          levels per side, price heaps per side, orders by id
                   submit(order) -> list[Trade], cancel(order_id), best_bid(), best_ask()

Matching rules

  • An incoming buy at price P matches resting sells priced at or below P, starting from the lowest.
  • The trade happens at the resting order's price. The order that was already on the book sets the price.
  • Each trade fills min(incoming.qty, resting.qty). A fully filled resting order leaves the queue.
  • Anything left of the incoming order rests on the book at its own price.

Implementation

import heapq
import itertools
from collections import deque
from dataclasses import dataclass
from enum import Enum


class Side(Enum):
    BUY = "buy"
    SELL = "sell"


@dataclass
class Order:
    id: str
    side: Side
    price: int          # integer ticks, never floats
    qty: int
    seq: int = 0
    cancelled: bool = False


@dataclass(frozen=True)
class Trade:
    buy_id: str
    sell_id: str
    price: int
    qty: int


class OrderBook:
    def __init__(self):
        self.levels = {Side.BUY: {}, Side.SELL: {}}     # price -> deque[Order]
        self.heaps = {Side.BUY: [], Side.SELL: []}      # bids stored negated (max-heap)
        self.orders = {}
        self._seq = itertools.count()

    def _key(self, side, price):
        return -price if side is Side.BUY else price

    def _best_level(self, side):
        """Best non-empty price level on `side`, dropping stale heap entries."""
        heap, levels = self.heaps[side], self.levels[side]
        while heap:
            price = abs(heap[0])
            q = levels.get(price)
            while q and (q[0].cancelled or q[0].qty == 0):
                q.popleft()                              # lazy removal of cancelled orders
            if q:
                return price, q
            heapq.heappop(heap)
            levels.pop(price, None)
        return None, None

    def best_bid(self):
        return self._best_level(Side.BUY)[0]

    def best_ask(self):
        return self._best_level(Side.SELL)[0]

    def submit(self, order):
        if order.qty <= 0 or order.price <= 0 or order.id in self.orders:
            raise ValueError("invalid order")
        order.seq = next(self._seq)
        trades = []
        opposite = Side.SELL if order.side is Side.BUY else Side.BUY
        while order.qty:
            price, q = self._best_level(opposite)
            if price is None:
                break
            crosses = price <= order.price if order.side is Side.BUY else price >= order.price
            if not crosses:
                break
            resting = q[0]
            fill = min(order.qty, resting.qty)
            order.qty -= fill
            resting.qty -= fill
            buy, sell = (order, resting) if order.side is Side.BUY else (resting, order)
            trades.append(Trade(buy.id, sell.id, price, fill))   # at the resting price
            if resting.qty == 0:
                q.popleft()
                del self.orders[resting.id]
        if order.qty:                                     # rest the remainder
            levels = self.levels[order.side]
            if order.price not in levels:
                levels[order.price] = deque()
                heapq.heappush(self.heaps[order.side], self._key(order.side, order.price))
            levels[order.price].append(order)
            self.orders[order.id] = order
        return trades

    def cancel(self, order_id):
        order = self.orders.pop(order_id, None)
        if order is None:
            return False
        order.cancelled = True                            # removed lazily when reached
        return True
book = OrderBook()
book.submit(Order("s1", Side.SELL, 101, 5))
book.submit(Order("s2", Side.SELL, 100, 5))
book.submit(Order("s3", Side.SELL, 100, 5))            # same price, later than s2
trades = book.submit(Order("b1", Side.BUY, 101, 12))
assert [(t.sell_id, t.price, t.qty) for t in trades] == [("s2", 100, 5), ("s3", 100, 5), ("s1", 101, 2)]
assert book.best_ask() == 101 and book.best_bid() is None
book.cancel("s1")
assert book.best_ask() is None

Design decisions to explain

  • Integer ticks for prices. Floats make equal prices compare as unequal.
  • The resting order sets the trade price. It's a standard rule, and interviewers check for it.
  • Lazy cancellation: marking an order cancelled is O(1), and the matcher skips it later. Removing it from the middle of a deque would be O(n). A doubly linked list per level gives O(1) removal too, and that's what production systems use.
  • Determinism: a single thread processes all orders for one instrument, in arrival order. Real exchanges run one sequential matcher per instrument rather than using locks, which also makes the book easy to replay.

[!INTERVIEW] State the invariants "The book is never crossed: the best bid is always below the best ask after matching. Within a price level, orders are in arrival order. Quantities are never negative." Writing these down, and asserting them in a test, signals exactly the rigor trading firms look for.

Follow-ups

  • Market orders: match at any price until the order is filled or the book is empty. Never rest the remainder.
  • Immediate-or-cancel / fill-or-kill: IOC drops the remainder. FOK first checks whether enough quantity is available at acceptable prices, then matches all of it or nothing.
  • Modify: a quantity decrease keeps the order's time priority. A price change or a quantity increase means cancel and resubmit, so it loses its priority.
  • Market data: publish the top-of-book and depth changes to observers. See Design a Market Data Feed.
  • Scale: see Design a Stock Exchange for sequencing, replay and fault tolerance.

[!TIP] Practice Design a Stock Exchange Order Book · Design an Online Auction · Heaps & Top-K