How to Build a Reliable Exchange with Deterministic Replay

To understand an exchange, start with its data structures and messages. A limit order book lists bids in decreasing price order and offers in increasing order: sellers prefer the highest bid and buyers the lowest offer. The point where the best bid and offer meet is called the inside or touch.

A participant can submit an order, such as buying 500 Apple shares at $33.29. The book generally sorts orders by price and time. If a new sell order crosses an existing bid, it is marketable: the exchange applies its rules deterministically, creates a trade and sends executions to the participants. An outstanding order can also be canceled.

The speaker estimates that adds account for about half of market messages, cancels 30–40%, and executions 1–2%, with cancel-replace and other messages making up the rest. Not every system can simply partition by instrument: some order types need to affect two instruments atomically.

For US equities, the illustrative scale is roughly three million messages per second at peak, thousands of connections, millions of live orders and around 10,000 symbols. Fairness means trying to deliver information to participants at the same time, including avoiding accidental advantages in system design.

At Island, a market-data server once looped through TCP connections in order when sending messages. Participants recognized that earlier connections received information sooner, and thousands of connection attempts per second sought the first position after shutdown and before the next opening. Small implementation details can produce incentives to race.

Reliability and durability are essential. Once two participants are told they traded, they may commit capital and make other trades; forgetting or retracting the execution can cause serious problems. The system also needs to isolate poorly behaved clients, whether their behavior comes from carelessness or from incentives created by order types.

Price improvement is an example of incentives. Traditionally the aggressive order receives the benefit when prices overlap, encouraging participants to send their most aggressive price. The speaker recalls a system where hidden orders received the improvement instead, prompting clients to probe prices one by one until they obtained an execution.

The proposed architecture looks unusual: one matching-engine application keeps the book in memory, while separate client-port processes accept connections and send orders and cancellations. The speaker recalls an earlier Island system running the whole market on one powerful x86 machine, surprising technologists accustomed to mainframes.

Other applications also need timely information. Drop ports send selected activity to clearing firms, a trade reporter reports executions, and market data publishes an anonymized and filtered transaction stream. Each consumer can build its own view from the same underlying activity.

The matching engine stays simple by moving work outside it. A cancel fairy observes orders requesting future cancellation and sends the cancel at the appointed time; several instances can race, so one can fail without stopping the function. Auction calculations can similarly run separately and send their results to the engine, rather than burdening continuous matching.

Multicast makes the architecture possible: a packet sent to a logical address is replicated by network equipment to interested recipients approximately simultaneously. Thus the parties to an execution, market data, drop ports and the trade reporter can see an event together. But UDP can lose packets and does not itself provide sequencing or retransmission.

Retransmission servers record messages and detect gaps using sequence numbers. They request missing messages from one another or, if necessary, from the matching engine's in-memory copy. This adds reliability while insulating the engine from much of the recovery work.

A client port is typically a separate process presenting a sequenced TCP connection, using FIX or another protocol. Internally transactions use UDP. Ports bridge private multicast and public access networks, validate and normalize client traffic, isolate bad clients and help with flow control.

The engine preallocates order representations and returns a locator to the port when it acknowledges an order. The port checks incoming cancellations, finds the appropriate order and supplies that locator, allowing the engine to find the order quickly. The locator is internal rather than a memory address sent to the client.

The retransmission stream makes deterministic state-machine replication possible. Each application rebuilds its state by replaying the ordered events from the start of the day. If a client-port process fails, another can replay the stream, recover open orders and message sequence numbers, and reconcile missed messages with the reconnecting client.

The matching engine itself needs a standby. A passive engine listens to the primary's ordered output, not independently to the ports, because UDP arrival order could differ. It runs the same deterministic state machine and code, identifies client-originated messages and independently generates the resulting executions.

If the primary dies after emitting an input but before finishing all its resulting execution messages, the passive engine can generate the same outputs from that input. An operator uses a careful failover procedure. The speaker contrasts this with consensus approaches such as Paxos, which add complexity and a round trip, while noting this is his experience of exchange practice.

An audience member asks about correlated failures: if the same input crashes the primary, might it also crash the standby running identical code? The speaker agrees this is a real weakness. Hardware or operating-system failures may differ, but the state machine must be exceptionally clean and thoroughly tested; shared code is a double-edged sword.

Speed serves more than a headline latency target. Every application sees every message and must discard irrelevant ones quickly. Each client port permits only one unacknowledged transaction in flight, so per-port throughput depends on round-trip latency. A small TCP socket buffer eventually pushes back on a client through TCP flow control.

Fast replay also simplifies recovery. Rather than maintaining separate state-transfer mechanisms for many kinds of application, the system can replay the day if it can rebuild state in 30 seconds or a minute. The speaker says this is achievable with largely commodity hardware and good network cards.

The speaker has implemented systems in C++, Java and OCaml, and says OCaml's relatively simple runtime helps achieve predictable performance. The critical path avoids excessive allocation: data arrives with ideally no copies, code reads values, updates side structures using reused pooled objects and repeats, with memory prepared in advance.

Parallelism is possible, but partitioning by symbol sacrifices some useful atomic operations. Jane Street's ETF market making involves overlapping components, so a single engine can enforce risk limits across the market atomically. Splitting matching across independent engines complicates those guarantees.

Within a machine, multiple cores can overlap memory fetches. The speaker has profiled matching engines where a single lookup takes roughly 30% of execution time because dereferencing an order locator often misses cache. Prefetching a batch can overlap those accesses, although it may not perform quite as well as multiple cores.

Partitioning engines also complicates output order. If several matching engines feed a single client stream, deciding the order of their responses creates state that must be recoverable. Some exchanges instead expose multiple sequence-number spaces and make no promise about their relative order, effectively proxying separate connections.

The speaker then explains locking as a general mechanism for competing changes. Each topic has its own sequence number, separate from the global message sequence. A contributor proposes the next transaction for a topic; if another transaction wins that sequence number, the contributor applies it, updates its state and retries. One in-flight request makes rollback simpler.

In the example, port P1 proposes a buy of 100 shares at $43.50 with topic sequence 3. The engine accepts and multicasts it. P2 then proposes selling 100 at $43.49 with its own sequence 8; the prices overlap, so the engine generates execution messages on both topics.

Meanwhile P1, unaware of the execution, proposes canceling its order at sequence 4. The engine has already used that sequence for the execution, so it silently drops the stale proposal. P1 sees that sequence 4 came from a different publisher, applies the execution and retries its intended cancel; the order is gone, so it proposes a cancel rejection at sequence 5.

Such contention can theoretically livelock, but the speaker says these trading transactions generally terminate quickly, as an executed order no longer exists to cancel. Applying the architecture elsewhere requires judgment. An audience member asks why the cancel rejection must return through the engine: in this protocol it is sequenced, and client-visible state must come from the globally ordered stream to be recoverable.

Another question concerns atomicity when an execution produces messages for two topics. The speaker says the ordered input is the crucial event: if it is recorded, the passive state machine deterministically regenerates the subsequent messages. The system still requires each individual message to be atomic at the packet and sequence level.

The speaker concludes that speed and determinism enable a simple robust architecture, not merely faster responses. State-machine replication makes testing and recovery repeatable: new engines can replay weeks of past data and also undergo fuzz testing. The discipline is that every state change, including timer-driven action, must be represented in the ordered stream.

Determinism also helps explain decisions to regulators: the system can reconstruct what it knew at each point, rather than guessing which concurrent event arrived first. More parallelism is possible, and the speaker discusses other approaches, but emphasizes that the choices in this design work together to solve exchange problems cleanly and scale naturally.