Stock exchange (order matching engine)
Accept limit and market orders, enforce pre-trade risk limits, and match buys against sells by strict price-time priority. Traditional database locks are orders of magnitude too slow and non-deterministic; a real exchange sequences commands into a total order per symbol and runs a single-threaded, in-memory deterministic state machine.
Component labels and connections
- Clients (client) · calls: Load balancer
- Load balancer (loadBalancer) · calls: Order gateway 1 (risk & FIX), Order gateway 2 (risk & FIX)
- Order gateway 1 (risk & FIX) (service) · calls: ClientOrderID dedup, Deterministic sequencer log (by symbol), L1/L2 market data cache, Order & execution store
- Order gateway 2 (risk & FIX) (service) · calls: ClientOrderID dedup, Deterministic sequencer log (by symbol), L1/L2 market data cache, Order & execution store
- ClientOrderID dedup (dedupStore) · calls: none
- Deterministic sequencer log (by symbol) (queue) · calls: none
- Matching engine (price-time priority) (worker) · calls: Order & execution store
- L1/L2 market data cache (cache) · calls: none
- Order & execution store (kvStore) · calls: none
Requirements
Functional
- Place new limit and market orders (`BUY` / `SELL`, `symbol`, `priceTicks`, `quantity`, `clientOrderId`) and cancel open orders.
- Match orders strictly by price-time priority (best price first; ties broken FIFO by sequencer timestamp/sequence).
- Publish execution reports to the trading parties and stream L1/L2 market data (top-of-book and depth) to subscribers.
Non-functional
- Deterministic total ordering per symbol: replaying the input command log must produce the exact same trades and order book state.
- Sub-millisecond to single-digit-millisecond matching latency; hundreds of thousands of orders/s across symbols.
- Zero lost or reordered executions, and zero duplicate orders when a gateway retries.
Worked estimates
Order rate
≈ 210k messages/s average, ≈ 1M/s at market open/close
5B orders & cancels per 6.5-hour trading day ÷ 23,400 s
Order book memory
≈ 640 MB total — every symbol's entire order book fits in L3 cache / RAM!
10M resting orders across 8,000 symbols × ~64 B per order node
Single-thread matching speed
one pinned CPU core matches ~1M–2M orders/s for a symbol partition
in-memory price map + doubly-linked FIFO queue (~200–500 ns per match)
Sequencer log size
≈ 320 GB/day — easily replicated in memory (Raft/Aeron) and archived to disk
5B messages/day × 64 B binary frame
Market data fan-out
≈ 50 MB/s per feed before subscriber fan-out
500k book updates/s × 100 B to multicast/gateway subscribers
API
NewOrderSingle (FIX / binary) / POST /v1/orders
Request: { clOrdId, symbol, side, ordType, priceTicks, qty }
Response: ExecutionReport { ordId, seqNum, status: 'NEW' | 'PARTIALLY_FILLED' | 'FILLED', fills[] }
OrderCancelRequest / DELETE /v1/orders/{ordId}
Request: { clOrdId, origClOrdId, symbol }
Response: ExecutionReport { status: 'CANCELED' }
O(1) removal via `orderId → node*` hash map into the price level's doubly-linked list.
GET /v1/marketdata/{symbol}/book
Request: depth = 10 | 50
Response: 200 { seqNum, bids[{ price, qty }], asks[{ price, qty }] }
Data model
- orders — store: bookstore
- trades — store: bookstore
The authoritative order book for each symbol partition lives in RAM inside its single-threaded matching engine: a hash map `orderId → OrderNode*` (for O(1) cancel) plus two price trees/arrays (`bids` descending, `asks` ascending) of doubly-linked FIFO `OrderNode` queues.
The sequencer log is the source of truth: every order/cancel gets a monotonic sequence number before touching the matching engine. Hot standby matching replicas consume the exact same log to stay in lockstep.
orders and trades in `bookstore` are written asynchronously down the outbound execution pipeline for client drop-copy, clearing, and historical queries.
High-level design
Trace permitted calls in the architecture above, then open the reference canvas to inspect routing.
Deep dives
Order book data structure for O(1) cancel and match
Cancels and modifications are 80–90% of exchange messages, so cancelling an order cannot scan a price level linearly. Represent each side of a symbol's book with: (1) a price index mapping `integerPriceTicks → PriceLevel*` (either a balanced tree, or a flat array indexed by tick offset around the current midpoint for O(1) lookup), (2) a doubly-linked list of `OrderNode`s inside each `PriceLevel` in FIFO arrival order, and (3) a hash map `orderId → OrderNode*`. Matching inspects only the head of the best opposite `PriceLevel`; cancelling looks up `OrderNode*` by `orderId` and unlinks its `prev`/`next` pointers in O(1) time.
The LMAX Disruptor / deterministic state-machine pattern
Why is a single thread faster than 32 threads for matching one symbol? Multi-threaded access to the top of the order book causes CPU cache-line bouncing, lock contention, and context switches (~1–5 µs), whereas a single thread pinned to a CPU core with no locks, no heap allocations (pre-allocated ring buffer of order structs), and no I/O executes a match in ~200–500 ns (>1M orders/s). Scale horizontally by partitioning symbols across independent single-threaded matching engines.
Sequencer replication and pre-trade risk at the gateway
Gateways terminate client sessions (FIX or binary SBE/OUCH), deduplicate `clientOrderId`, and check pre-trade risk limits (fat-finger max order size, price collar, buying power) using cached position state. Validated commands are sent to the sequencer, which assigns a gapless sequence number and replicates the command to a quorum of log nodes before the matching engines consume it. Because matching is a pure function of the sequenced command log (no `now()` calls, no random numbers, integer tick arithmetic only), any replica engine produces byte-for-byte identical fills.
Failure scenarios
Earnings release: 80% of all orders hit one ticker symbol
Scenario and expected result
A major tech stock reports earnings and 80% of order and book traffic targets a single symbol partition.
Expected: The reference design routes all orders for the symbol through its ordered sequencer partition and deterministic matching engine with a 500 ms visibility lease, preserving strict sequence order (`clean: true`) with zero `orderingViolated` anomalies.
9:30 AM market open: order and quote rate doubles
Scenario and expected result
From t = 1.2 s to 2.2 s traffic doubles as opening cross and algorithmic orders flood the gateways.
Expected: Pre-trade risk checks at the gateway and the in-memory sequencer/matcher absorb the burst well inside the 200 ms deadline.
Market data cache restarts
Scenario and expected result
At t = 1.5 s the L1/L2 market data cache restarts.
Expected: Order entry and matching continue without interruption; book snapshot reads repopulate the cache from the execution/book store in milliseconds.
Alternative designs
Reference
- Inspect the architecture above and run the same scenario.
Multi-threaded concurrent workers with variable latency and short visibility timeouts
- If multiple concurrent workers pull from a symbol's queue with variable execution times (e.g., lock contention or GC pauses) and a short visibility timeout (1 ms), a slow order's lease expires or is overtaken by a fast order on the same symbol. A later sequence number commits before an earlier one becomes visible and completes, violating price-time priority (`orderingViolated`). Run the hot-symbol scenario against this alternative to see `orderingViolated`.
Reference
- Inspect the architecture above and run the same scenario.
Match orders by scanning the store synchronously without a sequencer
- Storing resting orders in a database and matching with `SELECT ... WHERE side='SELL' AND price <= :buyPrice ORDER BY price ASC, created_at ASC FOR UPDATE` serialises every order on disk/store scans (~2–10 ms per order, or ~200 orders/s per symbol). In the simulator, scanning the store synchronously on the order path more than doubles p99 latency compared to the sequenced in-memory matcher.
Reference
- Inspect the architecture above and run the same scenario.
Active-passive vs deterministic active-active (replicated state machine)
- Shipping order book mutations to a standby replica after matching adds latency to the critical path. Instead, replicate the compact *input command log* at the sequencer (via Raft or Aeron UDP multicast) and run two or more identical deterministic matching engines in parallel; if the primary engine dies, the secondary already has the exact same in-memory book at the exact same sequence number.
Clarifying questions
- Which order types are in scope (limit, market, cancel, IOC/FOK)?
- What is the latency target at the matching engine (sub-millisecond vs tens of milliseconds) and peak message rate?
- How many symbols are traded, and can one hot symbol receive a large fraction of the volume?
- Are pre-trade risk checks (buying power, fat-finger limits) part of the gateway path?
Common mistakes
- Matching orders with SQL transactions and `SELECT ... FOR UPDATE` row locks.
- Using multi-threaded workers on the same symbol's order book, causing lock contention and out-of-order execution.
- Representing prices as IEEE 754 floating-point numbers instead of integer ticks (`priceTicks`), causing rounding bugs.
- Using a heap or array for price levels where cancelling an arbitrary `orderId` requires an O(N) scan.
- Calling `System.currentTimeMillis()` inside the matching engine instead of using the sequencer's timestamp, breaking deterministic replay.
Self-assessment rubric
requirements / levels 1-4
- 1/4 Buy and sell stocks.
- 2/4 Limit/market orders and cancels.
- 3/4 Price-time priority (FIFO), deterministic ordering, and low-latency market data.
- 4/4 Includes pre-trade risk checks, `clientOrderId` idempotency, and deterministic replay.
estimates / levels 1-4
- 1/4 None.
- 2/4 Orders/s only.
- 3/4 Calculates peak message rate (~200k–1M/s) and shows the entire resting book fits in <1 GB RAM.
- 4/4 Contrasts ~300 ns in-memory single-thread matching with millisecond disk/DB locking.
api / levels 1-4
- 1/4 POST order.
- 2/4 Order, cancel, and order book.
- 3/4 Includes `clOrdId`, integer `priceTicks`, and sequenced `ExecutionReport` events.
- 4/4 Distinguishes low-latency binary order entry (OUCH/SBE/FIX) from multicast market data feeds.
data model / levels 1-4
- 1/4 Orders table.
- 2/4 Orders and trades tables.
- 3/4 In-memory price levels + doubly-linked FIFO queues + `orderId → node*` map, backed by a sequenced command log.
- 4/4 Uses integer price ticks (never floating point) and monotonic sequence numbers.
high level / levels 1-4
- 1/4 API + DB.
- 2/4 Gateway + matching engine + DB.
- 3/4 Gateways (dedup + risk) → partitioned sequencer log → single-threaded matching engines → execution & market data fan-out.
- 4/4 Explains hot-standby state-machine replication fed by the same sequencer log.
deep dive / levels 1-4
- 1/4 None.
- 2/4 Mentions in-memory book.
- 3/4 Explains O(1) cancel via hash map + doubly-linked list and why single-threaded beats locks.
- 4/4 Details how concurrent workers or out-of-order retries break price-time priority (`orderingViolated`).
wrap-up / levels 1-4
- 1/4 Stops.
- 2/4 Mentions latency.
- 3/4 Identifies hot symbols, gateway reconnects, and runaway algorithms as key risks.
- 4/4 Includes kill-switch / cancel-on-disconnect and regulatory audit trail replay.