--- title: "Build: A Matching Engine and Exchange Simulator" book: "Microstructure and Execution" subject: quant language: en chapter: 26 exercises: 8 source: https://one-course.com/books/quant/10/en/chapter/26-build-a-matching-engine-and-exchange-simulator --- # Chapter 26 — Build: A Matching Engine and Exchange Simulator Every tutorial in the books that follow needs a venue: something that accepts orders, matches them, publishes what happened in a feed that can drop packets, and does exactly the same thing every time it is run with the same inputs. This chapter describes the one this book has used since chapter 1, `firm.exchsim`: what an exchange does, in messages; the [matching engine](https://one-course.com/books/quant/10/en/chapter/1-the-limit-order-book#def-mx-the-limit-order-book-engine); the feed and its recovery; the [order-entry sessions](#def-mx-build-a-matching-engine-and-exchange-simulator-oe); and the clock that makes it deterministic. It then certifies it: the conformance suite, the byte-identity of its three engines, and their speed on this laptop. ## 26.1 What an exchange does, in messages **Definition 26.1 (Exchange simulator).** An *exchange simulator* is a program that behaves toward its participants as a venue does: it accepts and acknowledges orders through [order-entry sessions](#def-mx-build-a-matching-engine-and-exchange-simulator-oe), matches them by the venue’s rules, and publishes the resulting [order-book events](https://one-course.com/books/quant/10/en/chapter/1-the-limit-order-book#def-mx-the-limit-order-book-event) in a sequenced market-data feed, with the latencies, losses and failures of a real connection, and with results that depend only on its inputs. **Definition 26.2 (Order-entry protocol, order-entry session, execution report).** An *order-entry protocol* is the message set a participant uses to send, modify and cancel orders and the venue uses to answer. An *order-entry session* is one logged-in connection that carries it, with its own sequence of messages, limits and state. An *execution report* is the venue’s message on that session about one order: accepted, executed (partly or fully), cancelled, rejected, replaced. `firm.exchsim` speaks four binary protocols, all generated from one table, `MESSAGES` in the codec module, with a machine-readable copy in `schema.json` from which One Quant Book 13 builds its codecs. The *feed* has fourteen message types in an ITCH-like layout (Book 1’s add, execute, cancel, delete and trade messages byte for byte, plus replace, execute-at-price, cross, imbalance, system event, trading action, stock directory, snapshot header and trailer); order entry has five (new order, replace, cancel, mass cancel, mass quote); [execution reports](#def-mx-build-a-matching-engine-and-exchange-simulator-oe) six (accepted, executed, cancelled, rejected, replaced, system); and a control protocol of ten messages drives the venue (system events, logins and drops, phases, bands, indicatives, crosses, cut-offs, expiries, reference quotes). `PROTOCOL.md` gives every rule; Nasdaq’s TotalView-ITCH 5.0 specification is the model for the feed (big-endian integers, a stock locate at the same place in every message, nanosecond timestamps since midnight). A client’s day, in process (`mx_exchsim.scenario`), shows the reports: a buy of 300 at 100.00 is accepted; a sell of 100 at 100.00 from the same session trades against it ([self-trade prevention](#def-mx-build-a-matching-engine-and-exchange-simulator-stp) is off for this session) and both sides get an execution; an immediate-or-cancel sell of 500 at 99.99 executes 200 against the rest and its remaining 300 are cancelled with reason “I”; a post-only buy of 200 at 100.02 rests; a sell of 100 at 100.01 executes against it at 100.02; a buy at 100.015 is rejected as off the tick grid (“X”); a cancel of the already-filled sell is rejected as too late (“L”); at the end of the day the post-only order’s last 100 shares expire (“E”). ## 26.2 The matching engine The engine (`firm_exchsim_engine`) keeps one book per instrument (chapter 1’s `firm.lob`) and applies chapter 2’s order types through `firm.ordertypes`: limit and [market orders](https://one-course.com/books/quant/10/en/chapter/1-the-limit-order-book#def-mx-the-limit-order-book-orders), immediate-or-cancel and fill-or-kill, post-only, hidden and [iceberg orders](https://one-course.com/books/quant/10/en/chapter/2-order-types-and-their-uses#def-mx-order-types-and-their-uses-hidden), midpoint and primary pegs, stops, minimum quantities, and [self-trade prevention](#def-mx-build-a-matching-engine-and-exchange-simulator-stp). **Definition 26.3 (Self-trade prevention, cancel on disconnect).** *Self-trade prevention* stops two orders of the same participant (or group) from trading with each other, by cancelling the resting order, the incoming one, both, or decrementing them. *Cancel on disconnect* cancels a session’s resting orders when the session is lost. Matching gives price priority, then allocates a [price level](https://one-course.com/books/quant/10/en/chapter/1-the-limit-order-book#def-mx-the-limit-order-book-tick) by its rule: first in, first out (price-time priority, Book 1, chapter 19), or pro rata with an optional top-order share (Book 1’s `firm.match`); it stops at a price band (chapter 25) and at the order’s limit. ```python if r.min_qty and rem < r.min_qty: continue elig.append(r) if not elig: if len(st.book.level_orders(opp, p)) == len(level): break # nothing executable: next price continue # STP removed some: look again if st.matching == "F": alloc = [] left = rem for r in elig: f = min(r.qty, left) alloc.append((r, f)) left -= f if left == 0: break else: book = [Resting(str(i), r.qty, False, r.top) for i, r in enumerate(elig)] got = configurable(book, rem, st.top_pct, 0, st.fifo_pct, st.min_alloc) alloc = [(r, got.get(str(i), 0)) for i, r in enumerate(elig)] for r, f in alloc: if f > 0: rem -= f self._execute(st, r, o, f, p, rem) return rem ``` ***Listing 26.1.** The allocation of one price level in the engine: the eligible resting orders (minimum quantities respected), filled in time order for price-time priority or by Book 1’s configurable pro-rata rule, each fill an execution at the resting price. code/firm/exchsim/firm_exchsim_engine.py* Phases come from a schedule: pre-open and opening call, continuous trading or [frequent batch auctions](https://one-course.com/books/quant/10/en/chapter/10-auction-mechanics-and-theory#def-mx-auction-mechanics-and-theory-fba) (chapter 10), closing call and auction, halts and pauses with reopening calls (chapter 25’s `firm.halts` policies act through the same controls), all uncrossed by chapter 10’s auction (`firm.auctionsim`). Throttles limit each session’s message rate with a token bucket; fees are charged per execution by liquidity flag. ## 26.3 The market-data feed: sequencing, redundancy, recovery **Definition 26.4 (Redundant feed lines, snapshot recovery, retransmission request).** *Redundant feed lines* carry the same sequenced packets twice, on separate paths, so that a receiver can take each packet from whichever line delivers it first. *Snapshot recovery* rebuilds a book from a periodic snapshot of its state, tagged with the last incremental sequence number it includes, followed by the incremental messages after it. A *retransmission request* asks the venue’s recovery service for messages by sequence number. The feed travels in MoldUDP64 packets (a session name, the sequence number of the first message, a message count; a count of zero is a heartbeat) on two lines, A and B, each with its own impairments drawn from counter-based random streams: independent loss, bursts of loss by a two-state Gilbert–Elliott channel, duplication, jitter, outages. CME’s MDP 3.0 documentation describes the same practice: process both feeds, take each sequence number from whichever arrives first, and treat a gap on both as loss that needs recovery; its snapshot messages carry the last incremental sequence number processed so that a receiver can splice the two. Ten minutes of Book 7’s synthetic tape through the venue (`mx_exchsim.recovery`), with bursts of loss drawn independently on each line and a ten-second outage on line B: of 5 793 messages, line A lost 308 and line B 517 (166 of them in the outage); taking each message from either line left 30 missing, and 30 [retransmission requests](#def-mx-build-a-matching-engine-and-exchange-simulator-feed) filled them, so the receiver had every message. A snapshot from the middle of the day (the venue took one every 30 seconds) plus the incremental messages after it rebuilt a book identical, ten levels deep on each side, to the engine’s own. ```python gaps = [s for s in range(1, last + 1) if s not in got] requests = 0 for s in gaps: pk = res.retransmit("", s, 1) requests += 1 got[s] = mold_parse(pk[0])[3][0] ``` ***Listing 26.2.** Line arbitration’s leftovers: the sequence numbers neither line delivered, each asked of the retransmission service, whose MoldUDP64 packet carries the missing message. code/microstructure/26-build-a-matching-engine-and-exchange-simulator/python/mx_exchsim.py* ## 26.4 The order-entry protocol and its sessions Participants connect through sessions: an agent in process has one per venue with its own latency model (entry, acknowledgement and data delays, jitter, spikes); a live client connects to the C++20 server on this machine over SoupBinTCP, Nasdaq’s point-to-point session protocol over TCP (login with a requested sequence number, sequenced data, heartbeats), and receives the feed by loopback multicast. Sessions carry the venue’s rules: [cancel on disconnect](#def-mx-build-a-matching-engine-and-exchange-simulator-stp), self-trade groups, throttles, and client order identifiers numbered per session (a multi-venue agent must make its own unique across venues, as chapter 18’s router did). [Execution reports](#def-mx-build-a-matching-engine-and-exchange-simulator-oe) go only to the session that owns the order; the feed goes to everyone, a drop copy to whoever asks. ## 26.5 Clock, latency and determinism The simulator is a discrete-event loop on a simulated clock (One Quant Book 7, chapter 17): every message, timer and control is an event at a nanosecond time, and ties are broken by a fixed order of event classes and insertion. Every random number (latencies, feed impairments, the background’s flow) comes from a counter-based generator (One Quant Book 4, chapter 26) keyed by the seed and by what it is for, so that adding a participant does not change the random numbers any other one sees. Running the same two-minute day twice gives the same bytes: the SHA-256 of line A’s recording and of the engine’s journal agree (`f7ede7cfa7b3…`). The engine exists three times: the Python reference, a C++20 engine and a Rust engine. A shared fixture (four minutes of tape flow plus a chaos agent that sends every message type and every control: 17 059 journal records) is replayed by each, and each must reproduce the Python engine’s output, feed messages, reports and final snapshots, byte for byte. Measured on a laptop (Intel Core Ultra 7 155H) under WSL2, with no isolated cores, the Python engine processes the fixture at about 60 000 records a second; the C++20 test program (which also decodes and checks 4 866 golden messages and compares every byte) runs through it at more than 500 000 a second. The live C++20 server serves the same engine to clients on localhost. ## 26.6 Tutorial: certification day **Goal.** Trade on the simulator in process and through its server, recover a lossy feed, and certify the three engines. **End state:** the numbers of sections 1, 3 and 5. 1. **In process.** `Simulator(ExchangeConfig)` , an `Agent` with `on_report` ; `mx_exchsim.scenario()` . 2. **Feed.** `FeedConfig(burst_loss, outages, snapshot_every_ns)` ; `res.recorded(line)` , `res.retransmit(venue, seq, count)` , the snapshots; `recovery()` . 3. **Determinism and identity.** `determinism()` ; `code/firm/exchsim/cpp/exchsim_engine_test.cpp` and `cargo test` in `code/firm/exchsim/rust` on the fixture; `throughput()` . 4. **Live.** `code/firm/exchsim/cpp/build.sh` , then `bin/exchsim_server –config cfg.json` and a SoupBinTCP client ( `code/firm/exchsim/tests/test_serve.py` shows one in Python). **What to change next.** Add implied calendar-spread matching (chapter 21 priced it outside the engine); feed the simulator from chapter 27’s agents as a background; certify a fourth engine against the fixture. ## 26.7 Build: exchange simulator **Purpose.** The venue under every simulated market of Books 10 to 13: matching, phases and auctions, halts, fees, feeds, sessions. **Interface.** `ExchangeConfig(venue, instruments, fees, phases, halts, throttle, engine_ns, speed_bump_ns, batch_interval_ns, feed, faults, reference)`, `Simulator(venues, sip, seed)` with `add_background`, `add_agent`, `add_events`, `schedule_call`, `run`; `Result` with `tape`, `feed_messages`, `recorded`, `retransmit`, `snapshot_bytes`, `reports`, `sip`; presets; the C++20 engine, codec and server; the Rust engine and codec (contract: `code/firm/INTERFACES.md`, section 7). **Rules.** Big-endian binary messages generated from one table; prices in 1/10 000 of a currency unit; counter-based randomness keyed by purpose; no wall clock anywhere in the engine. **Acceptance tests.** `code/firm/exchsim/tests/`: thirteen engine-rule scenarios; codec round trips and the schema; Book 1’s decoder on the feed; determinism by hash; the Python engine against the fixture’s SHA-256; sequencing, loss and recovery; snapshot rebuild; agents and tape export; consolidated feed and dark venues; the C++20 and Rust engines byte-identical on the fixture; the Python and C++20 servers round trip. **Stretch.** Implied spreads; a FIX gateway; a second feed layout in Simple Binary Encoding. Sources and further reading - Nasdaq, TotalView-ITCH 5.0 specification; MoldUDP64 protocol specification; SoupBinTCP specification. - CME Group, MDP 3.0: incremental feed arbitration; market data snapshot full recovery (client systems wiki). - FIX Trading Community, Simple Binary Encoding. - E. N. Gilbert, “Capacity of a burst-noise channel”, *Bell System Technical Journal* 39(5), 1960. ## 26.8 Exercises **Exercise 26.1 ★.** A MoldUDP64 packet has sequence number 5 001 and a count of 12. What sequence number does the next data packet carry? **Solution of Exercise 26.1.** 5 013: the packet carries messages 5 001 to 5 012, and heartbeats carry the next expected number without advancing it. **Exercise 26.2 ★.** From the recovery run, what share of the messages did each line lose, and what share did both lose? **Solution of Exercise 26.2.** Line A 5.3% ($308/5\,793$), line B 8.9% ($517/5\,793$), both 0.52% ($30/5\,793$). **Exercise 26.3 ★.** In the scenario, why was the cancel at 7 seconds rejected, and what reason would a cancel of an unknown order get? **Solution of Exercise 26.3.** The order had already been filled (at 5 seconds), so there was nothing to cancel: reason “L”, too late to cancel. A cancel of an unknown order gets the same reason. **Exercise 26.4 ★★.** Why must each random stream be keyed by what it is for, not drawn from one generator in event order? **Solution of Exercise 26.4.** With one generator in event order, adding a participant or changing one’s timing shifts every later draw, so every other participant’s latencies and the feed’s losses change: comparisons between runs stop being like for like. Keyed counter-based streams give each purpose its own sequence. **Exercise 26.5 ★★.** Why does [snapshot recovery](#def-mx-build-a-matching-engine-and-exchange-simulator-feed) need the snapshot’s last sequence number, and what goes wrong without it? **Solution of Exercise 26.5.** To know which incremental messages the snapshot already contains: apply those after its sequence number and skip the ones before. Without it a receiver applies some messages twice or misses some, and the rebuilt book is wrong in ways that may not show at the top. **Exercise 26.6 ★★.** What does byte-identity of three engines on a fixture prove, and what does it not? **Solution of Exercise 26.6.** That the three engines agree on every message, report and snapshot for the fixture’s inputs, which exercise every message type and control. It does not prove that the rules are right (all three could share a misreading of a rule), nor that they agree on inputs the fixture does not contain. **Exercise 26.7 ★★★.** *Coding.* Run the recovery with line B’s outage but no burst loss on either line. How many messages does each line lose, and how many [retransmission requests](#def-mx-build-a-matching-engine-and-exchange-simulator-feed) are needed? **Solution of Exercise 26.7.** Line A loses nothing, line B loses the 166 messages of its outage, and no [retransmission request](#def-mx-build-a-matching-engine-and-exchange-simulator-feed) is needed: line A delivers every message. **Exercise 26.8 ★★★.** *Find the flaw.* “The C++ engine is eight times faster than the Python one, so the simulator’s sessions will run eight times faster in C++.” **Solution of Exercise 26.8.** The simulator’s time goes into agents, the event loop, the background and the feed’s packets, not only the engine; and the C++ number includes the program’s start-up and checks, so it is a lower bound on the engine alone. A session’s speed-up depends on how much of it is the engine. ## 26.9 Problem: Certification Day **Problem 26.1.** Weekend problem — certification day Before other teams rely on the simulator, it must be certified: rules, recovery, determinism, identity across implementations and speed. **Part I — Messages.** 1. Define an [exchange simulator](#def-mx-build-a-matching-engine-and-exchange-simulator-sim) , an [order-entry protocol](#def-mx-build-a-matching-engine-and-exchange-simulator-oe) , a session and an [execution report](#def-mx-build-a-matching-engine-and-exchange-simulator-oe) . 2. List the four protocols and their message counts. 3. Walk through the scenario’s reports. 4. Define [self-trade prevention](#def-mx-build-a-matching-engine-and-exchange-simulator-stp) and [cancel on disconnect](#def-mx-build-a-matching-engine-and-exchange-simulator-stp) . **Part II — The engine.** 5. How does the engine allocate a [price level](https://one-course.com/books/quant/10/en/chapter/1-the-limit-order-book#def-mx-the-limit-order-book-tick) under each rule? 6. What stops matching? 7. Which phases can the venue be in, and what uncrosses a call? 8. How do `firm.halts` policies act on the venue? **Part III — The feed.** 9. Describe a MoldUDP64 packet and the two lines. 10. How are losses and outages drawn? 11. Give the recovery run’s losses, gaps after arbitration and retransmissions. 12. How was the book rebuilt from a snapshot, and how was it checked? 13. What does CME’s MDP 3.0 documentation recommend for its A and B feeds? **Part IV — Certification.** 14. What makes the simulator deterministic? 15. Describe the fixture. 16. *State the named result* : the conformance suite passed by each engine, the byte-identity of the three engines’ feeds on the fixture, and the engines’ messages per second on this laptop. 17. Why is the C++ number a lower bound on the engine’s speed? 18. Which parts of the simulator are not certified by the fixture? 19. What would you add before a live trading team used it? 20. In one sentence: why does a simulator need to be deterministic? **Solution of Problem 26.1.** **1.** See the definitions. **2.** Feed 14, order entry 5, [execution reports](#def-mx-build-a-matching-engine-and-exchange-simulator-oe) 6, controls 10 (plus SoupBinTCP’s own session messages). **3.** Accepted; a self-cross trade; an IOC’s 200 executed and 300 cancelled; a post-only order resting; an execution at the resting price; an off-grid rejection; a too-late cancel; an end-of-day expiry. **4.** See the definitions. **5.** Price-time: in time order at the level; pro rata: Book 1’s configurable allocation with a top-order share. **6.** The order’s limit, the price band, minimum quantities, [self-trade prevention](#def-mx-build-a-matching-engine-and-exchange-simulator-stp). **7.** Pre-open and opening call, continuous trading or batch auctions, closing call, halted, paused (reopening call); leaving a call uncrosses it. **8.** Through the controls R (band) and P (phase), called at scheduled times. **9.** Session, first sequence number, count, then messages; A and B carry the same packets. **10.** From counter-based streams keyed by line: independent loss, Gilbert–Elliott bursts, duplicates, jitter, outages. **11.** Line A lost 308 of 5 793 messages, line B 517; 30 were missing on both; 30 [retransmission requests](#def-mx-build-a-matching-engine-and-exchange-simulator-feed) filled them. **12.** A mid-day snapshot’s orders, then the incremental messages after its sequence number; compared with the engine’s book ten levels deep. **13.** Process both feeds, take each sequence number from whichever arrives first, and recover gaps on both. **14.** A simulated clock, fixed tie-breaking, counter-based randomness keyed by purpose, no wall clock in the engine. **15.** Four minutes of tape flow plus a chaos agent sending every message type and control: 17 059 journal records. **16.** *Named result*: the Python engine passes the thirteen engine-rule scenarios and reproduces the fixture’s SHA-256; the C++20 and Rust engines reproduce the Python engine’s output on all 17 059 fixture records byte for byte (and round-trip 4 866 golden messages); on this laptop the Python engine processes about 60 000 records a second and the C++20 test program more than 500 000. **17.** It includes the program’s start-up, decoding and byte comparisons. **18.** The agents, the latency models, the feed impairments and the live servers’ timing. **19.** Implied spreads, a FIX gateway, venue-specific rules checked against each venue’s documents. **20.** So that a difference between two runs can only come from a difference in their inputs. ## 26.10 Interview questions **Interview question 26.1 ★ developer.** How does a feed handler recover from a gap in a UDP multicast feed? **Solution of Interview question 26.1.** Arbitrate the A and B lines by sequence number; on a gap on both, buffer later messages and request the missing ones from the retransmission service; if the gap is too old, rebuild from a snapshot and apply the messages after its sequence number. *What the interviewer is looking for: Arbitration, retransmission, snapshots.* **Interview question 26.2 ★★ developer.** Design a [matching engine](https://one-course.com/books/quant/10/en/chapter/1-the-limit-order-book#def-mx-the-limit-order-book-engine)’s data structures for price-time priority with fast cancels. **Solution of Interview question 26.2.** A map from price to level (a sorted structure or an array indexed by ticks), each level a FIFO of orders, and a hash from order reference to its node so a cancel is O(1); keep the best prices cached. *What the interviewer is looking for: Levels, FIFO, reference index.* **Interview question 26.3 ★★ developer.** How would you make a market simulator reproducible to the byte, including its randomness? **Solution of Interview question 26.3.** A discrete-event loop on a simulated clock with deterministic tie-breaking, counter-based random streams keyed by purpose, no wall-clock or hash-order dependence, and a journal of every input; test by hashing outputs of repeated runs. *What the interviewer is looking for: Clock, randomness, ordering, testing.* **Interview question 26.4 ★★ trader.** Your IOC order was partly filled and the rest cancelled. What reports do you receive, in what order? **Solution of Interview question 26.4.** An acceptance, one execution per fill (with the quantity left), then a cancel for the remainder with the IOC reason; the feed shows the executions against the resting orders. *What the interviewer is looking for: Report sequence; leaves quantity.* **Interview question 26.5 ★★ risk.** Why do venues offer [cancel on disconnect](#def-mx-build-a-matching-engine-and-exchange-simulator-stp) and [self-trade prevention](#def-mx-build-a-matching-engine-and-exchange-simulator-stp), and what risks does each control? **Solution of Interview question 26.5.** [Cancel on disconnect](#def-mx-build-a-matching-engine-and-exchange-simulator-stp) prevents stale orders from trading while a participant cannot manage them; [self-trade prevention](#def-mx-build-a-matching-engine-and-exchange-simulator-stp) prevents wash trades between a firm’s own strategies and the fees and reporting problems they cause. *What the interviewer is looking for: Stale orders; wash trades.* **Interview question 26.6 ★★★ developer.** Two implementations of the same engine disagree on one message out of a million. How do you find out which is wrong? **Solution of Interview question 26.6.** Replay the journal to the first record whose output differs, decode both outputs, read the rule in the specification, and write a minimal scenario that reproduces it; add it to the fixture so the three engines are held to it. *What the interviewer is looking for: Bisection on the journal; a new test.*