Design High-Throughput Stock Exchange

The single most performance-critical data structure. Uses a hybrid approach: flat array indexed by price for the hot zone (O(1) lookup, 512KB fits in L2 cache) plus Red-Black Tree for far-from-market orders.

Operation Frequency Drives Optimization

64-Byte Order Struct (Exactly 1 Cache Line)

struct Order {  // hot fields first for prefetcher
  int64_t price;           // 8B — compared during matching
  uint32_t remaining_qty;  // 4B — decremented during fills
  uint32_t broker_id;      // 4B — checked for STP
  Order* next;             // 8B — linked list traversal
  Order* prev;             // 8B — linked list removal
  uint64_t order_id;       // 8B — for execution report
  uint64_t cl_ord_id;      // 8B — for broker response
  uint32_t original_qty;   // 4B — cold
  uint32_t symbol_id;      // 4B — cold
  uint64_t timestamp;      // 8B — cold
} __attribute__((packed, aligned(64))); // = 64 bytes ✓

Custom Open-Addressing HashMap for O(1) Cancel

1M slots × 16 bytes = 16 MB (fits in L3). Fibonacci hashing with linear probing — at 50% load factor, average 1.5 probes per lookup. 5-10 ns per cancel lookup vs 50-200 ns for std::unordered_map. Pre-allocated pool with free-list allocator on huge pages eliminates all malloc/free in the hot path.

The core product. Incoming marketable orders sweep through the opposite side of the book, matching against resting orders in FIFO order at each price level.

sequenceDiagram
    participant B as Broker
    participant G as Gateway
    participant M as Matching Engine
    participant D as Disruptor
    B->>G: FIX NewOrderSingle (BUY 100 AAPL LIMIT $187.46)
    G->>M: 64-byte InternalOrder (validated, normalized)
    Note over M: Check: $187.46 >= best ask $187.46 → MARKETABLE!
    Note over M: Match against resting sell at $187.46 (FIFO)
    Note over M: STP check: different brokers ✓
    Note over M: Fill 100 shares @ $187.46
    M->>D: TRADE event + ORDER_EXECUTED + QUOTE_UPDATE
    D-->>G: ExecutionReport (FILLED, liquidity='R' taker)
    D-->>G: ExecutionReport to seller (liquidity='A' maker)

Order Type Handling

Deterministic Replay

Same input sequence must produce same output sequence. Every time. No floating-point (integer prices), no system clock reads (timestamps from input), no randomness, no threads. Any trading day can be replayed and verified — regulatory requirement.

Pre-allocated ring buffer connecting the single-threaded matching engine to 5 downstream consumers. No copying, no locks, no allocation. All consumers read from the same memory with independent cursors.

Ring Buffer: 262,144 slots × 128 bytes = 32 MB (pre-allocated, huge pages)
Producer: Matching engine (single writer, ~1M events/sec)
Consumers (each on own core):
  Tier 1: WAL Writer + Replication Sender (no dependencies)
  Tier 2: Gateway Response + Market Data (gated behind Tier 1)
  Tier 3: Surveillance (gated behind Tier 2)

Cache-Line Padding Eliminates False Sharing

Each cursor is padded to 64 bytes (one cache line). Without padding: producer update invalidates ALL consumer cache lines (~40-70 ns per event). With padding: zero cross-core cache coherence traffic. This single optimization made the Disruptor "impossibly fast."

Dependency Barriers

Gateway cannot send broker ExecutionReport until BOTH WAL and Replication confirm the event is durable. This is the mechanism that achieves zero data loss for acknowledged events without adding latency to the matching engine.

The Linux kernel TCP/IP stack adds ~10 μs per packet (interrupts, memory allocation, TCP processing, context switches, data copying). Our entire budget is 10 μs. Kernel networking alone consumes 92% of our budget.

Three Levels of Bypass

Hardware Timestamping (PTP)

NIC PHY stamps every packet at the wire level with ±5 ns accuracy (GPS-synced PTP clock). This provides regulatory-quality nanosecond timestamps and enables the fairness sequencer.

No database — all state is in memory. Persistence via memory-mapped WAL: append 144-byte entries at ~0.1 μs (memcpy to page cache). OS flushes to NVMe asynchronously. True durability comes from RDMA replication to standby, not local disk.

Recovery Strategy

Cold recovery:
  1. Load latest snapshot (~310 MB, ~0.1 sec from NVMe)
  2. Replay WAL from snapshot timestamp (~30 sec of events)
  3. Replay speed: ~2M events/sec → ~6 seconds total
  4. Resume accepting orders

Hot failover (preferred):
  Standby takes over in ~5-10 ms
  Primary's WAL used only for convenience on restart

Deterministic Replay

Timer events (market open/close, LULD recompute) injected as input messages through the WAL — not from system clock. This ensures replay produces identical order book state. Verified nightly by replaying the full day and comparing every output event.

Pipelined RDMA replication: matching engine doesn't wait (0 μs cost), but gateway consumer IS gated behind replication (+1.5 μs to broker notification). Zero data loss for acknowledged events.

Failover Sequence (~5-10 ms total)

