Stock Exchange Order Matching System Design

By /

Core Concepts

A stock exchange at its core is a system that matches buyers and sellers. The central data structure is the order book: a list of all open (unfilled) buy and sell orders for a given security.

  • Bid: The highest price a buyer is willing to pay.
  • Ask: The lowest price a seller is willing to accept.
  • Spread: The difference between ask and bid. On liquid stocks this is 1 cent; on illiquid stocks it can be dollars.
  • Matching engine: The component that pairs buy and sell orders when their prices overlap.

When a new order arrives, the matching engine checks if it can be immediately filled against existing orders. If not, it joins the order book and waits.

Order Types

  • Market order: Execute immediately at the best available price. Guarantees execution, not price. Can result in unexpected prices during volatile markets.
  • Limit order: Execute only at the specified price or better (buy at $50 or less; sell at $50 or more). Guarantees price, not execution. Joins the order book if not immediately matchable.
  • Stop order: Inactive until the market price crosses a trigger price. Becomes a market or limit order when triggered. Used for stop-loss protection.
  • Stop-limit order: Becomes a limit order (not market) when the stop price is hit. Does not guarantee execution if market moves past the limit price.

Order Book Data Structure

The order book needs fast operations: insert new order, cancel existing order, find best bid/ask, match against best orders. The standard implementation:

  • Bids side: Sorted descending by price. At each price level, a deque (FIFO queue) of orders at that price.
  • Asks side: Sorted ascending by price. Same structure per level.
  • Implementation: A sorted dictionary (TreeMap in Java, sortedcontainers.SortedDict in Python) keyed by price. Each value is a deque of Order objects.

Complexity:

  • Insert: O(log n) to find or create price level, O(1) to append to deque.
  • Cancel: O(log n) to find price level, O(1) with order ID -> deque reference map. Remove empty price levels after cancellation.
  • Best bid/ask: O(1) – peek at first/last key of the sorted dict.
  • Match: O(k log n) where k is the number of price levels consumed.

Price-Time Priority

When multiple orders exist at the same price, exchanges use price-time priority (also called FIFO matching):

  • Price priority: Better-priced orders execute first. A sell order at $99 fills before one at $100.
  • Time priority: Among orders at the same price, earlier orders fill first. If two sellers both want $99, the one who placed the order first gets matched first.

This is why the per-price-level data structure is a deque (FIFO), not an unordered set. Time priority incentivizes market makers to post orders early.

Matching Algorithm

When a new buy limit order arrives at price P with quantity Q:

  • While Q > 0 and the best ask price <= P:
  • Get the oldest order at the best ask price level.
  • Fill quantity = min(Q, ask_order.remaining_qty).
  • Generate a Trade record: (buy_order_id, ask_order_id, price=ask_price, quantity=fill_qty).
  • Decrease Q and ask_order.remaining_qty by fill_qty.
  • If ask_order is fully filled, remove it from the deque (and remove the price level if empty).
  • If Q > 0 after the loop, add the remaining buy order to the bids side at price P.

For market orders: P = infinity for buys, P = 0 for sells (match against anything available). Market orders never rest in the book.

Order States

Order lifecycle with quantities:

  • OPEN: Order placed, filled_qty = 0, remaining_qty = original_qty.
  • PARTIALLY_FILLED: 0 < filled_qty < original_qty. Still active in the order book.
  • FILLED: filled_qty = original_qty. Removed from order book.
  • CANCELLED: Removed before fully filled. final_filled_qty may be > 0 if partially filled before cancellation.
  • REJECTED: Never entered the book (invalid price, insufficient account balance, etc.).

Database Schema

CREATE TABLE orders (
    id           BIGINT PRIMARY KEY,
    symbol       VARCHAR(10) NOT NULL,
    side         ENUM('BUY', 'SELL') NOT NULL,
    type         ENUM('MARKET', 'LIMIT', 'STOP', 'STOP_LIMIT') NOT NULL,
    price        DECIMAL(12,4),          -- null for market orders
    stop_price   DECIMAL(12,4),          -- for stop orders
    quantity     INT NOT NULL,
    filled_qty   INT NOT NULL DEFAULT 0,
    status       ENUM('OPEN','PARTIALLY_FILLED','FILLED','CANCELLED','REJECTED'),
    account_id   BIGINT NOT NULL,
    created_at   TIMESTAMP(6) NOT NULL,  -- microsecond precision
    updated_at   TIMESTAMP(6) NOT NULL
);

CREATE TABLE trades (
    id             BIGINT PRIMARY KEY,
    symbol         VARCHAR(10) NOT NULL,
    buy_order_id   BIGINT NOT NULL REFERENCES orders(id),
    sell_order_id  BIGINT NOT NULL REFERENCES orders(id),
    price          DECIMAL(12,4) NOT NULL,
    quantity       INT NOT NULL,
    executed_at    TIMESTAMP(6) NOT NULL
);

CREATE INDEX idx_orders_symbol_status ON orders(symbol, status);
CREATE INDEX idx_trades_symbol_time   ON trades(symbol, executed_at);

Settlement

