Design a stock exchange

Requirements

A stock exchange matches buy and sell orders for instruments and publishes the results. The constraints are unusual and they invert the usual scaling instincts. Why does an exchange need a design so different from everything else in this unit? Because “who traded first” is a legal question, not just an engineering one — and that changes everything.

Functional. Accept orders (instrument, side, price, quantity, type — limit/market). Maintain an order book per instrument: resting buy orders (bids) and sell orders (asks). Match incoming orders against the book by a fair rule. Execute trades, update positions, and publish market data (the book and the trade feed) to all participants. Support cancels and amends.

Non-functional. Fairness and determinism above all: a single canonical order of events, identical results on every replica, reproducible for audit years later. Ultra-low latency: matching in microseconds, because participants compete on speed. Durability: no acknowledged order may be lost, even through a crash. High throughput in bursts (millions of messages/sec at the open). Fairness is the constraint that dominates the design — it forces a single sequence, which forces a single-threaded core, which inverts everything.

The defining inversion: the rest of this unit fought to distribute state for scale. An exchange does the opposite — it deliberately funnels everything through one sequencer and one matching thread, because only a single total order can be fair and deterministic. Speed comes from making that single path absurdly fast, not from parallelism.

Estimation

instruments       = ~10,000 symbols
peak messages     = ~1,000,000–10,000,000 orders+cancels/sec (market open burst)
match latency     = target < 10 microseconds per order (in-memory)
order book        = thousands of price levels × orders per level, all in RAM
event log         = every message, appended, fsync'd, replicated → durability + audit
fan-out           = market data to thousands of subscribers, multicast

The numbers explain the architecture. The whole working set — order books for all instruments — fits in RAM (it’s millions of small records, not terabytes), so the matching engine is an in-memory program; touching disk in the hot path would blow the microsecond budget by orders of magnitude. The peak is bursty and brutal (the open), so the path must be lean. And every message is logged durably for both crash recovery and audit — but the log write is arranged so it never stalls the match (more below). This is why an exchange looks nothing like a sharded web backend: it’s a fast single-threaded core fed by a sequencer and backed by a log.

High-level design

The pattern (the LMAX architecture is the famous public example): a sequencer assigns every message a global sequence number, defining the one true order; that ordered stream is written to a durable, replicated event log; a single-threaded matching engine consumes the stream in order against an in-memory order book and deterministically produces trades; the results fan out as market data. Recovery and replicas are trivial because of determinism — replay the log from the start (or a snapshot) and you reach the exact same book.

Deep dive

Price-time priority and the order book

The matching rule must be fair and total, leaving no ambiguity about who fills first. The standard is price-time priority: orders are ranked first by price (a buyer offering more, or a seller asking less, has priority), and among orders at the same price, by time (first to arrive, first to fill — FIFO). This answers the hook precisely: the two same-price buys are ordered by their sequence numbers, and the earlier one fills.

The order book is the data structure that makes this fast: for each instrument, bids and asks are kept sorted by price (often as a map from price level to a FIFO queue of orders at that level). Matching an incoming order walks the opposite side from the best price inward, filling against resting orders until the incoming order is exhausted or no price crosses:

ASKS (sellers)        BIDS (buyers)
101.00  × 50          100.50  × 30   ← best bid
100.75  × 20          100.25  × 40
                      100.00  × 100

incoming: BUY 60 @ market
  → fill 20 @ 100.75, then 40 @ 101.00 (walk up the asks)  ⇒ two trades, book updated

Each level is FIFO so time priority holds; the best price is O(1) to find and matching is O(orders touched). The book is pure in-memory state mutated by the single matching thread, which is why it can run in microseconds.

Determinism and durability via the event log

Determinism is the property that the same sequence of input messages always yields the same trades and the same final book — no wall-clock reads, no random numbers, no thread-scheduling dependence inside the match. This is what makes the event log so powerful: because the engine is deterministic, the log of sequenced input messages is the system. You don’t need to log the resulting state; you log the inputs, and any replica replaying them rebuilds the identical book.

That gives durability and recovery cheaply: append each sequenced message to a log that is fsync’d and replicated before (or concurrently with) matching, so a crash loses nothing acknowledged; on restart, replay the log (from a periodic snapshot to bound replay time) to reconstruct the exact in-memory state. The replication is also the failover mechanism — hot replicas consume the same log and stand ready to take over at the same sequence number. Audit is the same machinery: the immutable, ordered log is a perfect record, and a regulator’s question (“why did this trade happen?”) is answered by replaying to that sequence number.

Market-data fan-out

Once the engine matches, the results — trades and incremental book updates — must reach every participant fairly and fast. This is a high fan-out broadcast (thousands of subscribers, each wanting the feed with minimal latency). Exchanges typically use multicast: the engine publishes each update once and the network duplicates it to all subscribers, so fan-out cost doesn’t grow with subscriber count and everyone receives it at nearly the same instant (fairness again — you can’t give one subscriber a head start). The feed is itself a sequenced stream (gap-fill protocols let a subscriber that missed a packet request a replay), and many exchanges publish tiered feeds (full depth-of-book vs top-of-book) to manage bandwidth. The fan-out is parallelized and kept off the matching thread — the engine emits, a separate publishing path distributes.

Bottlenecks & tradeoffs

The defining stance is determinism and fairness over parallelism: the matching core is single-threaded on purpose, so its throughput ceiling is one fast thread — you scale by making that thread faster (cache-resident book, no allocation in the hot path, mechanical sympathy) and by partitioning across instruments (independent books can run on separate engines), never by parallelizing one book. Durability vs latency is the central tension: the log write must happen before you acknowledge an order, yet an fsync is slow relative to a microsecond match — resolved by batching log writes, writing to fast storage, and overlapping replication so the durable write doesn’t serialize behind each match. In-memory means bounded by RAM and recovery time: the book fits in memory, but replay-from-log must be bounded by periodic snapshots or restart takes too long. And fan-out fairness constrains the network: multicast keeps it equal and scalable, but demands gap-recovery protocols and careful capacity so no subscriber is systematically advantaged. Throughout, the exchange accepts a single-threaded ceiling and elaborate durability plumbing as the price of the one thing it cannot compromise — a fair, deterministic, auditable order of trades.