Matching Engine Architecture

Prerequisite: Distributed Systems, Event-Driven Architecture

Your exchange processed 14 million orders yesterday without incident. Today a market maker submits a batch of 50,000 cancel-replace messages in 200 milliseconds. Your matching engine, which parallelizes order processing across 8 threads for throughput, produces a nondeterministic fill sequence. Two traders submit identical limit orders at the same price within the same microsecond. Depending on which thread wins the race, trader A gets filled first on one replay and trader B gets filled first on another. Your audit log says one thing. Your risk system, replaying the same sequence on a different core, says another. The exchange has lost determinism, and with it, the ability to prove that price-time priority was honored.

The matching engine is the only component in a trading system where single-threaded execution is not a performance limitation — it is a correctness requirement.

Why Single-Threaded

A matching engine’s job is to accept orders, apply matching rules, and emit fills. The order matters. Price-time priority — the foundational fairness guarantee of most exchanges — requires that orders at the same price are filled in the order they arrived. If two threads process orders concurrently, arrival order becomes ambiguous. The moment you parallelize, you introduce a race condition into the fairness model.

LMAX Exchange demonstrated this with their Disruptor architecture: a single-threaded business logic processor handling 6 million orders per second on commodity hardware. No locks, no contention, no context switches. The entire order book lives in L1/L2 cache. The single thread processes each message in sequence, and the sequence is the source of truth.

Architecture	Throughput	Deterministic	Audit-safe
Multi-threaded with locks	Variable (lock contention)	No	No
Sharded by symbol	N × single-thread	Per-shard yes	Yes (per shard)
Single-threaded event loop	6M+ orders/sec	Yes	Yes

The sharded model — one thread per symbol or symbol group — is a common compromise. Each shard is internally deterministic. Cross-symbol operations (portfolio margin, cross-asset spreads) require coordination between shards, which reintroduces ordering complexity at the boundary.

The Event Loop

The matching engine runs a tight loop: read a message from the input queue, process it, write the results to the output queue. No I/O, no system calls, no allocations in the hot path.

loop {
    message = input_queue.read()      // memory-mapped ring buffer
    match message.type {
        NewOrder    => process_new_order(message),
        Cancel      => process_cancel(message),
        Replace     => process_replace(message),
    }
    output_queue.write(results)       // fills, acks, rejects
    sequence_number += 1
}

The input queue is a pre-allocated ring buffer in shared memory. The gateway process writes inbound messages to the ring buffer. The matching engine reads from it. No system call, no kernel transition — both processes map the same memory region. LMAX’s Disruptor uses this pattern with mechanical sympathy: the ring buffer is sized to fit in L3 cache, and entries are padded to cache-line boundaries (64 bytes) to prevent false sharing.

The output side mirrors the input. Fills, acknowledgments, and rejects are written to an output ring buffer. Downstream consumers — risk engines, market data disseminators, drop-copy feeds — read from it independently.

Any system call in the hot path — malloc, write, futex — adds 1–10 microseconds of latency. At 6 million messages per second, each message has a budget of 167 nanoseconds. A single malloc can consume the entire budget.

Order Book Data Structures

The order book is a sorted collection of price levels, each containing a queue of orders at that price. The two critical operations are insertion (new order at a price) and matching (walk the opposite side of the book, filling orders in price-time priority).

Price levels are typically stored in a red-black tree or a sorted array. A red-black tree provides O(log n) insertion and lookup, where n is the number of distinct price levels. For liquid markets with 50–200 active price levels, a red-black tree lookup completes in 6–8 comparisons. A sorted array with binary search has similar asymptotic cost but better cache locality — the entire price ladder fits in a few cache lines.

Orders within a price level are stored in a FIFO queue — a doubly-linked list for O(1) insertion at the tail and O(1) removal of any node (cancellation). The order’s node is indexed by order ID in a hash map for O(1) cancel lookup.

struct OrderBook {
    bids: BTreeMap<Price, OrderQueue>,    // descending by price
    asks: BTreeMap<Price, OrderQueue>,    // ascending by price
    order_index: HashMap<OrderId, *mut OrderNode>,
}

struct OrderQueue {
    head: *mut OrderNode,
    tail: *mut OrderNode,
    total_quantity: u64,
}

A cancel operation looks up the order by ID in the hash map (O(1)), unlinks it from the doubly-linked list (O(1)), and updates the queue’s total quantity. No tree traversal, no search. On CME’s Globex platform, cancel rates reach 95% of total message volume during active trading — the cancel path must be as fast as the insert path.

Operation	Complexity	Typical latency
New order (no match)	O(log p) tree insert + O(1) queue append	200–500ns
New order (match)	O(log p) lookup + O(k) fills	300ns–2µs
Cancel	O(1) hash lookup + O(1) unlink	100–300ns
Replace	O(1) cancel + O(log p) insert	300–800ns

Where p is the number of price levels and k is the number of fills generated.

Matching Semantics

Price-time priority is the most common matching algorithm: the best-priced order fills first, and among orders at the same price, the one that arrived first fills first. The matching engine walks the resting book in price priority, consuming liquidity at each level until the aggressing order is fully filled or the book is exhausted.

