59. Walkthrough: Design a Stock Exchange Matching Engine

Step 0 — Clarify the business goal

🎤 Candidate: For an exchange, the product is fairness and trust: strict price-time priority, the same market data to everyone at the same time, no lost or duplicated orders, and a full audit trail for regulators. Speed matters because market makers choose venues by latency and reliability, and their liquidity attracts everyone else. Are we a regulated equities exchange or a crypto exchange? And is clearing/settlement in scope?

🧑‍💼 Interviewer: A regulated equities exchange. Clearing is out of scope.

Step 1–2 — Requirements

Step 3 — Estimates

1M orders/s peak; average message ≈ 100 B → ~100 MB/s of input to journal & replicate
Per symbol: highly skewed — top symbols take a large share of messages → a single hot symbol
  can see 100k+ msgs/s → one core per hot symbol shard
Order book size: active orders per symbol: thousands to ~1M → fits in memory (MBs-GBs total)
Journal per day: 1M/s peaks, ~10B messages/day × 100 B ≈ 1 TB/day → sequential disk, cheap

Step 5 — High-level architecture

 Members (brokers, market makers) ─FIX / binary protocol─▶ Order gateways (session auth, throttles,
                                                           message validation, client order IDs)
     ▼
 Pre-trade risk (per member credit limits, price bands, max order size)  ← in-memory, µs
     ▼
 SEQUENCER  ── assigns a global, gap-free sequence number + timestamp to every inbound event
     │         journals to disk & replicates to standby BEFORE forwarding (durability point)
     ▼
 Matching engine shards (partitioned by symbol; each shard SINGLE-THREADED, pinned core,
   in-memory order books; consumes sequenced events in order; no locks, no wall-clock reads)
     │ outputs: acks, executions, book changes (also sequenced)
     ├──▶ Order gateways → members (execution reports)
     ├──▶ Market data publisher → UDP multicast (L1/L2/trades) — same packets to everyone
     ├──▶ Drop copy / surveillance / regulatory audit trail
     └──▶ Post-trade → clearing (out of scope)
 Hot standby engines consume the SAME sequenced stream and compute identical state
   (state-machine replication) → failover = promote standby, no book reconstruction

Step 6 — Deep dives

1. Order book data structure:

   bids: price levels sorted desc ┐  each level: FIFO doubly-linked list of orders (time priority)
   asks: price levels sorted asc  ┘  orders_by_id: hashmap order_id → node   (O(1) cancel)
   Price levels: array indexed by tick offset around the current price (dense, cache-friendly)
                 or a balanced tree for wide/sparse ranges
   Match: incoming buy limit P → while best_ask ≤ P and qty > 0: fill against head of best level
   All prices and quantities are INTEGERS (ticks, lots) — never floats
   

2. Determinism and the sequencer: the engine is a pure function of the sequenced input. Time comes from the sequencer in the event, never from the engine's clock; there's no randomness and no multithreaded nondeterminism. That gives replay (rebuild state after a crash from a snapshot plus the journal), audit (regulators can reproduce any trade), and hot standbys that stay identical.
3. Latency engineering: kernel-bypass networking (DPDK, Onload), cores pinned and isolated, busy-polling instead of interrupts, no allocation or GC on the hot path (pre-allocated pools, or GC-free Java), cache-friendly structures, lock-free single-producer/single-consumer ring buffers between stages, and members co-located in the same data center.
4. Durability without losing microseconds: the sequencer journals to memory-mapped files and replicates to the standby before acknowledging. Acknowledged means present on two machines. Disk fsync batching is tuned for group commits.
5. Fairness: price-time priority; multicast market data sent to everyone simultaneously; equal cable lengths in co-location. Some venues add deliberate speed bumps.

Step 7 — Failure modes