Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Design Case Studies

System Design HLD-19.22

Order matching engine design: how a stock exchange matches orders

How a stock exchange order matching engine works: the order book data structure, price-time priority, order types, and why engines run single-threaded.

Advanced 22 min Last reviewed

What is an order matching engine

An order matching engine is the heart of a stock exchange: it takes buy and sell orders, decides which ones trade with each other, at what price and in what order, and tells everyone what happened. This lesson designs one end to end, from the order book data structure to the architecture around it.

An exchange is a meeting place for buyers and sellers. A broker sends "buy 300 shares at up to 100.45", and if someone is already offering at that price or better, a trade happens; otherwise the order waits in the order book until someone does. Every participant must see the same book, the same trades in the same order, and the rules must be applied with perfect fairness: the best price first, and among equal prices, whoever came first.

Most systems in this module scale by spreading work across many machines. An exchange does the opposite at its core. Fairness needs one total order of events per instrument, and the latency budget is microseconds, where a network hop to a database or a lock between threads would cost more than the matching itself. The design puts a single-threaded engine in memory behind a sequencer, and gets reliability by replaying the same ordered input on replicas.

Requirements

Functional

  • Accept new orders (limit and market, with day, IOC or FOK time in force), cancels and modifications from brokers.
  • Match orders per symbol by price-time priority; report fills to both sides.
  • Publish market data: every change to the book and every trade.
  • Pre-trade risk checks per broker (limits on order size and exposure).

Non-functional

  • Latency: tens of microseconds from order arrival to acknowledgement inside the exchange, with low jitter.
  • Throughput: 5,000 symbols, 500,000 messages a second at the open and close.
  • Determinism and fairness: identical input order gives identical results; no participant can jump the queue.
  • Durability: no acknowledged order or trade is ever lost, and the day can be replayed exactly.

Out of scope

  • Clearing and settlement (moving money and shares after the trade), and the brokers' own systems.

Estimates

  • Messages: 500,000 per second at peak across all symbols. Activity is skewed: the busiest symbol might see 20,000 a second.
  • Engine time: if handling one message in memory takes about 1 microsecond, one thread can process about a million messages a second. A handful of threads, each owning a group of symbols, covers the whole market with room to spare.
  • Journal: at 100 bytes per message, 500,000 a second is 50 MB/s. A 6.5-hour session is 23,400 seconds, so at most about 1.2 TB a day if the peak lasted all day.
  • Latency budget: one round trip inside a data center is about 500 microseconds on ordinary networks ( Latency numbers every engineer should know ). A database call per order would blow the whole budget many times over, which is why state lives in the engine's memory.

API

Broker -> gateway (binary protocol over TCP, one session per broker)
  NewOrder    { client_order_id, symbol, side, qty, price, type: limit | market, tif: day | ioc | fok }
  Cancel      { client_order_id }
Gateway -> broker
  Ack         { client_order_id, exchange_order_id }
  Fill        { exchange_order_id, qty, price, trade_id }
  Reject      { client_order_id, reason }
Market data (UDP multicast, sequenced)
  BookUpdate  { seq, symbol, side, price, new_qty }
  Trade       { seq, symbol, qty, price }

Text formats such as JSON over HTTP are too slow to parse at this latency budget, so the design uses compact, fixed-layout binary messages.

