9.7.25 — The Order Book & Matching Engine

"Design the matching engine for a stock exchange: buyers and sellers submit orders, and the engine decides who trades with whom, at what price."

Two people want to buy a share at £10.00 and one person is selling one share at £10.00. Somebody gets it and somebody does not, and the entire design exists to make sure that everyone — including the person who lost — can see exactly why.

An exchange is not judged on speed first. It is judged on determinism: given the same orders in the same order, the engine must produce the same trades every single time, and it must be able to prove it afterwards. Every structural decision on this page falls out of that one requirement, including the ones that look like performance decisions.

This page is the low-level design: the data structures, the matching loop and the order types. The distributed, multi-datacentre version of the same problem is 11.15 in Part 11.

1. The book is two sorted lists, and one rule decides everything

An order book for one instrument is two collections: people willing to buy (the bids) and people willing to sell (the asks). A share of one company is one book; a different company is a different book, and the two never interact. That independence is the single most useful fact in the whole design, and section 6 spends it.

Figure 1 — One order book. Bids sorted highest first, asks sorted lowest first, and a first-in-first-out queue inside every price level. The two structures are the same shape with opposite orderings.

The rule the whole engine implements is called price-time priority, and it is two comparisons:

Better price wins. A buyer offering £10.01 is served before one offering £10.00, always, regardless of when either arrived.

At the same price, earlier wins. Ana at 09:31:02 is filled before Ben at 09:31:07, completely, before Ben gets anything.

That is the whole fairness model, and it is worth saying why it is this and not something else: it is the only rule that is both explainable to the loser and impossible to game by anything except being better or being faster. A rule that allocated proportionally, or randomly, would be defensible in theory and would be argued about every day.

Nothing trades while the best bid is below the best ask. The gap between them is the spread, and a resting book with a spread is the normal, quiet state of an exchange. Trades happen only when a new order arrives that crosses the spread — a buy at or above the best ask, or a sell at or below the best bid.

2. Choosing the data structure, with the reasoning shown

The engine does four things constantly, and the structure must be good at all four:

Operation	How often	Needed
Find the best price	Every order	Constant time
Add at a price	Every resting order	Fast insert
Remove the oldest at a price	Every fill	Constant time
Cancel a specific order	Very often	Constant time

The last row is the one that eliminates the obvious answer. A heap gives an excellent best-price lookup, and it is the structure people reach for first. But cancelling a specific order in a heap means finding it, which is a linear scan, and on real exchanges most orders are cancelled rather than traded. A structure that is fast at the rare case and slow at the common one is the wrong structure.

What works is a two-level structure:

class Book {
  private bids = new SortedMap<Price, PriceLevel>(descending);   // (1)
  private asks = new SortedMap<Price, PriceLevel>(ascending);
  private index = new Map<OrderId, OrderNode>();                 // (2)

  bestBid(): PriceLevel | null { return this.bids.first(); }     // (3)
  bestAsk(): PriceLevel | null { return this.asks.first(); }
}

class PriceLevel {                                                // (4)
  price: Price;
  totalQuantity: Quantity;                                        // (5)
  head: OrderNode | null;                                         // (6)
  tail: OrderNode | null;
}

class OrderNode {                                                 // (7)
  order: Order;
  remaining: Quantity;
  prev: OrderNode | null;
  next: OrderNode | null;
  level: PriceLevel;                                              // (8)
}

(1) One sorted structure per side, keyed by price, holding a level rather than an order. The two sides are identical apart from the direction of the sort, which is why the same code can serve both by taking a comparator.

(2) A flat map from order identifier straight to its node. This is the line that makes cancellation constant time, and it is the reason this design beats a heap.

(3) The best price is the first entry of the sorted structure, which is a constant-time read.

(4) A price level is everything resting at one price, in arrival order.

(5) The total at the level is maintained incrementally rather than summed on demand, because the market data feed publishes it on every change and a level can hold thousands of orders.

(6) and (7) The level's orders are a doubly linked list. Filling takes from the head, which is the oldest and therefore the highest priority; new orders join the tail. Both are constant time and neither shifts anything.

(8) Each node points back at its level, so a cancellation found through the index in (2) can unlink itself and adjust the level's total without searching for where it lives. This back-pointer is what makes the whole cancel path constant time end to end.

