Overview
A stock exchange is one of the most latency-sensitive systems in existence — matching engines process orders in microseconds. The core challenge is maintaining a fair, deterministic, high-throughput order book while providing a reliable audit trail and sub-millisecond market data distribution.
Key requirements:
- Latency: order acknowledgment in < 100µs (matching engine < 10µs)
- Throughput: millions of orders per second
- Fairness: price-time priority — best price wins, ties go to earliest arrival
- Durability: no lost orders even on crash
- Market data: real-time price/volume distribution to thousands of subscribers
Architecture
ORDER SUBMISSION FLOW
════════════════════════════════════════════════════════
Trading Client
│
│ FIX Protocol (TCP) / REST (for less latency-sensitive)
▼
┌─────────────────────────────────────────────────────┐
│ Order Gateway / FIX Engine │
│ (validates order format, client auth, rate limit) │
└───────────────────────┬─────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────┐
│ SEQUENCER │
│ (assigns monotonic sequence number to each order) │
│ Single point — guarantees global order of events │
└───────────────────────┬─────────────────────────────┘
│
┌───────────┴────────────┐
│ │
▼ ▼
┌────────────────────┐ ┌──────────────────────────┐
│ Matching Engine │ │ Write-Ahead Log (WAL) │
│ (in-memory only) │ │ (async disk persist) │
│ TreeMap bid/ask │ │ replayed on crash │
└────────────────────┘ └──────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────┐
│ Market Data Publisher │
│ Level 1: best bid/ask → UDP multicast │
│ Level 2: top 5 levels → UDP multicast │
│ Trades: price+qty → UDP multicast │
└─────────────────────────────────────────────────────┘
ORDER BOOK STRUCTURE
════════════════════════════════════════════════════════
BID SIDE (buy orders, descending price)
┌──────────┬──────────────────────────────┐
│ $150.50 │ [Order#1: 100 shares 09:30:01]│ ← best bid
│ │ [Order#3: 200 shares 09:30:05]│
├──────────┼──────────────────────────────┤
│ $150.25 │ [Order#2: 50 shares 09:30:02] │
└──────────┴──────────────────────────────┘
ASK SIDE (sell orders, ascending price)
┌──────────┬──────────────────────────────┐
│ $150.75 │ [Order#4: 75 shares 09:30:03] │ ← best ask
├──────────┼──────────────────────────────┤
│ $151.00 │ [Order#5: 300 shares 09:30:04]│
└──────────┴──────────────────────────────┘
SPREAD = $150.75 - $150.50 = $0.25
MATCH: new buy limit at $150.75 → matches Order#4
Execution: 75 shares at $150.75
LATENCY BUDGET (µs)
════════════════════════════════════════════════════════
NIC receive 1–2µs
Kernel network stack 3–5µs (or ~0.5µs with DPDK)
FIX parsing 1–2µs
Sequencer assign 0.5µs
Matching engine 2–5µs
WAL write (async) 50µs (doesn't block order path)
Market data publish 1–2µs
Total (critical path): ~10µs
Technical Implementation
Order Book with Price-Time Priority
public class OrderBook {
// TreeMap: sorted by price, O(log n) insert/remove
// NavigableMap: floorKey/ceilingKey for best bid/ask
private final TreeMap<BigDecimal, ArrayDeque<Order>> bids =
new TreeMap<>(Comparator.reverseOrder()); // descending: best bid first
private final TreeMap<BigDecimal, ArrayDeque<Order>> asks =
new TreeMap<>(); // ascending: best ask first
public List<Trade> addOrder(Order order) {
List<Trade> trades = new ArrayList<>();
if (order.getSide() == Side.BUY) {
trades.addAll(match(order, asks, (bidPrice, askPrice) -> bidPrice.compareTo(askPrice) >= 0));
if (order.getRemainingQty() > 0 && order.getType() == OrderType.LIMIT) {
bids.computeIfAbsent(order.getPrice(), p -> new ArrayDeque<>()).offer(order);
}
} else {
trades.addAll(match(order, bids, (askPrice, bidPrice) -> askPrice.compareTo(bidPrice) <= 0));
if (order.getRemainingQty() > 0 && order.getType() == OrderType.LIMIT) {
asks.computeIfAbsent(order.getPrice(), p -> new ArrayDeque<>()).offer(order);
}
}
return trades;
}
private List<Trade> match(Order aggressor, TreeMap<BigDecimal, ArrayDeque<Order>> restingBook,
BiPredicate<BigDecimal, BigDecimal> priceMatches) {
List<Trade> trades = new ArrayList<>();
while (aggressor.getRemainingQty() > 0 && !restingBook.isEmpty()) {
Map.Entry<BigDecimal, ArrayDeque<Order>> bestLevel = restingBook.firstEntry();
if (!priceMatches.test(aggressor.getPrice(), bestLevel.getKey())) break;
ArrayDeque<Order> queue = bestLevel.getValue();
Order resting = queue.peek();
long fillQty = Math.min(aggressor.getRemainingQty(), resting.getRemainingQty());
BigDecimal fillPrice = resting.getPrice(); // price-time: resting order's price
trades.add(new Trade(aggressor.getId(), resting.getId(), fillQty, fillPrice));
aggressor.fill(fillQty);
resting.fill(fillQty);
if (resting.getRemainingQty() == 0) {
queue.poll();
if (queue.isEmpty()) restingBook.remove(bestLevel.getKey());
}
}
return trades;
}
public Optional<BigDecimal> bestBid() {
return bids.isEmpty() ? Optional.empty() : Optional.of(bids.firstKey());
}
public Optional<BigDecimal> bestAsk() {
return asks.isEmpty() ? Optional.empty() : Optional.of(asks.firstKey());
}
}
Sequencer — Deterministic Order Stamping
// Single-threaded sequencer — assigns global monotonic sequence number
// All matching engines replay the same sequence → deterministic state
public class Sequencer {
private final AtomicLong sequence = new AtomicLong(0);
private final WalWriter walWriter;
private final MatchingEngine matchingEngine;
public OrderAck submit(Order order) {
long seq = sequence.incrementAndGet();
order.setSequenceNumber(seq);
order.setReceivedAt(System.nanoTime());
// Write to WAL first (async — doesn't block critical path)
walWriter.writeAsync(seq, order);
// Process in matching engine (synchronous, in-memory)
List<Trade> trades = matchingEngine.process(order);
// Publish market data
marketDataPublisher.publish(trades, matchingEngine.getL1());
return new OrderAck(order.getId(), seq, OrderStatus.ACCEPTED);
}
}
Market Data Distribution
// Market data: Level 1 (best bid/ask) published via UDP multicast
// Low-latency: no TCP handshake, no ack, subscribers just listen
import * as dgram from 'dgram';
export class MarketDataPublisher {
private socket = dgram.createSocket({ type: 'udp4', reuseAddr: true });
private readonly MULTICAST_ADDR = '239.0.0.1';
private readonly L1_PORT = 9001;
publishL1(symbol: string, bid: number, bidSize: number, ask: number, askSize: number): void {
const msg = Buffer.allocUnsafe(32);
// Pack as binary for minimum size/parse time
msg.write(symbol.padEnd(8), 0, 'ascii');
msg.writeDoubleBE(bid, 8);
msg.writeInt32BE(bidSize, 16);
msg.writeDoubleBE(ask, 20);
msg.writeInt32BE(askSize, 28);
this.socket.send(msg, 0, msg.length, this.L1_PORT, this.MULTICAST_ADDR);
}
publishTrade(symbol: string, price: number, qty: number, aggSide: 'B' | 'S'): void {
const msg = Buffer.allocUnsafe(24);
msg.write(symbol.padEnd(8), 0, 'ascii');
msg.writeDoubleBE(price, 8);
msg.writeInt32BE(qty, 16);
msg.write(aggSide, 20, 'ascii');
this.socket.send(msg, 0, msg.length, 9002, this.MULTICAST_ADDR);
}
}
Interview Preparation
Q: Why is the matching engine single-threaded?
The matching engine must produce deterministic, reproducible results. With multiple threads touching the order book, you'd need locks — and lock contention at microsecond scale destroys latency. A single-threaded engine processes each order fully before the next, producing an unambiguous sequence of trades. The sequencer ensures orders arrive in a defined order, so the engine just processes them FIFO. This also makes crash recovery simple: replay the WAL in sequence and you get exact engine state.
Q: How do you achieve microsecond latency?
Several techniques compound: (1) Kernel bypass networking with DPDK or RDMA — skip kernel TCP stack, read directly from NIC in user space. (2) Busy polling instead of interrupt-driven I/O — the engine spins on a queue, paying CPU but eliminating interrupt latency. (3) CPU affinity — pin the matching engine thread to a dedicated core, disable hyperthreading, disable OS preemption on that core. (4) Off-heap memory in Java — avoid GC pauses by allocating order objects in ByteBuffer/Unsafe outside the heap. (5) Pre-allocated object pools — no allocation on hot path.
Q: How does the exchange guarantee no lost orders on crash?
The Sequencer writes every order to a Write-Ahead Log (WAL) before the matching engine processes it. The WAL is append-only and fsync'd to durable storage. On restart, replay the WAL from the last known good sequence number — the matching engine rebuilds its in-memory order book exactly. The system also takes periodic snapshots (order book state at sequence N) so recovery only needs to replay from snapshot forward, not from the beginning of time.
Q: How does the exchange handle a "circuit breaker" (market halt)?
A circuit breaker triggers when price moves > X% within Y seconds. The sequencer stops accepting new orders for the affected symbol — it drains in-flight orders, then switches the symbol's state to HALTED. All open orders are preserved (not cancelled). After the halt period (typically 5 minutes), a "call auction" opens: collect all orders, find the price that maximizes trade volume, execute that batch simultaneously. This absorbs the volatility spike without a chaotic cascade.
Learning Resources
- NYSE Market Data Feeds — how real exchanges publish data
- LMAX Disruptor — lock-free inter-thread ring buffer, used in trading
- Aeron Messaging — ultra-low latency IPC and network messaging
- Martin Thompson — Mechanical Sympathy — CPU-cache-aware programming
- Trading Systems and Methods — Perry Kaufman — market microstructure fundamentals