Design an order matching engine

01The design, in the six-step framework

1. Requirements and use cases

A matching engine keeps a book of resting orders for one instrument and crosses incoming orders against it. Correctness here is the order of events: price first, then time.

• A trader submits a limit order (side, price, quantity) and gets an order id.
• The engine matches an incoming buy against the lowest asks (and a sell against the highest bids), filling partially when needed, and rests the remainder.
• A trader cancels a resting order, in O(log n) or better, and cannot cancel a filled one.
• Anyone reads the top of book (best bid, best ask) and the depth at a few levels.
• The engine emits trades with price, quantity and both order ids for downstream consumers.

Out of scope: market and stop orders, multiple instruments, persistence and risk checks. Non-functional constraints: price-time priority must be exact; submit and cancel in logarithmic time; a single engine thread per instrument, so the code is sequential and fast rather than locked.

2. Core entities and relationships

• Order: mutable remaining quantity, immutable price, side and sequence number.
• PriceLevel: a FIFO queue of orders at one price plus the total quantity at that price.
• BookSide: all levels for one side: a heap of prices for best-first access and a map from price to level.
• OrderBook: two sides plus an index from order id to order, for cancels.
• Trade: an immutable event (price, quantity, taker id, maker id, sequence).
• MatchingEngine: processes commands (submit, cancel) in sequence and publishes trades to listeners.

The book composes its sides and levels: they are pure bookkeeping with no life of their own. Orders are aggregated by both a level (for matching order) and the id index (for cancels); the same object is reachable two ways, which is what makes cancel cheap.

3. Interfaces and key methods

class MatchingEngine:
    def submit(self, side: Side, price: int, qty: int) -> Order:
        """Cross against the opposite side while prices allow; rest any remainder. Emits trades in order."""
    def cancel(self, order_id: int) -> bool:
        """Remove a resting order; False if unknown or already filled."""
    def subscribe(self, listener: Callable[[Trade], None]) -> None: ...

class OrderBook:
    def best_bid(self) -> Optional[int]: ...
    def best_ask(self) -> Optional[int]: ...
    def depth(self, levels: int) -> tuple[list[tuple[int, int]], list[tuple[int, int]]]:
        """Top n (price, total_qty) on each side, best first."""

class BookSide:
    def best(self) -> Optional[PriceLevel]:
        """Best non-empty level, lazily discarding emptied prices from the heap."""
    def add(self, order: Order) -> None: ...
    def remove(self, order: Order) -> None: ...

Invariants: within a level the queue is ordered by sequence number; level.total equals the sum of remaining quantities in its queue; the best bid is strictly below the best ask whenever both exist (otherwise a match was missed); and an order is in by_id if and only if it is resting.

4. Design patterns and the choices behind them

Heap of prices plus a map of levels

The engine needs the best price in O(1) and any price in O(1) for cancels. A heap of prices gives best-first access; a dictionary from price to PriceLevel gives direct access. Emptied prices are discarded lazily when they surface at the top of the heap, which avoids an O(n) removal. The rejected alternative is a sorted list with bisect: O(n) inserts, fine for a demo, wrong at market data rates. A balanced tree is the production choice; Python lacks one in the standard library, which is worth saying out loud.

Trades as immutable events

A value object per trade, published through listeners, lets risk, ledgers and market data feeds consume the same stream. The engine never knows who listens, which is the domain event idea applied in one process.

Submit and cancel as commands

Every input is a command stamped with a sequence number. That number is what makes time priority exact and what lets the whole book be rebuilt by replaying the command log after a crash, a follow-up interviewers like.

Deque per level, not a global queue

FIFO within a price is a deque: O(1) pop from the front during matching. Cancelling from the middle of a deque is O(n) at that level, which is acceptable because levels are short; a doubly linked list with node handles is the upgrade if a level can hold thousands of orders.

5. Core flow and code

1. submit creates an Order with the next sequence number.
2. While the order has quantity and the opposite side's best level crosses the price, it pops the front maker order, fills min(remaining), emits a Trade at the maker's price, and removes filled makers.
3. Any remainder is added to its own side's level and indexed by id.
4. cancel looks the order up by id, removes it from its level and the index, and discards the level if empty.

from __future__ import annotations
import heapq
from collections import deque
from dataclasses import dataclass, field
from enum import Enum
from typing import Callable, Optional


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


@dataclass
class Order:
    id: int
    side: Side
    price: int
    remaining: int
    seq: int


@dataclass(frozen=True)
class Trade:
    price: int
    qty: int
    taker_id: int
    maker_id: int
    seq: int


class PriceLevel:
    def __init__(self, price: int) -> None:
        self.price = price
        self.queue: deque[Order] = deque()
        self.total = 0


