Design a Stock Exchange

• Accept limit and market orders — Place, cancel and replace, each acknowledged with a deterministic outcome. An acknowledgement is a promise about a position in a sequence, not a hope.
• Match by price, then time — The best price wins; at the same price the earlier order wins. This single rule is the product, and every design choice defends it.
• Publish market data — Top of book and full depth, plus a trade tape, to thousands of subscribers with identical content and no subscriber advantaged over another.
• Report fills to the owning participant — A private stream per participant carrying their own fills and order state, which must never miss an event.
• Risk checks before an order reaches the book — Credit, position and fat-finger limits. A rejected order must never touch the book, and the check must not cost the latency budget.
• Open, close, halt and replay — Auctions at the open and close, a halt on extreme moves, and the ability to reconstruct the day exactly from the log for regulators.
• Out of scope — Clearing and settlement (T+1 with a clearing house), custody of assets, market-maker incentive schemes, and the retail brokerage in front of the exchange.

• Matching latency (p99 < 100 µs in the engine) — Measured from the order entering the engine to the fill leaving it. Microseconds, not milliseconds: this is the one system in this catalogue where the units change.
• Determinism (byte-identical replay) — Replaying the input log must produce exactly the same fills in the same order. Without it there is no audit, no recovery and no failover.
• Throughput (1 M orders/s peak per symbol group) — The open is several times the average. Sizing for the average means failing exactly when it matters.
• Durability of the sequence (no acknowledged order lost) — An order acknowledged and then forgotten is a legal problem, not an engineering one.
• Fairness (equal access, provable order) — Every participant sees a change at the same moment, to within the physics. Ordering is decided in one place and is auditable afterwards.
• Availability (failover < 1 s, no lost state) — A halted market is preferable to an inconsistent one, but a market that halts often is not a market anyone uses.
• Auditability (every event retained 7 years) — Regulators ask what happened at a named microsecond, years later, and expect an exact answer.

• Orders per second: ~1 M/s peak — 5 000 symbols × ~200 orders/s each at the open = ~1 M/s, and the majority are cancels: a modern market is dominated by quote updates, not by trades.
• Order-to-trade ratio: ~20:1 — Market makers post and pull constantly, so roughly 20 order messages per executed trade. That is why cancel latency matters as much as match latency, and why the book is mostly churn.
• Order book memory per symbol: ~5 MB — ~50 k resting orders × ~100 B (id, participant, price, quantity, timestamp, links) = ~5 MB. 5 000 symbols = ~25 GB across the cluster — the entire market fits in the memory of a few machines.
• Event log volume: ~10 TB/day — 1 M/s at peak, averaging ~100 k/s over a 6.5-hour session ≈ 2.5 B events/day × ~200 B = ~500 GB/day of orders, and several times that with fills and book deltas: ~10 TB/day in total, retained seven years in cold storage.
• Market data fan-out: ~5 GB/s — 2 000 subscribers × full depth updates at ~2.5 MB/s each = ~5 GB/s, which is why data is multicast to a fan-out tier rather than unicast from the engine.
• Matching cost per order: ~1 µs — A price level lookup in an array indexed by ticks, then a walk of a linked list at that level: a handful of cache-friendly memory accesses, ~1 µs. The remaining 99 µs of the budget is network, serialisation and sequencing.
• Replication cost: ~30 µs — Replicating each sequenced event to two standbys in the same rack before acknowledging: ~10–30 µs on a tuned network. This is the price of not losing acknowledged orders, and it is a third of the whole budget.

