Design a Stock Exchange: Order Matching System Walkthrough

To design a stock exchange, put a single-threaded, in-memory matching engine behind a sequencer that stamps every inbound order with a sequence number, so every state change comes from one ordered, replayable log. The engine keeps an order book per symbol and fills orders by price-time priority, gateways run risk checks before orders reach it, and a market data publisher multicasts every book change and trade. Durability and failover come from journaling that sequenced input and replaying it on standby replicas.

The rest of this guide walks through it the way you would in a 45-minute round, including the data structure and trade-offs interviewers push on.

Step 1: Pin down the requirements

Scope the problem in the first five minutes, or auctions and clearing will eat the session:

• Which instruments? Assume equities in one currency.
• Which order types? Limit orders, market orders and cancels are the core. Leave stops, iceberg orders and opening/closing auctions out unless asked.
• Who connects? Brokers and trading firms; individual investors reach the exchange through a broker.
• Is post-trade in scope? Usually not. Emit trades to a downstream clearing system and move on.
• How many symbols, how much volume, what latency? Get numbers, or propose your own out loud.

Then state the non-functional requirements:

• Low, predictable latency. Talk about the 99th and 99.9th percentile, not the average.
• Fairness. Orders are handled in arrival order, and everyone receives market data at the same time.
• Determinism. The same input sequence always produces the same trades, for replay and audit.
• Correctness over availability. A fill is never lost or doubled. Halting a symbol is acceptable; matching it wrong is not.

A quick estimate. Suppose the interviewer gives you 1 billion orders a day. Over NYSE’s core session of 9:30 a.m. to 4:00 p.m. ET (23,400 seconds), that is roughly 43,000 orders per second on average, with peaks around the open and close. Raw throughput is not the hard part: Martin Fowler’s write-up of the LMAX trading platform describes one business-logic thread handling about 6 million orders per second on commodity hardware. Latency, fairness and correctness are.

Step 2: Draw the high-level architecture

Keep the latency-critical path short and push everything else onto the output stream:

Brokers / trading firms  (FIX or binary order entry)
        |
  [Order gateways]   auth, validation, throttling, stateless risk checks
        |
  [Sequencer]        assigns sequence numbers, journals, replicates
        |
  [Matching engine]  order books in memory, one thread per partition
        |
  [Sequenced output stream]
     |                 |                 |
 [Execution reports] [Market data]    [Post-trade: reporting,
  back via gateways   (UDP multicast)  clearing feed, audit]

Brokers typically connect over FIX, a tag=value messaging standard dating to 1992, or a leaner binary protocol. The gateway converts either into one compact internal format.

Step 3: The order book and price-time priority

Each symbol has a book with two sides: bids sorted highest price first, asks lowest price first. Under price-time priority, a better price always fills first, and at the same price the earliest order fills first. Some markets use pro-rata matching instead, splitting a fill across all orders at a price level in proportion to their size. Mention it, then build price-time unless told otherwise.

The data structure interviewers expect has three parts:

1. Price levels per side in a sorted map (a balanced tree) keyed by price, with a cached pointer to the best level. Because prices move in fixed ticks, an array indexed by tick is a faster option that costs more memory.
2. A FIFO queue per level, usually a doubly linked list of orders plus the level’s total quantity.
3. An order index: a hash map from order ID to its list node, so cancels never scan the book.

P is the number of active price levels on that side.

Walk through one match. The ask side holds order A for 100 shares at $10.01, then B for 200 at $10.01, then C for 300 at $10.02. A buy limit order for 250 at $10.02 arrives. It takes 100 from A and 150 from B, both at $10.01, and stops. B keeps its place at the front of the queue with 50 left; C is untouched. In typical continuous trading the trade prints at the resting order’s price, so the buyer pays $10.01, not its $10.02 limit.

match(incoming):
  opposite = book.side_opposite(incoming)
  while incoming.qty > 0 and opposite.best_crosses(incoming.price):
    level   = opposite.best_level()
    resting = level.head()
    fill    = min(incoming.qty, resting.qty)
    emit Trade(price = level.price, qty = fill, ...)
    incoming.qty -= fill
    resting.qty  -= fill
    if resting.qty == 0: level.pop_head(); index.remove(resting.id)
    if level.empty():    opposite.remove(level)
  if incoming.qty > 0:
    if incoming.type == LIMIT: rest_on_book(incoming)   # joins tail of its level
    else: emit Cancelled(incoming)                      # market / IOC remainder

Two details worth saying unprompted. Store prices as integer ticks, never floating point; Nasdaq’s TotalView-ITCH feed sends prices as integers with an implied four decimal places. And state your amendment rule: on many venues, a replace that changes the price or raises the size loses queue position.

Step 4: The sequencer, and why the engine has one thread

Every message that can change state passes through the sequencer and receives the next number in a single, gap-free sequence. The engine processes messages strictly in that order, and its outputs carry sequence numbers too. That one decision buys fairness (first in really is first processed), determinism (replaying the log rebuilds the same books and trades) and simple recovery and audit.

In his Jane Street tech talk “How to Build an Exchange,” Brian Nigito describes the same principle: one global, totally ordered stream, and only messages in that stream may change state or be shown to clients.

The engine itself runs on one thread. Fowler’s LMAX article explains why: the team’s first prototype spent more time managing queues between threads than running business logic, and locks trigger context switches that evict data from CPU caches. A single writer over in-memory state avoids both.

