Designing a Stock Exchange — Matching Engine, Sequencer & Market Data, Traced

The design where you scale down, not out

Every other system in this guide scales by adding machines and accepting weaker ordering. An exchange cannot: it must produce a single, fair, deterministic order of events, because the order is the fairness guarantee. If two traders submit at the same instant, exactly one gets the fill, and the rule deciding which must be consistent and defensible.

So the central design move is the opposite of the usual instinct: make the core single-threaded, and make it fast enough that you do not need to shard it. A modern matching engine running one instrument in one thread with its data in memory can process millions of orders per second, because there is no lock contention, no coordination, and no cache-line ping-pong. Concurrency is added by running different instruments on different engines, never by parallelizing one book.

Requirements

• Accept, match, cancel orders with price–time priority.
• Publish market data (quotes, trades) to participants.
• Latency measured in microseconds, with tail latency mattering more than the mean.
• Deterministic and auditable — a regulator can ask you to prove why a trade happened.
• Lose nothing: an accepted order must survive machine failure.

Orders

A limit order specifies a worst acceptable price ("buy 100 at no more than 100.01") and rests in the book if it cannot fill — it provides liquidity. A market order specifies quantity only and takes the best available price — it consumes liquidity, with no price protection. Participants typically speak FIX, a long-established financial messaging protocol, or a lower-latency binary variant of it.

The matching engine and the order book

The order book per instrument holds resting bids (descending) and asks (ascending). The matching rule is price–time priority: better prices match first; among equal prices, the order that arrived first matches first. That tie-break is why a deterministic sequence is a regulatory concern and not merely an engineering preference — time priority is only meaningful if there is one agreed notion of "first".

The traced example: a market buy for 250 against the book above sweeps 200 at the best ask of 100.01, then walks up to fill the remaining 50 at 100.02. The average fill of 100.012 against a quoted 100.01 is slippage — and it exists because the quoted price is only the price of the top of the book. This is why L2 depth is commercially valuable: it lets a participant estimate the cost of size before committing to it.

Data structures follow from the access pattern: price levels in a sorted structure (or, since ticks are discrete, an array indexed by price for O(1) access), each level holding a FIFO queue of orders to preserve time priority, plus a hash map from order ID to its position so a cancel is O(1). Cancels vastly outnumber trades in real markets, so cancel performance dominates — a design optimized only for matching will be slow at what it actually does most.

The sequencer: where determinism comes from

Before reaching the engine, every inbound event passes through a sequencer that assigns a monotonic sequence number and writes the event to a durable log. The matching engine then consumes that log strictly in order.

This one component provides four properties at once, which is why it is the design's keystone:

• Determinism. The engine is a pure function of the ordered input, so the same log always yields the same trades.
• Fairness. One authority decides ordering, rather than it emerging from network races.
• Recovery. A crashed engine restarts, replays the log from its last snapshot, and arrives at exactly the state it had.
• Audit. The log is the record, so any trade can be reproduced and explained years later.

This is event sourcing with the ordering guarantee made explicit and central. It also means the engine must contain nothing non-deterministic: no wall-clock reads, no randomness, no unordered iteration, no external calls. Timestamps are assigned by the sequencer and carried in the event, so replay uses the recorded value. Violate this and replay produces different trades from the original — which is not a bug you can ship past a regulator.

Redundancy is achieved by replicating the sequenced stream to hot standby engines that process the same log and hold the same state, ready to take over. Because they consume an identical ordered input, failover does not require state transfer — the standby is already correct. Leader election (Raft-style terms, or a dedicated arbiter) decides which engine is primary, and the sequence number doubles as the fencing token: a demoted leader's writes are rejected because its term is stale, which is what prevents two engines from both believing they are primary.

Market data: three levels, three economics

The engine emits every book change; the market data publisher turns that into feeds:

• L1 — best bid, best ask, last trade. Small, and consumed by nearly everyone.
• L2 — aggregated quantity at each price level. What you need to estimate slippage.
• L3 — every individual order and its queue position. Enormous, consumed by few.

Note the inverse relationship: volume grows by orders of magnitude from L1 to L3, while subscriber count shrinks by the same. So L1 is a fan-out problem (many consumers, small payload — multicast or fan-out infrastructure) and L3 is a bandwidth problem (few consumers, vast payload — dedicated links). Publishing them over one path sized for the worst case wastes money; sizing for L1 and hoping is how you drop L3 subscribers under load.

Derived products come off the same stream — candlesticks (open/high/low/close per interval) are a windowed aggregation, computed once centrally rather than by every client. That is the same aggregation pattern as ad-click counting, applied to trades.

Latency engineering, briefly and honestly

At microsecond targets the usual advice inverts. Some of what real exchanges do:

• Keep everything in memory. The book never touches disk on the critical path; durability comes from the sequencer's log write, which is the one unavoidable I/O.
• Avoid copies and kernel transitions. Memory-mapped ring buffers between stages, and kernel-bypass networking so packets reach user space without a syscall per message.
• Avoid garbage collection pauses. A 10 ms GC pause is thousands of times the latency budget, so managed-runtime implementations pre-allocate and pool aggressively to avoid allocating on the hot path at all.
• Batch nothing on the critical path. Batching improves throughput and destroys latency — the opposite trade from the message-queue page, because here the tail is the product.

The honest framing: this is the one design in the guide where mechanical sympathy beats architecture. The distributed-systems toolkit — shard it, replicate it, cache it — mostly does not apply, because the requirement is a single total order. What is left is making one thread extremely fast and everything around it asynchronous.

Which approach, when

