Design a stock exchange matching engine

The compute is small. Even the busiest symbol at 25,000 messages a second uses 12.5% of one core, so the design is about order, fairness and failover. Brokers connect to a gateway, then a risk check applies price bands, exposure limits and self-trade rules before an order can reach the book. A sequencer gives every message the next sequence number, sends it to the matching engine and writes it to a log replicated to three nodes.

The engine runs one thread per symbol and is a pure function of the sequenced input, using whole-number prices, so replaying the log gives identical trades. The book keeps a FIFO queue per price level and a map from order ID for constant-time cancels. A hot standby replays the same log and builds the same book. If the primary stops, an epoch number fences it off, and the standby takes over within a second with no gap and no duplicate, since outputs are deduplicated by sequence number.

Results return through the sequencer to the sender, and a publisher broadcasts market data once, with sequence numbers and resend on gaps, because sending to each subscriber would need 200 Gbit/s. The cost is strict determinism everywhere.

These numbers are assumptions for the exercise, not facts about a real system:

• There are 5,000 symbols. The peak is 500,000 inbound messages a second, counting new orders and cancels. The busiest symbol gets 5% of them.
• The session runs 6.5 hours (23,400 s) and averages 100,000 messages a second.
• Matching one message takes about 5 microseconds on one core. A message is 64 bytes.
• A book holds about 4,000 resting orders. A market data update is 50 bytes, and there are 1,000 subscribers.

The arithmetic:

Load on the busiest symbol

500,000 × 5%

25,000 messages a second

CPU for that symbol

25,000 × 5 µs = 125 ms of work per second

12.5% of one core, which can do 200,000 a second

Latency budget

Gateway 50 + risk 20 + sequencer 10 + log copy 100 + match 5 + out 50 µs

235 µs, inside the 1 ms goal

Input log per day

100,000/s × 23,400 s = 2.34B messages × 64 B

≈ 150 GB a day

Memory for all books

4,000 orders × 64 B = 256 KB per symbol; × 5,000

≈ 1.3 GB, and a hot book fits in a core's cache

Market data, if sent one by one

500,000 × 50 B = 25 MB/s = 200 Mbit/s; × 1,000 subscribers

200 Gbit/s, so one broadcast copy is needed

Each symbol has its own book with two sides. Bids (buys) are sorted from the highest price down. Asks (sells) are sorted from the lowest price up. Prices and quantities are whole numbers, in ticks and shares, never floating-point, so there is no rounding and results are identical on every machine.

Each price level holds a first-in, first-out queue of resting orders. That is the time priority. The book keeps the levels in a sorted structure, or in an array indexed by tick when the price band is bounded. A hash map from order ID to the order's place in its queue makes a cancel a single step, with no search.

Matching a limit order. An incoming buy at price P looks at the best ask. While it has quantity left and the best ask is at or below P, it trades with the oldest order at that level. The trade happens at the resting order's price. Whatever is left rests at the back of its own level.

A worked example. The asks are 100 shares (A) at 10.02, 50 (B) at 10.02, and 200 (C) at 10.03. A buy of 220 at 10.03 arrives. It trades 100 with A and 50 with B, both at 10.02. It then trades 70 with C at 10.03, leaving C with 130. The buyer asked to pay up to 10.03 but got 150 shares at the better price of 10.02.

A market order has no price. It takes whatever the book offers until it is filled or the book is empty, and any rest is cancelled; it never rests. A cancel finds the order by ID and unlinks it. If the order was already filled, the cancel is rejected as too late. Whichever of the two was sequenced first wins, which is what makes the answer fair.

Cutting the quantity of a resting order keeps its place in the queue. Raising it, or changing the price, sends it to the back. Matching costs time in proportion to the number of trades it makes. Cancels, which are most of the traffic, are constant time.

Matching must be a pure function of an ordered stream: new book = match(old book, next event). If the order of events is fixed, the result is fixed. So one component, the sequencer, decides the order. It stamps every message with the next sequence number. That is the answer to 'who was first', and it removes ties.

One thread per symbol. With a single writer there are no locks and no races. The book fits in the core's cache, about 256 KB, and the loop avoids memory allocation and system calls. At about 5 microseconds a message, one thread handles 200,000 a second, against 25,000 needed for the busiest symbol. To scale, spread symbols over many engine threads or machines. Never share one symbol between threads.

The replicated log. The sequencer appends each event to a log that is copied to three nodes, and it counts as written when two have it. The engine does not release a result until its input is safe. The engine's state is just a cache of the log. A snapshot of the book plus its sequence number is saved every few minutes, so recovery replays only the tail.

The hot standby reads the same log and applies every event in the same order, so its book is identical. It discards its outputs while it is not in charge. If the primary stops answering for, say, 200 ms, the standby takes over. First fence off the old primary: every output carries an epoch number, and a lower epoch is ignored downstream, so a primary that is only slow cannot emit stale results. Then replay any events past what it applied. Because the engine is deterministic, the results it regenerates are byte for byte what the old primary produced, and anything already published is dropped by its sequence number.

Do not read the wall clock in the matching code. Timestamps are assigned by the sequencer and carried in the event, so a replay is exact. The sequencer is a single point too, so run it as a primary and a backup with the same epoch rule, continuing from the last sequence number in the log.

Risk checks run before the sequencer, so a rejected order takes no sequence number and never touches the book. They are in-memory counters per participant, so each check takes microseconds.

• Fat-finger limits. Reject a price far from a reference, say outside 10% of the last trade, or a quantity above a cap, say 1 million shares.
• Exposure. Keep a worst-case figure per participant. For buys, it is the open buy quantity times each order's limit price, plus the value of the current position at the last trade price. Add the new order's quantity times its price, and reject it if the total passes the participant's limit. Sells are checked the same way against short exposure. A fill turns open quantity into position at the fill price, and a cancel or a sell lowers the figure.
• Rate caps. Limit messages a second per connection, so one runaway program cannot flood the engine.
• Self-trade prevention. Do not match a participant against itself. Cancel the older or newer order by a stated rule.
• A kill switch. One command cancels all of a participant's orders and blocks new ones.

Market data. The publisher turns the sequenced events into two streams. The incremental stream carries every change to the book and every trade, each with a sequence number. A snapshot stream repeats the top levels of each book every second or so, so a late joiner can catch up.

Sending 25 MB a second to each of 1,000 subscribers one by one is 200 Gbit/s, which no single publisher can do. Instead send each update once to a network that copies it, such as multicast inside the data centre, with a distribution tier beyond it. Subscribers watch the sequence numbers. On a gap, they ask a resend server for the missing range or wait for the next snapshot.

Fairness. Everyone should see events in the same order and at about the same time. Because outbound events also pass through the sequencer, there is one global order for reports and public data alike. Give co-located participants cables of equal length, so geography does not decide who is first. The event log doubles as the audit trail, kept for as long as regulators require.