• Participant (FIX / binary) — A broker, market maker or algorithmic trading firm, usually co-located in the same building. Sends orders and cancels, consumes its private fill stream and the public market data feed.
• Order gateway — Terminates the session, authenticates, decodes the wire protocol into the internal binary format, and timestamps arrival with a hardware clock. Deliberately thin: everything it does is on the latency budget.
• Pre-trade risk — Credit, position and sanity limits, evaluated from in-memory state in a few microseconds. Nothing reaches the book without passing it, because an exchange that lets a participant trade beyond its credit becomes the counterparty to the loss.
• Sequencer — The single point that decides order. Stamps every message with a monotonic sequence number and a timestamp, and that stamp is the definition of "first". One process per symbol group; its throughput is the market's throughput.
• Sequenced log (replicated in-memory ring + disk) — The ordered, durable record of every input. The matching engines are pure functions of this log, which is what makes replay, recovery and audit the same mechanism.
• Matching engine (single-threaded, in-memory book) — Consumes the log in order and applies price-time priority. Single-threaded on a pinned core with no allocation in the hot path: determinism first, and the speed follows from having no locks rather than from clever parallelism.
• Order book (in-memory, per symbol) — Price levels as an array indexed by ticks, each level a linked list of resting orders in arrival order, plus a hash from order id to node for O(1) cancel. Cancels are most of the traffic, so the structure is shaped around them.
• Hot standbys — Engines consuming the same log and applying the same transitions, in lockstep. Because the engine is deterministic, a standby is not a copy of state — it is the same computation, so failover is promoting a process that is already correct.
• Market data publisher (multicast) — Turns engine output into book deltas and a trade tape and multicasts them, so every subscriber receives the same packet at the same moment. Unicast would make the first recipient systematically faster, which is unfair by construction.
• Subscribers — Market makers, vendors and surveillance systems. Sequence numbers on the feed let a subscriber detect a gap and request a retransmission rather than silently trading on a stale book.
• Private fill stream — Each participant's own order state and fills, delivered reliably and in order. Unlike market data, a missed message here is unacceptable, so it is replayable by sequence number per participant.
• Event archive (object store, 7 years) — Every sequenced input and output, immutable, indexed by symbol and time. The regulator's copy and the input to any replay.
• Surveillance & reporting — Replays the log to detect manipulation — spoofing, layering, wash trades — and produces regulatory reports. Runs on the same log the engine consumed, so it can never disagree with what happened.

1. A buy order crosses the spread — The path that defines the system. Note that ordering is decided once, early, and everything downstream is a consequence.
   1. A participant sends a limit buy for 500 at 101.25; the gateway decodes and timestamps it.
   2. Pre-trade risk checks credit, position and sanity limits from in-memory state.
   3. The sequencer assigns the next sequence number for the symbol group.
   4. The sequenced event is replicated and appended to the log before it is acted on.
   5. The engine reads the event and walks the ask side while the price crosses.
   6. Fills go to the private streams of both sides; the book delta and the trade go to market data.
   7. Positions update in the risk service and the event lands in the archive.
2. A market maker cancels and re-quotes — Twenty times more common than a trade, and where the book's data structure earns its keep.
   1. The maker sends a cancel for a resting order.
   2. It is sequenced like any other message.
   3. The engine finds the order in O(1) and unlinks it from its price level.
   4. If the order already filled, the cancel is rejected as too late.
   5. A book delta is published, and the maker immediately posts a new quote.
3. The opening auction, and the burst behind it — The scale-breaking case. Order rate is five times normal in the first seconds and the price is discovered by a different algorithm entirely.
   1. Orders accumulate during the pre-open without matching.
   2. An indicative price is published periodically so participants can react.
   3. At the bell the engine computes the single price that maximises executed volume.
   4. Fills are published in one burst; the book flips to continuous trading.
   5. Order rate peaks at five times normal for the first seconds.
   6. A symbol too volatile to open is held in auction rather than opened badly.
4. The matching engine dies mid-sequence — The failure path. Because the engine is a pure function of the log, recovery is resumption rather than reconstruction.
   1. The primary engine stops responding after processing sequence 88 412 900.
   2. A standby that has consumed the same log to the same point is promoted.
   3. Fencing ensures the old primary cannot publish if it comes back.
   4. The new primary resumes at 88 412 901 and replays anything sequenced during the gap.
   5. Participants reconcile their own state from the private stream by sequence number.
   6. Trading resumes, typically inside a second, and the pause is published.
5. Publishing the book to two thousand subscribers — Fan-out where fairness is a physical property: the same packet, at the same moment, to everyone.
   1. The engine emits a book delta for every change.
   2. The publisher multicasts the delta with a sequence number.
   3. A subscriber detects a gap in the sequence and requests a retransmission.
   4. Periodic full snapshots let a late or lost subscriber recover without a full replay.
   5. Surveillance consumes the archived log rather than the live feed.

Ask: How do you establish a single, provable order for messages arriving from everywhere at once?

