Book Deep Reads · System Design Interview Vol 2 · Chapter 13
System Design Interview Vol 2 · Ch 13 · Alex Xu & Sahn Lam · 2022
You tap "buy" on your phone and a few milliseconds later it says "filled". The machine that paired you with a seller is a stock exchange, and this chapter teaches you how to build one. It is the strangest chapter in the book: the previous twelve teach you to spread work across more machines. This one goes the other way — it pulls the most critical work back into a single thread on a single machine.
Picture a farmers' market with two lists on the wall: everything people are willing to pay, and everything people are willing to accept, each sorted best-first. Someone shouts "I'll pay 10". The clerk checks the sell list for anything at 10 or cheaper: if there is, they pair it on the spot; if not, the slip goes up on the wall in price order to wait. Among equal prices, whoever arrived first goes first. That wall is the "order book", and that rule is "price first, then time".
You would guess an exchange is hard because of volume. It isn't. The book budgets a billion orders a day; spread over a six-and-a-half-hour session that's about forty-three thousand a second — lighter than a big company's own monitoring system.
The hard parts are three others: be absurdly fast (a hair slower and someone else takes the price you wanted); never let anyone cut the line (first come, first served is a legal obligation here, not a nicety); and never get a single one wrong, while being able to rewind the tape frame by frame, because a regulator can always ask what exactly happened in that one second.
If ten clerks edited that wall at once, they'd have to take turns — and who actually got there first would be genuinely hard to say. Once the order is fuzzy, line-cutting has already happened and nobody can reconstruct it afterwards. So the exchange does something plain: one clerk, and only one.
But it puts a ticket machine in front of that clerk. However many lanes orders arrive on, each takes a number at the door — 1, 2, 3 — written into a ledger, and they go in strictly by number. Two good things follow at once. The order is nailed down by the numbers, so cutting in is impossible. And replaying that ledger reproduces the market exactly as it was at any instant — on a different machine you get an identical result, which is why a standby can take over at any moment.
As for "won't one clerk be slow" — no. The work is all in memory: glance at two lists, cross out a few lines. The British exchange LMAX has publicly said its single thread handles six million orders a second. A machine's time goes into the network and the operating system, not into the matching. The cost is real, though: one stock's wall lives on one machine, so you grow only by giving different stocks to different machines — you cannot scale a single stock.
An exchange doesn't win with more machines. It wins with one queue order nobody can alter: take a number at the door, let one thread work strictly by number, and keep the ledger so you can rewind. Speed, fairness and forensics all grow out of that one move.
Want the order book structure, the sequencer, the latency budget and real exchange numbers? → Switch to the deep read
The closing chapter of Vol 2, and the only problem in the book whose answer is "don't make it distributed": an exchange's matching core must be single-threaded, in-memory and deterministic — because what it needs is not throughput but microsecond latency, strict price-time priority, and order-by-order replayability. Every distributed technique (replicas, scaling, recovery) is pushed outside that thread, behind a sequencer that flattens concurrent input into one immutable stream.
The last chapter of Vol 2 and, by common consent, the hardest. It is where two earlier chapters meet: Ch4 (building a message queue) taught you the append-only log, Ch12 (digital wallet) taught you event sourcing plus a replicated state machine, and this chapter pushes both to the latency extreme. The real-world counterparts are NYSE, Nasdaq, CME and LMAX — and anything else that needs determinism, replay and microseconds: matching, real-time risk checks, lockstep game servers.
Start with the numbers, because they invert the usual intuition. The book budgets roughly 100 symbols and a billion orders a day; the NYSE session runs 6.5 hours ≈ 23,400 seconds, giving ≈ 43,000 QPS on average and ≈ 215,000 QPS at a 5× peak.
Within this book that is not a big number — Ch5's monitoring system ingests tens of millions of metrics per second, Ch6's ad-click aggregation runs in the millions. So throughput was never the difficulty. Three other constraints are:
What happens when it isn't solved? In 2012, Nasdaq's IPO matching application hit a race condition during the Facebook listing and left tens of thousands of orders stuck for over two hours — see §6.
The order book is the matching engine's entire state: two sides, each side sorted into price levels, and within a level the orders held in a first-in-first-out queue. The matching rule is one sentence: an incoming order first takes the best levels on the opposite side, and whatever it can't fill rests on its own side at its price.
The engineering trick is to combine three structures: a price-ordered map of levels (to read the best price), a doubly-linked list inside each level (to keep FIFO and allow removal from the middle), and a hash map from order id to list node. With those, placing, cancelling and reading the best price are all constant time — a cancel doesn't scan the queue, it unlinks the node directly. This is why matching can run in microseconds: it is not an algorithmic problem at all, it is a few dozen memory accesses.
Intuition says: 43,000 QPS, so spin up threads and match in parallel. The chapter says no, and the reason is not performance but correctness:
So the answer is: one book per symbol, one thread per book, lock-free and entirely in memory. Fast enough? LMAX, which put its whole business logic on one thread, has publicly claimed 6 million orders per second on that thread (see §6) — more than an order of magnitude above the 215,000 peak needed here. Scaling is purely horizontal by symbol: 100 symbols spread across many machines, but a single symbol cannot be scaled. That is the real price of this design, and why it does not suit workloads where one hot key must grow without limit.
The matching thread is single-threaded, but intake can't be — gateways must authenticate, run risk checks and verify balances in parallel. So which of the concurrently arriving orders goes first? The answer is a sequencer between gateway and engine: it stamps every incoming event with a globally monotonic sequence number, appends it to an append-only log, and the engine consumes strictly in that order.
One component, three problems solved. (1) Fairness — precedence is nailed down by the number, so the matching thread cannot let anyone cut in. (2) Event sourcing — the stream is the ledger, and the engine's memory is merely a projection of it. (3) Replicated state machine — a standby engine fed the same stream necessarily reaches the same book, so failover needs no memory copying. This is exactly Ch12's wallet idea, reused along the latency axis.
Because matching is deterministic, replay becomes the universal tool. After a crash, start from the latest snapshot and replay the delta to be back where you were in seconds. When a regulator asks about the book at a given instant, replay to that sequence number. Before a new engine build ships, feed it yesterday's real stream and diff the output order by order — any behavioural drift shows up immediately. A system that stores current state and mutates fields has to build three separate mechanisms for those three jobs.
Every match emits a state change, and the market data publisher turns those into three broadcast tiers. L1 carries only best bid/ask with sizes and the last trade. L2 exposes aggregated size for the top N price levels. L3 is the order-by-order feed — you see each resting order's place in the queue. The deeper the tier, the more bandwidth and processing it costs, which is why retail apps subscribe to L1/L2 while market makers and high-frequency firms pay for L3. Candlestick charts are not a separate system either: they are the market-data stream aggregated into time windows.
Measure before optimising. Lay out one order's journey and the orders of magnitude are startling:
So the chapter's optimisation list is almost entirely about getting out of the operating system's way — what the book calls mechanical sympathy, writing code that goes with the hardware's grain. Kernel bypass (NIC data straight to user space, skipping the kernel stack and one copy). CPU pinning (nail a thread to one core so migration doesn't wipe its caches). Busy-wait instead of blocking (spin, and trade CPU for the microseconds a context switch costs). Lock-free ring buffers (a pre-allocated fixed array reused in a circle — no allocation, no locks; the LMAX Disruptor is the canonical one). Avoiding garbage collection (object pools and off-heap memory, so a GC pause never lands mid-match). Cache-line padding (separate hot neighbouring variables so two cores don't fight over one line). One layer further out sits colocation: the exchange rents racks to brokers, and shorter cable wins — which is why exchanges cut every customer's cable to the same length.
Table 1 · Three routes for a matching engine, and why the chapter takes the first
| Route | How | Fairness / replay | Cost | Fits |
|---|---|---|---|---|
| Single-threaded, deterministic | One book per symbol, one thread, in memory, lock-free, fed by the sequenced stream | Holds strictly: order fixed by sequence number, replay is identical | A single symbol cannot scale; one slow operation stalls the line | This chapter; exchanges, real-time risk |
| Multi-threaded with locks | Several threads share one book, guarded by locks | Fails: lock order drifts with the scheduler, replay may differ | Contention eats most of the parallelism gain | Essentially nothing — the chapter argues against it |
| Shard by symbol | Route symbols to different engine instances, each still single-threaded | Holds within a symbol; no global order across symbols | Cross-symbol combination orders (e.g. pairs trades) lose atomicity | The chapter's only scaling lever |
Table 2 · The three market-data tiers: depth traded directly for bandwidth
| Tier | Contents | Volume | Who buys it |
|---|---|---|---|
| L1 | Best bid/ask with sizes, last trade price | Smallest | Retail apps, price tickers |
| L2 | Aggregated resting size for the top N price levels | Moderate | Active traders, execution algos |
| L3 | Order-by-order, including queue position | Largest; usually multicast | Market makers, HFT strategies |
Table 3 · Microsecond-squeezing techniques and what each costs
| Technique | What it saves | What it costs |
|---|---|---|
| Kernel bypass | Kernel network stack plus one memory copy | Tied to specific NICs and drivers; portability and observability suffer |
| CPU pinning + busy-wait | Context switches and cache invalidation; jitter drops sharply | A core spinning at 100% forever — power and machine count priced at full load |
| Lock-free ring buffer | Lock contention and allocation | Fixed capacity, so a full buffer means back-pressure; high cognitive load |
| Off-heap / object pools | GC pauses (one pause is a multi-millisecond incident) | Manual lifetimes bring leaks and overruns back |
| Colocation | The milliseconds of long-haul transmission | Expensive, and it raises the "is this even fair?" regulatory argument |
This "sequence, single-thread, replay" pattern isn't confined to exchanges: real-time risk engines, lockstep game servers, anything where several parties must agree on one event order and answer for it later, share the same skeleton. In interviews it is a rare inverted question — when a prompt insists on fairness, auditability and microsecond latency, being able to say "this is where you should not distribute; pull the core into one thread behind a sequencer" is worth far more than reciting sharding again.
EVIDENCE FROM INDUSTRY
~1 µs; one same-datacenter round trip is ~500 µs. The CPU time parallelism would save rounds to zero against the network — while spending determinism to get it.350 µs delay on every order — a "speed bump" premised on the view that erasing the speed advantage is what fairness means. That collides head-on with this chapter's default that lower is always better.1. The scale: ~100 symbols, a billion orders a day, a 6.5-hour session → about 43,000 QPS, peaking near 215,000 — throughput is not the hard part.
2. The three real constraints are microsecond latency, strict price-time priority, and order-by-order replay for audit.
3. The order book = price-ordered levels + a FIFO linked list per level + an order-id hash map; place, cancel and best-price reads are all constant time.
4. Matching must be single-threaded, in memory and deterministic — locks make fill order drift with the scheduler, destroying fairness and replayability together.
5. The sequencer solves three things with one component: it fixes fair ordering, it is the event-sourcing log, and it makes a standby engine reach the same state from the same stream.
6. Replay is the universal tool: crash recovery, regulatory audit and order-by-order regression before a release all run off that one stream.
7. Scaling means sharding by symbol only; a single symbol cannot grow and there is no global order across symbols — the real price of this design.
8. Market data comes in L1 / L2 / L3, trading depth directly for bandwidth; candlesticks are a derived aggregation of that stream.
9. Latency lives almost entirely in the network and kernel (~500 µs round trip vs ~1 µs of matching), hence kernel bypass, pinning and spinning, lock-free ring buffers, GC avoidance and colocation.
10. Take this away: an exchange isn't buying machines, it's buying one queue order nobody can alter.