Why the price keys are integers, not decimals. Prices are stored in the smallest unit the instrument trades in — pence, or hundredths of a penny — as integers. Floating-point prices produce comparisons that are subtly wrong, and an exchange where £10.00 sometimes fails to equal £10.00 is not an exchange. This is the same integer-money rule the wallet insists on in 9.7.10, and here it also makes the sorted structure faster.

A practical note worth volunteering: real instruments trade in a small number of prices near the current one, so the sorted map is often replaced by an array indexed by price offset from a reference point. It turns a logarithmic lookup into an array index at the cost of memory and a rare, expensive rebase when the price moves far. Naming that trade shows you know what the structure is actually holding.

3. The matching loop

Every incoming order runs the same loop: take from the other side while it can, then rest whatever is left.

function match(book: Book, incoming: Order): Trade[] {
  const trades: Trade[] = [];
  let remaining = incoming.quantity;

  while (remaining > 0) {
    const level = book.bestOpposite(incoming.side);              // (1)
    if (level === null || !crosses(incoming, level.price)) break; // (2)

    const resting = level.head!;                                  // (3)
    const qty = min(remaining, resting.remaining);                // (4)

    trades.push({
      price: level.price,                                         // (5)
      quantity: qty,
      restingOrderId: resting.order.id,
      incomingOrderId: incoming.id,
      sequence: book.nextSequence(),                              // (6)
    });

    resting.remaining -= qty;                                     // (7)
    remaining -= qty;
    level.totalQuantity -= qty;

    if (resting.remaining === 0) book.remove(resting);            // (8)
  }

  if (remaining > 0 && incoming.restsOnBook)                      // (9)
    book.insert(incoming, remaining);

  return trades;
}

(1) Look at the best level on the opposite side. A buy looks at the lowest ask; a sell looks at the highest bid.

(2) Two ways to stop: nothing left on the other side, or the best price no longer crosses. For a buy, crossing means the ask price is at or below the buy's limit; for a sell, the bid is at or above. This single condition is the whole of "when does trading stop", and getting the direction wrong on one side is the classic bug in a first implementation.

(3) Take the head of the level, which is the oldest order there. This one line is where time priority actually happens, and it is the reason the level is a queue and not a set.

(4) Trade the smaller of the two quantities. Both partial fills fall out of this: the incoming order can be partly filled, or the resting one can, and the loop handles both without a special case.

(5) The trade happens at the resting order's price, not the incoming order's. This is the rule that surprises everyone and it must be stated. A buy order with a limit of £10.05 hitting a resting ask at £10.02 trades at £10.02. The person who was there first set the price; the person who arrived gets the benefit of the difference, which is called price improvement. Charging the buyer £10.05 would mean the exchange kept the difference, which is not what an exchange does.

(6) Every trade gets a sequence number from a single counter. Section 6 explains why this is the backbone of the whole system rather than a detail.

(7) Decrement all three quantities together — the resting order, the incoming order and the level's cached total. The level total is a derived value maintained in step, exactly like every other cached aggregate in this chapter.

(8) A fully filled resting order is unlinked from the level and removed from the index. If the level is now empty, it is removed from the sorted map so the next best-price lookup does not have to skip it.

(9) Whatever is left over rests on the book — unless the order type says it must not, which is the next section.

Walk it once with numbers. The book has asks of 150 at £10.02 and 700 at £10.03. A buy arrives for 400 with a limit of £10.03.

First pass: best ask is £10.02, which crosses. The head there has 150. Trade 150 at £10.02. Remaining is 250, the level empties and is removed.

Second pass: best ask is now £10.03, which still crosses. Trade 250 at £10.03. Remaining is 0.

Result: two trades at two different prices from one order, at an average of £10.0263. The buyer's screen will show one order filled at an average price, and the fact that it was two trades matters for every report afterwards. An engine that reports one trade at an average price has destroyed information that regulators, brokers and the sellers all need.

4. The order types, each in plain terms

The order types are not a feature list. Each one is a different answer to "what should happen to the part that could not be filled?", and seeing them that way makes the whole set memorable.

A limit order names a worst acceptable price. It fills as much as it can at that price or better, and the rest rests on the book. This is the default and everything else is a variation.

