system-design

Design a Stock Exchange / Trading System

Difficulty: Tier 3 Asked at: trading firms, Amazon, fintechs, senior loops Time budget: 45–60 min

A stock exchange is the most latency- and correctness-critical system in this repo: microseconds matter, ordering is sacred, and a wrong match means real money moved wrongly. It inverts almost every assumption elsewhere — here you often want a single fast in-memory matching engine, not a sprawling distributed system, because determinism and latency beat horizontal scale. The signature idea is the matching engine + order book, and the theme is determinism, ordering, and latency.

Prerequisites: Concurrency, Design Payment System, Consensus / Replication

1. Requirements

Functional:

Accept orders (buy/sell, limit/market, quantity, price).
Match buy and sell orders per price-time priority; execute trades.
Maintain the order book (resting buy/sell orders by price).
Publish market data (quotes, trades) to participants.
Cancel/modify orders.

Non-functional:

Ultra-low latency & determinism — matching in microseconds; identical inputs → identical outputs.
Correctness & fairness — strict price-time priority; no order jumps the queue.
Ordering — a total order of events is the ballgame (who was first matters, literally).
Durability & auditability — every order/trade recorded (regulatory).
High availability without sacrificing determinism.

Out of scope: clearing/settlement details, brokerage UI, the pre-trade risk internals (mention).

2. Why this inverts the usual playbook

🚨 Most designs in this repo scale out (many nodes, eventual consistency). A matching engine scales up and stays single-threaded and in-memory on purpose:

Matching must be deterministic — a total order of orders, processed one at a time, so the result is reproducible and auditable. Concurrency/distribution introduces nondeterminism you can’t have.
Latency budget is microseconds — a network hop or a lock is an eternity. Keep the order book in memory, process on one core, avoid coordination.
🚨 The insight: for the matching core, a single fast deterministic engine beats a distributed one. Distribution is used for redundancy (replicas), not for splitting the match.

3. The core: the matching engine & order book

Order book: resting orders, organized by price level, and within a price by time (first-come). Two sides: bids (buys, sorted high→low) and asks (sells, sorted low→high).

ASKS (sells)         BIDS (buys)
101.5  x300          100.0  x200
101.0  x150          99.5   x400
100.5  x100  ← best  99.0   x100  ← best bid
             ask

Matching: a new incoming order matches against the best opposite price. A buy at ≥ best ask executes against it (price-time priority: oldest order at that price first). Partial fills, then the remainder rests in the book. 🚨 Price-time priority processed in a strict sequence is the heart — implemented with sorted price levels + FIFO queues per level (often a heap/tree of price levels).

flowchart LR
    In[Incoming orders] --> Seq[Sequencer<br/>assigns total order]
    Seq --> ME[Matching Engine<br/>single-threaded, in-memory order book]
    ME --> Trades[Trade executions]
    ME --> MD[Market data feed]
    Seq --> Log[(Durable ordered log)]
    Log -.replicate.-> Backup[Hot standby engines]

4. Deep dives

4a. Determinism via a sequenced input log

🚨 All orders pass through a sequencer that assigns a strict total order and writes them to a durable log before matching. The matching engine consumes this ordered log deterministically. Because the input order is fixed and the engine is deterministic, replaying the log reproduces the exact same trades — essential for audit, recovery, and replicas. This is event sourcing applied to trading: the ordered order-log is the source of truth; the order book is a derived, replayable view.

4b. High availability without losing determinism

You can’t have two engines matching independently (they’d diverge). Instead: hot standby replicas consume the same sequenced log and stay in lockstep; on primary failure, a standby (already at the same state) takes over. Consensus/replication ensures the log is durable and agreed before matching. 🚨 Replicate the input log, not the matching decision — every replica deterministically derives the same book. (Consensus)

4c. Latency engineering

Microseconds demand unusual techniques (name a few to show awareness): everything in memory, single- threaded hot path (no locks), kernel-bypass networking, cache-friendly data structures, colocated servers, minimal GC/allocation. The design goal is a short, predictable, jitter-free path from order-in to match-out. This is the opposite of the “just add servers” reflex.

4d. Market data fan-out

Every match updates the book; participants need the feed fast and fairly (no one gets it earlier). The engine emits a stream of book updates/trades, fanned out to many subscribers via a fast multicast/streaming layer — decoupled from matching so publishing doesn’t slow the hot path. Fairness (equal-latency delivery) is a real concern.

4e. Durability, audit & recovery

The sequenced log is persisted (and replicated) → complete audit trail and crash recovery (replay the log to rebuild the book). Regulators require every order/cancel/trade recorded immutably. Order state transitions (new → partially filled → filled/cancelled) are all derived from the log.

4f. Pre-trade risk & validation

Before an order hits the book, validate (does the account have funds/shares, within limits?). Done at the gateway before sequencing to keep the matching hot path pure. Reject fast.

