Design a Stock Exchange

"Buy 100 at $50" must instantly find a match or wait for one. What structure makes that fast and correct?

1. Rejected. Scan all open orders for a match on each new order.

   Scanning every open order per incoming order is O(N) on the hottest path in the system — far too slow for microsecond matching. You need a structure sorted for instant best-price lookup.

2. Rejected. Store orders in a database and query for matches.

   A round-trip to disk-backed storage per order is orders of magnitude too slow, and SQL can’t express price-time matching cheaply. The book must live in memory, purpose-built.

3. The call. An in-memory order book of sorted resting bids/asks.

   Best bid and best ask sit at the top; matching crosses the spread — highest bid against lowest ask — until they no longer overlap. A market order takes best price; a limit order rests if it can’t match.

Many orders want the same price. Who trades first, fairly?

1. Rejected. Largest order first to maximize volume.

   Favoring size lets big players jump the queue and punishes small orders — manifestly unfair, and traders will leave. Fairness can’t depend on order size.

2. The call. Price-time priority: best price, then earliest order (FIFO).

   Best price wins; among equal prices the earliest order fills first. Organizing the book as price levels, each a FIFO queue, builds the rule into the data structure — deterministic and auditable.

3. Rejected. Randomly pick among equal-priced orders.

   Randomness makes fills unpredictable and unauditable — a trader can’t reason about where they stand in line. Matching must be deterministic, so equal-priced orders need a stable order: time.

A trader could submit an order they can’t afford or that blows past limits (fat-finger, rogue algo). Where do you stop it?

1. Rejected. Let it match, then unwind the trade if it can’t settle.

   Unwinding executed trades is disruptive, may be impossible once others traded against them, and corrupts the market. Bad orders must be stopped before they execute, not after.

2. Rejected. Check risk inside the matching engine.

   Putting credit/position checks in the single-threaded hot loop adds latency and non-determinism to the core. Keep the matcher tiny and fast; validate before it.

3. The call. A pre-trade risk check on the admission path, before matching.

   Verify buying power, position/credit limits and price/size sanity at the gateway, rejecting violations immediately — so only valid orders ever touch the engine, and the hot loop stays fast and deterministic.

Orders arrive concurrently from everywhere. How do you make matching fair, auditable, and replica-safe?

1. Rejected. Match concurrently with multiple threads for speed.

   Racing threads can’t guarantee the order events were processed, breaking fairness and making the engine non-reproducible — so replicas diverge. The core must process one agreed order.

2. The call. One sequencer assigns a global order; a single-threaded engine consumes it.

   A sequencer stamps every admitted order with a global sequence number, then a single thread processes that one stream — same input order, same output, on primary and every replica. Astonishingly fast in-memory, and perfectly reproducible.

3. Rejected. Timestamp orders and sort by wall clock.

   Wall clocks differ across machines and tie at microsecond scale, so timestamps don’t give a single agreed order. You need one authoritative sequencer assigning a total order, not independent clocks.

Every participant needs book updates and trades — and a latency edge is worth millions. How do you distribute fairly?

1. Rejected. Let each participant poll the engine for updates.

   Polling gives whoever polls fastest (or is closest) a systematic edge, and hammers the engine. Market data must be pushed equally, not pulled at each participant’s own rate.

2. Rejected. Send updates fastest to whoever pays the most.

   Selling a latency advantage is exactly the unfairness a fair exchange must prevent — it lets some systematically see the market first. Delivery should be equal-latency for all.

3. The call. Broadcast every change from one source with equal-latency delivery.

   The engine emits each change to a market feed (often multicast) so the same picture reaches everyone simultaneously. Distributing data fairly matters as much as matching fairly.

The order book lives in volatile memory for speed. How do you survive a crash without losing trades?

1. Rejected. Periodically snapshot the book to disk.

   A snapshot every few seconds loses every order and trade since the last one — catastrophic and possibly illegal for an exchange. Every event must be durable before it takes effect.

2. The call. Journal every event to an append-only log before applying it.

   Log first, apply second: on failure a replica replays the journal to reconstruct the exact book, and because the engine is deterministic the replay reproduces an identical result. The sequential write is cheap.

3. Rejected. Replicate the in-memory book to a hot standby synchronously.

   Synchronously copying full book state on every change is slow and still loses the in-flight event on a crash. Journaling the ordered event stream is cheaper and, with determinism, rebuilds state perfectly anywhere.