A market order names no price: fill it against whatever is there. The unfilled part does not rest, because an order with no price has no place on a book sorted by price. Two protections are mandatory rather than optional. A market order on a thin book can sweep several levels and fill at a terrible price, so exchanges apply a collar — a limit beyond which it will not trade, derived from the current price — and cancel the rest. Without that, a large market order into an empty book fills at whatever absurd price is resting there, and that trade will be in the newspaper.

Immediate-or-cancel fills what it can right now and cancels the remainder instead of resting. Used by someone who wants what is available and does not want to advertise their intention by leaving an order on the book.

Fill-or-kill is all or nothing: if the whole quantity cannot be filled immediately, nothing trades at all. This one needs a check before any change is made, because a partially applied fill-or-kill is not undoable in a system that has already published trades.

function availableAgainst(book: Book, o: Order): Quantity {       // (1)
  let total = 0;
  for (const level of book.levelsCrossing(o)) {                   // (2)
    total += level.totalQuantity;
    if (total >= o.quantity) return total;                        // (3)
  }
  return total;
}

if (o.type === "fillOrKill" && availableAgainst(book, o) < o.quantity)
  return reject(o, "insufficientLiquidity");                      // (4)

(1) Walk the crossing levels and add up what is there, before touching anything.

(2) Only levels that cross this order's limit count. Quantity resting at a price this order will not pay is not available to it.

(3) Stop as soon as there is enough. On a deep book this avoids walking thousands of levels to answer a question that was settled at the second one.

(4) Reject before any state changes. This is a check-then-act sequence, and it is only safe because the engine is single-threaded — nothing can change between the check and the act. On a concurrent engine this would be the classic race from 9.5.1, and section 6 explains why that concurrency does not exist here.

A stop order is not on the book at all. It is an instruction held aside — "when the price reaches £9.50, submit a sell" — and it becomes a real order only when a trade occurs at or through its trigger price. Two consequences follow. Stops are stored in a separate structure keyed by trigger price, not in the book, since they are invisible to everyone until they fire. And a single trade can trigger many stops, each of which becomes an incoming order that can trigger more, which is exactly how a fast fall becomes a very fast fall. A well-designed engine processes triggered stops through the same input queue as everything else rather than recursively inside the match, so the ordering stays defined and one cascade cannot blow the stack.

An iceberg order shows a small quantity and hides the rest. When the visible part fills, a new visible slice joins the level — at the back of the queue, not the front. That rule is what stops a hidden order from monopolising a price level forever, and it is the kind of detail that shows you have read how a real exchange behaves.

5. Cancel and amend, and the priority that gets lost

Cancelling is the common case, so it must be cheap.

function cancel(book: Book, id: OrderId): boolean {
  const node = book.index.get(id);                                // (1)
  if (!node) return false;                                        // (2)
  node.level.totalQuantity -= node.remaining;                     // (3)
  unlink(node);                                                   // (4)
  book.index.delete(id);
  if (node.level.isEmpty()) book.removeLevel(node.level);         // (5)
  return true;
}

(1) Straight to the node through the index. No search, no scan.

(2) A cancel for an order that is not there is not an error — it means the order filled or was already cancelled, and the two racing is completely normal. Returning "nothing to do" rather than throwing is the right behaviour, and the client is told which of the two happened.

(3) Adjust the level total before unlinking, while the quantity is still known.

(4) Unlink from the doubly linked list, which is a constant-time pointer update thanks to the node's prev and next.

(5) An empty level is removed so it does not sit in the sorted map slowing every best-price lookup.

Amending is where the rule that matters lives. A trader wants to change an order's price or quantity, and the engine's answer depends on which:

Reducing the quantity keeps time priority. The order is still the same order, still where it was in the queue, just smaller. Nobody behind it is disadvantaged by it asking for less.

Increasing the quantity loses time priority. The order goes to the back of its level. If it did not, a trader could join a queue with one share and grow it to a million just before a fill, jumping ahead of everyone who queued honestly. The rule exists to stop exactly that, and being able to explain why rather than just stating it is what the question is testing.

Changing the price always loses time priority, because the order is moving to a different queue and must join that one at the back.

The clean way to implement all three is cancel-and-replace, with the reduction case as the only shortcut: reduce in place, otherwise cancel the old node and insert a new one. That keeps one code path for the complicated cases and makes the priority rules a consequence of the mechanism rather than a set of conditions somebody has to remember.

6. One thread, and why that is the right answer