5. Bottlenecks & scaling further

Latency → in-memory single-threaded engine, kernel bypass, colocation, no locks/GC on the hot path.
Determinism → sequenced input log; engine as a pure function of the log.
HA → hot standbys consuming the same log; failover to an in-sync replica.
Throughput → partition by symbol (each stock’s book is independent → separate engine), scaling across symbols while each symbol stays single-threaded.
Market data → decoupled fast fan-out layer.

6. Trade-off summary

Decision	Chosen	Alternative	Why
Matching core	Single-threaded, in-memory	Distributed/parallel	Determinism + microsecond latency
Source of truth	Sequenced ordered log	Mutable book only	Replay, audit, deterministic recovery
HA	Standbys replay same log	Active-active matching	Independent matching would diverge
Scale-out axis	By symbol	Split one book	Each symbol’s book is independent
Risk checks	At gateway, pre-sequencing	In the engine	Keep the matching hot path pure

7. Follow-up questions

Why is a single-threaded, in-memory matching engine better than a distributed one here?

Because a stock exchange's hardest requirements are determinism, strict ordering, and microsecond latency — and distribution works against all three. Matching must be deterministic and reproducible: given the same sequence of orders, it must always produce the same trades, for auditability, recovery, and keeping replicas consistent. Processing orders one at a time on a single thread over an in-memory order book gives you exactly that — a well-defined total order with no concurrency nondeterminism and no locks. It's also the fastest: the latency budget is microseconds, so a network hop, a lock, or cross-node coordination is unaffordable, and keeping the whole book in memory on one core with a short, jitter-free code path is what hits it. Distributing the match across nodes would introduce coordination, nondeterministic interleavings, and latency, buying you horizontal scale you don't need for one symbol's book (which fits in memory and one core easily). So you scale *up* and stay deterministic for the matching core, and use distribution only for redundancy (replicas) and across independent symbols — the exact inversion of the usual scale-out playbook.

How do you make the system both deterministic and highly available?

By separating the ordered input from the matching computation and replicating the input, not the decision. All orders flow through a sequencer that assigns a strict total order and writes them to a durable, replicated log before any matching happens. The matching engine is a deterministic function of that log — it consumes the ordered stream and produces trades. For availability, hot-standby engines consume the very same sequenced log and stay in lockstep with the primary, so at any moment a standby has derived the identical order book; if the primary fails, a standby that's already at the same state takes over with no divergence and no lost trades. Consensus/replication guarantees the log is durably agreed before matching proceeds. The key idea is that you replicate the agreed sequence of inputs and let every replica deterministically compute the same output, rather than having multiple engines make matching decisions independently (which would diverge). This is event sourcing applied to trading: the ordered log is the source of truth, the book is a replayable derived view.

What does price-time priority mean and how is the order book structured to enforce it?

Price-time priority is the fairness rule that determines which resting order an incoming order matches against: better-priced orders match first, and among orders at the same price, the one that arrived earliest matches first (first-come, first-served at each price level). It's enforced by structuring the order book as sorted price levels for each side — bids descending, asks ascending — where each price level holds a FIFO queue of orders in arrival order. When a buy order comes in, it matches against the lowest ask price first, and within that price against the oldest resting order, filling in time order; if it isn't fully filled at the best price it moves to the next price level, and any remainder rests in the book at its limit price, joining the back of that level's queue. Implementations keep the price levels in a sorted structure (a tree or heap keyed by price) for fast best-price access and a FIFO queue per level for time priority. Processing this strictly in the sequenced order of incoming events is what makes the matching fair, correct, and reproducible.

How would you scale throughput if one engine isn't enough?

By partitioning across symbols, since each stock's order book is completely independent — a trade in one symbol never touches another. So you run a separate matching engine (single-threaded, in-memory, deterministic) per symbol or per group of symbols, spreading the total order flow across many engines while each individual symbol's book stays on one core with its own sequenced log and standbys. This scales horizontally in the number of symbols without ever splitting a single book (which would break determinism and price-time priority for that symbol). Within a symbol, throughput comes from making the single engine extremely fast (kernel-bypass networking, cache-friendly structures, no locks or GC on the hot path), not from parallelism. So the scaling axis is symbols, not sub-dividing a book — matching the natural independence of the domain, exactly as geographic partitioning matches ride-hailing's locality.

8. What junior / mid / senior answers look like

Junior: stores orders in a database and queries for matches — misses that this needs an in-memory deterministic engine with microsecond latency and strict ordering.
Mid: an in-memory order book with price-time priority matching, understands determinism matters, records trades durably.
Senior: recognizes the inversion (scale up, not out), builds a sequenced ordered input log as source of truth with a deterministic engine (event sourcing), achieves HA via lockstep standbys replaying the same log, engineers the microsecond latency path, partitions by symbol for throughput, decouples market-data fan-out, and keeps risk checks off the matching hot path.