Decision	Option	Choose when	Breaks when
Concurrency	Single-threaded engine per instrument	Fairness and determinism required	One instrument exceeds one core — rare, but a hard ceiling
Concurrency	Multi-threaded on one book	Essentially never	Lock contention destroys latency and determinism
Scale-out	Partition by instrument	Many symbols — the natural axis	Cross-instrument atomic trades (baskets) need coordination
Ordering	Central sequencer + log	Determinism, audit, replay-based recovery	Sequencer is a single point — needs hot standby and fencing
Ordering	Timestamps at the gateway	Never for matching	Clock skew between gateways makes priority arbitrary and unfair
Durability	Log write before matching	Accepted orders must survive failure	Adds the one unavoidable I/O to the critical path
Recovery	Hot standby replaying the same log	Sub-second failover with no state transfer	Costs a full duplicate fleet running continuously
Market data	Separate paths per level	L1 fan-out and L3 bandwidth differ hugely	More infrastructure than one shared feed

Pitfalls

• Non-determinism in the engine — reading the clock, iterating a hash map, calling out to a service. Replay then disagrees with production, and the audit trail is worthless.
• Ordering by gateway timestamp. Clock skew across gateways makes time priority meaningless and systematically favours whoever's clock runs fast.
• Optimizing match throughput and ignoring cancels, which are the majority of real traffic.
• Floating-point prices. Use integer ticks or fixed-point; binary floats cannot represent decimal prices exactly and comparisons at price boundaries decide who gets filled.
• Batching or queueing on the critical path to raise throughput, at the cost of the tail latency that is the actual product.
• No fencing on failover. Two engines both believing they are primary will both match the same orders — the worst possible outcome in this system.
• Publishing market data before the trade is durably logged, so a crash can leave participants having seen a trade the exchange cannot prove happened.

Cost model — what dominates the bill

An exchange has an unusual cost profile: tiny data volumes, extraordinary per-unit infrastructure cost. Nothing here is large by the standards of this guide, and everything here is expensive.

Rough BOTE: even a busy venue handling 10 million messages/second at ~100 bytes each is 1 GB/s ≈ 86 TB/day of sequenced log — large but unremarkable, and a fraction of what the message-queue page handled. Retained for years for regulatory purposes it becomes petabytes, which at cold-tier prices is thousands of dollars a month, not millions.

The money goes elsewhere. Latency-optimized infrastructure costs orders of magnitude more per unit of work than commodity cloud: high-clock-speed CPUs with cores pinned and reserved, kernel-bypass NICs, low-latency switching, precision time synchronization, and co-location — where the venue's revenue and cost both concentrate, since participants pay substantially for rack space physically near the engine. Add a complete hot-standby fleet running continuously and doing no useful work in the normal case, plus a disaster-recovery site, and you are paying for roughly 2–3× the capacity you use.

Dominant line items: co-location and specialized network hardware; then the idle redundant fleets; then market-data distribution bandwidth (dominated by L3); then long-term regulatory retention, which is comparatively cheap.

Levers: tier old log segments to cold storage (retention is a read-rarely requirement); size market-data paths per level rather than uniformly, since L1 and L3 have opposite shapes; and partition instruments across engines so each stays within one core's budget rather than over-provisioning every engine for the busiest symbol. What you cannot economize on is the standby fleet or the log write — those are the correctness guarantees.

Operability: the fingerprints of a sick exchange

Here the metric that matters is not throughput but tail latency, and the fingerprints are unusually precise. P99.9 order-acknowledgement latency spiking while mean stays flat is the canonical signal, and its usual causes are distinguishable: a garbage-collection or allocation pause (periodic, sawtooth), a page fault or memory-mapped flush (correlated with log rotation), or an interrupt landing on a pinned core (correlated with network bursts). Because the budget is microseconds, anything that would be invisible elsewhere is a production incident here.

Sequence-number gaps in a market-data feed mean a subscriber dropped messages — which is why every feed carries sequence numbers and every client is expected to detect gaps and request a replay. A gap that the exchange cannot explain from its own log is far more serious: it suggests the publisher, not the network, lost data.

The most dangerous fingerprints are the correctness ones. Replay of the sequenced log producing different trades than production means determinism has been violated somewhere, and it invalidates the audit trail wholesale; it should be verified continuously against a shadow replay rather than discovered on request. Standby state diverging from primary means the same thing and is the earlier warning — two engines consuming one ordered log must agree exactly, so any divergence is a determinism bug caught before it matters.

Watch also for cancel latency degrading faster than match latency (the order-ID index is losing its O(1) behaviour) and book depth thinning at the top, which is a market-quality signal rather than a technical one but is often the first sign participants have detected unfairness or instability and pulled back. Signals worth having: order-ack latency at P99/P99.9/max, GC and pause histograms, sequencer log-write latency, primary-versus-standby state hash comparison, shadow-replay diff, per-feed sequence-gap counts by subscriber, and cancel-versus-match latency split.

---

Authored for this guide to cover the stock exchange design (Alex Xu Vol. 2, ch. 28 — not present in the Vol. 1 PDF); order-book and market-data-level diagram hand-authored as SVG. Complements this guide's "Design an Online Stock Brokerage System" (OO&LLD) page, which covers the object model rather than the exchange core, plus the leader-election, fencing-token and event-sourcing material.

I just read a lesson on **Designing a Stock Exchange — Matching Engine, Sequencer & Market Data, Traced** (System Design) and want to truly understand it. Explain Designing a Stock Exchange — Matching Engine, Sequencer & Market Data, Traced from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Designing a Stock Exchange — Matching Engine, Sequencer & Market Data, Traced** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Designing a Stock Exchange — Matching Engine, Sequencer & Market Data, Traced** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Designing a Stock Exchange — Matching Engine, Sequencer & Market Data, Traced** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.