The instinct is to parallelise the engine. For this problem, the instinct is wrong, and knowing why is most of what separates a good answer from an average one.

The requirement is determinism. Given the same sequence of inputs, the engine must produce exactly the same trades — for replay after a crash, for the standby machine that must agree with the primary, and for the regulator who will ask, two years later, why Ana was filled and Ben was not. Concurrency inside the matching of one book destroys that, because the outcome then depends on thread scheduling, which is not reproducible and not explainable.

So the shape is: one thread per book, fed by a sequenced queue.

// (1) every input is sequenced before it reaches the engine
interface SequencedInput {
  sequence: bigint;
  receivedAt: Instant;
  payload: NewOrder | CancelOrder | AmendOrder;
}

// (2) the engine is a pure function of state and input
function step(book: Book, input: SequencedInput): { book: Book; events: Event[] }

(1) Everything entering the engine passes through one sequencer that stamps it with a number. That number is the definition of "first" for the entire exchange — not a clock reading, which can drift, jump backwards or tie. This is the same reasoning that gave the auction a server-assigned sequence in 9.7.20, applied to a system where it is the primary correctness mechanism rather than a tie-break.

(2) The engine is a function from state and input to new state and events. It reads no clock, generates no random numbers, and makes no network calls. That is what makes replay produce identical output, and it is a real constraint on the code rather than a description of it: a single Date.now() inside the matching logic breaks the property.

Where the parallelism actually goes. Books are independent — nothing about one instrument affects another — so different books run on different threads with no coordination at all, which is close to perfect scaling in the dimension that matters. And everything around the engine is parallel: decoding messages, risk checks, publishing market data, writing to disk. The serial part is only the matching, and it is small, in-memory and does no input or output, which is precisely why a single thread is fast enough to handle a very large exchange.

Durability without slowing the loop. The sequenced input log is written before the engine processes it, so a crash is recovered by replaying the log into a fresh engine. Nothing about the book itself needs to be written synchronously, because the book is entirely derivable from the inputs. Periodic snapshots exist only to shorten the replay. This is event sourcing (10.8.4) in its most justified form: the state is a fold over an ordered log, and the log is the truth.

7. What must happen before the book, and what must come out

Risk checks happen before the engine, never inside it. Does the account have the buying power? Is the order size within its limits? Is the price within the day's permitted band? Is the instrument halted? All of these need account data and configuration, and putting them inside the matching loop would make the engine depend on things that change underneath it. Outside, they can be parallel and they can be slow; inside, they would poison determinism and cost latency on every order.

Self-trade prevention is the one check that must be inside, because it needs the book. If the same firm is on both sides of a match, most exchanges forbid the trade — it can be used to create fake volume and a misleading price. The engine detects it during matching and applies one of three configured actions: cancel the incoming order, cancel the resting one, or reduce both by the overlap. Which action is a per-firm setting, and the reason it is a setting rather than a rule is that different firms have different reasons for having two orders in the same book.

Two feeds come out, and they are genuinely different things.

The private feed tells each participant about their own orders: accepted, filled, partially filled, cancelled, rejected. Every message carries the sequence number of the event that caused it, so a client can detect a gap and ask for a replay rather than silently working from an incomplete picture.

The public feed is the market data everyone sees: trades, and the state of the book. It carries no identities at all. A trade is published as price, quantity, time and sequence — never who traded — because publishing that would let anyone reconstruct a firm's whole position.

And the public book feed has a design decision worth naming. It can be published as full snapshots or as incremental updates. Snapshots are simple and enormous; increments are small and require the client to have kept up. The standard answer is both: a stream of increments, with periodic snapshots so a client that has fallen behind or just connected can recover without asking anyone. That combination is the same shape as the log-plus-snapshot recovery in section 6, arriving for the same reason.

8. What the interviewer will push on

"What data structure holds the book, and why not a heap?" A sorted map of price to price level, each level a first-in-first-out doubly linked list, plus a flat map from order identifier to node. A heap has excellent best-price lookup and terrible cancellation, and most orders are cancelled rather than traded, so the heap optimises the rare case. The back-pointer from node to level is what makes cancel constant time end to end.

"At what price does the trade happen?" The resting order's price. A buy limited at £10.05 hitting a resting ask at £10.02 trades at £10.02, and the buyer keeps the difference. The person who was there first set the price. Getting this wrong is the tell that a candidate has not thought about who the exchange serves.

