Design a Stock Exchange Matching Engine

1. The LMAX Disruptor Pattern

Matching engines trade in-memory speed against durability, balancing WAL fsync latency against sub-microsecond matching.

The industry benchmark for trading architecture. Rather than multi-threaded queues with locks, LMAX utilizes a lock-free, single-threaded consumer spinning over a pre-allocated ring buffer.

Pre-allocated ring buffer: Circular array of size 2^N (allows fast bitwise masking)
  Slot index = seq_num & (buffer_size - 1)  // Bitwise masking instead of modulo

Consumer features:
  - Cache-line padding: prevents false sharing between thread cores
  - Zero-allocation hot path: pre-instantiated event objects, no runtime GC
  - Busy-spin wait: never yields to the OS scheduler, avoiding context switch lag
  - sub-1μs delivery time in Java/C++

2. Why Not Kafka for Order Sequencing?

Kafka is designed for high throughput and durability, but its 2-5ms p99 latency profile is thousands of times too slow for a matching engine critical path requiring <10μs bounds.

Kafka Jitter Sources:
  1. TCP round-trip and broker batching delay.
  2. ISR (in-sync replicas) sync acknowledgments over WAN.
  3. OS page cache flush cycles causing microsecond stalls.

Strategy: Use custom Sequencer with NVMe storage for hot path. Use Kafka only for async downstream.

3. Circuit Breakers: LULD Mechanics

A rogue algorithm or flash crash can wipe out billions. Limit Up-Limit Down (LULD) price bands protect market stability.

def after_trade(trade):
    # Band width: e.g. 5% for large-cap stocks
    upper_band = reference_price * (1 + band_width)
    lower_band = reference_price * (1 - band_width)
    
    if trade.price > upper_band or trade.price < lower_band:
        set_instrument_state(LIMIT_STATE)
        start_timer(15_seconds) # Halt if no clearance in 15 seconds

def on_timer_expire():
    if still_in_limit_state:
        set_instrument_state(HALTED)
        start_timer(5_minutes) # 5-minute cooling-off halt

4. Market Order Edge Case: Sweeping the Book

A thin order book combined with an aggressive market order can lead to disastrous execution prices (e.g. paying $200/share instead of $150).

• Market Order Collar: Execution halts if the filled price deviates by more than 5% from the NBBO midpoint.
• Synthetic Limit Conversion: The exchange converts market orders internally to aggressive limit orders capped at the collar boundary.
• Notional Value Cap: Restricts market orders exceeding $1M, requiring explicit limit parameters.

5. Order Cancel and Amend Race Conditions

In a multi-threaded system, an incoming Cancel request and a matching execution Fill trigger complex race conditions. Single-threaded serialization resolves this cleanly.

Race 1: Cancel arrives while Fill is executing
  - Because sequencer enforces seq_num total ordering, whichever event receives the seq_num first wins.
  - If Fill seq_num < Cancel seq_num: order is matched, and Cancel gets a NACK (too late to cancel).
  - If Cancel seq_num < Fill seq_num: order is canceled, and incoming trade matches against the next level.

Amend Price:
  - Amending price always results in: Cancel old order + insert new order at new price.
  - This loses time priority.
  - Amending quantity down maintains the existing queue priority.

6. Self-Trade Prevention (STP) Modes

Algorithmic firms have hundreds of bots crossing bids/asks. Matching same-firm orders represents illegal wash trading.

• Cancel Newest (CN): The incoming order is instantly cancelled.
• Cancel Oldest (CO): The resting order in the book is cancelled.
• Decrement and Cancel (DC): Reduces both order quantities by the overlapping size, preserving priority on the remainder.

7. Market Data Distribution: Multicast UDP vs TCP

Distributing 5M updates/second to 10K clients requires optimized network routing.

TCP Unicast:
  5M updates x 10,000 clients = 50B packets/sec (overwhelming, doesn't scale).

Multicast UDP:
  - Exchange publishes 1 packet to a multicast group (e.g. 224.1.1.1 per partition).
  - Network switches replicate the packet at the hardware layer.
  - Clients detect gaps using sequential ITCH/SBE message numbers.
  - Missed packets are recovered out-of-band via TCP retransmission servers.

8. Why Java/C++ (Not Go/Rust/Python) for the Engine

• Python: GIL + dynamic memory allocation + interpreter overhead makes it ~1000x too slow.
• Go: Mandatory Garbage Collector pauses (even if sub-500μs) introduce unacceptable tail-latency jitter.
• Rust: Offers microsecond speed and memory safety, but suffers from a smaller pool of battle-tested financial libraries and HFT engineering talent.
• C++: The absolute standard. Provides kernel bypass (DPDK, Solarflare OpenOnload), manual struct cache alignment, and placement-new memory pools.
• Java: Utilized in custom environments (LMAX) with the Zing/Graal VM, off-heap buffers, and zero-allocation codebases to eliminate GC pauses entirely.

9. Clearing and Settlement: T+1

Clearing aggregates all executed trades from Kafka asynchronously, calculating net settlement positions at the end of the day. Because clearing occurs overnight, it resides entirely outside the microsecond critical path.

10. Order Book Data Structure: TreeMap vs Array

• TreeMap (Red-Black Tree): Offers O(log P) inserts for new price levels. Poor L1/L2 cache locality due to pointer chasing. Best for general instruments.
• Direct Array: Direct index mapping (\`Array[price_in_cents]\`). Provides absolute O(1) performance and contiguous cache alignment, but wastes gigabytes of memory on sparse order books.

11. Storage Choice: NVMe WAL vs BBRAM vs PMEM

SATA SSD fsync: 50-200 μs (Unusable).
NVMe SSD fsync: 5-20 μs (Intel Optane: 7-10 μs): good baseline.
Battery-Backed RAM (BBRAM): 0.1-0.5 μs (Ideal, ultra-low latency, expensive).