Good answers name: A single sequencer per symbol group, replicated for failover, Distributed consensus (Raft) for every message, Synchronised clocks and timestamp ordering, Per-gateway sequences merged downstream.

Our pick: One sequencer process per symbol group, assigning a monotonic sequence number and an authoritative timestamp, replicating each event to hot standbys before acknowledging, and writing it to a durable log. Symbol groups are the horizontal axis, sized so no group approaches one core's capacity. The engine and every downstream consumer derive their ordering from the sequence number and never from a clock.

1. The sequencer is a single point of failure. Justify that.
   It is a single point of *order*, which is what the product sells, and single points are not automatically bad when they are simple and replicated. It does almost nothing — assign a number, replicate, append — so it has very few failure modes, and its standbys are byte-identical. Removing it would not remove the requirement for a total order; it would only make that order harder to prove.
2. How do you fail over without forking the sequence?
   Epoch fencing. Promotion increments an epoch, every output carries it, and consumers reject anything from a lower epoch. The old sequencer, if it revives, finds its outputs ignored. A failover without fencing produces two sequences claiming the same numbers, which is the worst possible outcome — worse than a longer halt.
3. Why per symbol group rather than one global sequencer?
   Because there is no cross-symbol ordering requirement: an order in ACME and an order in BETA never interact. Grouping gives horizontal scale for free, and the only cost is that cross-symbol events — an index calculation, a basket order — need a defined rule, usually by sequencing them into every affected group.
4. A participant claims their order arrived first. How do you answer?
   With the gateway's hardware arrival timestamp and the assigned sequence number, both archived. If they were sequenced later despite arriving earlier, that is a gateway or network issue and it is visible in the data. The whole design exists so this conversation has an evidenced answer rather than a plausible one.

Ask: How do you get both microsecond latency and byte-identical replay?

Good answers name: Single-threaded engine per symbol group, pure function of the log, Multi-threaded with locks on price levels, Shard by symbol across threads on one machine, Distributed matching across machines for one symbol.

Our pick: One single-threaded engine per symbol, several pinned to dedicated cores on a machine, each a pure deterministic function from the sequenced log to fills and book deltas. No wall-clock reads, no random numbers, no iteration over unordered collections, no allocation in the hot path. Standbys run the identical binary over the identical log, and any divergence between primary and standby output is treated as a critical defect.

1. How do you actually detect non-determinism?
   Continuously: standbys compute a rolling hash of their output stream and compare with the primary. A mismatch is an immediate alert and a halt candidate, because a diverged standby cannot be failed over to. It also catches the subtle causes — a library upgrade changing a hash order, a compiler flag changing floating-point behaviour.
2. Prices are decimals. Are you using floating point?
   No. Prices are integers in ticks and quantities are integers, so all arithmetic is exact and identical on every machine. Floating point in a matching engine is a classic, subtle source of divergence between primary and standby, and there is no upside to it here.
3. The engine needs the current time for order timestamps. Does that break determinism?
   It would, so it does not read the clock. Time comes from the sequenced event, stamped once by the sequencer, and the engine treats it as data. Any input that is not in the log is a source of divergence, and the discipline is that the log is the only input.
4. What is the garbage collection story?
   Avoid it entirely in the hot path: pre-allocated object pools, ring buffers, no allocation per message. In a managed runtime that means running with essentially no garbage produced during the session; in a native one it means no malloc on the path. A collection pause of a few milliseconds is a hundred times the entire latency budget.

Ask: How do you store a book so that match, cancel and best-price are all fast?

Good answers name: Array of price levels indexed by tick, each a linked list, plus an id-to-node hash, Balanced tree (or skip list) of price levels, Two heaps, one per side, Hash map from price to a level object.

Our pick: A per-side array of price levels indexed by tick offset from a rebasable origin, each level holding an intrusive doubly linked list of orders in arrival order, with a hash from order id to its node for O(1) cancel and a cached best-price index per side. Nodes come from a pre-allocated pool so the hot path never allocates, and the array is rebased during a natural pause if the price walks out of range.

1. How wide is the array in practice?
   A few thousand ticks either side of the current price covers all realistic activity, which is tens of kilobytes of pointers per side — comfortably in L2. Orders far outside the band are rare and can go to an overflow structure, joining the array when the price approaches them.
