Design a Stock Exchange Matching Engine

This is lesson 8 of System Design Case Studies, Part 2. Most lessons in this series spread work over many machines. This one does the opposite on purpose: the core is not spread out, and the interesting part is why that is correct and how to make it safe. Lesson 1 (key-value store) showed replicated logs. Lesson 6 (unique ID generator) shows how to make the order IDs and sequence numbers we use here. Lesson 7 (multi-data-centre systems) covers what happens when the site itself fails.

Words used in this lesson

• Order is a request to buy or sell. It has a side (buy or sell), a quantity, and sometimes a price.
• Limit order says "buy up to 100 shares, but pay at most 50.00". It may wait in the book.
• Market order says "buy 100 shares at whatever the best prices are now". It never waits in the book.
• Cancel removes an order that is still waiting.
• Order book is the list of waiting orders. Bids are the buy orders. Asks (also called offers) are the sell orders.
• Best bid / best ask are the highest buy price and the lowest sell price. The gap between them is the spread.
• Price level is all the waiting orders at one price.
• Price-time priority: a better price goes first. At the same price, the order that arrived first goes first (FIFO, first in first out).
• Maker is the waiting order. Taker is the new order that hits it. A trade (also fill) happens between a maker and a taker.
• Partial fill is when an order trades only part of its quantity. The rest is the leaves quantity.
• Crossed means a buy price is at or above a sell price, so a trade must happen. A book that is crossed while at rest is a bug.
• Sequencer is the one component that puts all incoming commands into a single numbered line.
• Deterministic means the same inputs in the same order always give the same outputs.

1. Requirements

Functional

• Accept limit orders, market orders and cancels.
• Match by price-time priority. A trade happens at the resting (maker) order's price.
• Send each client an acknowledgement, then fills (partial or full), then a final state.
• Publish market data: the book depth (price and total quantity per level) and every trade.
• Run risk checks before an order can reach the book (size limit, price band, duplicate ID).

Non-functional

• Fair and deterministic: two orders at the same price must be served in a clear, provable order. Auditors must be able to replay the day and get the same trades.
• Low and steady latency: the number that matters most is the tail (the slowest 1 in 1000), not the average.
• Durable: an accepted order and a trade must never be lost, even if the machine dies.
• Correct above all: wrong trades cost real money. Prefer to stop than to guess.

2. Back-of-envelope numbers

Every number is an assumption.

Instruments (symbols)        3,000Orders per day               500 million (new + cancel), most are cancels or never tradeAverage rate                 500e6 / 23,400 s (6.5 h trading day) = ~21,000 orders/sPeak (open, news)            ~20x average on the busiest symbols = a few hundred thousand orders/s in totalBusiest single symbol        assume 50,000 orders/s at peakOrder message                ~64 bytes  -> 50,000 x 64 B = 3.2 MB/s (tiny)Event log (all events)       ~3 events per order x 500M x ~48 B = ~72 GB/dayBook size                    100,000 resting orders x ~100 B = 10 MB per busy symbol (fits easily in RAM)

What this shows:

• Bandwidth and storage are small. The hard part is latency and ordering, not volume.
• One busy symbol at 50,000 orders/s needs about 20 microseconds per order on average to keep up. My local test (section 6.2) did one command in 2 to 4 microseconds at p99 (median under 1) on a simple random workload, so one core has room. A real engine has more work per order (logging, network, risk).
• The book for one symbol is small enough to live in memory on one machine. So we do not need a distributed database for the book.

Latency budget (assumed target: 100 microseconds from the network card in to the network card out, p99):

network in + decode          10 usrisk checks                   5 ussequencer (assign number)     2 usappend to log + replicate    40 us    <- usually the biggest piecematch                         3 usencode + network out         10 usslack / jitter               30 us

The proportions matter more than the exact numbers. Matching is the cheap part. Durable logging and the network cost far more. My measured match step is under a microsecond to a few microseconds.

