Design a Stock Exchange (Matching Engine)

TL;DR. A stock exchange matching engine is the rare distributed system where the correct answer is "do not distribute." NASDAQ's INET matches orders in under 40 microseconds at over 1 million messages per second^[1]. LMAX demonstrated 6 million orders per second on a single thread (benchmarked on 2010-era hardware)^[2]. The architecture is a strictly serialized event log: a sequencer stamps every order, a single-threaded engine matches against a price-time-priority order book, and outputs fan out via UDP multicast to thousands of subscribers. The pivotal trade-off is determinism over parallelism: you cannot scale one symbol's matching horizontally, but you can replay any failure identically.

Learning Objectives#

After this module, you will be able to:

• Design a FIFO order book with price-time priority and explain its determinism properties
• Architect market data distribution via UDP multicast with gap detection and recovery
• Reason about hot-standby replication and sub-second failover for the matching engine
• Explain why single-threaded design and kernel bypass beat parallel architectures for this workload
• Identify pre-trade risk controls mandated by SEC Rule 15c3-5 and their architectural impact
• Estimate capacity for a production exchange handling 1M+ messages per second

Intuition#

A stock exchange looks like a trivial CRUD app. Accept an order, store it, match buyers with sellers. A college student could build one in a weekend.

Now add the constraint that matters: two orders arrive 800 nanoseconds apart. The first must execute before the second. Always. Deterministically. If you replay the same input stream tomorrow, you must get bit-identical output. No locks, no retries, no "eventually consistent." The order book is the single source of truth, and it lives on one thread because that is the only way to guarantee total ordering without coordination overhead.

The naive multi-threaded approach fails immediately. Two threads reading the same price level introduce a race: which order fills first? You could add a lock, but a lock at 6 million operations per second costs more than the matching itself. You could use optimistic concurrency, but retries destroy determinism. The industry tried and abandoned parallelism decades ago.

The insight: serialize the hard part (matching), parallelize everything else (network I/O, journaling, market data publishing, risk checks). The matching engine becomes a pure function: input event in, output events out, no side effects, no I/O, no blocking calls. Everything around it can be concurrent because the engine has already established the authoritative order of events^[2:1].

This is the LMAX Disruptor pattern, and it powers every major equities and futures exchange in production today.

Requirements#

Clarifying Questions#

• Q: What asset classes do we support? Assume: US equities (NMS stocks). Single venue, not a consolidated tape.
• Q: What matching algorithm? Assume: Price-time priority (FIFO). The dominant algorithm for US equities and futures^[3].
• Q: What is the latency target? Assume: Wire-to-wire p99 under 50 microseconds at the matching engine. NASDAQ INET achieves sub-40 microseconds^[1:1].
• Q: How many symbols? Assume: 8,000 listed symbols. Each symbol has an independent order book.
• Q: What is the failover requirement? Assume: Sub-second failover with zero order loss. A fast failover that drops one order is worse than a slow one that preserves everything^[2:2].
• Q: Do we need co-location? Assume: Yes. Equal-length fiber cross-connects for all participants, per NYSE Mahwah model^[4].
• Q: What regulatory constraints apply? Assume: SEC Rule 15c3-5 (pre-trade risk), LULD bands, and Reg NMS obligations.

Functional Requirements#

• Accept limit, market, and cancel orders via FIX/OUCH protocol over TCP
• Match orders using strict price-time priority and emit trade confirmations
• Publish real-time order book updates and trades to all subscribers via UDP multicast (ITCH protocol)
• Support opening and closing auction mechanisms
• Enforce LULD price bands and halt trading when bands are breached^[5]
• Provide TCP-based gap recovery for subscribers who miss multicast packets

Non-Functional Requirements#

• Throughput: 1M+ messages/sec sustained; peak 1.1M messages/sec (NASDAQ record: 1,134,640/sec)^[1:2]
• Latency: p99 < 50 microseconds wire-to-wire at the matching engine
• Determinism: Replaying the input journal must produce bit-identical output
• Availability: 99.999% uptime during market hours (6.5 hours/day, 252 days/year)^[1:3]
• Durability: Zero order loss on primary failure; journal persisted before acknowledgment
• Fairness: Equal-length cross-connects; no participant has geometric latency advantage^[4:1]

Capacity Estimation#

The critical insight: the entire active state fits in CPU cache. This is why single-threaded matching works. Cache misses, not CPU cycles, are the bottleneck at microsecond latencies.

API and Data Model#

API Design#

