Mar 13, 2017, 1:34 PM ETLecture, Keynote, Presentation

How to Build an Exchange

Limit order books are sorted by price and time: bids in decreasing order (maximizing sell price) and asks in increasing order (minimizing buy price).
"Ladder view" representations (asks on top, bids below) are avoided in this architecture due to historical patent litigation.
Transaction types are distributed by volume: approximately 50% are new orders, 30-40% are cancellations, 10-20% are cancel-replaces, and 1-2% are executions.
Atomic executions occur when an order's price overlaps with the opposite side of the book (marketable orders), immediately exchanging shares.

US equities markets require peak throughput of approximately 3 million messages per second.
Systems must handle thousands of participants, several million live orders, and roughly 10,000 trading symbols.
Fairness: Information must be delivered to all participants simultaneously to prevent latency-based advantages.
Reliability & Durability: Failed or duplicated trade notifications can trigger unintended capital commitments across the market, creating significant legal and financial liability.
Incentive Alignment: Price improvement must be granted to the aggressive (marketable) order to prevent "walking down" strategies where participants attempt to find the lowest price point systematically.

The core matching engine runs on a single commodity x86 machine (referred to as "Monster"), eliminating the need for complex distributed consensus like Paxos.
Client Ports: Separate processes handle TCP connections for clients, performing validation, normalization, and flow control before passing messages to the matching engine.
Distribution: The matching engine uses UDP multicast ("drop ports") to broadcast every transaction to clearinghouses, trade reporters, and market data feeds simultaneously.
Reliability Layer: A dedicated retransmitter system records UDP messages; if a client misses a packet, it requests retransmission from the retransmitter or the matching engine (which retains an in-memory log of recent messages).
State Machine Replication: All downstream applications (ports, reporters, clears) are deterministic state machines that replay message logs from the beginning of the day to rebuild state, allowing any instance to be killed and restarted without data loss.

A passive (secondary) matching engine listens to the primary's multicast output and applies the identical state machine code.
In the event of a primary crash, the passive engine detects the last processed message and mechanically regenerates all subsequent outputs (e.g., executions, rejections) based on the deterministic rules.
Failover is managed via operator switches rather than automated voting algorithms, relying on the deterministic nature of the code rather than consensus protocols.
Recovery time is targeted at 30–60 seconds by rebuilding state from the log rather than transferring full memory snapshots.

Speed vs. Scale: Low latency (single-digit microseconds) is prioritized to allow simple architectures to handle high throughput; "speed and determinism translate to better prices."
Flow Control: Client ports enforce a "one unacknowledged transaction" limit to prevent socket buffer overflows and manage backpressure via TCP windowing.
Language Choices: The system uses C++ and OCaml; OCaml is preferred for its simplicity and lack of complex garbage collection pauses, which can introduce non-determinism in Java environments.
Parallelism Constraints:
- Parallelizing by symbol is generally avoided for risk-critical systems (e.g., ETFs) to allow atomic enforcement of global risk limits.
- Most performance gains come from overlapping memory fetches rather than multi-threaded logic; profiled code spends ~30% of time on cache misses during array dereferencing.
- Multi-threaded NASDAQ implementations (e.g., 8 threads with symbol sharding) exist but add complexity in re-sequencing streams for clients.

Topic-Based Locking: Messages are assigned unique sequence numbers per "topic" (identified by the client port ID), rather than a single global sequence.
Collision Handling: If a port attempts a sequence number that is not the next expected one (due to a concurrent match), the match engine drops the message.
Rollback Semantics: The port detects the collision via the multicast stream, rolls back to the previous state, and retries the operation with the correct sequence number.
Atomicity: The matching engine's dual writes (to two different topics during a trade) are not strictly atomic at the hardware level but are safe because the passive engine can deterministically regenerate any missing message if the publisher crashes mid-write.

Determinism: The architecture ensures regulators and participants can reproduce exactly what the system knew and decided at any specific nanosecond.
Testability: The state machine model allows for exhaustive testing by replaying weeks of historical data and fuzzing inputs against the same logic.
Simplicity through Speed: High performance allows the system to forgo complex distributed consensus, keeping the core matching engine a single-threaded, simple process.
Future Evolution: While the current design is effective, the speaker notes that future iterations may explore more parallelism, though NASDAQ has already moved toward ring-based architectures to handle symbol-level distribution.