T=0ms    Primary crashes
T=3ms    Standby detects 3 missed heartbeats (1ms interval)
T=3.5ms  Standby fences primary via IPMI power-off
T=3.6ms  Standby replays pending events from RDMA buffer
T=4ms    Standby promotes to primary (new epoch)
T=5ms    Gateways notified, redirect order flow
T=6ms    Normal operation resumes

Split-Brain Prevention

Three mechanisms: physical fencing (IPMI power-off of old primary), epoch numbers (gateways reject old-epoch messages), 3-node quorum (primary needs 2/3 votes to continue). If fencing fails → failover aborted rather than risking two primaries.

Unicast to 1,000 subscribers at 1M msg/sec = 1 billion sends/sec = impossible. UDP multicast: send once, switch replicates to all. 50 MB/sec outbound vs 50 GB/sec for unicast.

Channel Architecture

~50 channels, ~100-200 symbols each. Hot symbols (AAPL, SPY) get smaller groups. Each channel has A/B feed on independent switch paths. MoldUDP64 framing with per-channel monotonic sequence numbers for gap detection.

A/B Feed Redundancy

Two completely independent network paths (different NICs, switches, fiber routes). A alone delivers 99.999% of messages. A OR B delivers 99.9999999% (nine 9s). TCP retransmit server handles the ultra-rare case where both feeds lose the same packet.

Adaptive Batching

Trades: flush immediately (0 delay). Quote updates: flush within 10 μs. Depth updates: batch up to 50 μs or 35 messages. Reduces packet rate by 97% while keeping latency-sensitive messages fast.

The defining constraint separating an exchange from any other high-performance system. SEC mandates equal access — latency differences translate directly into money.

IEX Speed Bump — Alternative Model

350 μs of coiled fiber on all paths. Makes microsecond-level differences irrelevant. 150 ns cable advantage becomes 0.04% of total delay. Our exchange uses the traditional model of minimizing latency for everyone equally.

At market open and close, a completely different algorithm finds a single equilibrium price maximizing matched volume. The closing auction price is the most important price in finance — used by every index fund, ETF, mutual fund, and option for valuation.

Algorithm: Cumulative Supply/Demand Curves

For each possible price P:
  buy_demand(P) = MOO buys + all limit buys at P or higher
  sell_supply(P) = MOC sells + all limit sells at P or lower
  matched(P) = min(buy_demand, sell_supply)

Clearing price = P that maximizes matched(P)
Tie-breakers: minimum imbalance → closest to reference price

All eligible orders execute at the SINGLE clearing price.
NOII (Net Order Imbalance Indicator) published every second
before auction so traders can adjust orders.

NASDAQ's closing cross handles $50-80 billion/day and 10-15% of total US equity volume. Getting the price wrong by $0.01 on AAPL can misvalue ~$168 million in index fund NAV.

Every optimization is rooted in understanding the CPU. L1 access: ~1 ns. L2: ~4 ns. L3: ~14 ns. DRAM: ~80 ns (80× slower than L1). A single DRAM access costs as much time as processing an entire order.

Key Techniques

rdtsc for Nanosecond Timestamps

~7 ns to read TSC register (no syscall). clock_gettime: ~20-50 ns (syscall overhead). At 1M timestamps/sec, saves ~30 ms/sec. Used for internal timing; NIC PTP clock for regulatory timestamps.

Stop orders don't sit on the visible book — they sit in a separate trigger table indexed by trigger price (same flat-array optimization). After every trade, check if trade price crosses any triggers.

Most trades don't trigger stops: one integer comparison (~2 ns). Only when a trade crosses a trigger does real work happen — triggered stops convert to market/limit orders and enter normal matching, potentially causing cascading triggers (positive feedback loop). LULD circuit breakers are the safety valve.

Market makers run 20+ strategies simultaneously. STP prevents wash trades (matching against yourself). Checked in the innermost matching loop — one integer comparison per potential match. Modes: cancel resting, cancel incoming, cancel both, cancel smallest. Per-broker configuration, supports sub-broker group-level STP.

Performance impact: branch predictor learns 99%+ of matches are between different brokers → ~0 penalty for the common case.

Every fill tagged as maker (resting, earns ~$0.002/share rebate) or taker (incoming, pays ~$0.003/share fee). Exchange net: $0.001/share × 3B shares/day = $3M/day revenue. Volume-tiered pricing: high-volume brokers get better rates. Fee model drives entire market microstructure — brokers route specifically to earn rebates.

Exchange cannot fail during extreme events (GME squeeze: 10-50× volume, Flash Crash: 20× message rate). Stress testing: replay historical extreme days at 2-10× speed. Capacity headroom: normal <30%, peak <60%, extreme <90%. Graceful degradation: throttle high-OTR brokers first, reject new orders while processing existing ones, widen LULD bands, never crash or lose data.

Core matching engine is generic, parameterized by: matching algorithm (FIFO vs pro-rata), tick size, trading hours, circuit breaker rules, fee schedule. Options: 3M order books (10K stocks × 300 series), pro-rata matching. Futures: 24-hour, margin model. Crypto: 24/7/365, no regulation. Cross-asset combo orders: atomic matching across multiple books — architecturally hardest extension.