Design a Stock Exchange Matching Engine

1. Problem Statement & Scope Clarification

System Mission

Design an ultra-low latency, deterministic electronic stock exchange matching engine (equivalent to NASDAQ, CME, or LMAX Exchange). The system must process hundreds of thousands of limit and market orders per second with strict Price-Time Priority (FIFO), sub-50 microsecond ($P99 < 50\,\mu\text{s}$) matching latencies, zero lock contention via a single-writer architecture, zero memory allocations on the critical hot path, and sub-millisecond hot-standby failover with $100\%$ determinism.

Matching Engine Performance Specifications

Functional Requirements

1. Order Ingestion (EnterOrder): Parse, validate, and sequence incoming Limit, Market, and Cancel orders using compact binary wire protocols (Simple Binary Encoding - SBE / OUCH).
2. Deterministic Price-Time Priority (FIFO) Matching Engine:
   • Price Priority: Orders at better prices (higher buy bids, lower sell asks) take strict precedence.
   • Time Priority: Orders at the exact same price level are executed in strict arrival sequence order (First-In, First-Out).
3. Constant-Time Cancellation (CancelOrder): Cancel or modify existing resting limit orders in $O(1)$ time complexity using direct memory pointers.
4. Real-Time Market Data Multicast (ITCH Protocol): Disseminate real-time binary market data feeds:
   • Level 2 (Aggregated Depth): Top 10–50 bids and asks with aggregated share quantities.
   • Level 3 (Order-by-Order Tick Data): Full visibility into every resting order state change.
5. Decoupled Post-Trade Clearing & Settlement: Asynchronously emit trade execution drops to downstream clearing houses, regulatory reporting systems, and member firm risk engines without stalling the core matching loop.

Non-Functional Requirements (SLAs & SLOs)

• Latency (P99):
  • Wire-to-Wire Matching Latency: $P50 < 15\,\mu\text{s}$, $P99 < 50\,\mu\text{s}$, $P99.9 < 150\,\mu\text{s}$.
  • Order Cancellation Latency: $P99 < 20\,\mu\text{s}$.
• Determinism: $100\%$ mathematical reproducibility. Replaying identical sequenced input events through a fresh matching engine instance must generate the exact same trade output tape bit-for-bit.
• Throughput & Capacity: Sustain $\ge 200,000\text{ orders/sec}$ per symbol partition on a single pinned CPU core, handling up to $500\text{ Million orders/day}$.
• Zero Lock Contention: Completely eliminate OS-level thread synchronization primitives (mutexes, semaphores, conditional variables) from the matching hot path using lock-free ring buffers and core isolation.
• Availability & Durability: $99.999\%$ uptime SLA; Zero lost transactions ($RPO = 0$, Recovery Point Objective) with sub-millisecond hot-standby takeover ($RTO < 5\text{ ms}$, Recovery Time Objective).

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

Ingestion Scale & Order Volume

• Listed Tradable Instruments: $10,000\text{ symbols}$ (Equities, ETFs, Indices).
• Daily Ingestion Volume: $500,000,000\text{ orders/day}$ (New, Cancel, Replace).
• Daily Executed Trades: $50,000,000\text{ matches/day}$ ($10\%$ execution ratio; $90\%$ of orders are cancellations or unexecuted limit quotes).
• Average Trading Day: 6.5 hours ($23,400\text{ seconds}$).
• Average Order Ingestion Rate: $\text{Rate}_{\text{avg}} = \frac{500 \times 10^6\text{ orders}}{23,400\text{ sec}} \approx \mathbf{21,367\text{ orders/sec}}$
• Peak Order Ingestion Rate ($10\times$ market open/close burst): $\text{Rate}_{\text{peak}} \approx \mathbf{200,000\text{ orders/sec per partition}}$

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

Synthesizing vector architecture diagram...

This diagram shows the six stages that every order passes through, in order, with the time budget of each stage. The order is read from the network card ring (10 μs), stamped with a sequence number by the sequencer (5 μs), placed in the Disruptor ring buffer (2 μs), matched by the single matching core (8 μs), written to the NVMe journal through SPDK (15 μs), and finally published as UDP multicast market data (10 μs). The stages run one after another for the same order, so their budgets add up: 10 + 5 + 2 + 8 + 15 + 10 = 50 μs, which is the end-to-end target. The largest single cost is the journal write (15 μs), and it happens before the result is published, so a published trade is always already durable.

In-Memory Order Book RAM Sizing

• Average active resting orders across all 10,000 symbols: $5,000\text{ open orders/book}$.
• Total live resting orders across the exchange: $N_{\text{orders}} = 10,000 \times 5,000 = \mathbf{50,000,000\text{ resting orders}}$
• Each order struct is padded to exactly 64 bytes (1 CPU cache line): $\text{Total Order Memory} = 50 \times 10^6 \times 64\text{ bytes} = 3.2 \times 10^9\text{ bytes} \approx \mathbf{3.2\text{ GB RAM}}$
• Price level nodes ($200\text{ bytes} \times 100\text{ levels} \times 10,000\text{ symbols} = 200\text{ MB}$).
• Total In-Memory Working Set: $\approx \mathbf{3.5\text{ GB RAM}}$. The entire global order book fits comfortably inside the CPU L3 cache and physical DDR5 RAM of an Amazon EC2 c6i.32xlarge or c6in.metal bare-metal instance.