"Someone increases their order size." They lose time priority and go to the back of the level. Reducing keeps priority; increasing or changing price does not. The reason is what is being tested: otherwise a trader queues with one share and grows it to a million just before a fill, jumping the whole queue.

"How do you make it fast?" By not making the matching concurrent. One thread per book, fed by a sequenced input queue, with the engine as a pure function of state and input — no clock, no randomness, no input or output. Parallelism comes from books being independent and from everything around the engine. Then the reason: determinism is a hard requirement for replay, for the standby machine, and for explaining a two-year-old fill to a regulator, and thread scheduling is not reproducible.

"How does fill-or-kill work without a race?" Sum the crossing levels first, reject if there is not enough, and only then match. It is a check-then-act sequence, which is safe here only because nothing else can touch the book between the two steps — and pointing out that this is exactly the pattern that would be a bug in a concurrent design shows you know why the single thread was chosen.

"A big sell triggers a hundred stop orders." Stops live outside the book in a structure keyed by trigger price, and a triggered stop is fed back through the same input queue rather than being matched recursively inside the current match. That keeps the ordering defined, keeps every event sequenced, and stops a cascade from becoming unbounded recursion.

The thing to volunteer that nobody asks for: the public feed carries no identities, and the private feed carries a sequence number on every message so a client can detect a gap. Candidates design the matching and stop at the trade. The moment you say that a trade is published as price, quantity, time and sequence — and never who — you have shown you understand that an exchange's hardest constraints are about information rather than throughput.

Recall

• A book is two sorted sides per instrument; books are fully independent of each other.
• Price-time priority: better price first, then earlier arrival. It is the only rule that is explainable to the loser and unable to be gamed except by being better or faster.
• Nothing trades while the best bid is below the best ask. The gap is the spread, and a new order must cross it.
• Structure: sorted map of price to level, each level a FIFO doubly linked list, plus a map from order identifier to node with a back-pointer to its level. Cancel is constant time.
• Not a heap — most orders are cancelled, and cancelling in a heap is a scan.
• Prices are integers in the smallest tradeable unit. Floating point makes £10.00 sometimes not equal £10.00.
• The trade price is the resting order's price, never the incoming order's. The buyer keeps the improvement.
• Order types are answers to "what happens to the unfilled part": limit rests, market cancels (with a collar), IOC cancels, FOK is checked before anything changes, stop is not on the book at all.
• Increasing quantity or changing price loses time priority; reducing keeps it — or a trader queues with one share and grows it before the fill.
• One thread per book, fed by a sequenced queue. The engine is a pure function of state and input: no clock, no randomness, no input or output.
• The sequence number, not the clock, defines "first" for the whole exchange.
• Durability is the input log; the book is derivable, and snapshots only shorten replay.
• Risk checks sit before the engine; self-trade prevention must be inside because it needs the book.
• Two feeds: private with sequence numbers so gaps are detectable, public with no identities at all.

Self-test: Why not a heap? At which price does a crossing order trade? What does increasing a quantity cost? Why is fill-or-kill's check-then-act safe here? Where do triggered stops go? What is missing from the public feed on purpose?

Quiz Bank

FoundationalDesign the order book structure. Justify it against a heap, and show the cancel path.

Four operations decide the structure, and they must all be fast. Find the best price on each side; add an order at a price; remove the oldest at a price when it fills; and cancel a specific order by its identifier.

The heap is the tempting answer and it fails on the fourth. A heap keyed by price gives an excellent best-price lookup. Cancelling a specific order means finding it inside the heap, which is a linear scan, and then repairing the heap. On a real exchange the great majority of orders are cancelled rather than traded — participants adjust their quotes constantly as the price moves — so the heap is fast at the uncommon operation and slow at the most common one.

The structure that works has two levels plus an index:

class Book {
  private bids = new SortedMap<Price, PriceLevel>(descending);
  private asks = new SortedMap<Price, PriceLevel>(ascending);
  private index = new Map<OrderId, OrderNode>();
}

class PriceLevel {
  price: Price;
  totalQuantity: Quantity;      // maintained, never summed on demand
  head: OrderNode | null;       // oldest — fills from here
  tail: OrderNode | null;       // newest — joins here
}

class OrderNode {
  order: Order; remaining: Quantity;
  prev: OrderNode | null; next: OrderNode | null;
  level: PriceLevel;            // back-pointer
}

