System design deep dive · HLD
Design a Stock Exchange Matching Engine: full high-level design.
Requirements, back-of-envelope capacity estimation, a high-level design diagram, a deeper deployment architecture diagram, sequence diagrams for order submission and cancellation, and an entity-relationship diagram for the trading data model - with the reasoning an interviewer expects behind every box and arrow.
1. Clarify requirements before drawing any box
A matching engine is one of the few systems where "fast" and "fair" are both hard functional requirements, not just non-functional goals - regulators, not just users, care about the ordering guarantees. Scope has to be pinned down before any box gets drawn.
Functional requirements
Non-functional requirements
2. Back-of-the-envelope capacity estimation
These numbers rule out entire categories of design before a single box is drawn: the 500-microsecond matching budget alone eliminates any shared lock, any network round trip, and any general-purpose database from the hot path.
| Metric | Assumption | Resulting estimate |
|---|---|---|
| Order messages (new + cancel + replace) | 5,000 listed symbols, ~40M messages/day | ~460 msg/sec average, ~50,000 msg/sec peak at the 9:30am open |
| Trades executed | ~15% of order messages result in a fill | ~6M trades/day, ~7,500 trades/sec at peak |
| Matching latency budget | End-to-end order-to-ack SLA of 1ms | Matching itself must finish in <500µs p99, leaving headroom for network + risk checks |
| Order book memory footprint | 5,000 symbols × ~400 resting orders × ~96 bytes/order | ~192MB - fits entirely in RAM on a single matching shard |
| Market data fan-out | 50,000 subscriber connections × 7,500 trades/sec × ~200 bytes | ~10.5 Gbps aggregate at peak - requires multicast, not per-subscriber TCP |
3. High-level design (HLD)
The HLD names the major components and the one-directional flow of an order from submission to trade and market data, without yet committing to core-pinning, replica counts, or failover mechanics - that belongs in the architecture diagram.
What each box owns
Order gateway (entry point)
Terminates the FIX session, validates message syntax and symbol tradeability, and normalizes the order into an internal representation. It is kept stateless so any gateway instance can serve any trader without sticky sessions - all per-order state lives downstream.
Risk check (pre-trade gate)
Synchronous checks against an in-memory account-limits cache: available buying power/margin, per-order and per-account fat-finger limits (max notional, max quantity), and self-trade prevention flags. Rejects return straight to the trader without ever reaching the matching engine, so a bad order never costs the book any time.
Sequencer + matching engine
The sequencer stamps every accepted order and cancel with a strictly increasing per-symbol sequence number before handoff - this is what makes WAL replay deterministic. The matching engine owns one in-memory order book per symbol, pinned to a single core, so two messages for the same symbol can never be processed concurrently and no lock is ever needed.
WAL, exec reports, and market data
Every accepted order and resulting trade is appended to a write-ahead log before any acknowledgment leaves the engine, so a crash can always be replayed to an identical book state. Exec reports return the fill confirmation to the originating gateway; the market data publisher fans the same trade and depth update out to every subscriber over multicast at the same instant, satisfying the simultaneous-access requirement.
4. Detailed architecture diagram
The architecture diagram answers "how is this actually deployed?" - and for a matching engine the most interview-relevant answer is what it deliberately does not do: it is not multi-region active-active, because speed-of-light latency differences between regions would themselves be a fairness violation.
| Decision | Choice | Reasoning |
|---|---|---|
| Multi-region | Single primary colocation facility, cold/warm DR site only | Active-active regions would let participants near one region see and react to a price move before participants near the other - a fairness/regulatory problem, not merely a latency one. |
| Sharding key | Symbol (ticker), pinned to one core | Matching for a given symbol must be strictly sequential; sharding by symbol means no cross-shard coordination is ever needed to process a single order. |
| Failover | Synchronous WAL replication to a hot standby core, same facility | An asynchronous standby could lose the last few trades on failover; synchronous replication trades a small amount of latency for zero data loss. |
| Market data delivery | UDP multicast + gap-fill retransmission server | Multicast delivers one packet to every subscriber at the same instant, satisfying simultaneous-access rules; TCP is used only to fill gaps a subscriber detects via sequence-number holes. |
5. Sequence diagrams for the two critical flows
This is where an interviewer checks whether the ordering guarantees are real: what happens when a cancel and a fill race each other, and whether the design can prove - not just claim - that replay always produces the same outcome.
5.1 Order submission and match
Step 5 happens entirely inside the matching engine's single core for that symbol - the WAL append and the in-memory match are the only work on the hot path, with no lock and no network hop. Step 7 is drawn as a separate, non-blocking arrow because market data subscribers are not part of the response path back to the trader, but unlike an analytics pipeline it still fires within microseconds - "async" here means "not on this response," not "eventually."
5.2 Cancel racing a fill (sequence-number resolves the race)
The cancel and the fill arrived at the matching engine at almost the same instant, but the sequencer had already stamped the incoming sell order as seq#500 and the cancel as seq#501 - so the engine processes them in that exact order, filling 60 shares first and canceling only the remaining 40. Replaying the WAL from scratch always reproduces this exact outcome, which is precisely what a post-trade audit or regulator re-check requires: the ordering is a property of the sequence number, not of wall-clock timing at the engine.
6. Entity-relationship (ER) diagram and schema
The data model has to answer three questions: what is authoritative for a resting order's remaining size, how is the immutable trade audit trail kept separate from mutable order state, and how is the L2 depth view served without querying the live in-memory book.
Key modeling decisions
| Storage choice | Use when | Watch out for |
|---|---|---|
| Relational (Postgres, sharded by symbol), for orders/trades | You need transactional guarantees on order-state transitions and joins for compliance/audit reporting. | The relational store is never on the matching hot path - it's fed asynchronously from the WAL, so it can lag the in-memory book by milliseconds. |
| Wide-column / time-series store (kdb+, Cassandra) for trade history | Query pattern is append-heavy time-series analytics (VWAP, historical replay) at extreme volume. | Cross-symbol joins and strong consistency are harder to express; kdb+ is the de facto industry choice specifically for this workload. |
7. Deep dives interviewers actually probe
Why keep the order book fully in-memory and single-threaded per symbol, instead of a shared database table?
Any lock or round trip to a shared store on the hot path adds latency measured in the wrong units - matching must resolve in microseconds, while disk or network I/O is milliseconds. Pinning each symbol's book to one core removes the need for any lock at all, since there is no concurrent writer to coordinate with by construction. Durability comes from the WAL append, not from the book itself being persistent.
How does price-time priority actually get implemented as a data structure?
Each side of the book (bid/ask) is a price-indexed structure such as a red-black tree or skip list keyed by price, with the best price at one end. Each price level holds a FIFO queue of resting orders in arrival order. An incoming order walks the opposite side outward from the best price, filling FIFO at each level until exhausted or price no longer crosses; a new order joining an existing price level is appended to the tail of that level's queue, never inserted ahead of resting orders.
// simplified match loop for an incoming BUY order
while (order.remainingQty > 0 && askSide.bestPrice() <= order.price) {
PriceLevel level = askSide.bestLevel();
Order resting = level.queue.peekFirst(); // FIFO within the level
long fillQty = Math.min(order.remainingQty, resting.remainingQty);
emitTrade(order, resting, level.price, fillQty);
resting.remainingQty -= fillQty;
order.remainingQty -= fillQty;
if (resting.remainingQty == 0) level.queue.pollFirst();
}What happens to market data fairness if one subscriber's network is faster than another's?
The exchange guarantees simultaneous publish - a single multicast send - not simultaneous receipt; regulators require the source to be fair, not the last mile. This is exactly why market data goes out over UDP multicast rather than per-connection TCP: every subscriber receives the same packet the instant it leaves the publisher, and any latency differential afterward is the subscriber's own colocation and hardware problem - which is precisely why HFT firms pay to rack servers physically close to the exchange.
How do you prevent one misbehaving order from stalling the whole engine?
Pre-trade risk checks (buying power, max notional, max order size, self-trade prevention) run before an order ever reaches the matching engine, rejecting dangerous orders synchronously and cheaply. Because each symbol is isolated on its own core, even a pathological order that slips through - an accidental oversized market order - can only ever affect that one symbol's book and its own subscribers; it cannot stall matching for any other symbol.
What is the single biggest bottleneck as message volume scales 10x during a volatility spike?
Not the matching computation itself - that stays effectively O(log n) per order and symbols are already isolated. The real bottleneck is correlated bursts across many symbols at once (a market-wide circuit-breaker event), which stresses the sequencer tier and the market-data network's bandwidth headroom simultaneously - solved by scaling sequencer capacity per shard group and ensuring the multicast network itself, not just the publisher process, has enough spare bandwidth so a slow consumer on a shared segment can never create backpressure on the publisher.
Post a Comment
Add