Data model

  • Order book (in the engine's memory, per symbol): bids sorted by price descending, asks by price ascending, each price level a FIFO queue of resting orders.
  • Journal (append-only, replicated): every sequenced input message, in order. The book at any moment is a pure function of the journal up to that point ( Event-driven architecture and event sourcing ).
  • Snapshots: periodic dumps of every book, so recovery replays only the journal after the snapshot.
  • Trades and order history (written asynchronously to databases for reporting, surveillance and clearing).

High-level design

Exchange: order, match and publish paths Order path: brokers connect to gateways, which authenticate them, run pre-trade risk checks and forward orders to the sequencer, which stamps each with a global sequence number and writes it to a replicated journal. Match path: the single-threaded matching engine consumes sequenced messages in order, updates the in-memory order book, and emits acknowledgements and fills back through the gateways; a standby engine consumes the same journal and holds an identical book. Publish path: every book change and trade goes to the market data publisher, which multicasts sequenced updates to subscribers, and asynchronously to databases for reporting. orders append in order replay acks, fills book changes Brokers Gateways auth, risk checks Sequencer global seq number Journal replicated Matching engine 1 thread, in memory Standby engine same input, same book Market data multicast Subscribers Reporting DBs async Figure 1. Everything funnels through one ordering point. The sequencer fixes the order, the engine applies it deterministically in memory, and replicas that read the same journal reach the same state.
  1. Order path Brokers send orders to gateways, which authenticate, apply risk checks and forward to the sequencer. The sequencer stamps every message with the next global sequence number and appends it to a replicated journal.
  2. Match path The matching engine reads sequenced messages strictly in order and updates the in-memory book on one thread, sending acknowledgements and fills back through the gateways. A standby engine replays the same journal and keeps an identical book.
  3. Publish path Every book change and trade is published as sequenced market data over multicast, so all subscribers get the same stream at the same time. Reporting databases are updated asynchronously, off the critical path.

Deep dives

Eight parts of the design deserve a closer look: the matching rule, the order types, the order book, the threading model, durability, market data, latency, and the build order.

Price-time priority matching

For each symbol the engine keeps resting buy orders (bids) and sell orders (asks). An incoming buy matches against the lowest asks while the ask price is at or below its limit; at the same price, the oldest resting order fills first. Trades happen at the resting order's price. Whatever is left of the incoming order rests in the book. Here is a book processing six orders in sequence order:

book.pyruns with python3 (standard library)
# A limit order book with price-time priority, processed by one thread in
# sequence-number order. Best price first; at the same price, oldest first.
import heapq

bids, asks = [], []   # heaps: bids by (-price, seq), asks by (price, seq)
trades = []

def submit(seq, side, qty, price):
    book, other = (bids, asks) if side == "buy" else (asks, bids)
    while qty and other:
        key, oseq, oqty, oprice = other[0]
        crosses = price >= oprice if side == "buy" else price <= oprice
        if not crosses:
            break
        fill = min(qty, oqty)
        trades.append((seq, oseq, fill, oprice))  # at the resting price
        qty -= fill
        if fill == oqty:
            heapq.heappop(other)
        else:
            other[0] = (key, oseq, oqty - fill, oprice)  # key unchanged
    if qty:                                         # rest the remainder
        key = -price if side == "buy" else price
        heapq.heappush(book, (key, seq, qty, price))

orders = [  # (sequence number, side, quantity, limit price in cents)
    (1, "sell", 100, 10_050), (2, "sell", 200, 10_040),
    (3, "buy", 150, 10_000), (4, "sell", 50, 10_040),
    (5, "buy", 300, 10_045), (6, "buy", 100, 10_060),
]
for o in orders:
    submit(*o)
for taker, maker, qty, px in trades:
    print(f"order {taker} filled {qty:3} against resting order {maker} "
          f"at {px / 100:.2f}")
best_bid = (bids[0][3] / 100, bids[0][2]) if bids else None
best_ask = (asks[0][3] / 100, asks[0][2]) if asks else None
print("best bid (price, qty):", best_bid, " best ask:", best_ask)

Output

order 5 filled 200 against resting order 2 at 100.40
order 5 filled  50 against resting order 4 at 100.40
order 6 filled 100 against resting order 1 at 100.50
best bid (price, qty): (100.45, 50)  best ask: None

Order 5 (buy 300 up to 100.45) took 200 from order 2 and then 50 from order 4, both at 100.40: same price, so order 2 went first because it arrived first. The 100.50 ask was above its limit, so the remaining 50 rested as the new best bid. Order 6 crossed the spread and filled at 100.50, the resting order's price.

The whole algorithm for an incoming limit buy fits in a few lines (a sell is the mirror image, matching against the highest bids):

while buy.qty > 0 and the best ask price <= buy.price:
    resting = oldest order at the best ask price
    q = min(buy.qty, resting.qty)
    emit trade(q, at resting.price)
    buy.qty -= q; resting.qty -= q
    if resting.qty == 0: remove it (and its price level if now empty)
if buy.qty > 0: add buy to the tail of its price level on the bid side

A market order runs the same loop with no price limit and never rests; whatever cannot fill is cancelled.

Order types: limit, market, cancel, IOC and FOK

Every order type is a small variation on the same matching loop. What changes is the price limit, and what happens to the part that does not fill straight away (its time in force):

OrderPrice limitUnfilled remainder
Limit (day)yesrests in the book at its price until filled, cancelled or the session ends
Marketnonecancelled; a market order never rests
IOC (immediate or cancel)yescancelled straight away instead of resting
FOK (fill or kill)yesthe whole order fills at once, or none of it does
Cancelnot an orderremoves a resting order: look it up in the id map and unlink it
Modifychanges price or quantityusually keeps time priority only if the quantity goes down (see the build steps below)

In the loop, IOC changes one line: instead of add buy to the tail of its price level, the remainder is cancelled and reported back. FOK needs one extra step before any trade: walk the opposite side of the book, without changing it, and add up the quantity available at acceptable prices. If that total is less than the order's quantity, reject the whole order; otherwise run the normal loop, which is now guaranteed to fill it completely. Because the engine is single-threaded, nothing can change the book between the check and the fill.

The exact rules for each type, such as whether an unfilled market order is cancelled or converted, are set in each exchange's rulebook.

Order book data structure

The heaps above keep the example short. A production order book is usually three structures per symbol:

Order book (one per symbol)
  bids:   price level -> FIFO queue of resting orders   (best = highest price)
  asks:   price level -> FIFO queue of resting orders   (best = lowest price)
  orders: order id    -> that order's node in its queue (for cancels)
  • Prices are integers, counted in ticks (100.45 is stored as 10045 when the tick is 0.01). Floating point would make equal prices compare unequal and break determinism.
  • Price levels live in a sorted map (a balanced tree), or, because prices sit on a fixed tick grid, in an array indexed by ticks from a reference price. The best bid and best ask are cached, so the common case never searches.
  • Each level's queue is a doubly linked list. Matching takes from the head; a new order joins the tail; a cancel looks the order up in the id map and unlinks it in constant time, without scanning the level.

With these, adding, cancelling and matching against the best price are all constant or near-constant time.

Single-threaded vs parallel matching engines

Matching is inherently sequential per symbol: whether order 6 fills depends on everything before it. With many threads, you would need locks around the book, and lock contention and thread scheduling add microseconds of unpredictable delay. A single thread that owns a symbol's book and processes messages from an in-memory queue has no locks, keeps the data hot in the CPU cache, and is fully deterministic.

The sequencer creates the one order. Every input gets the next sequence number before the engine sees it, and the sequenced stream is written to the journal. Gateways may receive orders in parallel, but once sequenced, there is exactly one history. Fairness disputes become simple: the sequence number is the answer.

To scale across symbols, run several engine threads, each owning a group of symbols, all fed from the sequenced stream. No order ever needs two symbols' books, so the groups never coordinate.

So the answer to "single-threaded or parallel?" is both, at different levels:

  • Within one order book: one thread. If two threads matched against the same book, the order of events would be decided by whichever thread won a lock, which changes from run to run. A replica replaying the same input could then reach a different book, and fairness could no longer be proven from the sequence numbers.
  • Across books: parallel. Symbols are partitioned across engine threads or machines, like shards ( Partitioning and sharding ).
  • Around the engine: parallel. Decoding messages, risk checks, journaling, replication and encoding market data are independent per message, so they run on other threads and cores, and the matching thread only does matching.

LMAX, a retail trading venue, made this design well known. Its core, described in Martin Fowler's article on the LMAX architecture, is a business logic processor that runs on a single thread, entirely in memory, using event sourcing, and handles about 6 million orders a second. Unmarshalling, journaling and replication of input happen concurrently around it, connected by the Disruptor, a ring buffer that passes messages between threads without locks (the LMAX Disruptor paper). The lesson from LMAX is that one thread with no locks and data hot in the CPU cache usually beats many threads fighting over shared state.

Reliability through deterministic replay

The engine's state lives in memory, so how is it durable? Because the engine is a deterministic state machine: same journal in, same book and same outputs out ( Consensus: Raft ). That gives three things:

  • Durability: a message is acknowledged only after it is in the replicated journal; after a crash, the book is rebuilt from the latest snapshot plus the journal after it.
  • Hot standby: a second engine on another machine consumes the same sequenced stream and keeps an identical book, ready to take over at once. Its outputs are suppressed until it becomes primary.
  • Audit and testing: any day can be replayed exactly to investigate a dispute or test a new engine version against real traffic.

Determinism has strict rules: no reading the wall clock inside the engine (time comes from the sequencer's stamp), no random numbers, no iteration over unordered hash maps where order affects results.

Market data and low-latency networking

Every book change is market data that thousands of subscribers want simultaneously. Sending a separate TCP stream to each would make some subscribers consistently earlier than others. Exchanges use UDP multicast ( Networking basics: IP, TCP, UDP and ports ): the network fabric copies each packet to all subscribers at once. Each message carries a sequence number; a subscriber that sees a gap requests the missing messages from a retransmission service or rebuilds from a periodic snapshot channel.

Inside the exchange, the low-latency toolbox includes binary protocols, kernel-bypass networking that reads packets directly from the network card, pinning engine threads to dedicated CPU cores, preallocated memory so there are no garbage collection pauses, and, if participants place servers in the exchange's data center, giving every one of them equal network paths, so physical distance does not decide who is first.

Latency: where the microseconds go

For an exchange, latency is about fairness as much as speed. What matters is not only the average time from order in to acknowledgement out, but the tail (the 99th and 99.9th percentile) and the jitter: every participant should see the same small, predictable delay.

Follow one order along the critical path:

  1. Gateway: decode the binary message, check the session and the broker's risk limits.
  2. Sequencer: stamp the next sequence number.
  3. Journal: write the message to the replicated journal. This is usually the most expensive step, because it waits on a disk or a network round trip to a replica, so engines write messages in small batches (group commit) instead of one write per message.
  4. Matching: the cheapest step, about a microsecond in memory, as in the estimates above.
  5. Outputs: the acknowledgement and fills to the brokers, and the book update on the market data feed.

The rest of the toolbox removes sources of delay and jitter on that path: no memory allocation or garbage collection while trading (objects are preallocated and reused), no system calls or locks on the matching thread, threads that busy-poll their input queue instead of sleeping and waking, each hot thread pinned to its own CPU core, and a compact order book (an array of price levels rather than scattered objects) so the data the engine touches stays in the CPU cache.

Building a matching engine step by step

If you want to build a matching engine yourself, as a learning project or as the core of a real venue, this order keeps each step testable:

  1. Define the messages. New order, cancel and modify in; acknowledgement, fill, reject and book update out. Use integer prices in ticks and integer quantities.
  2. Build the order book for one symbol: the price levels, FIFO queues and order id map from the order book data structure section.
  3. Write the matching loop for limit orders. While the incoming order crosses the best opposite price, fill against the head of that level at the resting price, then rest any remainder. Add market orders (take liquidity until filled or the book is empty) and cancels.
  4. Decide the modify rules. Most exchanges keep an order's time priority if only its quantity goes down, and send it to the back of the queue if its price changes or its quantity goes up.
  5. Put a sequencer and a journal in front. Every input gets a sequence number and is written to an append-only log before it is processed, as in Event-driven architecture and event sourcing .
  6. Prove determinism. Replay a recorded journal twice and compare every output byte for byte; then rebuild from a snapshot plus the journal tail and compare again.
  7. Add the outside world: gateways with sessions and risk checks, market data publishing, a hot standby that consumes the same journal, and a separate engine thread per group of symbols.

Steps 1 to 3 fit in a few hundred lines in any language. Almost all of the real effort goes into steps 5 to 7: making the engine durable, fast and identical on every replica.

Try it

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Try this:

  1. Find the round trip within one data center. How many 1-microsecond matching operations fit in one such round trip?
  2. Switch to the human scale. If a main memory read takes 100 seconds, how long is a single database call over the network?
  3. Using the ladder, explain why the order book cannot live in a remote database or cache.

Bottlenecks and failure modes

FailureImpactMitigation
Engine crashTrading halts for its symbolsHot standby on the same journal; snapshot plus replay
Sequencer failureNo new orders acceptedReplicated sequencer with fast failover; journal consensus
Non-determinismStandby book divergesNo wall clock, randomness or unordered iteration in the engine
Market data packet lossSubscriber book wrongSequence numbers, retransmission service, snapshot channel
Runaway broker algorithmFloods the enginePer-session rate limits and risk checks at the gateway
Busy symbolOne thread saturatedRebalance symbol groups; keep per-message work minimal

Trade-offs we made

OptionWins whenLoses when
Single-threaded engine per symbol group (chosen) No locks, deterministic, cache-friendly, microsecond latency One thread's capacity per group; careful symbol placement
Multi-threaded engine with locks Uses more cores per symbol Contention, jitter and non-determinism
In-memory state with a journal (chosen) No database on the critical path; exact replay Recovery depends on snapshots and replay speed
Multicast market data (chosen) Same data to everyone at the same moment UDP needs gap detection and retransmission

Extensions

  • Auctions at the open and close, which match all orders at one clearing price.
  • More order types such as stop orders, iceberg orders and good-till-date time in force.
  • Circuit breakers that halt trading when prices move too far too fast.
  • Surveillance for manipulation, consuming the same journal offline.

How NYSE and Nasdaq-style matching engines are architected

Real exchanges follow the shape of this lesson closely, with a few layers added around the core:

  • Order entry gateways. Brokers connect over FIX or, for the lowest latency, an exchange's own binary protocol. Nasdaq's OUCH is a well-known example: fixed-size binary messages for entering, replacing and cancelling orders. Gateways authenticate the session, check risk limits and throttle runaway clients before anything reaches matching.
  • Many matching engines, each owning a set of symbols. No single process matches the whole market. Symbols are spread across engine instances, each a sequenced, mostly single-threaded loop over its own books, which is exactly the "parallel across books, single-threaded within a book" split from the single-threaded vs parallel section. NYSE's markets run on its Pillar trading platform, and Nasdaq's US equities matching descends from INET, the electronic market Nasdaq acquired in 2005.
  • Sequenced binary market data. Every book change goes out on a multicast feed with sequence numbers, such as Nasdaq TotalView-ITCH or the NYSE Integrated Feed. Subscribers rebuild the full book from the stream and fill gaps from a retransmission service, as in the market data section.
  • Auctions as well as continuous matching. The day opens and closes with auctions that collect orders and match them all at one price (Nasdaq's Opening and Closing Cross, NYSE's opening and closing auctions). Between them the book matches continuously by price and time.
  • Colocation. The matching engines sit in one primary data center (NYSE in Mahwah and Nasdaq in Carteret, both in New Jersey), with a backup site. Trading firms can rent racks in the same building, and the exchange makes the network paths to every rented rack equal, so physical distance inside the hall does not decide who is first.

The exact rules for priority, order types, auctions and halts are published in each exchange's rulebook and protocol specifications, and they differ in details. Some markets, common in futures, even replace time priority at a price level with pro-rata allocation, where every resting order at the best price gets a share of the fill in proportion to its size.

In the wild

Where you will see this: stock and futures exchanges, cryptocurrency exchanges, and the internal matching engines of trading firms and ad auctions. The recurring pattern, beyond finance, is the sequencer plus deterministic single-threaded state machine: a total order of inputs, applied in memory, made durable and highly available by journaling and replaying that order.

FAQ

What does an order matching engine do?

The component of an exchange that keeps the order book for each instrument and pairs buy orders with sell orders according to the exchange's rules, usually price-time priority. It decides every trade and produces the fills and market data that participants see.

How does a stock exchange matching engine work?

Orders arrive through gateways, get a sequence number from a sequencer and are journaled. The engine applies them in that order to an in-memory order book: an incoming buy trades against the lowest asks at or below its limit, oldest first at each price, at the resting order's price, and any remainder rests in the book. Every change is then published as market data.

Should a matching engine be single-threaded or parallel?

Single-threaded per order book, parallel across books. One thread per book needs no locks, keeps data in the CPU cache and gives the same result every time the same input is replayed. Exchanges get more throughput by partitioning symbols across threads and machines, and by running everything except matching (decoding, risk checks, journaling, market data) on other cores.

What data structure does an order book use?

A sorted collection of price levels for each side (a tree map, or an array indexed by price ticks), where each level is a FIFO queue of orders, plus a hash map from order id to its queue node so cancels are constant time.

How do you build a matching engine?

Start with integer prices, one symbol's order book and the matching loop for limit orders, then add market orders, cancels and modify rules. After that comes the hard part: a sequencer and journal in front, replay tests for determinism, snapshots, a hot standby and per-symbol-group engine threads. The step-by-step list above walks through it.

Check yourself

  1. Two sell orders rest at 100.40. Which fills first against a new buy?

    Show answer

    B. The one that arrived first, by sequence number Price-time priority: best price first, then earliest arrival.

  2. Why does the matching engine run on a single thread?

    Show answer

    B. Matching is sequential per symbol; one thread avoids locks and keeps results deterministic Lock-free, cache-hot processing in sequence order gives low, predictable latency and exact replay.

  3. How does a standby engine keep an identical order book?

    Show answer

    B. It consumes the same sequenced journal and, being deterministic, reaches the same state Deterministic state machine replication: same inputs in the same order give the same state.

  4. Why is market data sent with UDP multicast instead of a TCP stream per subscriber?

    Show answer

    B. The network delivers each update to all subscribers at once, so none is systematically ahead Fan-out in the network fabric is fast and fair; sequence numbers handle the occasional lost packet.

Recap

  • Each symbol has an order book matched by price-time priority, at the resting order's price.
  • A sequencer gives every input one global order and journals it before processing.
  • A single-threaded, in-memory engine applies that order without locks, deterministically.
  • Durability and failover come from replaying the journal: snapshots, hot standbys and exact audits.
  • Market data goes out as sequenced multicast; gaps are filled by retransmission.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy

Next up