3. API

Real exchanges use binary protocols (FIX is the common text protocol for clients; venues add their own binary ones). For clarity here is a JSON view:

# Client -> gateway (one persistent connection, session-based, orders are sequenced per session){ "type": "limit",  "clientOrderId": "c-881", "symbol": "ABC", "side": "buy",  "price": 10050, "qty": 100 }{ "type": "market", "clientOrderId": "c-882", "symbol": "ABC", "side": "sell", "qty": 40 }{ "type": "cancel", "clientOrderId": "c-881" }# Engine -> client (execution reports){ "seq": 90211, "kind": "ack",       "id": 881 }{ "seq": 90211, "kind": "trade",     "maker": 770, "taker": 881, "price": 10050, "qty": 60 }{ "seq": 90300, "kind": "cancelled", "id": 881, "leaves": 40, "reason": "user cancel" }{ "seq": 90301, "kind": "reject",    "id": 883, "reason": "price outside band" }# Market data (public, one-way multicast or stream){ "seq": 55012, "symbol": "ABC", "type": "level", "side": "bid", "price": 10050, "totalQty": 40 }{ "seq": 55013, "symbol": "ABC", "type": "trade", "price": 10050, "qty": 60 }

Notes:

• Prices are integers counted in ticks, the smallest price step (here 10050 means 100.50 when a tick is 0.01). Floating point cannot be trusted to add up exactly, and an exchange must.
• Every event carries a sequence number. A client that sees a gap knows it missed something and asks for a replay.
• A rejected order gets an explicit reject with a reason. Silence is never an answer.

4. Data model

Command log (append-only, replicated):   seq | symbol | type | order id | side | price | qty | receive timeEvent log   (append-only):               seq | ack / trade / cancelled / reject ... (what the engine decided)Order book  (in memory, one per symbol): bids: sorted price levels, each a FIFO queue                                         asks: sorted price levels, each a FIFO queue                                         id -> order  (hash map, for O(1) cancel)Snapshots   (object store, periodic):    the whole book + last seq, so recovery does not replay the whole dayReference data:                          symbols, tick size, price bands, limits (read-only for the engine)

The book is not a table in a database. It is a few plain objects in the engine's memory. The log is what is durable. The book can always be rebuilt from the log.

5. High-level architecture

 Clients ---> Gateways (many) ---> Risk checks (pre-trade) ---> SEQUENCER (one per partition)   (FIX /      auth, rate limit,      size, price band,              |  assigns seq 1,2,3...    binary)    decode, session        duplicate id                   v                                                         Command log (replicated, durable)                                                                     |                                                  +------------------+-------------------+                                                  v                                      v                                        MATCHING ENGINE (primary)               MATCHING ENGINE (hot standby)                                        single thread, in-memory books          same input, same order, same state                                                  |                                    events: ack / trade / cancelled / reject                                                  |                        +-------------------------+----------------------------+                        v                         v                            v                 Execution reports        Market-data publisher        Downstream: clearing,                 back to the gateways     (depth + trades, seq nos)    surveillance, audit, reports

Key points:

• One sequencer, one engine thread per partition. A partition is a group of symbols (often one busy symbol alone). Different symbols never trade against each other, so partitions run in parallel without any shared state.
• The command log is the source of truth. The primary and the standby read the same log, so they reach the same state.
• Gateways and risk checks scale out (many machines). Only the sequencer and the engine are single-threaded per partition.

6. Deep dives

6.1 The order book data structure

What the engine does all day:

1. Insert a limit order at a price (join the back of that price's queue).
2. Find the best price on the opposite side, and take from the front of its queue.
3. Cancel an order by ID, from anywhere.
4. Remove a price level when it becomes empty.

My implementation (engine.ts) uses these exactly. The core data structures:

interface Node  { id: number; side: Side; price: number; qty: number; prev: Node | null; next: Node | null; level: Level }interface Level { price: number; head: Node | null; tail: Node | null; total: number }   // FIFO queue + total qty// bids ascending (best = highest = LAST), asks descending (best = lowest = LAST)class Side_ {  levels: Level[] = [];                       // sorted so the best price is the last element  byPrice = new Map<number, Level>();         // price -> level  getOrCreate(price) { /* binary search, splice a new level in */ }}// Engine also has: orders = new Map<number, Node>()   // id -> resting order, for O(1) cancel

Why a linked list and not an array per level: cancelling from the middle of an array costs O(n), and a level can hold thousands of orders. With the id -> node map and a doubly linked list, cancel is a few pointer changes.

Trade-off I did not remove: inserting a new price level uses splice on a sorted array, which is O(number of levels). Removing an emptied level uses indexOf, also O(levels). With 50 to 60 levels per side in my test this is invisible. A real book can have thousands of levels. Options: a balanced tree (O(log n)), or a fixed array indexed by price - minPrice when prices are bounded integers (O(1), and the usual choice in fast engines because it is cache friendly). Most orders land near the best price, so the work is usually near the end of the array anyway.

6.2 The matching algorithm

For a new order the engine does this (the loop from engine.ts):

const book = cmd.side === "buy" ? this.asks : this.bids;            // trade against the other sideconst crosses = (p) => cmd.type === "market" ? true : cmd.side === "buy" ? p <= cmd.price : p >= cmd.price;let left = cmd.qty;for (let lv = book.best(); lv && left > 0 && crosses(lv.price); lv = book.best()) {  while (lv.head && left > 0) {                                      // FIFO = time priority    const maker = lv.head;    const q = Math.min(left, maker.qty);    maker.qty -= q; lv.total -= q; left -= q;    this.lastPrice = lv.price;                                       // trade at the RESTING order's price    emit({ kind: "trade", maker: maker.id, taker: cmd.id, price: lv.price, qty: q });    if (maker.qty === 0) this.unlink(maker);                         // remove it (and the level if empty)  }}if (left > 0 && cmd.type === "limit") restInBook(cmd, left);         // remainder waits at its limit priceelse if (left > 0) emit({ kind: "cancelled", ..., reason: "market order unfilled" });

The rules, in plain words:

• A buy matches the lowest asks first, as long as the ask price is at or below the buy limit. A sell matches the highest bids first.
• Inside a price level the oldest order goes first.
• The trade price is the maker's price. A buyer willing to pay 105 who meets a seller at 100 pays 100. This is called price improvement.
• A limit order that is not fully filled rests with its remaining quantity. It goes to the back of its level's queue.
• A market order never rests. Whatever is not filled is cancelled and reported. If the book is empty, the whole order is cancelled.
• A partial fill of a maker keeps the maker's place in the queue with the smaller quantity. It does not go to the back.

Here is a trace from demo.ts (real output). Orders 1 to 3 are sells, 4 is a buy that waits, 5 is a big buy that crosses:

{"type":"limit","id":1,"side":"sell","price":101,"qty":5}    {"seq":1,"kind":"ack","id":1}{"type":"limit","id":2,"side":"sell","price":100,"qty":4}    {"seq":2,"kind":"ack","id":2}{"type":"limit","id":3,"side":"sell","price":100,"qty":6}    {"seq":3,"kind":"ack","id":3}{"type":"limit","id":4,"side":"buy","price":99,"qty":8}    {"seq":4,"kind":"ack","id":4}{"type":"limit","id":5,"side":"buy","price":101,"qty":12}    {"seq":5,"kind":"ack","id":5}    {"seq":5,"kind":"trade","maker":2,"taker":5,"price":100,"qty":4}    {"seq":5,"kind":"trade","maker":3,"taker":5,"price":100,"qty":6}    {"seq":5,"kind":"trade","maker":1,"taker":5,"price":101,"qty":2}{"type":"cancel","id":4}    {"seq":6,"kind":"cancelled","id":4,"leaves":8,"reason":"user cancel"}{"type":"market","id":6,"side":"sell","qty":3}    {"seq":7,"kind":"ack","id":6}    {"seq":7,"kind":"cancelled","id":6,"leaves":3,"reason":"market order unfilled"}{"type":"limit","id":7,"side":"buy","price":130,"qty":1}    {"seq":8,"kind":"reject","id":7,"reason":"price outside band"}depth {"bids":[],"asks":[[101,3]],"last":101}

Read it line by line. Order 5 (buy 12 at up to 101) took the 100 level first, order 2 then order 3, because 2 arrived first. Then it took 2 from order 1 at 101. Order 1 is a partial fill: 3 shares remain in the book (asks: [[101, 3]]). The market sell (order 6) found no bids, because order 4 was cancelled, so it was cancelled whole. Order 7 was rejected by the price band before it touched the book.

6.3 Tests, including partial fills and cancels

Matching bugs are expensive, so the engine has a table of small tests (engine.test.ts). I ran them with node --test engine.test.ts:

ok 1 - limit order rests when it does not crossok 2 - full fill at the resting price (price improvement for the taker)ok 3 - partial fill: taker rests with the remainderok 4 - partial fill: maker keeps its place with the remainderok 5 - price priority: best price first, then time priority within a levelok 6 - market order with an empty book is cancelled, never restsok 7 - cancel removes an order; the level disappears when emptyok 8 - cancel after a partial fill returns only what is leftok 9 - cancel of unknown or finished order is rejectedok 10 - a cancelled order in the middle of a queue does not break time priorityok 11 - risk checks reject bad orders and nothing reaches the bookok 12 - replay of the command log gives the same events and the same bookok 13 - invariant: book never crossed, quantity conserved# tests 13# pass 13# fail 0

Two of these are different in kind. Test 13 runs 3,000 random commands and after every command checks that the best bid is below the best ask, and at the end checks conservation: every accepted share is either traded (counted once for the taker and once for the maker), cancelled, or still resting. Test 12 is the replay test in the next section. These two are the ones I would keep even if I deleted all the example-based tests.

6.4 Determinism: one thread, one sequencer

Why not match orders on many threads with locks? Because the result would depend on timing. Two orders at the same price arrive "at the same time" on two threads; whichever grabs the lock first wins. That is unfair, impossible to replay, and impossible to audit.

The design instead:

1. Every command gets a number from the sequencer: 1, 2, 3, ... That number is the order of events. There is no "at the same time" any more.
2. One thread takes commands in that order and applies them to the book. No locks, no shared mutable state, no timing luck.
3. The engine reads no clock, no random numbers, no network while matching. Anything it needs (like the time) is written into the command by the sequencer. This is what makes the matching a pure function: (state, command) -> (new state, events).

sequencer ----> [cmd 1][cmd 2][cmd 3] ... ----> engine thread ----> [events]

This also explains why a single thread is fast: no lock waits, the book stays in one CPU's cache, and there is no thread switching. The throughput limit of one thread is high enough for one symbol (section 2). Different symbols run on different threads or machines.

6.5 Event log and replay

Because the engine is deterministic, we only need to save the commands in order. The state is derived. I tested this: 2,000 random commands (limits, markets, cancels) ran on a live engine. A second engine was built by replaying only the command list. Test 12 checks two things: the final book fingerprint is equal, and the full event log is equal, event by event. It passed. The demo shows the same on the small trace:

replay same book? true | same log? trueB[] A[101:1x3] last=101

(The last line is the book fingerprint: no bids; one ask level at 101 with order 1 holding 3 shares; last trade 101.)

What replay gives you:

Rules that keep replay honest:

• The log must be written before the engine's result is sent to anyone (write-ahead). If we told a client "trade done" and then lost the command, the books would disagree with reality.
• Replicate the log to at least one other machine before acknowledging (quorum or synchronous replica). The same idea as a replicated log in Lesson 1.
• The engine code must be versioned with the log. A new engine version that matches differently will not replay an old day the same way. Keep the version number with each day's log.

6.6 Measured speed of the data structure

I ran 1,000,000 commands on one engine: 70% limit orders at random prices in a 200-tick range (random side), 30% cancels of random earlier IDs (many of which no longer exist and are rejected). I timed each command with process.hrtime.bigint() and cleared the event log after each one so it would not fill memory. Two runs on the same machine:

commands 1000000, total 1.58 s, 634k commands/slatency per command (includes hrtime overhead) us: p50 0.69  p99 2.07  p99.9 15.91  max 142621price levels bids/asks: 59 49 resting orders: 120366commands 1000000, total 1.46 s, 686k commands/slatency per command (includes hrtime overhead) us: p50 0.67  p99 3.65  p99.9 39.54  max 129309price levels bids/asks: 59 49 resting orders: 120366

Read it with care:

• About 650,000 commands per second on one thread in a language with a garbage collector. This tells you matching is cheap, as section 2 said.
• The median is under a microsecond; the tail is not. p99.9 was 16 to 40 microseconds and the worst command took about 130 to 140 milliseconds. I did not find the cause. A garbage-collection pause or the operating system taking the core are my guesses; I did not test either. This is exactly why exchanges write matching engines in languages without a garbage collector, pre-allocate memory, and pin the thread to one core: the tail, not the average, is the product.
• This workload is random. Real traffic clusters near the best price, and the cost per order depends on how many levels a market order sweeps.

6.7 Risk checks

Bad orders must not reach the book. There are two places to check:

• Pre-trade checks, before the sequencer (parallel and scalable, in the gateway layer): is the client allowed, is the message well-formed, the order size within the client's limit, the client's total exposure within its credit limit, the rate of orders within limits.
• Checks inside the engine (cheap, deterministic, and part of the replayed state): a duplicate ID, a quantity limit, a price band.

My risk() function does the second kind: duplicate order ID, quantity not a positive integer, quantity over the maximum, price not a positive integer, and price more than a set percentage away from the last trade. Test 11 checks that each of these is rejected with a clear reason and that nothing reaches the book.

[ "bad quantity", "quantity over limit", "price outside band", "duplicate id" ]   (test 11)

Why the price band matters: a "fat finger" order (someone types 1000 instead of 100) can move the market and cause real losses. The band blocks it. Exchanges also use circuit breakers: a halt in trading when the price moves too fast.

Where to put checks that need shared state. A client's total exposure across many symbols cannot be checked by one symbol's engine. The usual answer is to check it in the gateway or a risk service before sequencing, with limits that are a little conservative, and accept that it can be slightly stale. The engine itself keeps only checks that depend on the symbol's own state.

6.8 Market-data feed

The market-data publisher does not read the book. It reads the event stream. Each trade event and each change to a price level becomes a public message with its own sequence number.

Two kinds of feed, a common split:

My depth() returns the top N levels as [price, totalQty]. The engine keeps total on every level, updated on each fill and each cancel, so the depth is a cheap read:

depth(n) { return { bids: bids.levels.slice(-n).reverse().map(l => [l.price, l.total]), asks: ..., last } }

Design points:

• One-to-many, one-way. Use multicast or a fan-out layer so the engine does not slow down when there are 10,000 subscribers. The engine never waits for a consumer.
• Sequence numbers + a snapshot channel. A subscriber that joins late (or sees a gap) reads a recent snapshot of the book and then applies the incremental messages after that snapshot's sequence number. This is the same "snapshot plus log" idea as recovery.
• Because the feed is made from the same event log, it is consistent with the trades. A trade message never appears for a price level that the book did not have.

6.9 Failover and scaling

Failover. The primary and the standby both consume the same command log, so the standby is only slightly behind. When the primary stops: a coordination service (or an operator in the strictest venues) picks the standby, which finishes applying the log up to the last durable entry, and starts publishing. Two dangers:

• Split brain: both think they are primary and publish different trades. Prevent this with a single leader lease or a fencing token, and by making the log the only truth: whoever cannot append to the log cannot trade.
• Duplicate output: the new primary may re-send events the old one had already sent. Sequence numbers on every event let receivers drop duplicates.

For a failure of the whole data centre, see Lesson 7 (multi-data-centre systems). A second site that receives the log with some delay is a disaster-recovery copy. A venue chooses between a possible small loss (asynchronous copy) and slower, safer trading (synchronous copy).

Scaling. Partition by symbol. Symbols never interact, so each partition has its own sequencer, log and engine. The only shared piece is the gateway and risk layer, which is stateless or has per-client state and scales out. A very busy single symbol cannot be split: its ordering is the point. For that you make the single path faster (kernel bypass networking, pinned cores, pre-allocated memory) rather than wider.

7. Failure modes and trade-offs

Trade-offs to say aloud

• Single thread vs many threads: simple, fair, replayable and fast enough, but one core is the ceiling for one symbol.
• Durability vs latency: waiting for a replicated log write costs most of the budget; skipping it risks lost trades. Choose durability.
• Array of levels vs tree vs index by tick: simple and fast for typical depth, against a guaranteed O(log n) or O(1) bound.
• Strict synchronous replication vs async to a second site: no data loss against higher latency.

8. How to say it in an interview (60 seconds)

"Orders come through gateways that authenticate and run pre-trade risk checks, then into a sequencer that numbers every command. A single-threaded engine per symbol group applies commands in that order to an in-memory book: sorted price levels, each a FIFO queue, plus a hash map from order ID to node so cancel is constant time. A new order matches the best opposite price first, then the oldest order at that price, and trades at the resting order's price. A limit order rests with what is left; a market order never rests. Because the engine is deterministic, with no clocks and no threads inside, the command log is enough to rebuild everything: a standby applies the same log, and I replay a day for audit. I tested partial fills, cancels, and replay equality, and a random 3,000-command run keeps the book uncrossed and share counts balanced. In my local test one thread did about 650,000 commands a second with a median under a microsecond, but the tail had spikes, so a real engine avoids garbage collection and pins a core. Market data is derived from the same events, with sequence numbers and a snapshot channel. We scale by partitioning symbols, never by splitting one symbol."

Run it yourself

Files: engine.ts (book, matching, replay, risk), engine.test.ts (13 tests), demo.ts (the trace in 6.2) and bench.ts (the speed test). Put them in one folder, then:

node --test engine.test.tsnode demo.tsnode bench.ts

Node 22.22 strips the types, so no build is needed. The code uses only Node's standard library and avoids constructor parameter properties, which type stripping does not support.

Interview questions

Key takeaways

• A matching engine is a small, hot, in-memory state machine. Volume is low by cloud standards; ordering, fairness and tail latency are the hard parts.
• Book = sorted price levels + FIFO queue per level + id -> node map for constant-time cancel.
• Match best price first, then the oldest order. Trade at the maker's price. A limit remainder rests; a market remainder is cancelled.
• One sequencer and one thread per symbol group makes the result deterministic. Never use locks to decide who was first.
• The command log is the truth. Replay rebuilds state for recovery, standby, audit and testing. Measured: replay of 2,000 random commands gave an identical book and event log.
• Risk checks in two layers: before the sequencer (scalable, may be stale) and inside the engine (exact, replayed).
• Market data comes from the event stream, with sequence numbers and snapshots, and never slows the engine.
• Locally measured (one process, no network): about 650,000 commands/s, median under 1 microsecond, but a long tail. Say the tail is the product.

What's next

Lesson 9: Design Sales Ranking by Category. We go back to a read-heavy, many-machine design: count sales per product per category over a time window, and serve the top N from a Redis sorted set. It is the same "snapshot plus event stream" idea, with a different goal.