Design a Real-Time Order Matching Engine
Scenario prompt
Design the core matching engine for a trading venue (an equities exchange or a crypto exchange) that pairs incoming buy and sell orders against a live order book, per instrument. Requirements:
- Matching must be strictly deterministic and enforce price-time priority — given the same sequence of inputs, replaying them must always produce the exact same sequence of trades
- A single busy instrument needs sustained high throughput at microsecond-level matching latency; an illiquid instrument sitting nearly idle must not consume resources it doesn't need, and neither instrument's load should degrade the other's
- If the matching process crashes mid-session, no accepted order or trade can be lost, and none can be double-counted — recovery must reconstruct the exact order book state that existed the instant before the crash
- Pre-trade checks (buying power, position limits, regulatory halts) must run before an order reaches the book, without adding queuing delay to the matching path itself
Mihir's attempt
[!todo] Write your own attempt here before reading the model solution below — how you'd guarantee deterministic replay after a crash, and how you'd stop one instrument's load from touching another's latency.
Model solution
Partition by instrument, and give each partition a single-writer matching loop. Every instrument's order book is owned by exactly one thread/process at a time, processing that instrument's orders strictly sequentially — no locks needed on the hot path because there's never concurrent access to a given book. This is the same blast-radius-containment instinct as Bulkhead Pattern applied to compute rather than connection pools: a single-symbol partition means a burst of activity in one instrument can only ever saturate its own partition, never steal cycles from a quiet instrument's book or, worse, a busy neighbor's. Partitions can be scheduled onto worker threads dynamically so idle instruments cost near-zero and hot ones get dedicated capacity.
Make the order book a projection of an append-only event log, not the source of truth itself. Every accepted order, cancel, and resulting trade is written to a durable, sequentially-numbered log (a WAL, or a Kafka-style partitioned log keyed by instrument) before the matching engine acknowledges it — the in-memory limit order book is rebuilt by replaying that log, exactly the write-model/read-model split described in Event Sourcing and CQRS. Because matching is a pure deterministic function of ordered input events, recovery after a crash is just "replay the log from the last durable checkpoint" — there's no separate reconciliation step, because the book's state was never anything other than a derivation of the log to begin with.
Sequence numbers per instrument make the log itself the idempotency mechanism. Every event in an instrument's log carries a strictly increasing sequence number assigned at ingestion. A worker resuming after a crash knows precisely which sequence it last durably applied and replays from there — no double-application, no gaps — the same closed-loop reasoning as Idempotency Keys, but applied to log replay instead of request retries. A unique, sortable identifier per order (see Design a Distributed Unique ID Generation Service) makes this traceable end-to-end from order entry through to trade confirmation.
Keep pre-trade risk checks entirely off the matching thread's critical path. Buying-power and position-limit checks hit external state (account balances, risk limits) that can be slow or occasionally unavailable — running them inline inside the matching loop would tie the fastest part of the system to the latency of its slowest dependency. Instead, checks run at order ingestion, before an order is admitted to its instrument's queue; a circuit breaker (see Circuit Breaker Pattern) protects the ingestion tier from a degraded risk service without ever touching the matching loop itself, which stays dependency-free by design.
Replicate the log asynchronously for failover, and be explicit about the consistency window that buys. Synchronous cross-region replication of every matching event would cap throughput at wide-area round-trip latency — unacceptable for a microsecond-latency system. Asynchronous replication to a hot standby, paired with a fenced (single-owner, no split-brain) failover protocol, accepts a small window of potential data loss on a true regional failure in exchange for keeping the primary path fast — a tradeoff that has to be named explicitly to stakeholders, not hidden inside "we have DR."
Gaps to revisit
- Cross-instrument atomicity — basket orders or paired trades that must succeed or fail together break the clean single-instrument-partition model; what's the minimal coordination mechanism that doesn't reintroduce cross-partition locking on the common case
- Market data fan-out — publishing book snapshots and incremental deltas to thousands of downstream consumers without that publish path ever applying backpressure to the matching loop itself
- Fairness and gaming — colocated participants can observe log/market-data timing details that create latency-arbitrage opportunities; does the sequencing design need to account for that, and how do venues typically constrain it (e.g., discrete time buckets, speed bumps)
Engineering Lens
This is one of the purest instances of "the log is the system" — the order book isn't a data structure with a backup, it's a cache of a log that happens to be recomputable at any time, and that reframing is what makes crash recovery trivial instead of a bespoke reconciliation project. The single-writer-per-partition design is also worth defending explicitly in a review: it looks like it's leaving concurrency on the table, but for a domain where determinism and provable correctness matter more than raw core utilization, trading parallelism for a lock-free, replayable design is the right call — and being able to articulate why is exactly the kind of tradeoff reasoning that distinguishes Capital Markets system design from a general "make it fast" performance exercise. The pre-trade-checks-off-the-hot-path decision generalizes even further: any system with one latency-critical core loop and several slower, less-critical dependencies should be asking the same "what's allowed to touch the hot path, and what has to be pushed to the edges" question.