Design a Stock Exchange (Matching Engine)

A stock exchange’s core is a matching engine: it accepts buy and sell orders for each security, matches them by strict rules, produces trades, and broadcasts the result to the world — all in microseconds, deterministically, and fairly. This is the opposite of nearly every other system in this book. Where the news feed embraced eventual consistency and horizontal sharding, the matching engine’s entire value is being a single, authoritative, totally ordered place where price discovery happens. You don’t scale it out — you make one thread go absurdly fast and keep it perfectly deterministic. We’ll follow the framework.

1. Requirements

Functional

• Accept limit and market orders, plus cancel/modify.
• Maintain an order book per security and match by price-time priority.
• Emit executions (trades) and a market-data feed of book changes.

Non-functional

• Ultra-low latency — order-to-ack in microseconds; predictable, not just fast on average.
• Determinism — the same inputs in the same order always produce the same trades (for replication and audit).
• Fairness — earlier orders at a given price get filled first; no participant gets to peek or jump.
• Durability & audit — every order and trade is recoverable; regulators can replay the day.

The unusual goal: be a single point of total order — on purpose

Most systems fight to avoid a single bottleneck. An exchange is the bottleneck by design: matching must happen at one authoritative point so there’s exactly one truth about who traded with whom, in what order, at what price. The engineering challenge isn’t distributing the match — it’s making one deterministic place fast enough.

2. Back-of-envelope estimation

THROUGHPUT
  busy symbol:    can see 100k+ order events/sec during volatility (illustrative)
  whole market:   millions of order events/sec aggregate across all symbols
  matching cost:  each event is a few in-memory data-structure ops → one core can do millions/sec

LATENCY (this is the whole game)
  target:         single-digit microseconds inside the matching engine
  for scale:      light in fiber travels ~200 m/µs (~2/3 c) → distance literally costs microseconds
  market data:    one book change fans out to thousands of subscribers, latency-critically

The shocking part isn’t the throughput — a single in-memory thread handles millions of ops/sec easily. It’s that latency is measured in microseconds, where the speed of light in fiber becomes a design constraint: a server 200 metres farther from the engine is a microsecond slower. That’s why the whole matching engine runs in memory on essentially one thread, and why participants pay to put their servers in the same building.

3. The order book and matching

The order book is two sorted collections per security:

        BIDS (buyers, want low)             ASKS (sellers, want high)
        price   qty   queue (FIFO by time)  price   qty   queue
        100.02  500   [A, B]                100.05  300   [C]
        100.01  900   [D, E, F]             100.06  800   [G, H]
        100.00  200   [I]                   100.07  100   [J]
         ▲ best bid (highest buy)            ▲ best ask (lowest sell)
        the gap 100.02 → 100.05 is the SPREAD

Bids are sorted highest-price-first, asks lowest-price-first; within a price level, orders queue FIFO by arrival time — this is price-time priority. Matching: when an aggressive order crosses the spread (a buy at ≥ best ask, or a sell at ≤ best bid), it fills against the resting orders best price first, then earliest first, generating trades until it’s filled or its limit price is reached; any remainder rests in the book. Cancels remove a resting order. That’s the entire core — and its simplicity is what lets it run deterministically at microsecond speed.

4. The matching engine: single-threaded determinism

The defining design choice: process all orders for a book on a single thread, in memory, with no locks. It sounds backwards — wouldn’t more threads be faster? No:

• Determinism: one thread processing a fixed input sequence yields exactly one possible output. Add concurrency and you add nondeterministic interleavings — fatal when trades must be reproducible and auditable.
• No lock contention: locks and cache-line bouncing between cores cost far more than the matching work itself. A single thread owning the book keeps it hot in L1/L2 cache.
• It’s enough: matching an order is a handful of in-memory operations; one modern core does millions per second.

Under the hood — the LMAX Disruptor pattern

LMAX, a UK financial exchange, hit exactly this problem and published the Disruptor (open-sourced 2011) — now the canonical pattern for low-latency matching engines. The business logic (matching) runs on one thread; everything else — receiving orders, journaling, replication, publishing — runs on other threads that communicate through a pre-allocated ring buffer instead of queues with locks.

   inbound ─► [ RING BUFFER ]  (pre-allocated, lock-free, mechanical-sympathy friendly)
                  │  consumers read at their own cursors, in parallel:
        ┌─────────┼───────────────┬──────────────────┐
        ▼         ▼               ▼                  ▼
   journal     replicate     un-marshal     ──►  BUSINESS LOGIC (single thread):
   to disk     to backups    input               match against the order book
                                                  │
                                                  ▼  emit trades + market data

LMAX reported the Disruptor sustaining on the order of millions of operations per second with microsecond latencies on a single thread, by avoiding locks, garbage, and cache misses (“mechanical sympathy” — writing code that works with CPU cache and memory hardware, not against it). The lesson generalizes: for the hottest path, one thread done right beats many threads contending.

5. Sequencing, durability, and high availability

If matching is single-threaded and deterministic, how do you make it fault-tolerant without introducing nondeterminism? State-machine replication.

   all inbound events ─► SEQUENCER ─► assigns a global, gap-free sequence number ─►
        │
        ├─► PRIMARY matching engine  (processes seq 1,2,3,... deterministically)
        └─► REPLICA matching engines (replay the SAME sequence → identical state)
        │
        └─► JOURNAL to disk (the sequenced input log = the source of truth)

A sequencer stamps every incoming event with a total order before it reaches the engine. Since the engine is deterministic, any replica that consumes the identical sequence reaches the identical book state — so a backup can take over by replaying the journal, and recovery after a crash is “replay the sequenced input log.” The sequence is the truth; the order book is just a deterministic function of it. This is the same total-ordering idea as time, clocks and ordering and underpins consensus-style replicated state machines; durability is the journaled input log, not a database of book snapshots, and replicas play the role of replication for the in-memory state.