Each piece earns its place. The sorted map gives the best price as its first entry. The level's linked list gives time priority for free — fill from the head, insert at the tail, both constant time and neither shifting anything. The index gives a constant-time jump from an identifier to a node. And the back-pointer from node to level is what completes it: a cancellation reached through the index can adjust its level's total and unlink itself without ever searching for where it lives.

The cancel path, which is now four pointer operations:

function cancel(book: Book, id: OrderId): boolean {
  const node = book.index.get(id);
  if (!node) return false;                       // already filled or cancelled
  node.level.totalQuantity -= node.remaining;
  unlink(node);
  book.index.delete(id);
  if (node.level.isEmpty()) book.removeLevel(node.level);
  return true;
}

Note the return false rather than an error. A cancel arriving for an order that just filled is completely normal — the two are racing all day — and treating it as a failure produces noise about a situation that is expected. The client is told which of the two happened, and that is the useful information.

totalQuantity is maintained incrementally, not computed. The public market data feed publishes the quantity at each level on every change, and a level can hold thousands of orders. Summing on demand turns a constant-time publish into a linear one at exactly the moment the market is busiest. It is a cached aggregate under the same conditions as everywhere else in this chapter: updated in the same step as the change, and rebuildable by walking the list if it is ever doubted.

One more decision that belongs in the answer: prices are integers. They are stored in the smallest unit the instrument trades in, so comparisons are exact. Floating-point prices produce cases where £10.00 does not equal £10.00, and an exchange whose equality is approximate cannot implement price priority at all — quite apart from being much slower as a sorted-map key.

And a refinement worth naming rather than implementing. Real instruments trade across a small band of prices near the current one, so the sorted map is often replaced by an array indexed by the offset from a reference price. That turns a logarithmic lookup into an array index, at the cost of memory and a rare, expensive rebase when the price moves far. It is the right optimisation for a real engine and the wrong one to reach for first.

AppliedWalk the matching loop with real numbers, including where the trade price comes from and what a partial fill leaves behind.

The book before anything arrives:

Bids		Asks
£10.00	400	£10.02	150
£9.99	1,200	£10.03	700

The best bid is £10.00, the best ask is £10.02, and the spread is 2p. Nothing is trading, which is the normal resting state.

A buy order arrives: 400 shares, limit £10.03.

First pass. The best opposite level is £10.02, and £10.02 ≤ £10.03, so it crosses. The head of that level has 150 remaining. min(400, 150) is 150, so 150 trade at £10.02. The incoming order has 250 left, the level is now empty and is removed from the sorted map.

Second pass. The best ask is now £10.03, which still crosses the limit of £10.03 — the comparison is at-or-better, so an exact match trades. The head there has 700. min(250, 700) is 250, so 250 trade at £10.03. The incoming order is now fully filled, and the resting order at £10.03 has 450 left and keeps its place at the head of the queue.

Third pass. Remaining is zero, the loop exits, and nothing rests.

The result is two trades from one order: 150 at £10.02 and 250 at £10.03, an average of £10.026 25.

Now the price rule, which is the part of this that surprises people. Both trades happened at the resting order's price, never at the incoming order's limit. The buyer was willing to pay £10.03 for all 400 and paid less for 150 of them. That difference is called price improvement and it goes to the buyer, because the person who was resting on the book set the price — they advertised a willingness to sell at £10.02 and that is what they get. An engine that charged the buyer their full limit and kept the 3p would be taking money from participants on every crossing trade, which is not what an exchange is for.

What the partial fill leaves behind matters as much as the trade. The resting order at £10.03 now shows 450 instead of 700, and it is still at the front of that level's queue. Its time priority is untouched, because it did not do anything — it was filled against. This is the counterpart to the amendment rule: priority is lost by the actions you take, not by things happening to you.

Two trades, not one averaged trade. The engine publishes both, each with its own price, quantity and sequence number. Reporting a single fill of 400 at £10.02625 would destroy information that several parties need: the two sellers were different people, the two trades happened at different prices, and every downstream report — the broker's confirmation, the regulator's record, the public tape — is built from individual trades. The client's screen may show one order with an average price, and that is a display decision computed from the trades rather than a decision made in the engine.

