Stock Exchange: requirements, scale and the matching engine

"Design a stock exchange." The hardest problem in this course, and the only one where the unit of latency is the microsecond and where scaling out is the wrong first instinct.

This lesson covers what an exchange does, the requirements and numbers, and the order book at its core. The second lesson explains why the matching engine is single-threaded and where the microseconds go; the third covers reliability, market data and the follow-up questions.

What an exchange actually does

An exchange is a venue where buyers and sellers submit orders and the venue matches them according to published rules. It does not take a position, does not decide prices, and does not choose who trades with whom beyond applying its rules mechanically.

The rules are the product. If the venue's matching is unpredictable, unfair, or unexplainable, participants leave — and regulators intervene.

The questions that shape everything after

1. Which order types? Limit and market alone is a full lesson. Stop orders, iceberg orders, immediate-or-cancel, and auction orders each add state and edge cases. Scope to limit and market, and name the others as extensions.
2. What is the latency target, and measured how? Ask specifically: from where to where, and at which percentile. "Median under 50 microseconds and 99th percentile under 200, measured from the packet arriving at our network card to the acknowledgement leaving it" is a requirement. "Low latency" is not.
3. What throughput, at peak? Market opens and closes are far above average, and a design sized on the average fails on the day it matters.
4. How is market data distributed, and to how many subscribers? This turns out to be the largest data-volume problem in the system, larger than order handling by two orders of magnitude.
5. What fairness and audit obligations apply? Fairness is a hard functional requirement here, not a nicety, and auditability shapes the core architecture rather than sitting beside it.
6. Single instrument class and single venue, or a group of markets? Scope to one venue and one asset class.

The assumptions this section uses

Requirements and scale

Functional requirements

• Accept, cancel, and modify limit and market orders from authenticated participants.
• Match orders by price-time priority, deterministically.
• Acknowledge every order, and report every fill, to the submitting participant.
• Publish market data: best prices, depth, and trades.
• Record every event in an order that can be replayed exactly.
• Halt trading in an instrument when circuit-breaker conditions are met.

Non-functional requirements

• Determinism. The same input sequence always produces the same trades.
• Fairness. Price-time priority holds strictly and observably.
• Latency as tabled: median under 50 µs, 99th percentile under 200 µs.
• Auditability. Every trade explainable from the recorded sequence.
• Availability during market hours, with failover that does not lose or reorder events.

Notice the ordering. Determinism and fairness come before latency, and latency comes before availability. That ordering is unusual in this course and it is deliberate.

The arithmetic

Order volume. 200,000 orders per second at peak. Over a 6.5-hour session averaging 50,000 per second, that is 50,000 × 23,400 s ≈ 1.2 billion messages per day.

Inbound bandwidth. A binary order message is compact — instrument, side, price, quantity, participant, sequence, timestamps — call it 100 bytes. 200,000 × 100 = 20 MB/s inbound at peak. Trivially small. Bandwidth is not the problem; latency is.

Journal volume. 1.2 billion messages × 100 bytes = 120 GB per day, retained for years for regulatory replay. Also modest.

Market data, and the number that surprises people. Every order that changes the book produces an update. At 200,000 book changes per second and 100 bytes per update, one subscriber receives 20 MB/s. With 5,000 subscribers over unicast, that is 5,000 × 20 MB/s = 100 GB/s, or 800 Gbit/s, from one publisher.

That is impossible with individual connections and it is why market data goes out over multicast, where the publisher sends once and the network replicates. One send at 20 MB/s instead of 5,000 sends at 100 GB/s — a factor of 5,000. Market data and follow-ups develops it.

Order book memory. A liquid instrument might hold 10,000 resting orders across a few hundred price levels. At 100 bytes per order that is 1 MB per book, and 5,000 instruments is 5 GB — all of it in memory, none of it touching disk on the hot path.

The matching engine and the order book

Now the core. Get the data structure and the rules right and everything else is plumbing.

The rules, precisely

Price priority. A buy order at a higher price matches before a buy order at a lower price. A sell at a lower price matches before a sell at a higher one.

Time priority. Among orders at the same price, the one that arrived first matches first. This is what makes "arrival order" a correctness concept rather than an implementation detail.

Price improvement goes to the resting order. An incoming buy limited at 100.05 matching a resting sell at 100.04 trades at 100.04 — the resting order's price. The resting order set the terms; the incoming order accepted them.

The data structure

Three pieces, each chosen for one operation:

Price levels. For each side, a collection of price levels ordered by price. For liquid instruments almost all activity is within a few dozen ticks of the touch, so an array indexed by price tick gives O(1) access to any level, with a sorted map handling the rare far-away prices. The best bid and best ask are cached pointers, updated when a level empties or a new best appears.

Orders within a level. A doubly linked list in arrival order. Appending a new order is O(1) at the tail; matching consumes from the head; removal from the middle is O(1) given a pointer. Time priority is the list order, which means it is structural rather than computed.

Order lookup. A hash map from order identifier to its list node, so a cancel is O(1): find the node, unlink it, decrement the level.

Costs: adding a resting order O(1); cancelling O(1); matching O(k) in the number of orders consumed, which is what it must be, since each fill is a separate event to report.

A worked trace

Invented instrument, invented participants. Starting book:

Best bid 100.02, best ask 100.04, spread 0.02.

Order 1: limit buy 200 @ 100.03. 100.03 is below the best ask of 100.04, so it does not cross. It rests as a new best bid. Book: best bid 100.03 × 200 (F).

Order 2: limit sell 600 @ 100.02. It crosses. Walking bids from the best:

• 100.03 × 200 (F) → trade 200 @ 100.03. F is fully filled and removed. 400 remaining to sell.
• 100.02 × 500 (A) → trade 400 @ 100.02. A is partially filled, 100 remaining, and keeps its place in the queue — a partial fill does not cost time priority.

The sell is fully filled and never rests. Two trades, at two different prices, from one order. Best bid is now 100.02 × 100.

Order 3: market buy 500. No price limit; it takes what is there:

• 100.04 × 400 (D) → trade 400 @ 100.04. D removed.
• 100.05 × 900 (E) → trade 100 @ 100.05. E partially filled, 800 remaining.

One market order swept two price levels and moved the best ask from 100.04 to 100.05. That is market impact, visible in the book.

Order 4: cancel order B. One hash lookup, one unlink, one level decrement. O(1), and the crucial point is that it does not disturb anyone else's time priority.

Order 5: limit buy 200 @ 100.02. Rests behind A's remaining 100 at the same price, because A arrived first. If a fill arrives for 150 at that level, A gets 100 and the new order gets 50. That is time priority made concrete.