How to design a stock exchange

An exchange is a deterministic state machine wrapped in a network: a per-symbol matching engine is easy, and the whole engineering problem is imposing one arrival order, replicating it, and fanning out results, all inside a hard latency budget with no throughput problem to solve.

The four pieces

• Order book: resting orders not yet paired, one per symbol, buyers dearest-first, sellers cheapest-first.
• Matching engine: single-threaded fold over the log, pairs each aggressor against the resting side by price-time priority (best price first, then FIFO).
• Sequencer: one process stamps every accepted message with a strictly increasing seq + timestamp before anything sees it. That number is the official arrival order.
• Multicast fanout: one UDP copy per event to a group; the switch fabric duplicates it so all 500 subscribers get it at the same instant.

flowchart LR
    M["Member (colocated)"] --> GW["Gateway<br/>kernel bypass + risk"]
    GW --> SEQ["Sequencer<br/>seq + ts"]
    SEQ --> LOG[("Event log<br/>THE state")]
    LOG --> ENG["Engines<br/>1 thread / symbol shard"]
    LOG --> STBY["Hot standby<br/>same fold, hashed"]
    ENG --> MD["Multicast A/B feeds"]
    ENG --> GW
    style LOG fill:#1d3557,color:#fff

Key numbers

• Round trip (tick-to-trade) p50 = 11.55 us = 8.70 inbound + 2.85 outbound; p99.9 under 50 us.
• Peak 427,350 msg/s (8,547 avg x 50 open burst). Matching hop 470 ns (~1 us) so peak = 43% of one core. No throughput problem; everything is bought with latency or variance.
• 20 inbound messages per trade, 19 of 20 never fill (mostly market-maker cancel+add).
• Sequencer replication = 4.5 us = 39% of budget, spent on majority-ack durability.
• Multicast 0.376 Gbps vs unicast 188 Gbps; unicast’s real sin is the 500th copy leaving 500 us late (43 budgets of unfairness).

Order book: array + bitmap

• Layout: levels[] array indexed by (price - base)/tick, FIFO queue + depth/count per level; index hash (order_id to node) for O(1) cancel; two-level occupancy bitmap for O(1) best-price.
• Size: ~1,000 levels x 32 B = 64 KB/symbol, ~192 MB market (fits L2 cache; use 1 GB huge pages).
• Prices are i32 integer ticks, never floats ($100.02 = 10002).

• Gotcha: repairing best by walking the array is O(n) (501 slots for one add+cancel, 999 per requote loop) and does not amortize. Bitmap replaces it with two find-set-bit ops for ~272 B/symbol (0.4%).

Order types & market data

• Limit rests the remainder; Market takes any price, discards rest; IOC fills now, cancels rest; FOK fills whole or nothing. All are one matching rule with different remainder handling.
• A market order = IOC limit at the worst price. Against an empty book it fills/rests/rejects nothing — it is simply cancelled (avoids flash-crash prints and false rejects).
• Feed levels: L1 = best bid/offer (BBO); L2 = qty per price, anonymous; L3 = every individual order (needed to rebuild the book; snapshots use L3).

Determinism forbids

Same numbered log through the same program = byte-identical output, always.

• Payoff: a hot standby is the same program on the same log — no replication protocol, just a per-message output-hash check. On divergence, halt the symbol (a book members can’t reconstruct is worse than an outage).

Rules & gotchas

• Shard by symbol and nothing else — AAPL never matches MSFT, so it is the only independent axis. Sharding by account or order_id breaks matching.
• Threading the engine: ~79% serial work, Amdahl caps 8 threads at ~23% gain, and cache-line contention adds 200 ns to a 470 ns hop (43% regression). Not worth it.
• Log is the state, book is a materialized view; recovery = replay from last snapshot (~0.51 s, under the 1 s target).
• Durability = majority ack (3 copies), no fsync on the hot path (an fsync is 10–20 us, doubles the budget).
• Kernel bypass is mandatory: the normal kernel path is ~13.2 us both ways (114% of budget) and its tail is far worse; bought for jitter, costs one spinning core.
• Colocation is a regulated equal-length product because 1 km adds ~9.8 us (85% of what the exchange controls).
• Jitter killers (each 1–4 orders of magnitude bigger than the hop): page fault (100 us), C-state exit (50–100 us), GC pause (1–100 ms), interrupt on an engine core. Prevented via mlockall, isolcpus, IRQ affinity, no managed heap.
• Speed bumps: a random bump reorders arrivals (nondeterministic, breaks priority); a fixed bump preserves order and can protect makers from stale-quote arbitrage (a policy choice, not neutrality).