Design a stock exchange
An exchange is a correctness-first, latency-sensitive system whose whole architecture bends around one decision: make the matching core a single deterministic writer, and arrange everything else to feed it and read from it without ever getting in its way.
This is the anchor case for the exchange arc. Here we build the whole pipeline and the order book. Two satellites zoom in: C39 (match buy and sell orders) opens the matching kernel itself — price-time priority, partial fills, cancel/replace — and C38 (microsecond-latency architecture) opens the latency budget — kernel bypass, busy-spin, NUMA pinning. We introduce the pipeline; they go deep. Cross-link, don't duplicate.
1. Clarify the contract
Treat the prompt as a product contract before drawing boxes. A central-limit-order-book (CLOB) exchange must:
- Accept and cancel orders — limit and market orders, with a client-supplied order ID for idempotency.
- Match by price-time priority — best price first; within a price level, oldest order first (FIFO). This rule is fairness.
- Publish trades and market data — both a public feed (top of book, depth) and per-participant fill reports.
- Persist a complete, ordered audit trail — every input the matcher saw, in the order it saw it, durable enough to reconstruct any historical book state.
- Run pre-trade risk checks — reject orders that breach a participant's limits before they can create a trade.
And, just as importantly, what it need not do, so the core stays small: it is not a custody/settlement system (T+1 settlement, clearing, and ledger live downstream — see C33's double-entry ledger); it is not where you do analytics or surveillance (those consume the published log offline); and it does not need horizontal scaling within a symbol. Keeping these out of the matching loop is what keeps the loop fast.
2. Put numbers on the shape
The numbers drive the architecture, so derive them rather than asserting them.
Per-symbol throughput. A well-written single-threaded matching loop touches only in-memory data: a couple of price-level lookups, a queue pop, an arithmetic fill. That is on the order of ~1 μs of CPU work per order, giving a ceiling near 1 / 1\,\mu s = 10^6 ≈ 1M orders/s for one symbol on one core. Real venues run lower (more bookkeeping, risk, logging) but the point stands: one core is more than enough for even the busiest single symbol, whose peak is tens of thousands of messages/s. The scarce resource is not throughput — it is latency and determinism. That is why you spend the core on being predictable, not on being parallel.
Scaling across symbols. With ~10,000 listed symbols and one logical matcher per symbol, you do not need 10,000 cores — you pin many symbols' books to a core and shard cores across a handful of matching servers. Symbols are independent (an AAPL order never touches the TSLA book), so this is embarrassingly parallel between books and strictly serial within one.
The journal latency delta — the load-bearing number. Every input order must be journaled before it is considered accepted (that is what makes replay possible, below). You can do this two ways, and the gap is enormous:
An fsync() that forces the write to stable storage costs on the order of 1 ms — a spinning disk seek, or a flush to an SSD/NVMe and back. Your entire matching loop is ~1 μs. So a naive "fsync every order" makes durability 1000\times more expensive than matching — the journal becomes the whole latency budget. A buffered, batched append (write to an OS page-cache-backed log and group-commit many orders per fsync) brings the per-order amortized cost to ~10 μs, a ~100× win. The price you pay is a recovery window: orders accepted but not yet flushed can be lost on a sudden power cut. The whole sync-vs-async persistence trade-off below is exactly this number — you are buying ~100× latency by accepting a sub-millisecond loss window, and you close that window with replication (a second node acks the input) rather than with the disk.
3. Define the surface area
Keep the API small; it expresses operations, not internals.
| API / operation | Why it exists |
|---|---|
submit(client_order_id, symbol, side, price, qty, type) | Place a limit/market order. client_order_id is the idempotency key (C35 mechanics) so a retried submit never double-places. |
cancel(client_order_id) | Remove a resting order. Also serialized through the same input stream as a submit. |
subscribe(symbol, depth) | Join the market-data feed — top of book, or N levels of depth, or a full event stream. |
trade_report (push) | Per-participant fill notification: which of my orders traded, at what price and quantity. |
4. Model the data — the order book
The data model is the architecture. The central object is the order book for one symbol: two sorted collections of price levels (bids, descending; asks, ascending), where each level is a FIFO queue of resting orders. Price-time priority falls straight out of this shape: the best price is the head of the sorted side, and within a level the oldest order is the head of the queue.
A new buy limit order at 150.02 would cross the spread, match against the resting 200 at the best ask, and either fill or rest as the new best bid. The matcher's inner loop — exactly how it walks levels, splits partial fills, and handles cancel/replace — is the subject of C39; here we care that the book is an in-memory, single-owner structure.
5. Linearized design — follow one order through the pipeline
Walk the order in the order it actually moves. The shape to internalize is a funnel into a single writer, then a fan-out: gateway → risk check → sequencer → matcher → market-data fanout.
- 1. Gateway. Authenticate the session, validate and normalize the message (symbol exists, price tick valid, quantity sane), and stamp the
client_order_idfor idempotency. This is the only place that talks to untrusted clients; the core never does. - 2. Pre-trade risk. Check the participant's limits — buying power, position/exposure caps, fat-finger price bands — before the order is allowed to be sequenced. (Why before, not after, is a deep dive.)
- 3. Sequencer. Assign every accepted order a strict, gap-free sequence number and append it to the sequenced input log. This single ordered stream is the heart of the system: it is the total order of everything that ever happened.
- 4. Matching core (single writer). One thread per symbol consumes the sequenced log in order and applies each input to its in-memory book deterministically. It is a pure function of (current book state, next input) → (new book state, output events). No clocks, no random, no shared mutable state.
- 5. Market-data fanout. The matcher's outputs — fills and book deltas — are published to the public feed and to per-participant fill reports. Crucially this is a separate path that reads the output stream; it never reaches back into the matcher.
The first bottleneck is now visible and intentional: everything funnels through one writer per symbol. That is not a flaw to fix; it is the property that makes the exchange correct and replayable. The job is to keep that writer's loop tiny.
6. Deep dives
6.1 Single-thread book vs distributed book — why exchanges choose determinism
The tempting "scalable" design is to shard one symbol's book across machines and coordinate with locks or a consensus protocol per order. It is the wrong instinct here, and seeing why is the senior signal. Two costs sink it:
- Coordination latency. Distributed locking or a Paxos/Raft round (lesson 10) costs hundreds of microseconds to milliseconds per order — three orders of magnitude over the ~1 μs single-thread match. You would spend your entire latency budget agreeing on order before you ever matched one.
- Non-determinism. The moment two threads can interleave on one book, the fill outcome depends on scheduling — which is irreproducible. You lose the ability to say "given these inputs, the book must be in this state," which is exactly what auditing and recovery require.
So the design inverts: one thread, no locks, no contention — the book lives in L1/L2 cache and the loop is a tight, branch-predictable hot path. The "throughput ceiling" cost (you cannot exceed one core's matching rate per symbol) is a non-issue because one core already exceeds any single symbol's real volume by 1–2 orders of magnitude. This is single-leader replication (DDIA Ch. 5) applied to matching: one writer owns the data so that ordering is unambiguous, and you scale across leaders (symbols), never within one. The microsecond-level techniques that make this single thread actually hit its budget — busy-spin instead of blocking, kernel bypass, pinning the thread to an isolated core — are C38.
6.2 The sequenced log: total-order broadcast → deterministic replay = state-machine replication
This is the conceptual core. The sequencer turns a chaotic set of concurrent submits and cancels into a single linear sequence — order #1, #2, #3, … — that every downstream component sees identically. That is precisely total order broadcast (DDIA Ch. 9): a message-delivery primitive where all consumers see all messages in the same order. The matcher is then a deterministic state machine, and feeding the same ordered inputs to a copy of that state machine reproduces the same state exactly. That equivalence — total order broadcast + deterministic state machine = state-machine replication — is what buys you three things at once:
- Recovery: rebuild a crashed book by replaying the log from a checkpoint (the senior question below).
- Hot standby: a backup node consumes the same sequenced log and stays bit-for-bit identical, ready to take over.
- Audit: a regulator replays the log offline and gets exactly the fills the exchange reported — the system is its own proof.
DDIA Ch. 11 makes this an explicit example: log-based stream processing where the log is the system of record and all views are derived from it. The matcher's in-memory book is just a materialized view of the log; the log, not the book, is the durable truth. Note the ordering point is also where durability lives — you journal at the sequencer, before matching, so the recorded input order is the authority. The persistence trade-off from §2 lives right here.
6.3 Market-data fanout — read-side scaling without touching the writer
Order ingress is modest (thousands/s per symbol); market-data egress can be orders of magnitude larger — every price change multiplied by every subscriber (market makers, brokers, retail apps, surveillance). If the matcher had to fan that out itself, the slowest subscriber would back-pressure the hot path. So fanout is a strictly separate stage that consumes the matcher's output stream:
- Multicast at the wire level (UDP multicast on the colocation LAN): publish each update once, the network replicates to all subscribers — O(1) work for the publisher regardless of subscriber count. Subscribers detect gaps by sequence number and request retransmit out-of-band.
- Conflation for slow/retail consumers: if a subscriber cannot keep up, collapse intermediate book states and send only the latest snapshot — trading precision for bandwidth. This is the "full vs conflated feed" trade-off; professional feeds take every tick, retail takes conflated.
- Decoupling means a stalled subscriber never slows matching — the same asynchronous-messaging boundary as lesson 11, applied so that read-side load can never harm the write path.
7. Trade-offs
| Choice | Buys | Costs | Choose when |
|---|---|---|---|
| Single-thread book vs distributed book | determinism + ~1 μs matches, replayability | per-symbol throughput ceiling (one core) | essentially always for a CLOB core |
| Sync fsync vs buffered/group-commit journal | sync: zero loss window | sync: ~1 ms/order, ~100× the matching cost | buffered + replication for latency; sync only if no replica |
| Full market data vs conflated feed | full: every tick, exact | full: high fanout bandwidth | full for pro/algo feeds, conflated for retail |
| Strict price-time fairness vs throughput batching | auditable fairness | less batching efficiency | CLOB; batching suits periodic-auction venues |
The sharpest one is sync vs async persistence, and the senior framing is to refuse the false choice. Synchronous fsync (~1 ms) makes durability dominate the entire latency budget; pure async risks losing accepted orders on a crash, which is unacceptable for a regulated venue. The resolution is to move durability off the disk's critical path and onto the network: a buffered, group-committed local journal (~10 μs amortized) plus synchronous replication of each sequenced input to a hot standby. An order is "accepted" once a second node has it in memory — replication latency (microseconds on a colo LAN) replaces fsync latency (milliseconds), and the loss window closes because two independent nodes would have to fail simultaneously. You bought ~100× latency without giving up durability.
8. Failure modes
| Failure | Mitigation |
|---|---|
| Matching engine crashes mid-session | Promote the hot standby (already tailing the sequenced log) for instant failover; rebuild any cold replica by replaying the log from the last checkpoint and verifying with state checksums (see Q&A). |
| Duplicate order submit (client retry) | Gateway dedups on client_order_id (C35 idempotency mechanics) before sequencing — the matcher only ever sees each order once. |
| Market-data lag / slow subscriber | Fanout is a separate path from matching, so it cannot back-pressure the core; subscribers detect gaps by sequence number and request retransmit; conflate for those who fall behind. |
| Risk state stale (risk service unreachable) | Fail closed: fence the session and reject new orders rather than admit unchecked exposure into the book. |
| Sequencer is a single point of failure | Active/standby sequencer with the seq# as a fencing token; the log's gap-free numbering makes a missed or duplicated sequence immediately detectable. |
9. Interview prompts you should be ready for
- The matching engine crashes mid-session — rebuild the exact book state. (senior answer) The book is a deterministic function of the sequenced input log, so I replay it. Concretely: take the most recent checkpoint (a periodic full book snapshot tagged with the seq# it reflects), load it, then replay every sequenced input after that seq# in order. Because the matcher is deterministic — no clocks, no randomness, no shared state — replay reproduces the identical book. I verify with a state checksum: the live engine emits a rolling hash of book state at known sequence points, and the rebuilt engine must match it at the same seq#, proving the reconstruction is bit-for-bit correct. In practice a hot standby has been tailing the same log all along, so failover is instant and replay is only needed to bring a cold node back. This is state-machine replication (DDIA Ch. 9/11): the log is the truth, the book is a derived view.
- Why single-threaded? Isn't that throwing away parallelism? (senior answer) Matching one symbol is inherently serial — deciding which order trades first is the product, you cannot do it concurrently without a tiebreaker that is itself a serialization. A single in-cache thread matches in ~1 μs, which beats any locked or consensus-coordinated design by 2–3 orders of magnitude, and it is deterministic, which locking is not. I parallelize across symbols (independent books, embarrassingly parallel) and never within one. One core already exceeds any real symbol's volume.
- How is durability not a latency disaster if matching is ~1 μs? (senior answer) A synchronous
fsyncis ~1 ms — 1000× the match cost — so fsync-per-order is a non-starter. I use a buffered, group-committed journal (~10 μs amortized) and get my durability guarantee from synchronous replication to a hot standby instead of from the disk: an order is accepted once a second in-memory node holds it. Replication on a colo LAN is microseconds, so I keep low latency and still survive a single-node crash. - Why must risk checks run before sequencing, not after matching? (senior answer) Once an order is sequenced and matched, it has created a trade — an irreversible, published, settling event. Risk after the fact can only detect a breach, not prevent it; you would be unwinding real trades. Pre-trade risk is the only place to reject buying-power or fat-finger violations before they become market events. The cost is a bit of latency in the gateway path, which is acceptable because risk state is read-mostly and cacheable per session.
- What exactly does the sequencer guarantee, and why does it matter? (senior answer) Gap-free total order: every accepted input gets a strictly increasing seq# and all consumers — matcher, standby, market data, audit — see the same sequence. That is total-order broadcast (DDIA Ch. 9). It is the single thing that makes deterministic replay, hot standbys, and regulatory replay all possible from one mechanism. Without a single ordering authority, "what happened first" becomes ambiguous and the system is neither replayable nor auditable.
- Why separate the market-data path from the matching path? (senior answer) Egress can be orders of magnitude larger than ingress, and subscribers vary wildly in speed. If the matcher fanned out directly, the slowest subscriber would back-pressure the hot path. So fanout consumes the matcher's output stream asynchronously (multicast, plus conflation for slow consumers), and a stalled subscriber can never slow matching. Read-side load is fully isolated from the write path.
- How do you handle a participant submitting the same order twice on a network retry? (senior answer) Idempotency at the gateway on
client_order_id(C35's insert-if-absent mechanics): the first submit is sequenced, a retry with the same ID is recognized and returns the prior result without re-sequencing. The matcher therefore only ever sees each order once, preserving the determinism of the input log.
Related lessons
This case anchors the exchange arc: C39 opens the matching kernel (price-time priority, partial fills, cancel/replace) that we treated as a black box here, and C38 opens the microsecond latency budget (kernel bypass, busy-spin, NUMA pinning) that makes the single-thread loop hit ~1 μs. On the foundations: the sequenced log is lesson 09's total-order broadcast and linearizable ordering; making the sequencer/standby reliable is lesson 10's consensus and leader election; the single-writer-owns-the-data pattern is lesson 08's single-leader replication; the read-side decoupling is lesson 11's async messaging; and idempotent submits reuse C35's idempotency-key mechanics.