Stock Exchange

What the interviewer is asking

"Design a stock exchange" (or "design a matching engine") comes up often at trading and fintech companies. The hard part isn't storage: thousands of orders a second for one symbol must be matched in a strict, fair order, in well under a millisecond, with the same result every time. The walkthrough follows the 8 steps of the interview framework.

1. Scope: what version 1 must do

• Limit orders: brokers send buy and sell orders with a limit price, such as "buy 500 XYZ at up to $102".
• Matching: buyers meet sellers by price-time priority: best price first, and at one price, first come, first served.
• Cancels: a broker can take back an order that is still waiting.
• Market data: everyone sees the best bid, the best ask and each trade.

The interviewer adds: fair (first come, first served at a price), deterministic (the same inputs always give the same trades), fast (say under 1 ms inside the exchange) and durable: an acknowledged order is never lost. Park the rest: options, opening and closing auctions, market orders, margin, and clearing and settlement, which happen after the trade at a clearing house (in the US, one business day later).

2. Data: orders and the order book

An order is a small record: an id, the broker, the side, the symbol, a limit price, a quantity, and its sequence number (its place in the arrival order). The orders still waiting for one symbol form its order book: buy orders, bids, highest price first; sell orders, asks, lowest price first; and at each price, arrival order. The book of a symbol XYZ after six orders, A to F, none of which could trade:

side   price   waiting, oldest first
bid    $100    B 300
bid    $99     A 200, then E 100
ask    $101    C 200
ask    $102    D 400, then F 200

The best bid ($100) is below the best ask ($101), so nothing trades until a new order crosses that gap, the spread.

3. The API: orders in, fills and market data out

new_order(order_id, side, symbol, price, quantity)
  → ack now; then a fill per trade: (shares, price)
cancel(order_id)
  → canceled, unless it already traded
market data feed
  → best bid, best ask, each trade, live

Brokers keep a long-lived connection to the gateway and stream messages on it (real exchanges use binary protocols or the FIX standard). Answers are asynchronous: an ack at once, the promise that the order won't be lost, then a fill each time part of it trades. The order id is the broker's own, so an order sent again after a timeout is recognized, as with idempotency keys.

4. The busy path: one order

1. The broker sends the order to the gateway.
2. The gateway checks it: a known broker, a real symbol, a sane price and size.
3. The gateway passes it to the matching engine for its symbol.
4. The engine matches it against the other side of the book.
5. The engine reports: fills to both brokers, new prices to everyone.

Check, match, report, for every order, in under 1 ms.

5. The numbers

From the interviewer: 10,000 symbols, and about 1 million orders a second at the market open, new orders and cancels together.

• Per symbol: 1,000,000 ÷ 10,000 = 100 orders a second on average. Trading is uneven, though: the busiest symbol gets about 50,000 a second, 500 times the average.
• Per thread: say one engine thread handles about 1 million orders a second, all in memory, about 1 µs each. Every symbol on one thread would fill it at the open, but the busiest symbol alone uses 50,000 ÷ 1,000,000 = 5% of a thread: one thread takes 20 times its load.
• The log: say an order takes about 100 bytes: 1 million a second is about 100 MB a second, a fifth of the roughly 500 MB a second a disk can append. Market data, about one update per order, is about as big.

6. Services: gateway, matching engine, market data feed

• Gateway (many servers): the brokers' connections, message checks, and later the risk limits. Fills go back this way.
• Matching engine: keeps the books and matches; nothing else.
• Market data feed: sends each change to every subscriber, plus a snapshot for a firm that joins late, so readers never slow the matching.

7. Scale: split by symbol

An XYZ order only ever trades with other XYZ orders, so symbols are independent: give each engine a group of symbols, balanced by load, and let the gateway route each order by its symbol. Each book lives whole on one engine and no engine waits for another. Within a symbol, never split: at 5% of a thread even the busiest fits, and one thread is exactly what first come, first served needs.

8. Deep dive: matching with price-time priority

A new order G arrives: buy 500 XYZ at up to $102. The engine walks the asks from the best price up, and at each price it takes the oldest order first:

step   best ask   trade           G has left
1      $101       C 200 at $101   300
2      $102       D 300 at $102   0

Each trade happens at the waiting order's price, so G pays $101 for C's 200 shares, not its own limit. At $102, D arrived before F, so D trades first and keeps 100, with F behind it. Had G wanted more than the 800 shares on offer at $102 or less, the rest would wait in the book as a bid at $102.