2. Why an intrusive linked list rather than a vector per level?
   Cancel. Removing from the middle of a vector is O(n) and shifts memory; with an intrusive list the hash gives the node directly and removal is two pointer writes. Since cancels dominate, that trade is the whole argument — even though a vector would have better locality for matching.
3. What does the engine keep besides the two sides?
   Aggregate quantity per level, maintained incrementally so market data can publish a level without walking it; the best-price index per side; and the id-to-node hash. Recomputing aggregates on publish would make the market data path scale with book depth rather than with the change.
4. How do hidden or iceberg orders fit?
   They rest in the book with a displayed quantity and a hidden remainder. Matching consumes the hidden part, and only the displayed quantity is published. Priority rules usually rank hidden liquidity behind displayed at the same price, which is a policy decision that has to be stated explicitly because it changes who gets filled.

Ask: When is an order safe, and what does the acknowledgement actually promise?

Good answers name: Replicate to in-memory standbys before acknowledging, persist asynchronously, Write to disk before acknowledging, Acknowledge on receipt, replicate afterwards, Cross-datacentre synchronous replication.

Our pick: The sequencer replicates each sequenced event to two standbys over a low-latency fabric and acknowledges once both have it in memory — roughly 30 µs. The log is flushed to local NVMe asynchronously and shipped to the archive continuously. A remote site replicates asynchronously for disaster recovery, with an explicit and published recovery point: a site-loss failover may lose the last fraction of a second, and the market halts rather than pretending otherwise.

1. Rack loses power. What did you lose and what do you do?
   Whatever was acknowledged but not yet flushed — at most a few milliseconds of events. The market halts, the log is recovered from disk and from the archive, and the end of the sequence is reconciled against participants' own records before reopening. A halt with a documented reconciliation is survivable; silently reopening with a different book is not.
2. Why two standbys rather than one?
   So that losing the primary still leaves two copies, and the promoted standby is not a single copy while a replacement starts. It also means a standby can be taken out for maintenance without dropping to a single point of durability during the session.
3. What does the participant do if they never get an acknowledgement?
   Never blind-retry. They query order status by their own client order id, which is unique and idempotent on our side, and act on the answer. A retry that creates a second order because the first was acknowledged but the ack was lost is one of the most expensive bugs a trading firm can have.
4. How is the archive kept honest?
   It is written from the sequenced log, checksummed per segment, and periodically replayed end to end in a separate environment to confirm it reproduces the day's fills exactly. An archive that has never been replayed is a hope, not a backup — and the one time it is needed is the one time that matters.

Ask: What does it mean for an exchange to treat participants equally, and what enforces it?

Good answers name: Equalised cable lengths, multicast market data, single sequencer, published latency statistics, Randomised delay (a "speed bump") on incoming orders, Batch auctions every few milliseconds instead of continuous matching, Do nothing; let participants buy advantage.

Our pick: Equal-length cabling to every colocated rack, identical gateway hardware and software, one sequencer deciding order, and multicast market data so every subscriber receives the same packet simultaneously. Per-gateway latency distributions are published so participants can verify there is no faster door. Where a genuine advantage remains — a participant's own hardware — it is theirs to have; what the exchange controls, it equalises.

1. Market data reaches a co-located firm before a remote one. Is that unfair?
   It is physics, and it is disclosed rather than hidden: colocation is sold on equal terms to anyone who wants it. What would be unfair is an asymmetry inside the venue — one gateway faster than another, or a fan-out that serves some subscribers first. The line is between advantages the exchange creates and advantages the participant buys transparently.
2. Does the private fill stream reach a participant before the public tape?
   It generally does, and that is deliberate and disclosed: a participant learns about their own fill first. The asymmetry that matters is whether anyone learns about *someone else's* fill early, and they do not — the public tape is multicast to everyone at once.
3. How would you detect a fairness bug?
   Measure and publish the distribution of gateway-to-sequencer latency per gateway, and alert on divergence between them. A gateway that is consistently ten microseconds faster is a real, exploitable advantage that would otherwise be discovered by a participant before it is discovered by us — which is the worst way to find out.
4. What about co-location customers with more cross-connects?
   Port capacity is sold in defined tiers with published limits, and the sequencer's per-participant rate limits prevent one firm from crowding the ingest path. More bandwidth is not more priority: the sequencer processes messages in arrival order regardless of who sent them.