Design a stock exchange order-matching engine

Matching on one symbol is inherently sequential: whether order B trades depends on whether order A just took the liquidity. Multithreading one book needs locks, and locks add latency jitter and make the result depend on thread timing, which breaks determinism and fairness. So each symbol belongs to exactly one engine thread, pinned to a CPU core, with no locks and data that stays in L1/L2 cache. Scale out by partitioning symbols across threads and machines; symbols never interact in matching, so this is embarrassingly parallel. Balance partitions by load, not by count: index options and a few large-cap stocks get their own cores. Inside the thread, avoid anything that can pause: no garbage collection in the hot path (preallocated object pools, or C++/Rust), no system calls, no logging to disk from the thread. Communication with the sequencer and publisher uses lock-free single-producer single-consumer ring buffers, the pattern popularised by the LMAX Disruptor. A single thread can process millions of simple order events per second, so one core per busy symbol is plenty. The hard limit is not CPU but the cost of journaling and replicating each message before matching, which is why that path gets the most engineering.

The engine is a state machine: state_n+1 = apply(state_n, message_n). If every replica sees the same messages in the same order and apply() is deterministic, every replica has the same book. That is the whole fault tolerance story. The sequencer assigns a monotonically increasing sequence number to each inbound message and writes it to an append-only journal. Before the primary engine acts on message n, the journal entry must be durable on at least the standby (and ideally replicated to the DR site, asynchronously because of distance). This is why the primary never loses a trade it has published: anything it acted on is in the journal. Determinism rules: no wall-clock reads inside apply() (use the timestamp stamped by the sequencer), no random numbers, no hash-map iteration order dependence, no floating point for prices. Reference data changes, halts and end-of-session events are also sequenced commands. Recovery = load latest snapshot + replay journal from its sequence number. A replay of an hour of messages takes seconds because matching is fast. The same journal also feeds audit and surveillance: regulators can reconstruct the exact book at any microsecond.

Operations to support: add an order, cancel by id, modify, and match against the best opposite price. Prices are integers in ticks. Because exchanges set a daily price band (say ±10-20%), the number of possible prices is bounded, so a fixed array of price levels indexed by (price - band_low) / tick_size gives O(1) access to any level. Keep a pointer to the best bid and best ask; when a level empties, scan to the next non-empty level, which is fast because the book is dense near the top. Without bands, use a red-black tree or skip list of levels (O(log n)). Each level is a FIFO doubly linked list of orders plus a cached total quantity, so adding at the tail and removing any order are O(1). A hash map from order_id to its list node makes cancel O(1), which matters because most messages are cancels and modifies. Modify semantics are part of fairness: reducing quantity keeps time priority; increasing quantity or changing price is treated as cancel-and-replace and goes to the back of the queue. Market orders walk levels until filled or the book is empty; IOC orders cancel any remainder instead of resting. Stop orders sit in a separate trigger book keyed by stop price and enter the main book when the last trade price crosses them.

Every book change is published on UDP multicast, because one packet reaches thousands of subscribers at the same time and TCP fan-out would give earlier connections an advantage. Messages carry a per-channel sequence number. Two identical streams (A and B) go over separate network paths; receivers take whichever copy arrives first and use the other to fill gaps. If both miss a packet, the receiver asks a TCP retransmission service for that sequence range, or, after a long gap, requests a full snapshot and then applies incremental updates after the snapshot's sequence. Fairness extends to co-location: exchanges equalise cable lengths to member racks so no member gets data nanoseconds earlier because of location; NSE's 2015 tick-by-tick co-location issue in India showed how much regulators care about this. Publish tick-by-tick order-level data to co-located members and conflated snapshots (for example top-5 depth every second) for retail and vendors. The publisher runs off the engine's output stream, never in the matching thread, so a slow network does not slow matching.

Putting risk checks before the sequencer keeps rejects out of the journal and the engine, but risk state (member exposure) then changes outside the deterministic core. Putting member-level risk inside the engine makes it deterministic but adds work to the hot path. Common choice: stateless validation and simple limits in gateways, exposure-based limits in a dedicated risk stage that is itself sequenced.

Waiting for the standby to persist each message adds a few to 20 µs per message, but guarantees no trade can be lost on failover. Async replication is faster but a primary crash can lose trades that were already reported to brokers, which is unacceptable. Replication to a distant DR site stays async, and DR failover is a declared event with reconciliation.

Continuous price-time matching rewards speed and drives the latency arms race. Frequent batch auctions (match every few milliseconds at one clearing price) reduce the value of being microseconds faster. Most exchanges use continuous matching during the day and call auctions at open (and sometimes close). Mention the trade-off; implement continuous plus a pre-open auction.

Kernel bypass (DPDK, Solarflare/OpenOnload, RDMA) and busy-polling cores cut network latency from tens of microseconds to a few. It costs dedicated hardware, CPU cores spinning at 100%, and harder operations. For a real exchange it is standard; for an interview design, say where it matters (gateways, sequencer, publisher) and that the matching logic itself is not the bottleneck.

On expiry day, at-the-money index options can take a large share of all messages. One symbol cannot be split across threads, so give it a dedicated core and machine, keep its gateway and journal path short, and throttle members per session. If needed, move other symbols off that partition during the day using a sequenced 'migrate' command at a quiet moment.

At 10x messages, the journal (not matching) saturates first. Batch journal writes (group commit every few microseconds), use NVMe with direct I/O or replicate over RDMA, and partition the sequencer by symbol group so there are several independent journals. Global order across partitions is not needed because symbols do not interact.

Algos may send 100 messages per trade, and most are cancels. Exchanges control this with per-session message rate limits and order-to-trade ratio charges. Technically, O(1) cancel and fast reject paths in the gateway keep this load cheap.

The hot standby has the same state from the same sequenced stream. After fencing the primary, the standby turns on its outputs. Gateways deduplicate outbound messages by engine output sequence, so brokers see each execution report once. Recovery time is seconds.

The sequencer is the most critical single point. Run a standby sequencer that receives the journal; on failover it resumes numbering from the last durably replicated sequence. Messages received but not journaled are lost from the exchange's view, and gateways tell brokers to resend or treat those orders as never received (brokers check status by client_order_id).

Trading halts. The DR site has an asynchronously replicated journal; operators compare the last sequence with member drop copies, decide the recovery point, and announce it before resuming. Exchanges rehearse this with mandatory live DR drills. Honest answer: an exchange prefers a short halt over trading on uncertain state.