The data structure follows from that loop: each side is a set of price levels, each a FIFO queue of orders. The levels are kept sorted, in a heap (as in the course's heap lessons, such as Kth Largest Element in a Stream) or a sorted map, so the best level is always on top; a hash map from order id to its place in a queue makes a cancel quick.

9. Deep dive: one sequencer, one order of events

Orders arrive through many gateway servers. If two brokers each send "buy 300 at $102" in the same microsecond and only 300 shares are for sale at that price, whoever is first gets all 300. Gateway clocks can't settle it (two servers' clocks differ by microseconds), and neither can threads racing for a lock (the winner changes from run to run).

So every order goes through a sequencer: one place that gives it the next number and appends it to a log. The engine reads the log in order, on one thread per book: no locks, and no clock or random choice inside the engine, so the same log always produces the same trades. The sequencer stores each entry, on disk and on the standby, before the ack goes out: that's what makes "never lose an accepted order" true.

The log is also how the engine survives a crash. A hot standby reads the same log and applies every entry, as the primary does: it copies the inputs, not the book. Replaying the log of a symbol ABC from an empty book:

#   entry               best bid       best ask       trade
1   A: buy 100 at $50   A 100 at $50   –              –
2   B: sell 200 at $52  A 100 at $50   B 200 at $52   –
3   C: buy 300 at $51   C 300 at $51   B 200 at $52   –
4   D: sell 250 at $51  C 50 at $51    B 200 at $52   250 at $51
5   cancel C            A 100 at $50   B 200 at $52   –

The standby ends with exactly the primary's book. When the primary dies, a majority vote, as in consensus and leader election, makes the standby the one primary, and trading resumes in moments; outputs carry the number of the entry that caused them, so receivers drop repeats. A snapshot plus the log after it starts a new standby quickly. LMAX, a London trading venue, made this design well known: one business-logic thread over a replicated input log, reported to handle about 6 million orders a second.

10. Deep dive: latency

Recall the latency numbers: memory about 100 ns, a round trip inside one data center about 0.5 ms, a disk seek about 10 ms. With a budget under 1 ms, a seek per order is ten times over it and a database call spends half of it. So everything lives in memory; the one disk write per order is the sequencer's append, sequential and batched; trades reach a database afterwards, from the log; and gateways, sequencer and engines sit side by side on a fast network, where a hop takes tens of microseconds or less.

The pre-trade risk check (is this broker within its limits?) belongs in the gateway, before the sequencer, against limits kept in memory, so a rejected order never reaches the log. In the engine, asking the accounts database for each order would make its one thread wait about 0.5 ms each time: at most about 2,000 orders a second, far below the busiest symbol's 50,000. After the match is too late: a reported trade is final.

11. Deep dive: fair market data

Whoever sees a price change first can trade on it first, so fair means everyone gets each update at the same moment. Sending a copy to each of 1,000 subscribers in turn, at about 1 µs each, means the last firm hears about 1 ms after the first; at 100 MB a second per firm it would also take 100 GB a second, the network of about 100 servers. Instead the feed sends each update once by multicast, and the network copies it to every subscriber at the same moment. Multicast runs over UDP, which can drop packets, so each update carries a sequence number and a firm that sees a gap asks for the missing one.

What breaks first

• A burst on a hot symbol: its engine's queue grows; give the hottest symbols engines of their own and watch the queue.
• The sequencer: every order passes through it, so it needs a hot standby of its own.
• A runaway broker: limit each broker's order rate in the gateway, and reject prices far from the market.
• Lost market data: gaps show up in the sequence numbers and are refilled from a snapshot.

Summary: the order to follow

1. Scope: limit orders, price-time matching, cancels, market data; fair, deterministic, under 1 ms, nothing accepted is lost.
2. Data: a book per symbol: bids high to low, asks low to high, oldest first at a price.
3. API: new_order and cancel, answered with an ack, then fills; a market data feed.
4. Busy path: check, match, report.
5. Numbers: 1 million orders a second at the open; 100 for an average symbol, 50,000 for the busiest.
6. Services: gateway, matching engine, market data feed.
7. Scale: engines split by symbol; the busiest symbol uses 5% of a thread.
8. Deep dives: price levels with FIFO queues; one sequenced log on one thread, replayed by a hot standby; risk checks in the gateway; multicast market data.

The same steps work for any "design X" question.