3. High-Level Architecture & AWS Component Mapping

The exchange architecture follows the LMAX Disruptor Single-Writer Pattern: all thread concurrency, locking, and socket contention are eliminated by funnelling incoming network packets through an atomic sequencer into a cache-line aligned lock-free ring buffer, serviced by a single dedicated CPU core running the matching algorithm.

Synthesizing vector architecture diagram...

Follow an order from the top. It arrives over Direct Connect and is read straight from the network card by a polling thread that bypasses the kernel, saving microseconds. In the "Deterministic Sequencing Domain" panel, one pinned CPU core gives every order the next sequence number and writes it into a lock-free ring buffer. In the "Single-Writer Matching Core Domain" panel, a single core owns the entire order book in memory and matches orders by price, then time; because only one thread ever writes, there are no locks. Every sequenced event is journaled to local NVMe and mirrored to a hot standby on another host, which replays the same events in the same order and can take over with no data loss. In the "Low-Latency Market Data & Post-Trade Settlement" panel, results go out as UDP multicast to all participants at once, and trades are sent asynchronously through SQS to settlement in Aurora, well away from the latency-critical path. Determinism is the key: the same input sequence always produces the same book, which makes the standby and replay possible.

Data Flow Walkthrough

1. Network Ingress via Kernel Bypass: Inbound order packets bypass the Linux operating system kernel network stack entirely using DPDK and AWS ENA Express. Ingress packets move directly from the physical network interface controller (NIC) into user-space memory buffers without context switches or interrupts.
2. Deterministic Sequencing: The single-threaded Sequencer pinned to CPU Core 2 receives the binary packet, validates account credentials, assigns an unalterable, gapless 64-bit sequence identifier (seq_id = 1004812), and inserts the order into the circular LMAX ring buffer.
3. Single-Writer Matching Engine: CPU Core 3, isolated via Linux isolcpus and cgroups, polls the ring buffer continuously in a busy-spin loop ($0\text{ ns}$ thread wake-up latency). It matches the order against the in-memory double-sided order book using the Price-Time Priority algorithm.
4. Synchronous SPDK Fast Journaling: Before publishing executions, the trade event is persisted to local NVMe SSDs via SPDK (Storage Performance Development Kit), achieving microsecond-level durability. Concurrently, the exact sequenced input event (not the output) is mirrored to the Hot-Standby engine on a second bare-metal host, which executes it in lockstep; a standby on the same host would die with the same kernel panic it is meant to survive.
5. UDP Multicast Dissemination: CPU Core 5 packages match events into compact binary ITCH packets and streams them over UDP multicast directly to market participants.
6. Asynchronous Settlement Decoupling: Post-trade clearing and regulatory archival are offloaded asynchronously via Amazon SQS FIFO queues into Amazon Aurora PostgreSQL, completely insulated from the ultra-fast matching path.

Core Request Tracing Execution Walkthrough

4. In-Memory Order Book Data Structures

To guarantee $O(1)$ order insertions, $O(1)$ order cancellations, and sub-microsecond price depth sweeps:

1. Price Levels: Indexed via a Direct-Indexed Flat Array (for tick ranges close to current mid-market price) or a cache-conscious B-Tree sorted by price.
2. Time Priority Queue: An Intrusive Doubly-Linked List of resting Order structs at each price level. Insertion is $O(1)$ at the tail; matching is $O(1)$ from the head.
3. Cancellation Hash Map: A pre-allocated, flat Cache-Conscious Hash Table mapping order_id -> Order*. This enables instantaneous $O(1)$ cancellations by unlinking the order directly from its doubly-linked list without searching the book.

Synthesizing vector architecture diagram...

This diagram shows the AAPL order book at one moment. The best bid is $185.50 and the best ask is $185.51, so the bid-ask spread is $185.50 to $185.51. In the "AAPL bids: highest price first" panel, each price level holds its resting orders as a doubly linked list in arrival order: at $185.50, Order 101 (100 sh) arrived first and sits at the head, then Order 104 (500 sh), then Order 109 (50 sh) at the tail, for 650 shares in total; at $185.49, Order 102 (200 sh) is ahead of Order 105 (100 sh). In the "AAPL asks: lowest price first" panel, $185.51 holds Order 201 (150 sh) ahead of Order 203 (250 sh), and $185.52 holds Order 202 (1,000 sh). An incoming order is matched against the head of the best opposite level first, which is the price-time (FIFO) rule. The "Fast cancellation lookup map (pre-allocated flat array)" panel shows why a cancel is O(1): the map returns a pointer straight to the Order 104 node, and because the list is doubly linked, the node can be unlinked from its neighbours Order 101 and Order 109 without walking the list.

5. API Interface Design & Binary Wire Protocols

Stock exchanges do NOT use JSON or HTTP for order ingestion. They deploy compact binary protocols (e.g., NASDAQ OUCH for order entry and ITCH for market data feeds) to minimize serialization overhead and network packet sizes.

1. Order Entry Protocol: Enter Order Message (OUCH Binary Format)

2. Market Data Protocol: Order Executed Message (ITCH Binary Format)