Order entry uses OUCH (NASDAQ's binary protocol over SoupBinTCP) or FIX for compatibility^[7][8]:

-- OUCH Enter Order (binary, fixed 49 bytes)
OrderToken:       14 bytes (client-assigned)
Side:              1 byte  (B=buy, S=sell)
Shares:            4 bytes (quantity)
Symbol:            8 bytes (padded)
Price:             4 bytes (fixed-point, 4 decimal places)
TimeInForce:       4 bytes (DAY, IOC, GTC)
Display:           1 byte  (visible, hidden, attributable)

-- OUCH Accepted (exchange response, 66 bytes)
OrderToken:       14 bytes
OrderRefNum:       8 bytes (exchange-assigned sequence)
Side, Shares, Symbol, Price, TimeInForce, Timestamp

-- OUCH Cancel
OrderToken:       14 bytes
Shares:            4 bytes (partial cancel quantity)

Market data uses ITCH over MoldUDP64 (sequenced UDP multicast)^[9]:

-- ITCH Add Order (28 bytes)
MessageType:       1 byte  ('A')
SequenceNumber:    8 bytes (monotonic, gap-detectable)
OrderRefNum:       8 bytes
Side:              1 byte
Shares:            4 bytes
Symbol:            8 bytes
Price:             4 bytes

Data Model#

-- Order (in-memory, intrusive linked list node)
struct Order {
    order_id:       u64,        -- exchange-assigned sequence number
    client_token:   [u8; 14],   -- client reference
    symbol_id:      u16,        -- index into symbol table
    side:           Side,       -- Bid | Ask
    price:          i64,        -- fixed-point (price * 10000)
    remaining_qty:  u32,
    timestamp_ns:   u64,        -- sequencer timestamp
    prev:           *Order,     -- intrusive list pointers
    next:           *Order,
}

-- Price Level (one per distinct price in the book)
struct PriceLevel {
    price:      i64,
    head:       *Order,     -- FIFO queue head (oldest)
    tail:       *Order,     -- FIFO queue tail (newest)
    total_qty:  u64,        -- aggregate visible quantity
}

-- Order Book (one per symbol)
struct OrderBook {
    bids:       SortedMap<i64, PriceLevel>,  -- descending by price
    asks:       SortedMap<i64, PriceLevel>,  -- ascending by price
    order_map:  HashMap<u64, *Order>,        -- O(1) cancel lookup
}

The order_map is critical: cancels outnumber executions by roughly 20:1 in US equities^[6:1], so O(1) cancel via hash lookup dominates performance.

High-Level Architecture#

Orders flow through risk checks and a sequencer into a single-threaded matching engine; outputs fan out to a journal, a hot standby, and a multicast market data publisher.

Write path (order entry). A member firm sends an order over TCP (OUCH/FIX). The gateway decodes and validates the wire format. Pre-trade risk checks enforce Rule 15c3-5 limits (fat-finger size, daily credit, duplicate detection)^[10]. The sequencer stamps a monotonic sequence number, establishing the authoritative total order. The matching engine consumes the sequenced event, updates the order book, and emits output events (trade, add-to-book, or cancel-ack).

Output path (market data). The market data publisher serializes output events into ITCH messages and multicasts them over UDP to all subscribers simultaneously. Every message carries the sequence number. Subscribers detect gaps and request TCP retransmission from the recovery service^[9:1].

Failover path. The hot standby receives the same sequenced input stream (via IP multicast or dedicated replication link). It processes every event identically but discards its own output. On primary failure, it becomes the leader in microseconds^[2:3].

Deep Dives#

Single-threaded matching and the LMAX Disruptor#

The matching engine runs on one thread. Not because engineers are lazy, but because it is provably optimal for this workload.

Why single-threaded wins. At 6 million events per second, each event gets ~167 nanoseconds of CPU time^[2:4]. A single cache miss to DRAM costs ~100 nanoseconds. A mutex lock/unlock pair costs ~25 nanoseconds uncontended, ~1,000 nanoseconds contended. Any coordination mechanism between threads would consume the entire time budget for the event itself.

The LMAX Disruptor solves the surrounding concurrency problem. It is a lock-free ring buffer (power-of-two size, so index computation is a single bitwise AND instead of a modulo division)^[11]. Multiple consumers (journaler, replicator, unmarshaller) read from the ring in parallel without locks. Only after all consumers complete does the Business Logic Processor (the matching thread) consume the event.

// Ring buffer index: single-cycle bitwise AND replaces modulo
this.indexMask = bufferSize - 1;  // bufferSize must be power of 2
E element = entries[BUFFER_PAD + (int)(sequence & indexMask)];

Cache-line padding prevents false sharing between producer and consumer sequence counters. The 64-byte padding on either side of hot fields guarantees each counter sits alone in its cache line^[11:1]:

The Disruptor parallelizes I/O consumers around a single-threaded matching core; the BLP never blocks on I/O.

Deterministic replay. Because the matching thread is a pure function of its input stream, bug reproduction is trivial: copy the journal to a dev box, replay, and the bug reproduces identically. LMAX restarts from a nightly snapshot plus journal replay in under 60 seconds^[2:5].

The hard ceiling. One core is the vertical limit. You cannot scale matching for a single symbol horizontally. But you can shard by symbol: each symbol's book runs on its own engine instance, and the sequencer routes by symbol ID.

Market data multicast with gap recovery#

The matching engine emits every book update and trade as a binary ITCH message to a UDP multicast group. This is the only architecture that scales: one packet per update reaches all 1,000+ subscribers without the engine maintaining per-subscriber state^[9:2].

Protocol stack. NASDAQ uses MoldUDP64 as the sequencing layer over UDP multicast. Every message carries a monotonic 64-bit sequence number. Subscribers track the expected next sequence; any gap triggers a retransmission request to the recovery service over TCP^[9:3]. Redundant A/B feeds on disjoint network paths help fill gaps without explicit retransmission requests.

Wire format. ITCH messages are fixed-size binary: no length prefixes, no varints, no parsing. A subscriber decodes by casting a pointer to a struct. At 1M+ messages/sec, parse cost matters^[8:1].

Subscribers detect gaps via monotonic sequence numbers and request TCP retransmission; the engine never blocks waiting for slow consumers.

Why not TCP? TCP provides reliability but requires per-subscriber state on the server. At 1,000 subscribers and 1M messages/sec, the engine would maintain 1,000 TCP connections, each with its own send buffer, congestion window, and retransmission timer. A single slow subscriber would back-pressure the engine. UDP multicast decouples the engine from subscriber speed entirely.

Hot-standby failover and deterministic recovery#

Zero order loss on failover is the non-negotiable requirement. LMAX runs three replicas: two in the primary data center, one in DR. All receive the sequenced input stream via IP multicast. All process every event identically. Only the leader's output is published; standby output is discarded^[2:6].

Failover sequence:

1. Standby detects primary heartbeat loss (typically 3 missed heartbeats at 1ms intervals = 3ms detection)
2. Standby verifies it has processed all journal entries up to the last known sequence
3. Standby promotes itself to leader and begins publishing output
4. Market data publisher switches source; sequence numbers continue monotonically
5. Subscribers see either a clean continuation or a small gap (handled by standard gap recovery)

The hot standby replays any missing journal entries, takes over output with continued sequence numbers, and subscribers recover via standard gap-fill mechanisms.

Why not Raft/Paxos? Consensus Protocols introduced quorum-based replication. Exchanges reject it for the matching engine because consensus adds a round-trip per event (tens of microseconds minimum). Instead, the sequencer establishes total order unilaterally, and replicas follow deterministically. The cost: failover requires an external arbiter (or human) to declare the primary dead, because there is no quorum vote. This is acceptable because failover happens once per year, not once per second.

Real-World Example#

NASDAQ INET: sub-40 microsecond matching at scale#

NASDAQ's INET platform (acquired in 2005) is the matching engine behind NASDAQ, several Nordic exchanges, and multiple third-party venues worldwide.

Scale numbers. INET processes over 1 million messages per second at sub-40 microsecond latency^[1:7]. Its published record day handled 1,684,103,265 messages at a peak rate of 1,134,640 messages/sec and 193,350 executions/sec^[1:8]. The platform claims 99.999% uptime.

Architecture. INET is written in C/C++ with two distinct protocol stacks: OUCH over SoupBinTCP for order entry (reliable, sequenced TCP) and ITCH over MoldUDP64 for market data (unreliable multicast with gap recovery)^[7:1][8:2]. The separation is deliberate: you must not lose a customer's order (TCP), but you must not hold the entire market for one slow subscriber (UDP).

Co-location. NASDAQ operates from Carteret, NJ. Member firms rent rack space with equal-length fiber cross-connects to the matching engine (following the same normalized-distance model used at NYSE's Mahwah data center^[4:2]). The round-trip from a co-located rack to the engine is estimated at sub-microsecond latencies. Firms using kernel bypass (DPDK, Solarflare OpenOnload) achieve sub-microsecond wire-to-userspace latency by eliminating interrupts and context switches.

The IEX counterpoint. IEX deliberately rejects the speed race. Its 38-mile (61 km) fiber coil imposes a 350-microsecond delay on every inbound and outbound message^[12][13]. Co-location is not offered. The architectural statement: "equalize latency" is a valid design axis alongside "minimize latency." IEX's Discretionary Peg order type uses a proprietary signal to detect imminent NBBO changes and refuses to execute during those moments, removing latency-arbitrage opportunities^[13:1].

Trade-offs#

The meta-decision: speed vs fairness. NASDAQ and NYSE optimize for minimum latency, attracting liquidity through speed. IEX optimizes for equal access, attracting institutional flow that fears adverse selection. Both are valid; the architecture follows the business model.

Scaling and Failure Modes#

• At 10x load (10M messages/sec): Shard by symbol group. Each matching engine instance handles a subset of symbols. The sequencer becomes a per-symbol-group sequencer. Market data publishers aggregate across groups. NASDAQ already does this: different symbol ranges run on different engine instances.
• At 100x load (100M messages/sec): Move to FPGA-based matching for the hottest symbols. FPGAs eliminate JVM/OS jitter entirely and achieve single-digit microsecond matching. The journal becomes the bottleneck; use battery-backed NVMe with direct I/O.
• At 1000x load (crypto peak): Binance reportedly handles over 1 million orders/sec at peak^[15]. At this scale, the architecture remains fundamentally the same (single-threaded per symbol), but the number of independent engine instances grows to hundreds.

Failure modes:

• Primary engine crash mid-match: The hot standby has processed all sequenced inputs up to the crash point. It promotes and continues. The one order that was mid-match is replayed from the journal; because matching is deterministic, the standby produces the identical partial fill. Subscribers see a brief gap and recover via TCP retransmission.
• Network partition between engine and market data publisher: The engine continues matching (journal captures everything), but subscribers see a halt in market data. Detection: heartbeat timeout. Recovery: publisher reconnects, replays from journal, subscribers gap-fill.
• Knight Capital scenario (runaway algorithm): A member firm's order router sends aggressive orders at maximum rate for 45 minutes^[16]. Detection: pre-trade risk checks (Rule 15c3-5) should catch abnormal order rates and sizes^[10:1]. Kill switch: the exchange can disable a member's port within seconds. Knight lacked this and lost more than $460 million^[17].

Common Pitfalls#

Follow-up Questions#

Exercise#

Exercise 1: Failover mid-match#

The primary matching engine crashes at 10:00:00.123456 while processing a market buy order that has partially filled (100 of 300 shares filled against the best ask). The hot standby must take over. Design the handoff: how the standby knows it should take over, how it guarantees it has all orders up to the crash point, how subscribers detect the source switch, and what happens to the partially-filled order.

Key Takeaways#

• Single-threaded beats multi-threaded for matching. Determinism is worth more than parallelism when you must replay identically and the entire state fits in L3 cache^[2:11].
• The sequencer is the single source of truth. Total order is established by stamping, not by consensus vote. This trades quorum latency for unilateral speed.
• Multicast is the only sane market data architecture. One packet reaches all subscribers; the engine never blocks on a slow consumer^[9:6].
• Kernel bypass is the last 10 microseconds. You do not need DPDK to build an exchange, but you need it to compete with NASDAQ^[4:4].
• Failover correctness trumps failover speed. A fast failover that loses one order is categorically worse than a slow one that preserves everything^[2:12].
• Pre-trade risk controls are architectural, not optional. Knight Capital's $460M loss in 45 minutes proved that kill switches and deployment discipline are load-bearing infrastructure^[16:1][18:1].

Further Reading#

• The LMAX Architecture. Martin Fowler's definitive writeup of single-threaded, event-sourced matching with measured throughput numbers; the starting point for any exchange design.
• LMAX Disruptor technical paper. The ring buffer design with cache-line padding analysis and false-sharing prevention; explains why power-of-two sizing matters.
• NASDAQ INET performance page. Real published throughput and latency records for OUCH and ITCH; the benchmark every exchange design is measured against.
• SEC/CFTC Flash Crash report (2010). The joint report on the 2010 crash that drove LULD and updated circuit breakers; required reading for market microstructure.
• SEC cease-and-desist against Knight Capital. The deployment-failure case study with regulatory findings; the most teachable incident in exchange engineering.
• Databento ITCH protocol reference. Concise, correct explainer of the binary market data protocol used by NASDAQ and derivatives.
• IEX Exchange overview. The speed-bump design and its rationale in the exchange's own words; the architectural counterargument to pure speed optimization.

Flashcards#

References#