To scale, partition by symbol. Matching in one stock never touches another, so each partition gets its own sequencer and engine. Name the cost: anything that spans symbols, such as a firm-wide risk limit, now needs coordination across partitions. Nigito notes that his team chose not to split by symbol for exactly that reason, to keep cross-instrument risk limits atomic.

Step 5: Low-latency design choices

You do not need to be a performance engineer for this round, but know which levers exist.

• No database on the hot path. State lives in memory; durability comes from an append-only journal.
• Pre-allocate. Reuse order objects from pools and pass messages through pre-sized ring buffers, so the hot path never allocates or pauses for garbage collection. LMAX built its Disruptor library, a lock-free inter-thread messaging framework, after finding that queues between stages added latency.
• Compact binary formats. Parse once at the gateway and map ticker symbols to small integer IDs. ITCH does this with a “stock locate” code meant to serve as an array index.
• Few thread hand-offs. Each hop adds latency and variance. Pinning hot threads to dedicated cores and busy-polling are common techniques.
• Measure the tail. Report p99 and p99.9 latency and jitter. As Nigito puts it, “Latency determines throughput.”

Step 6: Risk checks before the book

• Stateless checks in the gateway (parallel and cheap): the symbol exists and is trading, the price sits inside a collar around a reference price, quantity and notional are under per-order maximums, and the client order ID is not a duplicate.
• Stateful checks (need ordered state): buying power, position limits, open-order counts and a per-firm kill switch. Funds are reserved when an order is accepted, released on cancel and settled on fill. Run these in a component that sees the sequenced stream so they stay consistent with the book.

For context, the SEC’s market access rule (Rule 15c3-5, adopted in 2010) requires US broker-dealers with market access to have pre-trade controls that block orders exceeding pre-set credit or capital thresholds or that appear erroneous. Reserving funds on accept and settling on fill mirrors the authorize-then-capture flow in our payment system design walkthrough.

Step 7: Market data distribution

Every engine output becomes public data. The usual tiers (names vary by vendor):

Nasdaq TotalView-ITCH is a real example of the full-depth tier: a binary feed of sequenced, order-level messages with nanosecond timestamps, offered over MoldUDP64 (UDP) or SoupBinTCP. Design points to make:

• Multicast for fairness. UDP multicast delivers each update to every subscriber at about the same moment.
• Gap recovery. UDP drops packets, so receivers watch sequence numbers and request missing ranges from retransmission servers.
• Snapshots for late joiners. A client connecting mid-day needs the current book plus the stream from that point; Nasdaq offers a service called GLIMPSE for this.
• Slow consumers never slow the engine. A subscriber that falls too far behind is dropped back to snapshot recovery.
• Derived data stays downstream. Candlestick (OHLC) bars and tick history are built off the output stream.

Step 8: Persistence, replay and fault tolerance

This is event sourcing: the sequenced input log is the source of truth, and the order books are derived state.

• Journal first. The sequencer persists and replicates each message before results are released, so an acknowledged order can always be reproduced.
• Snapshot plus replay. Fowler reports that LMAX takes nightly snapshots, and a full restart, loading a snapshot and replaying a day’s journals, takes less than a minute.
• Hot standbys. Replicas consume the same input, run the same deterministic code and hold identical books. LMAX ran two processors in its main data center and a third at a disaster recovery site; Nigito describes a passive replica with an operator switching over on failure.
• Pick a failover model. Raft for the sequencer’s log is defensible if you name the cost: a quorum round trip on every order. Nigito says he knows of no exchange using consensus protocols such as Paxos, so primary-backup is equally reasonable.
• Protect determinism. The engine never reads the wall clock or a random number generator; timestamps come from the sequencer.
• Make retries safe. A reconnecting broker resends with the same client order ID and the gateway deduplicates it.

The sequenced, append-only log is the same building block as a partitioned message queue, so our distributed message queue walkthrough is useful background.

Running the 45-minute interview

Have a one-line answer ready for follow-ups like these:

• “A cancel and a fill race for the same order.” Whichever the sequencer ordered first wins; a cancel after the fill is rejected as too late.
• “The primary dies mid-trade.” The standby holds the same state through the last sequenced message; downstream systems deduplicate by sequence number.
• “One symbol is too busy for one thread.” A single book cannot be split across threads without breaking time priority, so give that symbol its own partition and core.

Contention on one hot item is also the core problem in designing Ticketmaster, and the building blocks every design round draws on are in our 14 core system design concepts. Then rehearse out loud on a timer: a free AI mock interview in CoPilot Interview can include system design questions, reads each aloud and scores your spoken answer.

FAQ

What is price-time priority in a matching engine?

A better price fills first, and at the same price the earliest order fills first, which is why it is also called FIFO matching. Some markets use pro-rata instead, splitting fills at a price level by order size.

What data structure should I use for an order book?

Two sorted collections of price levels (bids highest first, asks lowest first), each level holding a FIFO queue of orders, plus a hash map from order ID to its node so cancels take constant time.

Why is the matching engine usually single-threaded?

One thread reading one sequenced stream needs no locks, keeps CPU caches warm and gives the same result on every replay. Martin Fowler's write-up of LMAX describes one such thread processing about 6 million orders per second on commodity hardware.

How does a stock exchange recover from a crash?

The sequenced input log is the source of truth. A new engine loads the latest snapshot and replays the journal after it, while hot standbys that consumed the same stream can take over with identical books.

Do I need to know FIX or ITCH for a system design interview?

No, but naming them shows you know real venues. FIX is the long-standing tag=value standard for order messages, and Nasdaq TotalView-ITCH is a binary, order-by-order market data feed. Spend your time on the design.