Finally, the two ways the loop stops are worth naming explicitly because they are the whole control flow. Either the incoming quantity reaches zero, or the best opposite level stops crossing. Everything else — partial fills on either side, sweeping multiple levels, resting the remainder — falls out of min(remaining, resting.remaining) and the loop condition. There is no special case for any of it, and a design that needs one has usually put the priority rule in the wrong place.

InterviewWhy is the matching engine single-threaded, and what would break if it were not?

Start with the requirement, because the threading decision is a consequence rather than a preference. An exchange must be deterministic: the same inputs in the same order must produce exactly the same trades, every time. Three separate needs depend on that.

Recovery. The engine is recovered after a crash by replaying its input log. If replay can produce different trades from the original run, the recovered exchange disagrees with the trades it already published, and there is no way to reconcile them.

The standby machine. A second engine consumes the same inputs so it can take over instantly. It is only useful if it holds an identical book, which requires identical processing.

Explaining a fill. Two years later, someone asks why Ana was filled and Ben was not. The answer must be reconstructible from the record, and "the scheduler happened to run Ana's thread first" is not an answer anyone will accept.

Concurrency inside the matching of one book destroys all three, because the outcome becomes a function of thread scheduling, which is neither reproducible nor explainable.

So the shape is one thread per book, behind a sequenced queue:

interface SequencedInput {
  sequence: bigint;
  receivedAt: Instant;
  payload: NewOrder | CancelOrder | AmendOrder;
}

function step(book: Book, input: SequencedInput): { book: Book; events: Event[] }

The sequencer defines "first" for the whole exchange, and it is deliberately not a clock. Clocks on different machines disagree, drift, and occasionally move backwards, so two orders can carry timestamps that make the wrong one earlier. A single counter cannot do any of that. The clock is kept for humans and for reports; the sequence is what correctness rests on — the same separation the auction makes in 9.7.20, promoted here from a tie-break to the primary mechanism.

The engine has to be a genuinely pure function, and this is a real constraint on the code rather than a description of its style. No reading the clock, no random numbers, no network calls, no database lookups. A single Date.now() inside the matching logic makes replay produce different timestamps, and if any decision depends on that value, different trades. Anything time-dependent is stamped by the sequencer on the way in and passed through as data.

What would break without the single thread, specifically:

Price-time priority becomes unprovable. Two threads matching against the same level can interleave so that a later order is filled first, and the record will not show why.

Fill-or-kill becomes a race. It works by summing available quantity and then matching, which is a check-then-act sequence. With one thread, nothing can change in between, so it is safe. With two, another order can consume the quantity between the check and the act, and a fill-or-kill either fills partially — which is precisely what it must never do — or needs a lock over the whole book, which is the single thread again with extra steps.

The book itself needs locking. Levels merge, empty and are removed; nodes are unlinked. Doing that safely under concurrency means locks, and the lock over the hot part of the book is exactly the serial section you were trying to avoid. The parallelism was never real.

Where the parallelism actually is, and why the single thread is fast enough. Books are completely independent, so different instruments run on different threads with no coordination at all — which scales in the dimension that actually grows. Everything around the engine is parallel: decoding messages, risk checks, writing the input log, publishing market data, calculating fees. The serial part is only the matching, and matching is a few pointer operations on in-memory structures with no input or output at all. A single core does millions of those a second, which is why the highest-performance exchanges in the world are built this way rather than despite it.

Durability without slowing the loop. The sequenced input log is written before the engine sees each input. A crash is recovered by replaying it into a fresh engine, so nothing about the book needs to be written synchronously — the book is entirely derivable from the inputs. Snapshots exist only to make replay shorter. This is the strongest possible case for event sourcing: the state is a fold over an ordered log, the log is small and append-only, and the fold is deterministic by construction.

StaffA large sell order triggers a hundred stop orders, which trigger more. Show what the design does, and what protects the market from the cascade.

Stops are not on the book, and that is the first thing to establish. A stop order is an instruction held aside — "if the price reaches £9.50, submit a sell" — and it is invisible to every participant until it fires. It lives in a separate structure keyed by trigger price, with sell stops ordered so that the highest triggers first on a falling market and buy stops the mirror image.

class StopBook {
  private sellStops = new SortedMap<Price, StopOrder[]>(descending);
  private buyStops  = new SortedMap<Price, StopOrder[]>(ascending);

  triggeredBy(tradePrice: Price): StopOrder[] { /* all stops at or through it */ }
}

