Stock Exchange Matching Engine Architecture, in depth

What the engine must guarantee

The core contract in most equity markets is price-time priority. A buy at a higher price is served before a buy at a lower price; among orders at the same price, the earliest arrival is served first. 'Earliest' must have exactly one meaning, so the engine needs a single total order of events per instrument. Some derivatives markets allocate pro rata within a price level instead of first-in-first-out, but they need the same single sequence.

Three further guarantees follow. Determinism: the same input sequence produces the same trades, so the engine can be replayed for audit, recovery and replica checks. Durability before acknowledgement: no participant may receive a fill the exchange could later forget. Consistency: the private report and public data derived from one event describe the same state.

Architecture end to end

Gateways terminate participant sessions, typically FIX for general clients and a compact binary protocol for latency-sensitive ones (Nasdaq's OUCH is a well-known example). They authenticate, validate, throttle message rates and translate to the internal format. Pre-trade risk checks (credit limits, maximum size, price collars) run before the book, because a matched trade cannot be quietly taken back.

The sequencer is the heart of correctness. It assigns each inbound message a monotonically increasing sequence number and a timestamp, appends it to a journal, makes it available to replicas, and only then releases it to the matching core, which consumes the stream strictly in order. Outputs are sequenced too: private reports return through the gateway to the order's owner, public updates go to the market data publisher, trades go to clearing and to drop-copy feeds that firms use for independent reconciliation.

Instruments are partitioned across matching cores, each owning its symbols on one thread. Symbols never interact, so they are the natural unit of parallelism, and one owner thread keeps each book lock-free.

The order book data structure

A book has two sides; each side is a set of price levels; each level is a FIFO queue of resting orders. Four operations must be fast: find the best price, append to the tail of a level, remove from the head as orders fill, and cancel an arbitrary order by ID. The standard layout is:

• Integer prices in ticks. Never floating point. Where the plausible range is bounded, which price bands ensure, an array indexed by tick offset gives constant-time access to any level; a sorted tree or skip list handles unbounded ranges in logarithmic time.
• An intrusive doubly linked list per level. Each order carries prev and next pointers, so removing a cancelled order from the middle of a queue needs no search.
• A hash map from order ID to order. Cancels and modifies arrive by ID and the map yields the node directly.
• Cached best bid and best ask. When the best level empties, scan to the next non-empty level; liquidity clusters near the touch, so the scan is short.
• Preallocated order objects. Engines in garbage-collected languages pool orders and avoid allocation on the hot path, so collector pauses do not land mid-match.

Modifies need a rule: reducing quantity normally keeps time priority, while increasing quantity or changing price is a cancel-and-replace that loses it, otherwise participants could jump the queue.

The matching loop

An incoming order is marketable when a buy is priced at or above the best ask, or a sell at or below the best bid. The incoming order is the aggressor: it trades against resting orders at the resting price, best level first and oldest order first, until it is filled or no longer marketable. Whatever remains rests in the book if its type allows.

def crosses(order, best_px):
    if best_px is None:
        return False
    if order.type == MARKET:
        return True
    return order.price >= best_px if order.side == BUY else order.price <= best_px

def submit(book, order, seq):
    opp = book.opposite(order.side)
    if order.post_only and crosses(order, opp.best_price()):
        return [Reject(seq, order.id, "post-only would take liquidity")]
    # fillable_qty skips same-account orders that STP would cancel
    if order.tif == FOK and opp.fillable_qty(order) < order.qty:
        return [Cancel(seq, order.id, "fill-or-kill not fully fillable")]

    events = []
    while order.remaining > 0 and crosses(order, opp.best_price()):
        level = opp.best_level()
        resting = level.head()
        if resting.account == order.account:     # self-trade prevention:
            events.append(book.cancel(resting, seq, "STP"))   # cancel-resting mode
            continue
        qty = min(order.remaining, resting.remaining)
        events.append(Trade(seq, level.price, qty, order.id, resting.id))
        order.remaining -= qty
        resting.remaining -= qty
        if resting.remaining == 0:
            book.remove(resting)                  # unlink, drop from ID map,
                                                  # drop level if now empty
    if order.remaining > 0:
        if order.type == LIMIT and order.tif in (DAY, GTC):
            book.rest(order)                      # tail of its level
            events.append(Accepted(seq, order.id, order.remaining))
        else:                                     # IOC and market never rest
            events.append(Cancel(seq, order.id, "unfilled remainder"))
    return events

Trades print at the resting order's price, which is how a buy limited at 100.60 fills at 100.50. The fill-or-kill check walks the book before changing anything, so an unfillable order leaves no trace. And the function returns events instead of touching the outside world, so the same code drives the live engine, the replica and the replay tool.

Order types and edge cases

Self-trade prevention is a policy rather than an order type: when two orders from the same account or firm would match, the venue cancels the resting order, the incoming order or both, according to a flag the participant chose. Stop triggers need particular care because they originate inside the engine. They must be enqueued as new sequenced events after the trade that fired them, never matched recursively inside the same step, or a replay will diverge from what happened live.

Determinism and the sequencer

A matching core is a deterministic state machine: state plus the next input yields the next state plus outputs. That is what allows lockstep replicas, crash recovery by journal replay, and proof to a regulator of why each trade happened. It is easy to break:

• Reading the wall clock inside the core. Use the timestamp the sequencer stamped on the input instead.
• Iterating a hash map whose order depends on memory addresses or a random seed. Iterate the price-ordered structures.
• Multiple threads touching one book. One owner thread per partition removes both locks and interleavings.
• Floating-point prices. Two builds can round differently; integer ticks cannot.
• Timers. Order expiry, auctions and trading-phase changes become inputs injected into the sequenced stream, not callbacks.

This is event sourcing at its most demanding: the journal of inputs is the source of truth and the book is a cache derived from it. Periodic snapshots of the book let recovery start from a recent point instead of the morning's first message.

Replication and failover

An engine cannot run a consensus round per order and keep microsecond latency, so venues typically replicate the input stream rather than the state. The sequencer journals each message and sends it to one or more backups, which run the same code over the same stream and hold an identical book. How much acknowledgement the primary waits for before releasing a message to matching is the central durability decision: waiting for a backup to confirm receipt costs a network round trip, but it means no acknowledged fill is lost if the primary dies.

Failover must be decided outside the pair, by a cluster manager or operator, because two engines that both believe they are primary would produce two histories. The promoted backup resumes from its last processed sequence number, and participants use session sequence numbers to request reports they missed. Diffing the primary's and backup's outputs event by event is a strong continuous test: any divergence means non-determinism has crept in.

Market data distribution

Public market data is derived from the same sequenced output. The usual shape is an incremental feed of add, modify, delete and trade messages, each carrying a sequence number, sent over UDP multicast so every subscriber receives it at the same time, plus a snapshot service for recovery. Nasdaq's ITCH is a well-known order-by-order feed of this kind. A subscriber that sees a gap in sequence numbers requests retransmission, or rebuilds from a snapshot and replays the increments after the snapshot's sequence number.

Multicast removes per-client fan-out from the publisher. Private execution reports travel over the participant's own session and must not trail the public update for the same event, so an owner never learns of its own fill from the public feed first.

Worked example: one aggressive buy

One instrument, prices in cents. The asks hold two levels: 10050 with order A for 300 shares (arrived first) then B for 200, and 10060 with C for 500. The best bid is 10040. A buy limit for 700 shares at 10060 arrives and is sequenced as event 9001.

1. Level 10050, head A: trade 300 at 10050. A is filled and unlinked. The incoming order has 400 left.
2. Level 10050, head B: trade 200 at 10050. B is filled, the level empties and is removed, and the best ask becomes 10060. 200 left.
3. 10060 still crosses the limit. Head C: trade 200 at 10060. C keeps its place at the head with 300 left. The incoming order is filled and never rests.
4. Outputs, all tagged 9001: three trades; execution reports to the buyer and to the owners of A, B and C; public messages deleting A and B, reducing C to 300 and printing three trades; three trade records to clearing.

Had the order been fill-or-kill for 1,100 shares, the feasibility check would find only 1,000 shares at or below 10060 and cancel it with no trades. Had it been post-only, it would have been rejected at once, since it crosses 10050.

Capacity arithmetic

Size from message rates, not trade rates: most orders are cancelled without trading. Suppose a partition must absorb bursts of 200,000 messages per second. One thread then has 5 microseconds per message for decode, match and encode. A book operation of a few hundred nanoseconds fits; a system call or lock per message does not, which is why engines batch I/O.

At 100 bytes per journalled input, that burst writes 20 MB per second per partition: easy for local NVMe, material across a replication link. A million resting orders at 128 bytes each is 128 MB, fine for RAM but not cache, so keeping the levels near the touch hot matters more than total size. These figures are illustrative arithmetic, not measurements of any venue.

Failure modes and controls

• Runaway algorithm. A participant's bug floods orders or sweeps the book. Controls: per-session throttles, maximum size and notional, price collars, a kill switch that cancels all of a firm's orders, and market-wide circuit breakers that halt trading.
• Replica divergence. Non-deterministic code builds a different book on the backup, so failover would rewrite history. Diff outputs continuously and halt the partition rather than run a divergent pair.
• Market data gaps. Multicast packets are lost. Subscribers must detect gaps by sequence number and recover by snapshot plus replay, never silently continue.
• Slow consumer. A drop-copy or clearing consumer falls behind. Decouple outputs through a persisted stream so the core never blocks on any consumer.
• Clock trouble. Regulatory timestamps need synchronised clocks, commonly via PTP. A clock step must never reorder events: order comes from the sequence number, and the timestamp is metadata.

Trade-offs

A single-threaded, partitioned core trades elasticity for determinism and latency: one hot book cannot be spread across machines. Replicating inputs instead of state is fast and simple but demands strict determinism everywhere. Waiting for backup acknowledgement before matching costs a round trip but removes the chance of losing an acknowledged fill. Tick-indexed arrays are fastest but waste memory over wide price ranges; trees are compact but slower. Price-time priority rewards speed and so fuels a latency race; pro-rata allocation and periodic batch auctions reduce that pressure at the cost of complexity. The broker that sits on the other side of these gateways is a different system with different constraints, covered in retail trading architecture.

What to do next

1. Write the book with integer ticks, intrusive FIFO lists and an ID map, and unit-test price-time priority with scripted order sequences.
2. Implement limit, market, IOC, FOK and post-only, keeping feasibility checks separate from mutation.
3. Make the core a pure function from sequenced events to output events; ban wall-clock reads and hash-order iteration inside it.
4. Journal inputs before matching and build a replay tool that reproduces a day's outputs byte for byte.
5. Run a shadow replica on the same stream and diff its outputs continuously.
6. Add throttles, collars and a kill switch before any external participant connects.
7. Study the Disruptor ring buffer for the inter-stage pipeline, and event-driven order design for order lifecycle state machines.