Trade execution and settlement are separate events:

  • T+0 (trade date): Match occurs, trade record created, both parties notified.
  • T+2 (settlement date): Actual transfer of cash and shares. Standard for US equities (moved from T+3 in 2017, T+2 in 2017, T+1 proposed for 2024).
  • Clearing house: Acts as counterparty to both buyer and seller (novation). If the buyer defaults, the clearing house still pays the seller, and vice versa. This eliminates bilateral counterparty risk. The clearing house manages this risk via margin requirements.
  • DTCC: Depository Trust and Clearing Corporation handles most US equity clearing and settlement.

Performance Requirements

High-frequency trading demands extreme performance:

  • NYSE order processing: ~10 microseconds latency. NASDAQ: ~70 microseconds. Compare to typical web app: 10-100 milliseconds.
  • In-memory order book: The hot path never touches a database. The order book lives entirely in RAM. Database writes happen asynchronously for audit and recovery purposes.
  • Per-symbol threads: Each traded symbol gets its own matching thread. No cross-symbol locking. Apple (AAPL) matching never blocks Amazon (AMZN) matching.
  • Lock-free data structures: For the highest performance, use compare-and-swap (CAS) operations instead of mutexes. Avoids thread scheduling overhead.
  • Network: Co-location – HFT firms pay exchanges to place their servers in the same data center as the matching engine, eliminating network latency.

For a system design interview, the key architectural decision is separating the in-memory hot path (matching engine) from the persistent storage path (audit log, position tracking). The matching engine is single-threaded per symbol for simplicity and performance – no locking needed within a symbol’s order book.

{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How does an order matching engine work?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The matching engine maintains an order book per trading symbol: bids (buy orders) sorted by price descending, then time ascending; asks (sell orders) sorted by price ascending, then time ascending. When a new buy order arrives: check if the lowest ask price <= buy price. If yes, match: fill min(buy_qty, ask_qty) units at the ask price, generate a trade, decrement quantities. Repeat until the buy order is filled or no more matchable asks. The reverse for sell orders. Price-time priority (FIFO at each price level) ensures fairness: among equal-priced orders, earlier submissions get priority. The data structure is a sorted map from price to deque of orders, enabling O(log n) insertion and O(1) access to the best bid/ask.”}},{“@type”:”Question”,”name”:”What is the difference between market and limit orders?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A market order executes immediately at the best available price, regardless of what that price is. It is guaranteed to fill (as long as there are counterparty orders) but the execution price is unknown. Used when speed of execution matters more than price. A limit order specifies a maximum price (for buys) or minimum price (for sells). It only executes at that price or better. If no matching counterparty exists at the limit price, the order rests in the order book until matched or cancelled. Limit orders provide price certainty but not execution certainty. Most algorithmic trading uses limit orders to control execution cost; retail market orders prioritize certainty of execution.”}},{“@type”:”Question”,”name”:”How do you store an order book efficiently for fast matching?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use a sorted dictionary (TreeMap in Java, SortedDict in Python) from price to a deque of orders at that price. Bids: max-heap semantics (highest price first). Asks: min-heap semantics (lowest price first). Operations: insert order at a price level O(log n), add to deque O(1). Remove filled order from front of deque O(1). Remove cancelled order requires O(1) deque removal if you maintain a direct reference to the deque node (doubly linked list). Cancel is the hardest operation – use a hash map from order_id to order object to find the order quickly, then remove from its price level deque. This gives O(1) cancel with O(log n) for rare price level cleanup when a level becomes empty.”}},{“@type”:”Question”,”name”:”How does a stock exchange achieve microsecond-level latency?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Five techniques: (1) In-memory order book – never touch disk on the matching hot path. (2) Per-symbol thread or process – each symbol's order book is handled by a single thread, eliminating lock contention between symbols. (3) Lock-free data structures – use CAS (compare-and-swap) operations instead of mutexes for the input queue. (4) CPU affinity – pin matching threads to specific CPU cores, preventing context switching and cache evictions. (5) Kernel bypass networking – use DPDK or RDMA to receive network packets directly into user space, bypassing the OS kernel network stack (saves 2-5 microseconds per packet). FPGA-based matching engines (used by the fastest exchanges) push latency to nanoseconds by implementing matching logic in hardware.”}},{“@type”:”Question”,”name”:”What is T+2 settlement and why does it exist?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”T+2 (Trade plus 2 business days) means that when you buy a stock today, the cash leaves your account and shares arrive 2 business days later. This delay exists for operational reasons: clearance (verifying that both parties have what they are exchanging), netting (aggregating thousands of trades to minimize actual transfers), and settlement (the actual exchange of cash and securities). A central counterparty clearing house (CCP) interposes itself as the buyer to every seller and seller to every buyer, eliminating counterparty risk. The CCP requires margin from both parties as collateral. The industry is moving toward T+1 (implemented in US equities in 2024) and eventually T+0 for cryptocurrency-style instant settlement. For crypto, settlement is near-instant as blockchain state is the definitive record.”}}]}

Robinhood system design covers order matching and trade execution. See design patterns for Robinhood interview: stock exchange and matching engine design.

Coinbase builds a crypto exchange. See order matching and settlement design patterns for Coinbase interview: exchange and order book system design.

Stripe system design covers financial settlement and transaction processing. See patterns for Stripe interview: financial transaction and settlement design.

Scroll to Top