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

Non-functional requirements

From version 1 to the final design

  1. Version 1: one list of orders, scanned for a match every time (slow).
  2. Version 2: buy and sell heaps ordered by price, first in first out at each price.
  3. Version 3: partial fills, cancels and market orders.
  4. Version 4: one single-threaded engine per stock, fed by a queue, with an event log for replay.

The design, step by step

  1. 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.
  2. Any quantity left over rests in the book.
  3. 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

Common mistakes

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.