By the numbers — when the speed of light is your budget

At microsecond latencies, geography is arithmetic, not hand-waving:

light in fiber ≈ 200,000 km/s ≈ 200 m/µs   (≈ 2/3 of c, due to fiber's refractive index)
  server 1 km farther from the engine:  +1 km ÷ 200 m/µs ≈ +5 µs each way (+10 µs round trip)
  a cross-town datacenter (10 km away):  +~100 µs vs co-located — an eternity here
  ⇒ co-location: every participant racks their server in the exchange's building,
    with equal-length cables, so distance is neutralized to within nanoseconds

This is why exchanges sell co-location and run the engine on one in-memory thread: once the matching itself is microseconds, the propagation delay of the cable dominates. Shaving distance buys latency advantage measured in microseconds — which, for high-frequency traders, buys real money. That direct “latency = money” conversion is what makes the next trade-off so fraught.

6. Market-data fan-out and the latency-vs-fairness tension

Every book change must reach thousands of subscribers — and they all want it first. Fan-out uses multicast (often UDP) so the engine writes the update once and the network duplicates it to all listeners simultaneously, rather than the engine looping over thousands of TCP sockets (which would make whoever’s served first systematically faster). Slow consumers can’t be allowed to back-pressure the engine, so market data is typically fire-and-hose with sequence numbers and a separate recovery channel — related to real-time delivery but tuned for speed over guaranteed in-order delivery.

Now the deep tension. Price-time priority is “fair” — earliest order wins — but it makes being microseconds faster enormously valuable, fueling a speed arms race (co-location, microwave links, custom hardware). Exchanges sit on a knife edge: optimize purely for latency and you reward whoever can afford the fastest pipe; add fairness mechanisms and you deliberately slow things down.

It actually happened — Knight Capital’s $440M, 45-minute meltdown (2012)

On 1 August 2012, market-maker Knight Capital deployed new trading software to its servers but missed one of eight — and reused a flag that, on that stale server, reactivated long-dead test code (“Power Peg”). The moment the market opened, that code began firing millions of unintended orders into the market. In roughly 45 minutes Knight accumulated a loss commonly cited around $440–460 million, wiping out the firm, which was acquired soon after. The lesson sits at the center of this page’s design values: trading systems demand deterministic, audited, carefully-sequenced behavior and flawless deployment, because at exchange speed a bug doesn’t cause a slow degradation — it does catastrophic, irreversible damage in minutes. (For the fairness side of the tension, the exchange IEX went the other way in 2016, adding a deliberate ~350-microsecond “speed bump” — a 38-mile coil of fiber — to neutralize the latency advantage of the fastest traders, popularized by Michael Lewis’s Flash Boys.)

Key trade-offs

• Single-threaded engine vs multi-threaded: one thread buys determinism, no lock contention, and cache-hot speed; it costs you the inability to parallelize matching (mitigated by sharding by symbol across engines).
• Sequencer + journaled input vs database snapshots: sequencing buys deterministic replication and replay-based recovery; it costs a hard requirement that the engine be perfectly deterministic.
• Multicast market data vs per-socket push: multicast buys simultaneous, fair fan-out; it costs guaranteed delivery (needing sequence numbers and a recovery channel).
• Latency vs fairness: pure speed buys efficient price discovery but rewards whoever’s fastest; speed bumps and equal-length cabling buy fairness by deliberately giving up raw latency.

Check your understanding

1. Why is a matching engine deliberately a single point of total order, unlike most systems that avoid single bottlenecks?
2. Describe the order book and price-time priority. How does an aggressive order match against it?
3. Why is the matching engine single-threaded and in-memory? Give two concrete benefits beyond raw speed.
4. How does sequencing make a deterministic engine fault-tolerant without introducing nondeterminism?
5. Explain the latency-vs-fairness tension, and what the Knight Capital incident teaches about exchange software.

Show answers

1. An exchange’s value is having one authoritative place where price discovery happens — exactly one truth about who traded with whom, in what order, at what price. Distributing the match would create ambiguous orderings; instead it’s a single point of total order by design, and the challenge is making that one deterministic place fast enough (microseconds), not spreading it out.
2. The order book holds bids sorted highest-price-first and asks sorted lowest-price-first, with orders at each price level queued FIFO by arrival time (price-time priority). An aggressive order that crosses the spread (a buy ≥ best ask, or sell ≤ best bid) fills against resting orders best price first, then earliest first, generating trades until filled or its limit is reached; any remainder rests in the book.
3. Matching is a few in-memory operations, so one core does millions/sec — multi-threading isn’t needed and hurts. Two benefits beyond speed: determinism (one thread on a fixed input sequence has exactly one possible output, essential for replication/audit) and no lock contention (the single thread owns the book, keeping it cache-hot and avoiding cross-core cache-line bouncing). This is the LMAX Disruptor pattern.
4. A sequencer assigns every inbound event a global, gap-free sequence number before it reaches the engine. Because the engine is deterministic, any replica that replays the identical sequence reaches the identical book state — so backups stay in sync and crash recovery is just replaying the journaled input log. The sequenced input is the source of truth; the book is a deterministic function of it.
5. Price-time priority is fair (earliest order wins) but makes being microseconds faster hugely valuable, driving a speed arms race (co-location, microwave links); adding fairness mechanisms (like IEX’s ~350µs speed bump) means deliberately slowing down. Knight Capital (2012) shows the stakes: a botched deploy reactivated dead code and lost ~$440M in ~45 minutes — at exchange speed, bugs cause catastrophic, irreversible damage fast, so determinism, sequencing, audit, and flawless deployment are non-negotiable.