Design a Stock Exchange Matching Engine

1. Problem Statement & Scope Clarification

System Mission

Design an ultra-low latency, deterministic electronic exchange matching engine (similar to NASDAQ, CME, and LMAX) capable of executing hundreds of thousands of limit and market orders per second with strict Price-Time Priority (FIFO), sub-50 microsecond ($< 50\,\mu\text{s}$) matching latencies, zero lock contention, and zero data loss.

Functional Requirements

1. Order Ingestion (PlaceOrder): Ingest Limit, Market, and Cancel orders with sub-microsecond parsing using binary protocols (SBE / FIX / ITCH-OUCH).
2. Deterministic Price-Time Priority (FIFO Matching):
   • Orders matched first by Best Price (Highest Bid, Lowest Ask).
   • Equal price orders matched strictly by arrival sequence timestamp.
3. Order Cancellation & Modification (CancelOrder / ModifyOrder): Execute cancellations in $O(1)$ constant time.
4. Market Data Feed Dissemination: Broadcast real-time Level 2 (Aggregated Price Depth) and Level 3 (Full Order State) feeds to market participants.
5. Asynchronous Clearing & Settlement: Decouple the ultra-low latency matching core from downstream settlement, risk reporting, and regulatory clearing.

Non-Functional Requirements (SLAs & SLOs)

• Ultra-Low Latency: End-to-end matching latency $P50 < 15\,\mu\text{s}$, $P99 < 50\,\mu\text{s}$, $P99.9 < 150\,\mu\text{s}$.
• 100% Determinism: Replaying the sequenced input log on a backup node MUST produce an identical trade execution tape.
• High Availability: Sub-millisecond failover to a hot-standby replica with zero uncommitted state loss.
• Throughput: Support $> 200,000\text{ sustained orders/sec}$ per matching engine partition.

2. Capacity & Scale Estimation (Back-of-the-Envelope Math)

Ingestion Scale & Latency Budget

• Listed Tradable Symbols: $10,000\text{ instruments}$ (Equities, Futures, Options).
• Peak Order Ingestion Rate: $200,000\text{ orders/sec}$ per active partition.
• Daily Order Volume: $500,000,000\text{ orders/day}$ (500M orders/day).
• Average Trades Executed: $\approx 50,000,000\text{ executions/day}$ ($10\%$ fill ratio).

Microsecond Latency Budget Breakdown ($50\,\mu\text{s}$ Target)

Memory Sizing for In-Memory Order Books

• $10,000\text{ symbols} \times 5,000\text{ open orders/book} = 50,000,000\text{ active orders}$.
• Order struct size in memory: $64\text{ bytes}$ (fits exactly in 1 CPU cache line). $\text{Total Active Order Book Memory} = 50 \times 10^6 \times 64\text{ bytes} \approx \mathbf{3.2\text{ GB RAM}}$ The entire global order book easily fits into the physical RAM and L3 CPU cache of a single bare-metal server.

3. High-Level Architecture & AWS Component Mapping

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

4. In-Memory Order Book Data Structures

To achieve sub-microsecond price lookup and $O(1)$ order cancellation:

1. Price Levels: Indexed via a Sparse Direct-Indexed Flat Array or Red-Black Tree ordered by price.
2. Time Priority at Price Level: Intrusive Doubly-Linked List of Order structs (FIFO queue).
3. Order Lookup Map: Cache-padded Flat Hash Map (order_id -> Order*) enabling $O(1)$ cancellation without tree traversal.

textCopy
Symbol OrderBook (e.g. AAPL):
BIDS (Highest Price First):
  Price: $185.50 -> [Order 101 (100 sh)] <-> [Order 104 (500 sh)] <-> [Order 109 (50 sh)]
  Price: $185.49 -> [Order 102 (200 sh)] <-> [Order 105 (100 sh)]
  Price: $185.48 -> [Order 108 (1,000 sh)]

ASKS (Lowest Price First):
  Price: $185.51 -> [Order 103 (300 sh)] <-> [Order 106 (150 sh)]
  Price: $185.52 -> [Order 107 (400 sh)]

Cache-Line Friendly C++ Order Struct (64 Bytes Aligned)

cppCopy
struct alignas(64) Order {
    uint64_t order_id;        // 8 bytes
    uint64_t sequence_num;    // 8 bytes
    uint64_t timestamp_ns;    // 8 bytes
    uint32_t account_id;      // 4 bytes
    uint32_t symbol_id;       // 4 bytes
    int64_t  price_cents;     // 8 bytes
    uint32_t remaining_qty;   // 4 bytes
    uint8_t  side;            // 1 byte (0 = BUY, 1 = SELL)
    uint8_t  order_type;      // 1 byte (0 = LIMIT, 1 = MARKET)
    uint8_t  padding[18];     // 18 bytes padding to fill exactly 64 bytes
    Order*   prev;            // Intrusive list pointer
    Order*   next;            // Intrusive list pointer
};

5. The LMAX Disruptor Lock-Free Concurrency Engine

Multi-threaded matching engines suffer from thread context switching, OS kernel scheduling jitter, and mutex lock contention ($10 - 50\,\mu\text{s}$ penalties). The system uses the LMAX Disruptor pattern:

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

Why Single-Threaded CPU Pinning Wins

• Zero Mutex Locks: No CPU spinlocks, condition variables, or kernel context switches.
• L1/L2 Cache Warmth: Order book memory stays pinned in CPU L1/L2 cache lines with zero cache eviction from context switches.
• Predictable Execution: Eliminates the long-tail latency distribution ($P99.9$ is nearly identical to $P50$).