Designing a Stock Exchange: The Low-Latency Matching Engine

Most distributed systems fight tail latency with replication, retries, and eventual consistency. An exchange cannot: every order must be processed exactly once, in a provable order, with microsecond latency, and two replays of the same input must produce byte-identical output — regulators will ask. The design that achieves this looks almost nothing like a typical web backend, and that inversion is why "design a stock exchange" separates candidates who pattern-match from candidates who reason.

Requirements

Functional: accept limit and market orders, cancel/replace, match by price-time priority, publish executions and market data. Non-functional: ~1M orders/sec per symbol group, sub-100µs order-to-ack inside the engine, zero lost orders, deterministic replay, fairness (first come, first matched at equal price).

The order book

Per symbol, two sides: bids (sorted descending by price) and asks (ascending). Within a price level, a FIFO queue — that is the "time" in price-time priority.

        BIDS                      ASKS
  price     qty            price     qty
  100.05    300  <- best   100.07    500  <- best
  100.04    1,200          100.08    900
  100.02    700            100.10    2,000

An incoming buy limit at 100.08 crosses the spread: it fills 500 @ 100.07, then 400 @ 100.08 (partial), and the remainder — none here — would rest on the bid side.

The data structure everyone reaches for: a balanced tree or sorted array of price levels, each level holding an intrusive doubly-linked list of orders, plus a hash map from order ID to node for O(1) cancels. Cancels are 30-50% of real exchange traffic — if your design makes cancel O(n), you have already failed the follow-up.

class PriceLevel:
    def __init__(self, price):
        self.price = price
        self.orders = DoublyLinkedList()   # FIFO within level

class OrderBook:
    def __init__(self):
        self.bids = SortedDict()           # price -> PriceLevel
        self.asks = SortedDict()
        self.index = {}                    # order_id -> node, O(1) cancel

The counterintuitive core: single-threaded matching

Matching for a symbol is single-threaded. No locks, no concurrent data structures. A lock-free ring buffer (the LMAX Disruptor pattern) feeds one pinned CPU core that owns the book; it processes events one at a time from L1/L2 cache.

Why this beats a clever concurrent design: matching is a serial problem by definition — order N+1's outcome depends on order N's effect on the book. Any concurrency you add must be serialized again to preserve price-time fairness, so you pay synchronization cost for nothing. LMAX famously ran 6M TPS on one thread. You scale horizontally by sharding symbols across engines, never by threading one book.

Determinism and recovery

The engine is a deterministic state machine: state × ordered inputs → state × outputs. That gives you the whole reliability story:

• Sequencer in front assigns a gapless sequence number to every inbound event and journals it (append-only, fsync or replicated) before the engine sees it.
• Recovery = load snapshot + replay journal. Byte-identical outcome, auditable by regulators.
• Hot-hot replica = feed the same sequenced stream to a second engine; it stays in lockstep. Failover is "start reading outputs from the replica" — no state transfer, no reconciliation.

No randomness, no wall-clock reads, no iteration over unordered maps inside the engine. One HashMap iteration order leaking into matching and your replicas silently diverge.

Everything around the hot path

Risk checks (buying power, position limits, fat-finger bounds) run before the sequencer — pre-trade gate services that can be scaled out per member.

Market data fan-out: the engine emits an execution/quote stream; a separate tier builds the consolidated feed and multicasts it (real exchanges use UDP multicast so all members receive ticks simultaneously — TCP fan-out would create fairness disputes between fast and slow subscribers).

Downstream: clearing, settlement, surveillance consume the same journal asynchronously. Note the pattern — the journal is a transactional-outbox-style source of truth; everything else is a projection.

Latency budget

Stage	Budget
NIC → sequencer (kernel-bypass, e.g. DPDK)	~5µs
Sequence + journal (replicated memory ack)	~10µs
Ring buffer hop	~1µs
Match + book update	~1-5µs
Ack out	~5µs

GC pauses are lethal at these scales, which is why engines are C++/Rust or allocation-free Java with pre-allocated object pools.

Interview traps

"Why not put the order book in Redis/Postgres?" — a network round-trip already blows the entire latency budget by 10x. "How do you scale a hot symbol?" — you don't shard one book; you make the single thread faster and accept per-symbol serialization as the fairness contract. "Exactly-once?" — sequence numbers end-to-end: members retransmit with the same ID, engine dedupes; consumers ack by sequence and replay gaps.

The one-sentence summary interviewers want: sequence everything, journal before processing, match on a single deterministic thread, and scale by sharding symbols.