class BookSide:
    def __init__(self, is_bid: bool) -> None:
        self.is_bid = is_bid
        self.levels: dict[int, PriceLevel] = {}
        self.heap: list[int] = []          # bids store -price so the heap is a max-heap

    def _key(self, price: int) -> int: return -price if self.is_bid else price

    def best(self) -> Optional[PriceLevel]:
        while self.heap:
            price = -self.heap[0] if self.is_bid else self.heap[0]
            level = self.levels.get(price)
            if level and level.queue:
                return level
            heapq.heappop(self.heap)        # stale price: level emptied earlier
            self.levels.pop(price, None)
        return None

    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))
        level.queue.append(order)
        level.total += order.remaining

    def remove(self, order: Order) -> None:
        level = self.levels[order.price]
        level.queue.remove(order)
        level.total -= order.remaining


class OrderBook:
    def __init__(self) -> None:
        self.bids, self.asks = BookSide(True), BookSide(False)
        self.by_id: dict[int, Order] = {}

    def side(self, s: Side) -> BookSide: return self.bids if s is Side.BUY else self.asks
    def opposite(self, s: Side) -> BookSide: return self.asks if s is Side.BUY else self.bids
    def best_bid(self) -> Optional[int]:
        lvl = self.bids.best(); return lvl.price if lvl else None
    def best_ask(self) -> Optional[int]:
        lvl = self.asks.best(); return lvl.price if lvl else None

    def depth(self, n: int) -> tuple[list[tuple[int, int]], list[tuple[int, int]]]:
        def top(side: BookSide) -> list[tuple[int, int]]:
            prices = sorted((p for p, l in side.levels.items() if l.queue), reverse=side.is_bid)[:n]
            return [(p, side.levels[p].total) for p in prices]
        return top(self.bids), top(self.asks)


class MatchingEngine:
    def __init__(self) -> None:
        self.book = OrderBook()
        self.listeners: list[Callable[[Trade], None]] = []
        self.seq = 0

    def subscribe(self, listener: Callable[[Trade], None]) -> None:
        self.listeners.append(listener)

    def _next(self) -> int:
        self.seq += 1
        return self.seq

    def _crosses(self, taker: Order, maker_price: int) -> bool:
        return taker.price >= maker_price if taker.side is Side.BUY else taker.price <= maker_price

    def submit(self, side: Side, price: int, qty: int) -> Order:
        if qty <= 0 or price <= 0:
            raise ValueError("price and quantity must be positive")
        taker = Order(self._next(), side, price, qty, self.seq)
        opp = self.book.opposite(side)
        while taker.remaining > 0:
            level = opp.best()
            if level is None or not self._crosses(taker, level.price):
                break
            maker = level.queue[0]
            fill = min(taker.remaining, maker.remaining)
            taker.remaining -= fill
            maker.remaining -= fill
            level.total -= fill
            trade = Trade(level.price, fill, taker.id, maker.id, self._next())
            for fn in self.listeners:
                fn(trade)
            if maker.remaining == 0:
                level.queue.popleft()
                del self.book.by_id[maker.id]
        if taker.remaining > 0:
            self.book.side(side).add(taker)
            self.book.by_id[taker.id] = taker
        return taker

    def cancel(self, order_id: int) -> bool:
        order = self.book.by_id.pop(order_id, None)
        if order is None:
            return False
        self.book.side(order.side).remove(order)
        return True

6. Extensions, concurrency and what interviewers probe

• Market orders are a taker with an infinite price on its side that never rests; immediate-or-cancel is a taker whose remainder is discarded. Both are flags on submit, not new structures.
• Threading: one engine thread per instrument is the standard answer. Producers enqueue commands on a bounded queue; the engine drains it. Locks inside the book would only slow the hot path, and interviewers want you to say that sequencing, not locking, is what gives determinism.
• Replay: because every command and trade carries a sequence number, the book after a crash is the result of replaying the command log; snapshotting the book every N commands bounds replay time.
• Cancel cost: deque.remove is linear in the level; the upgrade is a linked list per level with the order holding its node, giving O(1) cancel. Mention it before being asked.
• Test first: a buy at 101 against asks at 100 (qty 5) and 101 (qty 5) for quantity 8 produces two trades at 100 and 101 with the maker prices, and leaves 2 resting on the ask at 101; a cancel of a filled id returns false; best bid stays below best ask after every submit.
• Common mistake: trading at the taker's price instead of the maker's. The resting order set the price; the aggressor gets price improvement.

02Where this question was reported

• LLD Mastery · Google-tagged (Medium); price-time priority, order book
• LLD Mastery · Google-tagged with Goldman/Coinbase/Robinhood
• interviewkickstart.com · Interview Kickstart Google list: 'How to design a limit order book for trading systems?'
• LLD Canvas · Focus on the matching engine
• GitHub · Machine coding 'Stock Exchange' (Navi)
• interviewkickstart.com · Weak: listicle