fn match_order(book: &mut OrderBook, order: &mut Order) -> Vec<Fill> {
    let mut fills = Vec::new();
    let opposite_side = match order.side {
        Buy  => &mut book.asks,  // buyer matches against asks
        Sell => &mut book.bids,  // seller matches against bids
    };

    while order.remaining > 0 {
        let best_level = match opposite_side.first_entry() {
            Some(level) => level,
            None => break,  // book exhausted
        };
        if !order.price_crosses(best_level.key()) {
            break;  // no match at this price
        }
        // fill against resting orders in FIFO sequence
        while order.remaining > 0 && !best_level.is_empty() {
            let resting = best_level.front();
            let fill_qty = min(order.remaining, resting.remaining);
            fills.push(Fill { aggressor: order.id, resting: resting.id,
                              price: *best_level.key(), quantity: fill_qty });
            order.remaining -= fill_qty;
            resting.remaining -= fill_qty;
            if resting.remaining == 0 { best_level.pop_front(); }
        }
        if best_level.is_empty() { opposite_side.pop_first(); }
    }
    fills
}

Pro-rata matching — used for some futures contracts — allocates fills proportionally to order size rather than arrival time. This changes the data structure requirements: the engine must iterate all orders at the best price level and allocate based on each order’s share of total quantity. Pro-rata incentivizes large resting orders over fast ones, which changes market microstructure.

Algorithm	Priority	Incentivizes	Used by
Price-time (FIFO)	Price, then arrival time	Speed	Most equity/crypto exchanges
Pro-rata	Price, then order size	Liquidity provision	CME Eurodollar, some options
Price-time with allocation	Price, time, then pro-rata for remainder	Both	ICE, some hybrid venues

Event Sourcing and the Sequence

Every message into the matching engine and every result out of it receives a monotonically increasing sequence number. The sequence is the canonical ordering. The order book at any point in time is a deterministic function of the message sequence from the beginning.

This is event sourcing applied to the most latency-sensitive system in finance. The event log is the source of truth. The in-memory order book is a projection — a materialized view that can be rebuilt by replaying the log from any checkpoint.

The sequence enables three critical capabilities:

Deterministic replay. Feed the same input sequence to a fresh matching engine instance and it produces identical output. This is how exchanges validate their audit trail, test new matching logic, and prove to regulators that price-time priority was honored for every fill.

Gap detection. Every consumer of the output stream checks for sequence gaps. A missing sequence number means a missed message. Market data feeds, risk engines, and drop-copy systems all validate sequence continuity. A gap triggers an immediate resynchronization — the consumer requests a snapshot of the current book state plus the output stream from the gap forward.

Consistent snapshots. A snapshot is the order book state at a specific sequence number. Snapshot S plus all messages after sequence S reconstructs the current book. Snapshots are taken periodically (every 60 seconds or every N messages) and stored for recovery.

Deterministic replay is not optional for a regulated exchange. MiFID II (EU), Reg SCI (US), and similar frameworks require that exchanges can reconstruct the exact state of the order book at any point in time, including every intermediate state between fills.

Failover and Recovery

The matching engine runs as a hot-standby pair. The primary processes messages and writes to the output stream. The standby replays the same input stream, maintaining an identical in-memory order book, but does not write to the output stream. If the primary fails, the standby promotes itself and begins writing output.

Recovery time is bounded by the gap between the last snapshot and the current sequence number. With snapshots every 60 seconds and a throughput of 100,000 messages per second, the standby replays at most 6 million messages on failover. At replay speeds of 10–50 million messages per second (no I/O, no network, pure computation), recovery completes in 120–600 milliseconds.

Snapshot interval	Max replay on failover	Recovery time (at 20M msg/sec replay)
10 seconds	1M messages	50ms
60 seconds	6M messages	300ms
5 minutes	30M messages	1.5 seconds

The standby validates its state against the primary’s output. If the standby produces a different fill for the same input sequence, it halts and raises an alert — the divergence indicates a bug in the matching logic or a corrupted input stream.

Some exchanges run a third instance in a different data center for disaster recovery. This instance replays asynchronously with a deliberate lag (seconds to minutes), providing a recovery point that survives a full site failure.

The Latency Budget

Matching engine latency is measured at three points: wire-to-wire (network ingress to network egress), gate-to-gate (gateway ingress to gateway egress), and engine-only (message read to result write). The engine-only number is what the matching logic controls.

Exchange tier	Engine-only latency	Wire-to-wire latency
HFT-focused equity (IEX, MEMX)	1–10µs	20–50µs
Major futures (CME Globex)	1–5µs	10–30µs
Crypto (Binance, Coinbase)	5–50µs	100µs–1ms
Startup exchange	50–500µs	1–10ms

The gap between engine-only and wire-to-wire is network serialization, gateway processing, and kernel overhead. Kernel bypass (DPDK, Solarflare OpenOnload) eliminates the kernel’s network stack, saving 5–15 microseconds per message. FPGA-based gateways move serialization and basic validation into hardware, saving another 2–5 microseconds.

Measurement discipline matters more than raw speed. A matching engine that reports median latency of 5 microseconds but has a p99.9 of 500 microseconds has a jitter problem. The outlier — caused by a garbage collection pause, a cache miss on a cold price level, or an OS interrupt — is what market makers price into their quotes. Reducing jitter (tightening the gap between median and tail) often matters more than reducing median latency.

The standard measurement tool is a hardware timestamping NIC (Solarflare, Mellanox) that stamps packets at the network interface with nanosecond precision. Software timestamps using clock_gettime(CLOCK_MONOTONIC) have 25–100 nanoseconds of jitter from the system call itself — acceptable for microsecond-resolution measurement but not for nanosecond-resolution analysis of the matching engine’s inner loop.