A trade is what fires them. After each trade, the engine asks which stops the trade price has reached. On a large sell sweeping down through several levels, that can be a hundred stops at once.

The critical decision is where those triggered orders go, and there is a clearly right answer. They are fed back through the same sequenced input queue as everything else, and processed after the current input finishes. They are not matched recursively inside the current match.

Three things follow from that, and each is a real failure the design avoids:

The ordering stays defined. Every triggered order gets its own sequence number and appears in the log exactly like an order from a participant. The record shows what fired what, in order, and it replays identically.

The recursion is bounded. A cascade becomes a longer queue rather than a deeper stack. A hundred stops that trigger fifty more that trigger twenty more is three passes through a loop, not three levels of recursion inside a matching function that was never designed for it.

The engine stays a pure step function. step(book, input) still returns new state and events. A triggered stop is one of those events, routed back in, which keeps the model intact.

Now the market problem, which is the real subject of the question. The cascade is genuinely dangerous: sells trigger stops, which are more sells, which push the price lower, which trigger more stops. This is how a market falls a long way in seconds with no news at all, and no engine-level cleverness fixes it, because the engine is doing exactly what it was told. The protections are policy, and they sit in defined places:

Price collars on market orders. A market order will not trade beyond a band around the current price, and the remainder is cancelled rather than filled at any price. This is what stops one large market order emptying a thin book down to absurd prices, and it is not optional on any real exchange.

Price bands per instrument. Orders priced outside a permitted band are rejected before they reach the engine — one of the risk checks that lives outside precisely so it can be reconfigured during the day.

Circuit breakers. If the price moves more than a set percentage within a set window, trading in that instrument halts for a few minutes. The halt is a state change on the book: new orders are accepted or rejected by policy, no matching occurs, and the stop structure does not fire. Then the restart is its own designed event, usually an auction — a period where orders accumulate without matching, followed by a single calculation of the one price that trades the most volume. Restarting straight back into continuous matching would let the same cascade resume at the moment the halt lifts.

Stops triggering as limit orders rather than market orders. A stop that becomes a market order fills at whatever is there. A stop that becomes a limit order at a stated price will not sell into the collapse below that price, and it rests instead. Many venues have moved to this as the default, and knowing that is a strong detail.

The design consequence worth naming. The halt is a property of the book, checked in one place at the top of the step function, and the halted state must reject and accept the right things — cancels, in particular, must still be accepted during a halt, because a participant with an exposed resting order that cannot be withdrawn during a market event is being held hostage by the venue. That single rule is easy to miss and very unpopular when it is missing.

What I would monitor. The rate of stop triggers per second, which is the early signal of a cascade before the price shows it; the depth of the input queue, since a cascade shows up as a queue that stops draining; the count of market orders cancelled by the collar, which says the book has become too thin to absorb what is arriving; and the time from the last trade to the market data publish, because a feed falling behind during exactly this event is how participants end up trading against a picture of the past.

Flashcards

FlashPrice-time priority

Better price first; at the same price, earlier first. It is the only allocation rule that is both explainable to the person who lost and impossible to game except by being better or faster.

FlashWhy not a heap

Cancelling dominates trading on a real exchange, and cancelling in a heap is a scan. Use a sorted map of price to level, a FIFO linked list inside each level, and an identifier-to-node index with a back-pointer to the level.

FlashWhich price does the trade happen at

The resting order's price. A buy limited at £10.05 hitting a resting ask at £10.02 trades at £10.02, and the buyer keeps the difference. The one who was there first set the price.

FlashWhat an amendment costs

Reducing quantity keeps time priority; increasing it or changing price sends the order to the back of the level. Otherwise a trader queues with one share and grows it to a million just before the fill.

FlashOne thread, on purpose

Determinism is required for replay, for the standby engine and for explaining a two-year-old fill. Thread scheduling is not reproducible, so matching is single-threaded per book, behind a sequencer, as a pure function with no clock and no input or output.

FlashWhere triggered stops go

Back through the same sequenced input queue, never matched recursively inside the current match. The ordering stays defined, the cascade becomes a longer queue rather than a deeper stack, and collars, price bands and circuit breakers are what actually protect the market.

Next: 9.7.26 — music streaming and live scores, two problems that look unrelated and are both about pushing a changing value to people who joined at different times.