How a Matching Engine Works

Every model of markets you will ever read assumes that when a buy meets a sell, a trade occurs. The matching engine is the piece of software that makes that assumption true. It is worth knowing exactly, because almost every microstructure oddity — queue jumping, flickering quotes, why your cancel arrived "too late" — is a consequence of how this one program is built.

Strip away the plumbing and it is a loop:

Take the next message in sequence. Apply it to the in-memory book. Emit what happened.

The two words carrying the weight are next and sequence. The engine imposes a single, total order on every message from every participant, and from that moment the outcome is fully determined. Two firms sending a cancel and an aggressive order at the same microsecond do not "race" inside the engine; they raced before it, at the gateway, and the sequencer has already decided who won.

An actual session, message by message

Start with this book. Two orders rest at the best bid: B1 (500 shares, posted 09:30:00.100) and B2 (300, posted at .200), so B1 has time priority.

Side	Price	Resting
Ask	10.02	A2: 900
Ask	10.01	A1: 400
Bid	10.00	B1: 500, then B2: 300
Bid	9.99	B3: 1,000

Now four messages arrive.

seq 1041 — new sell limit, 600 @ 10.00, IOC. It crosses. Price–time priority allocates from the front: 500 to B1, then 100 to B2. The engine emits two fills, both printed at 10.00 — the resting order always sets the price. Book after: bid 10.00 now shows 200 (B2's remainder).

seq 1042 — cancel B2. Accepted, the 10.00 level empties, and the best bid drops to 9.99. The quoted spread has just gone from 1 tick to 2, from a message that traded nothing.

seq 1043 — new buy limit, 300 @ 10.01, post-only. At 10.01 it would immediately take A1. Post-only means "add liquidity or don't exist", so the engine rejects it rather than crossing. No book change.

seq 1044 — new buy market, 1,200 shares. It walks the ask: 400 from A1 at 10.01, then 800 from A2 at 10.02. Volume-weighted fill $= (400 \times 10.01 + 800 \times 10.02)/1200 = 10.0167$. Book after: ask 10.02 shows 100, best bid still 9.99.

Everyone on the multicast feed sees these four outcomes in exactly this order, and a replay of the same four messages will always produce the same book.

What is inside the core

The data structures are chosen so the hot path never allocates and never searches:

• Price levels in an array or map indexed by ticks, so finding a level is arithmetic, not a search.
• Each level a FIFO list of orders — usually an intrusive doubly-linked list, so an order removes itself in $O(1)$.
• A hash map from order ID to node, so a cancel is a lookup plus an unlink, with no scan of the book.
• Best bid and best ask cached, updated only when a level empties or a new one is created.

Add, cancel, and match at the touch are all constant time, which is how venues sustain hundreds of thousands to millions of messages per second with wire-to-wire latencies in the tens of microseconds.

The core also owns behaviour people wrongly assume is the exchange's "rules" in the abstract: time in force (IOC, FOK, day, GTC), self-trade prevention (cancel the resting order, the incoming one, or both, when the same firm would trade with itself), price bands that reject orders far from the reference price, and the matching algorithm itself — FIFO on most equity venues, pro-rata or hybrid on many futures and options products, where allocation is proportional to displayed size and the incentive flips from arriving early to showing size.

In interviews

Two questions recur. First, "design a limit order book" — answer with the structures above and justify each by the operation it makes $O(1)$. Second, "why are matching engines single-threaded?" — because determinism is worth more than parallelism: a replayable sequence gives you audit, gap recovery, warm-standby failover, and identical answers on the primary and the backup. Being able to state that a resting order sets the trade price, and that one aggressive order can produce many fills, marks you as someone who has actually looked at a tape. See Order Book Data Structure for the implementation and Latency & High-Frequency Trading for the race that happens before the sequencer.