29 — Design A Stock Exchange

An electronic exchange is the computer system that stands between everyone who wants to buy a share of a stock and everyone who wants to sell one, pairs them off, and announces every resulting price change to the whole market.

This chapter builds one end to end, in four pieces:

• The structure that stores orders which have not yet found a counterparty.
• The single-threaded loop that pairs them.
• The numbering service that decides whose order arrived first.
• The broadcast that reaches all subscribers at the same instant.

It derives the round-trip delay budget of 11.55 microseconds line by line, and explains why the design uses only one processor core per stock.

Exchange vocabulary is defined before it is used, and every constant is either derived on the page or named where it came from.

What goes in

The input is a stream of small fixed-size binary messages sent by members — the banks, brokers and trading firms licensed to trade on the venue.

Each message says one of three things: place this order, cancel that order, or replace that order with this one. An order is an instruction such as “buy 500 shares of AAPL at $100.00 or better”.

What comes out

Two streams come out, and both are views of the same events.

The member who sent an order receives execution reports addressed only to them: accepted, partly filled, filled, cancelled, rejected. Nobody else sees these.

Anyone who subscribes receives the market data feed, a public broadcast of every change to the visible pool of unmatched orders. It carries no member identities at all.

The vocabulary, defined once

The terms below are used throughout the chapter and defined here.

The book and the orders in it

• An order book — or just the book — is the collection of orders that have arrived and not yet been paired off, one book per stock, with the buyers sorted dearest-first and the sellers sorted cheapest-first. An order sitting in the book waiting for a counterparty is resting.
• A bid is a resting buy order and its price. An offer is a resting sell order and its price. Offer and ask mean the same thing, and both appear below — including in this chapter’s code, where the comment on self.best reads best bid idx, ask idx.
• A quote is a bid and an offer posted together by the same firm. A market maker is a firm that continuously posts quotes in a symbol and earns the gap between its buy price and its sell price. Market makers generate most of the message traffic, because moving a quote means cancelling the old order and adding a new one.
• A limit order names the worst price its sender will accept (“buy at $100.00 or less”) and rests in the book if nothing on the other side is cheap enough right now. A market order names no price at all: it takes whatever the book is offering and never rests.
• A price level is one price together with the FIFO queue of resting orders at it. A book is therefore a sorted array of price levels, each holding a queue.

Matching

• The matching engine is the program that reads each arriving order and pairs it against the resting orders on the opposite side. A successful pairing is a fill — a quantity of shares changing hands at one price. A single incoming order can produce many fills.
• An arriving order crosses when its price overlaps the best price on the other side, so it can trade immediately. An order that does not cross is non-crossing and simply rests. An order large enough to trade through several price levels at once sweeps them.
• The arriving order is the aggressor; the order it trades against was already resting. Liquidity is the quantity available to trade right now — the total sitting in the book — so an order that sweeps three levels has consumed the liquidity at those levels.
• Price-time priority is the pairing rule the exchange sells as its product: among resting orders the best price is served first, and among several orders at the same price the one that arrived earliest is served first. That second half is a plain FIFO queue — first in, first out, the same discipline as a supermarket till line.

The properties the design is built to protect

• The sequencer is a single process that stamps every accepted message with a strictly increasing number and a timestamp before anything else sees it. That number, rather than the physics of the network, is the official arrival order.
• Determinism means that feeding the same numbered messages through the same program twice produces byte-for-byte identical results, always. It is what lets a regulator reconstruct any instant of any trading day from the log, and what lets a spare machine be trusted to take over mid-session.
• Latency is the delay between an event and the response to it. Jitter is how much that delay varies from one message to the next. An exchange is judged on both, and the second one is harder.

How to read the arithmetic blocks

Every number in this chapter is derived in a plain-text block that looks like this:

label for the input, with its unit                        300
another input                                            1.47
label for the result, with its unit
  300 / 1.47                             =  204

A line with a number on the right and no arithmetic is an input — an assumption or a hardware constant. A line whose next line is indented and contains = is a result: the indented line shows the substitution, so you can redo it yourself. Every input is either stated on the line, derived earlier in the chapter, or taken from the hardware table in Latency numbers and what each one forbids.

Two abbreviations appear throughout the blocks and are not spelled out inside them. us means microseconds (µs), a millionth of a second. ns means nanoseconds, a billionth of a second, a thousand to the microsecond. The matching step is measured in hundreds of nanoseconds; the round trip it sits inside is measured in tens of microseconds.

The shape of the argument

Correctness here is assumed rather than achieved: an exchange that pairs the wrong two orders is not a slow exchange, it is not an exchange.

The hard part is being exactly right inside a budget of 11.55 microseconds, derived in Deep dive 3 the latency budget in microseconds. Correctness and latency pull against each other on every line below.

Three ways candidates lose this round

All three are the same mistake: importing a habit from a system whose binding constraint was different.

1. They thread the matching engine to get more throughput. 7b why threading the engine is a trap prices it: 23% faster at eight threads, and determinism gone — the one property the exchange actually sells.
2. They write the market data feed as a loop of individual network writes, one per subscriber. Deep dive 5 market data fanout and why tcp unicast fails shows that leaves the 500th subscriber 500 microseconds behind the first, which is 43 times the entire internal budget.
3. They put the order book in a database. A durable row update costs roughly 100 microseconds (Alternatives rejected) against a 1-microsecond matching step — a hundred times over, before the first query has even been parsed.

Two ideas borrowed from other chapters

Both are restated in a sentence here so this chapter stands on its own; neither needs to be read first.

• The hardware latency table. How long a main-memory read, a solid-state disk seek, or a cross-country network round trip takes. Every microsecond figure below traces back to it. Full table: Latency numbers and what each one forbids.
• The append-only log. A file you may only add to, never edit, where each entry has a permanent position number called an offset, so any number of readers can independently replay the same entries in the same order from any point. Developed at length in Why a log beats a queue 328 devices or one.

1. Framing: what decision, and what breaks

An exchange has four properties it is not allowed to trade away, and each one forbids a technique that is standard practice everywhere else.

An exchange is a deterministic state machine wrapped in a network. A state machine is a program whose entire output is decided by its current state plus the next input, with nothing else allowed to influence it.

The state machine itself is trivial: a sorted book and a matching rule that a bright teenager can implement in an afternoon.

Everything hard lives in the wrapper. You must impose a single agreed order on messages that arrive in parallel, copy that order onto backup machines without adding delay to it, and tell five hundred parties the outcome simultaneously.

The four properties, and what each one forbids

In the right-hand column, each forbidden technique is normal, sensible engineering somewhere else and off the table here.

Four terms in that table need pinning down before they do any work:

• p99.9 is the 99.9th percentile: the delay that only one message in a thousand exceeds. It is how bad the rare slow case gets.
• A C-state is a power-saving idle mode a processor core drops into when it has had nothing to do. Climbing back out of one costs tens of microseconds.
• Garbage collection is the pause a language runtime such as Java’s or Go’s takes to reclaim memory nobody is using any more. The pause is invisible in most systems and fatal in this one.
• An ack, short for acknowledgement, is the exchange’s promise back to the member that their order now exists and will be honoured. That is why a lost acked order is a legal problem rather than an operational one.

The one sentence to memorise

“The matching engine is a single-threaded deterministic state machine per symbol, the sequencer’s log is the exchange’s state, and everything else in the design exists to feed that log or to fan out what it emits.”

A symbol is the short ticker code identifying one tradable stock, such as AAPL. It is the unit everything in this design is partitioned by, so it is worth noticing that the sentence says per symbol rather than per exchange.

What actually breaks in production

Three things, and every one of them is a burst rather than a steady load. That matters, because a system sized for the average handles none of them.

1. The opening auction. The once-a-day event where every order accumulated overnight is released at once to establish a starting price. It delivers the whole backlog in about a second, into queues that were quietly sized for the daily average.
2. One dropped packet on the broadcast feed. All 500 subscribers notice the gap at the same instant and all 500 request the missing data at the same instant.
3. A member’s algorithm falls into a loop, cancelling and re-placing the same order forever, and consumes an entire entry point on its own.

2. Requirements

What the system must do matters less than the seven targets it must hit: the targets decide every structural choice later, and the feature list barely does.

Functional

The exchange must accept four kinds of new order, plus cancel and cancel-replace, and the four kinds differ only in what happens to the part of an order that could not be filled immediately:

• A limit order rests the unfilled remainder in the book at its stated price.
• A market order takes whatever is available at any price and discards the remainder.
• An immediate-or-cancel order, abbreviated IOC, fills whatever it can right now and cancels the rest instead of resting it.
• A fill-or-kill order, abbreviated FOK, fills the entire quantity in one go or does nothing at all and leaves the book untouched.

All four are the same matching rule with different remainder handling, and Deep dive 2 the array of price levels derived implements them as such — including what a market order does against a completely empty book, which is the case a requirements list never mentions and an exchange has to answer anyway.

The remaining functional requirements are these:

• Match by price-time priority: best price first, and within a price, earliest arrival first.
• Send execution reports to the order’s owner: acknowledged, partially filled, filled, cancelled, rejected.
• Publish market data at three levels of detail, described below.
• Run pre-trade risk checks, meaning checks applied to every order before it can trade rather than after: per-order size limits, per-account exposure caps, price bands that reject obviously mistyped prices, and self-trade prevention so one member cannot match against itself.
• Run opening and closing auctions, and enforce halts (trading in a symbol stops entirely) and limit-up/limit-down bands (a price range outside which a symbol may not trade, which pauses runaway moves).

The three market-data levels get their own list because they are named constantly from here on and the names are not self-explanatory:

• L1 is just the best price on each side, called the best bid and offer or BBO — the highest price anyone is currently willing to pay and the lowest price anyone is willing to sell at.
• L2 aggregates: for each price, the total quantity resting there, without saying who owns it.
• L3 is every individual resting order. It is what a member needs to rebuild the exchange’s own book exactly.

(Unrelated warning, because the collision bites people: Deep dive 2 the array of price levels derived also talks about L1 and L2 caches, which are processor memories. Same letters, nothing to do with market data. The chapter says “L2 cache” whenever it means the hardware one.)

Three things are explicitly out of scope, and saying so out loud is part of the answer:

• Clearing and settlement — the separate, slower system that actually moves shares and cash between accounts, typically one business day after the trade, which the industry writes as T+1. Different system, different clock.
• The smart order router, the logic that decides which of several competing venues to send an order to. That belongs to the member, not to the exchange.
• Options combination books, where a single order buys one contract while selling another. A real product, but it does not change anything that follows.

Non-functional — the rows that decide the design

These seven rows are what the design is accountable to. Every one of them is derived later in the chapter rather than asserted here, and the right-hand column says where.

Three terms from that table are used constantly from here on:

• Tick-to-trade is the round trip that matters commercially: the elapsed time from the moment a price change leaves the exchange, to the moment the member’s reaction to it has been matched and the result published again. It covers the exchange’s outbound leg, the member’s think time, and the exchange’s inbound leg. This chapter budgets the exchange’s two legs.
• p50 is the median: half of all messages are faster than it. Both percentiles are quoted because the design has to hit both, and the second one is what the architecture is actually shaped by.
• Colocated means the member’s own machine is racked inside the exchange’s building. It is a service the exchange sells, and the reason it can be sold is derived in 9e why colocation is not an optimization.

3. Back of the envelope

Two facts carry the rest of the design: the peak message rate fits comfortably on a single processor core, and broadcasting market data separately to each subscriber would need 188 gigabits per second of network capacity against 376 megabits for the alternative. Both findings remove options rather than add them.

Sizing the day

Turn the assumptions into three daily totals. The average message rate is needed first, because the peak is expressed as a multiple of it.

assume  3,000 symbols, a 6.5-hour continuous session,
        200,000,000 inbound messages/day (new, cancel, replace),
        20 inbound messages per trade, 500 market-data subscribers,
        and a 100-byte market-data message on the wire

seconds in the session
  6.5 x 3,600                            =  23,400
average inbound rate, msg/s
  200,000,000 / 23,400                   =  8,547
trades/day
  200,000,000 / 20                       =  10,000,000
market-data events/day, one per accepted message plus one per fill side
  200,000,000 + 2 x 10,000,000           =  220,000,000

Two lines in that block matter. Trades per day is inbound messages divided by 20, because the assumption is that it takes twenty order messages to produce one trade — nineteen of them are quote updates and cancels that never fill. And market-data events exceed inbound messages, because each accepted order produces one event and each trade produces two more (one for each side of the fill), giving 220 million events from 200 million messages.

From average to peak

The average does not size the system, because the workload is bursty.

The first second after the open carries the entire overnight order backlog. Measured opening bursts run 30 to 100 times the rest-of-session mean, so the design takes 50 times as the sizing figure — the middle of that range.

Multicast versus unicast, priced

The next block contrasts two ways of getting one message to 500 listeners:

• Unicast sends a separate, individually addressed copy to each listener. The sender does 500 times the work and pushes 500 times the bytes.
• Multicast sends exactly one copy addressed to a group. The network switches themselves duplicate the packet on the way out to whoever has joined that group, so the sender’s cost does not depend on how many listeners there are.

Two factors drive the arithmetic: the x 1.1 that scales the inbound peak into a market-data peak (the 220/200 ratio from the block above), and the x 500 that appears in the unicast line and nowhere in the multicast one.

peak inbound, msg/s
  8,547 x 50                             =  427,350
peak market-data rate, scaled by 220/200, events/s
  427,350 x 1.1                          =  470,085
one multicast copy, B/s
  470,085 x 100                          =  47,008,500
in Gbps
  47,008,500 x 8 / 1,000,000,000         =  0.376
TCP unicast to 500 subscribers, B/s
  470,085 x 100 x 500                    =  23,504,250,000
in Gbps
  23,504,250,000 x 8 / 1,000,000,000     =  188
machines at 1 Gbps each just to push bytes
  188 / 1                                =  188

376 megabits per second of multicast against 188 gigabits per second of unicast — a 500x difference, and it is only the second-worst thing about unicast (Deep dive 5 market data fanout and why tcp unicast fails has the first, which is a fairness problem rather than a capacity one).

The finding that reframes the chapter

The last block asks what one message costs the matching engine, and how many of those a single processor core can absorb in a second.

The 1-microsecond input is a rounding-up, not a measurement. 7b why threading the engine is a trap breaks the matching step into six pieces that sum to 470 nanoseconds; this section rounds that to 1 microsecond so the headline finding survives even if the real implementation is twice as slow as the breakdown claims.

cost of one message through the matching engine, us      1
messages per second per core
  1,000,000 / 1                          =  1,000,000
peak load as a fraction of one core
  427,350 / 1,000,000                    =  0.427

The entire market fits on 43% of one core.

There is no throughput problem. Every design decision below is therefore bought with latency or with variance rather than with capacity. That is what this estimate establishes: the problem is latency, not scale.

4. API sketch

The wire format — the exact bytes a member sends and the exact bytes that come back — embeds four choices a reviewer will question, and each is defended below.

Every message is binary with fixed offsets and no memory allocation. Unpack that phrase:

• Binary — the fields are raw integers, not text.
• Fixed offsets — each field always sits at the same byte position in the message, so reading a field is a pointer cast rather than a parse.
• No memory allocation — handling a message never asks the operating system for memory.

Order entry at the public edge of a real venue is often FIX, the Financial Information eXchange protocol: an industry-standard text format where each field is written as a numeric tag, an equals sign and a value. The internal representation below is deliberately not FIX, and the second bullet after the listing prices the difference.

The listing shows six message types in three groups: what a member sends inbound, what comes back to that member privately, and what goes out on the public feed. The field types carry the argument of this section.

NewOrder      { client_order_id u64, account u32, symbol u16, side u8,
                order_type u8, tif u8, qty u32, price i32 }   -- 32 B, fixed
Cancel        { client_order_id u64, orig_order_id u64, account u32 }
Replace       { client_order_id u64, orig_order_id u64, qty u32, price i32 }

ExecReport    { order_id u64, seq u64, exec_type u8, leaves u32,
                cum_qty u32, last_px i32, last_qty u32, ts_ns u64 }

-- market data, one multicast group per symbol partition
AddOrder      { seq u64, symbol u16, order_ref u64, side u8, px i32, qty u32 }
Executed      { seq u64, order_ref u64, qty u32, px i32, match_id u64 }
Cancelled     { seq u64, order_ref u64, qty u32 }

The type names. u32 means an unsigned 32-bit integer, i32 a signed one, u64 an unsigned 64-bit integer, and u8 a single byte. So side is one byte holding buy or sell, and qty is a whole number of shares. Every field is an integer; there is not a string or a float anywhere in the listing.

The field names that are not obvious. tif is time in force, the one byte that says which of the four remainder policies from Functional this order wants. leaves is the quantity still unfilled and resting. cum_qty is the quantity filled so far, and last_px/last_qty describe the most recent fill. On the market-data side, order_ref is the exchange’s public handle for one resting order — a number that identifies the order without identifying its owner, which is what lets a subscriber rebuild the book exactly while learning nothing about who is trading.

Four choices in that listing are worth defending explicitly, because a reviewer will ask about each one:

• Prices are i32 in ticks, never floating point. A tick is the smallest price increment the instrument trades in, one cent for a typical US stock, so a price of $100.02 travels the wire as the integer 10,002. The reason is not compactness. The decimal fraction 0.1 has no exact representation in binary floating point, so two implementations of the same matching rule can round in different directions and build two different books from one input stream. This is a determinism requirement, not a precision preference.
• Fixed offsets, so decoding is a cast. Parsing a 200-byte FIX tag-value message costs 1 to 2 microseconds because it means scanning text and splitting on delimiters, whereas reading fields at known byte offsets costs about 50 nanoseconds because the bytes are already in the layout the program wants. At the peak of 470,085 events per second the raw processor cost of parsing would actually be affordable — it is the 1.5 microseconds added to every single order that is not, because the entire matching step is 1 microsecond.
• seq is carried on every outbound message, market data and execution report alike. It is the sequencer’s number from Deep dive 4 the sequencer and the log that is the exchange, and putting it everywhere makes three separate problems into one mechanism: a subscriber detects a lost packet by noticing a missing number, replays history by asking for a range of numbers, and reconciles two redundant copies of the feed by matching numbers across them.
• ts_ns is a nanosecond timestamp assigned by the sequencer and merely carried, never read by the engine. An engine that asked the operating system for the time — the clock_gettime system call — would not be deterministic, because replaying the same log tomorrow would stamp different times and produce a different output stream.

5. Data model: the order book

The whole exchange is built around one data structure, and four of its six operations must complete in constant time — that is, in a number of steps that does not grow as the book gets bigger, written O(1).

The sketch below is a field layout, not code: it names what exists in memory per symbol and what exists once globally.

per symbol, per side:
  levels[]     array indexed by (price - base) / tick
                 head, tail   -- FIFO of resting orders at this price
                 depth        -- aggregate qty, maintained incrementally for L2
                 count        -- number of resting orders, for L2
  occupancy    one BIT per level, packed 64 to a word
  summary      one bit per occupancy word    -- 1,000 levels -> 16 words -> 1 word
  best         index of the best non-empty level, read off the two bitmaps

global:
  index        order_id -> pointer to the intrusive list node   (O(1) cancel)
  accounts[]   account_id -> risk state, pinned, array-indexed

The level array

For each symbol and each side there is a plain array of price levels. An array is a block of memory where slot number n is found by arithmetic rather than by searching, and here the slot number is how many ticks the price sits above a fixed base price. A $100.00 order in a book based at $95.00, at a one-cent tick, lands in slot 500.

Each slot holds the head and tail of a FIFO queue of resting orders, plus two running totals kept up to date as orders arrive and leave:

• depth — the total quantity resting at that price.
• count — the number of orders resting at that price.

Maintaining those two on every write is what makes publishing L2 market data free on the read. The alternative is walking a queue and adding up quantities every time somebody asks, on a structure that gets asked constantly.

The two bitmaps above it

A bitmap is an array of single bits used as a compact yes/no index. There are two here, stacked:

• occupancy holds one bit per price level, set when that level has at least one order in it, packed 64 bits to a machine word.
• summary holds one bit per occupancy word, set when that word is not all zeros.

For a 1,000-level book that is 16 occupancy words, summarised by a single word. Their purpose is to answer “what is the best non-empty price?” without ever scanning the array, and Deep dive 2 the array of price levels derived is where that pays off.

The two global structures

index maps an order id straight to the memory location of that order’s node inside its queue, so cancelling never has to search for the order it is cancelling.

accounts is an array of per-account risk state, pinned — meaning the memory is locked into physical RAM and can never be swapped out to disk — so a risk check is always a fast local read and never a disk access.

One word in that sketch that carries weight

Intrusive, in “intrusive list node”, means the linking pointers live inside the Order object itself rather than in separate container nodes allocated alongside it. Python’s list and C++‘s std::list do the opposite: they allocate a wrapper node per element.

It matters here for exactly one reason: adding an order to a queue allocates no memory at all. 7a what determinism costs on the hot path explains why allocation on this path is forbidden outright.

What each operation must cost

Each operation’s cost is a design constraint. The third column says why the cost has to be what it is. Four of the six rows say O(1).

Two of those rows carry the weight of the section, and both are about cancels.

Cancel must be O(1) because cancels are the traffic

At 20 inbound messages per trade, 19 of every 20 messages never result in a fill at all.

The overwhelming majority are quote updates: a market maker moving the price it is willing to trade at. On the wire that is a cancel followed by an add. So the single hottest operation in the whole exchange is a cancel.

A design whose cancel path walks along a price level looking for the right order is O(queue depth) on that hottest operation, where queue depth is however many other orders happen to be resting at that price. The index map is what avoids it: hash the order id, get the node’s address, unlink it.

The same demand applies to what a cancel leaves behind

Removing the last order at the best price makes the cached best index wrong. Something has to recompute it.

The obvious repair is to step along the array until an occupied level turns up. That repair is O(empty levels crossed), not O(1). And the number of empty levels crossed is set by how far the last quote happened to sit from the rest of the book — a quantity the exchange does not control and cannot bound.

Why walking the level array is on measured instruments this exact book and counts the reads. A walking repair does 501 array-slot reads to get back to an empty book after one add 500 ticks off the base and one cancel, and 999 steps on every cancel under a market maker quoting and requoting at the best price. The occupancy bitmap replaces the walk with two word operations, no matter what shape the book is in.

The bitmap costs 2 x (16 + 1) x 8 = 272 bytes per symbol against a 64 KB level array — 0.4% — and it is the difference between the O(1) cancel this table promises and an O(n) one. The 2 is the two sides, the 16 + 1 is sixteen occupancy words plus one summary word, and the 8 is bytes per 64-bit word.

6. High-level architecture

The clearest way to see the architecture is to follow one order all the way through it, naming each box it passes and what that box is allowed to do — the deep dives that follow each attach to one of those boxes.

The colours in the diagram are not decoration: the orange box is the sequencer, the dark blue cylinder is the log, the green boxes are matching engines, and the red box is the market data publisher. Those four are the ones the rest of the chapter argues about. Everything above the log is getting into the total order; everything below it is reading the total order.

flowchart TD
    M["Member algo<br/>colocated, same building"] -->|"binary order, 10 m fiber"| GW["Gateway<br/>kernel bypass, decode"]
    GW --> RISK["Pre-trade risk<br/>leased buying power"]
    RISK --> SEQ["Sequencer<br/>assigns global seq + ts"]
    SEQ -->|"append + majority ack"| LOG[("Event log<br/>THE exchange state")]
    LOG --> ENG1["Engine A<br/>1 thread, symbols 1-100"]
    LOG --> ENG2["Engine B<br/>1 thread, symbols 101-200"]
    LOG --> STBY["Hot standby<br/>same fold, output hashed"]
    ENG1 --> MD["Market data publisher"]
    ENG2 --> MD
    MD -->|"UDP multicast, A and B feeds"| SUB["500 subscribers"]
    MD --> RTX["Retransmit + snapshot service<br/>separate capacity"]
    ENG1 --> GW
    ENG2 --> GW
    GW -->|"execution report"| M

    style SEQ fill:#bc6c25,color:#fff
    style LOG fill:#1d3557,color:#fff
    style ENG1 fill:#2d6a4f,color:#fff
    style ENG2 fill:#2d6a4f,color:#fff
    style MD fill:#9d0208,color:#fff

Follow one order through, box by box

Stage 1 — the member algo. The member’s own trading program, running on a machine racked in the exchange’s own building. That is what colocated, same building means, and 9e why colocation is not an optimization shows why the building matters more than the code. It sends a binary order over roughly 10 m of fiber — a short optical cable to the exchange’s switch.

Stage 2 — the gateway. Two jobs, and nothing else:

• It pulls the packet off the network card using kernel bypass: the application reads the network hardware directly instead of going through the operating system’s networking code. 9d why the kernel is not an option prices what that saves.
• It decodes the fixed-offset message into fields, which is a cast rather than a parse (Api sketch).

Stage 3 — pre-trade risk. Checks the order against the account’s limits before it is allowed anywhere near the book. It uses leased buying power: a slice of the account’s spending capacity handed to this gateway in advance, so the check is a local memory read and not a network round trip. Derived in 12b buying power is shared state which the sharding rule forbids.

Stage 4 — the sequencer. It assigns a global seq and ts: one strictly increasing sequence number and one timestamp, assigned by exactly one process for the whole exchange. That single assignment is what makes arrival order a fact rather than an opinion.

Stage 5 — the event log. The sequencer appends the stamped message and waits for a majority ack, meaning more than half of the log’s replicas confirm they have it, before releasing it downstream. The log is labelled THE exchange state in the diagram and the capitals are deliberate: the log is the authoritative record, and the order book is merely something rebuilt from it. Argued in full in 10a the sequencer is the total order.

The three kinds of reader below the log

All three are fed the identical byte stream.

The matching engines. Engine A runs one thread over symbols 1-100, Engine B one thread over symbols 101-200, and the numbering continues in blocks of 100 across the remaining engines. Each owns a disjoint slice of the 3,000 symbols and shares no mutable state with any other engine at all.

The hot standby. It performs the same fold — the same left-to-right accumulation of the log into a book — as the primary, and hashes its output. The primary compares hashes message by message, so a divergence is caught in microseconds rather than at end-of-day reconciliation (10c recovery is replay).

The market data publisher. It emits one copy of each event as UDP multicast on two feeds, A and B. UDP is the connectionless network protocol that does not retransmit lost packets; A and B are two identical copies of the same feed sent over physically separate network paths, so a subscriber can take whichever arrives first (Deep dive 5 market data fanout and why tcp unicast fails).

Alongside the publisher, the retransmit and snapshot service runs on its own machines with its own bandwidth, so that a burst of recovery requests cannot slow the live feed. And each engine’s execution reports go back out through the gateway to the member who owns them — the last two arrows in the diagram.

Three assertions the picture makes

Each is defended later, and each is a place an interviewer will push.

1. The sequencer sits upstream of everything and is a single point by design. Being single is precisely what a total order means. Making it survivable without making it plural is Deep dive 4 the sequencer and the log that is the exchange.
2. The engines read the log, not the network. That is what lets a primary and a standby be the same program fed the same bytes, with no replication protocol between them.
3. Market data leaves through a publisher that sends exactly one copy. Not through the engine, and never through one network connection per subscriber.

7. Deep dive 1: determinism, and why “just shard it” has exactly one answer

Given that the workload fits on half a core, what is the right way to split the work across machines? Only one split turns out to be legal — every other one either destroys determinism or returns almost nothing. Sharding here means splitting the data across independent machines so each owns a disjoint slice, and the shard key is the field you split on.

7a. What determinism costs on the hot path

Determinism means: state = fold(apply, log), and two machines folding the same log produce byte-identical state and byte-identical output.

Two terms in that sentence:

• A fold is walking a sequence from the start, applying a function to each element to update an accumulated value, and ending with one final value. Here the sequence is the log, the function is apply, and the accumulated value is the order book. Python’s functools.reduce is a fold; so is a for loop that keeps updating one variable.
• The hot path is the code every single order must pass through, as opposed to code that runs only occasionally.

That equation rules out most of what a normal server does. Every ban in the table comes with a replacement, shown in the third column.

Two entries in that table need unpacking:

• Hash-map iteration is what happens when a program loops over the contents of a hash table. The order it visits entries in depends on how many entries were inserted and in what sequence — history the log does not record — so two machines with the same logical contents can legitimately visit them in different orders. Note the table bans iterating a hash map, not looking up in one: the order-id index in Data model the order book is a hash map and is fine, because it is only ever asked about one key at a time.
• malloc is the C library call that asks the operating system for a block of memory. It is banned twice over: the addresses it returns vary between runs, and it can occasionally block for a long time while the allocator reorganises itself.

The payoff, which is larger than the cost

A hot standby is not a replication protocol. It is the same program reading the same log.

There is no state transfer, no leader-follower negotiation, no catch-up procedure — because there is nothing to transfer. Both machines are folding identical input, so they hold identical state by construction.

That collapses failover correctness to one question: does the standby’s output hash match the primary’s at this sequence number? One comparison per message, and a divergence surfaces in microseconds instead of at end-of-day reconciliation.

7b. Why threading the engine is a trap

The tempting move is to parallelise matching across cores. It returns 23% while costing more than that in lock overhead, before determinism is even considered. The mechanism comes first.

The matching hop is the work done for one message, from arrival at the engine to the outbound message being handed off. The block below breaks it into six pieces and sums them. Every figure is in nanoseconds, and the 100-nanosecond main-memory reference marked [ch 02] comes from the hardware latency table in Latency numbers and what each one forbids. Five of the six pieces touch the order book; only one does not:

index insert into the order_id hash (one cache line)      50
level array lookup, one main-memory reference [ch 02]    100
FIFO tail append, one dirty cache line                   100
aggregate depth and count update                          20
market-data message build                                100
ring-buffer publish to the outbound thread               100
matching hop, ns
  50 + 100 + 100 + 20 + 100 + 100        =  470

A cache line in that breakdown is the 64-byte block that is the smallest unit a processor moves between memory and its caches. “One dirty cache line” means one such block was written to and now has to be published to the other cores.

That 470 nanoseconds is the number the whole chapter runs on. Back of the envelope rounded it up to 1 microsecond to size the core; 9b the inbound path member nic to matched budgets 1 microsecond for it too. Everything from here that says “the hop” means these six lines.

Now apply Amdahl’s law

The one piece that does not touch the shared book is building the market-data message, at 100 ns. So the serial share — the fraction of the work that cannot be done by two cores at once — is 470 - 100 = 370 nanoseconds out of 470.

Amdahl’s law turns a serial share into a hard ceiling on speedup: if a fraction s of the work is unavoidably serial, then no number of cores n can ever do better than 1 / (s + (1 - s) / n). The intuition is that the serial part is paid in full no matter how many cores you have, and only the remaining 1 - s gets divided by n.

serial share of the hop
  370 / 470                              =  0.79
Amdahl speedup with 2 threads, 1 / (s + (1 - s) / n)
  1 / (0.79 + 0.21 / 2)                  =  1.12
with 8 threads
  1 / (0.79 + 0.21 / 8)                  =  1.23

Eight threads buy 23%. Not 8x, not 4x — 23%, and that is the ceiling, before any coordination cost is paid at all.

Now price what the threads cost

An atomic operation is a single instruction the hardware guarantees no other core can interleave with. It is how threads coordinate, and every shared-book update needs at least one.

• Uncontended — no other core wants the same memory: about 20 nanoseconds.
• Contended — the cache line holding the lock is bounced back and forth between cores: about 200 nanoseconds.

Contention is the case that matters, because every thread wants the same book. On a 470-nanosecond hop, adding 200 nanoseconds is a 200 / 470 = 0.43 regression: 43% slower, against a 23% ceiling on the gain.

The locking costs roughly twice what the parallelism returns, and you have traded away determinism to get there.

The reason is structural rather than incidental. A book update is a read-modify-write on one shared structure whose inputs already have a total order defined over them. There is no parallelism inside it to find, so there is nothing for the extra cores to do except queue for the same lock.

7c. Therefore: shard by symbol, and by nothing else

An order in AAPL can never match an order in MSFT. Symbols are therefore the only independent axis in the problem, and the only legal shard key.

So: partition the 3,000 symbols across engines. Each engine is one thread pinned to one core — meaning the operating system is instructed never to move that thread to a different core — owning its symbols exclusively, with no shared mutable state between engines at all.

If throughput was never the constraint, what does sharding buy?

Low utilisation, which in a latency system is a knob rather than a waste.

To see why, use M/M/1, the simplest queueing model there is: one server, arrivals that are random and independent, service times that are random with a known mean. Its central result is that if rho (the Greek letter rho) is utilisation — the fraction of the time the server is busy — then the average time a request spends waiting in the queue before service is rho / (1 - rho) service times.

The block below has two pairs. The first is one engine handling the whole market; the second is the same load split thirty ways. The rho values come from Back of the envelope’s 0.427, divided by the number of engines. The answers are in service times, and one service time is the 1-microsecond hop, so the numbers double as microseconds.

one engine for the whole market, rho
  0.427
mean queueing delay in service times
  0.427 / (1 - 0.427)                    =  0.745
30 engines, per-engine rho
  0.427 / 30                             =  0.0142
mean queueing delay in service times
  0.0142 / (1 - 0.0142)                  =  0.0144

0.745 microseconds of queueing delay on one engine versus 0.014 across thirty — a 52x reduction in the latency contributed purely by waiting, on a system that was never short of capacity.

That is the honest reason to run 30 engines at 1.4% utilisation each. The second reason is blast radius, meaning how much of the system a single failure takes down: a crashed engine halts 100 symbols instead of 3,000.

The tail behaves worse than the mean and moves in the same direction. Queueing delay grows as 1 / (1 - rho), which is a curve that goes vertical as rho approaches 1. At rho = 0.9 the mean wait is already 0.9 / 0.1 = 9 service times, and the one-in-a-hundred case is far beyond that.

In a latency system, utilisation is a number you choose, not a number you tolerate.

7d. What you give up

Sharding by symbol has one real cost, worth stating explicitly.

What you give up is cross-symbol atomicity: the ability to make two things in different symbols happen together or not at all.

A spread order is exactly that. It buys one instrument while selling another — both legs or neither — because the trader wants the price difference between them rather than either price on its own. If one leg fills and the other does not, the trader is holding a position they never wanted.

Two independent engines cannot guarantee that without a two-phase commit: the protocol where a coordinator asks every participant to prepare, waits for all of them to agree, and only then tells them to commit. Its round trip is several times the entire 11.55-microsecond budget, so it is not available here.

Real venues do one of two things instead, and saying which you would pick is the answer:

• Make the combination its own instrument with its own order book, owned by a single engine that also owns the individual legs. That engine can then match the combination against the legs atomically, because all of it is one thread’s private state and one thread cannot interleave with itself.
• Refuse the guarantee. Fill the legs independently and let the member carry the risk that one fills and the other does not. This is cheaper, and it is what most equity venues actually do.

8. Deep dive 2: the array of price levels, derived

The order book’s physical layout can be derived from first principles, and the textbook answer loses to it by a factor of three. Both claims are made concrete below in runnable Python, ending with the constant-time best-price lookup that makes the O(1) cancel real.

Why not a tree

A book needs to answer two questions: what is the best price on each side, and what are the orders at a given price in arrival order?

A balanced tree or a skip list answers both. Both are ordered structures that find a key in roughly log2(n) comparisons by following pointers, and both are what a textbook would reach for. Both also lose here, and the arithmetic below says by how much.

First, size the array so there is something to compare against. The chain is: how wide a price range must the array cover, how many bytes is one level, and therefore how much memory for one symbol and for the market.

price levels within +/- 5% of a $100 last trade at a $0.01 tick
  0.05 x 100 / 0.01                      =  500
levels allocated per side, with headroom
  2 x 500                                =  1,000
bytes per level: head 8 + tail 8 + depth 8 + count 4 + pad 4
  8 + 8 + 8 + 4 + 4                      =  32
bytes per symbol, both sides
  2 x 1,000 x 32                         =  64,000
all 3,000 symbols, bytes
  3,000 x 64,000                         =  192,000,000

64 KB per symbol, and 192 MB for the whole market. Both of those numbers get used again below.

Now compare what one price-level lookup costs in each structure, and then substitute the tree’s cost into the 470-nanosecond hop from 7b why threading the engine is a trap — replacing the array’s 100 ns with the tree’s 1,000 ns, which is the 470 - 100 + 1,000 line:

array: subtract the base, divide by the tick, one indexed load
  one main-memory reference [ch 02], ns  =  100
tree: log2(1,000) pointer chases, each a random load
  10 x 100                               =  1,000
the matching hop if the tree replaces the array, ns
  470 - 100 + 1,000                      =  1,370
as a multiple of the 470 ns hop
  1,370 / 470                            =  2.9

The tree triples the matching hop, and it does so on every message. The array wins for three compounding reasons and only the first is obvious:

1. Indexing is arithmetic, not search. One subtraction and one shift replace ten comparisons, and arithmetic on a value already in a register is essentially free.
2. 64 KB fits in the L2 cache. Processors keep a hierarchy of small fast memories in front of main memory. L1 cache is a few tens of kilobytes and takes about 1 nanosecond; L2 cache is around a megabyte and takes about 4; main memory takes about 100. (These are processor caches, not the market-data levels of the same name from Functional.) A 1 MB L2 holds the entire level array of an actively traded symbol, so the “main-memory reference” costed above is in practice usually an L2 hit at roughly 4 nanoseconds. The tree’s 1,000 nodes add up to the same total size but are reached by chasing pointers to scattered addresses, so no prefetcher — the hardware unit that guesses which memory you will want next and fetches it early — can predict them.
3. The hot levels are physically adjacent. Trading concentrates at the touch, the boundary between the best bid and the best offer, and the gap between those two prices is the spread. Because the array is laid out in price order, the two or three levels either side of the spread share cache lines and arrive together. In a tree those same levels are wherever the memory allocator happened to put them.

Huge pages, from the same 192 MB

A processor translates the addresses a program uses into physical memory addresses, using a hardware cache of recent translations called the TLB, or translation lookaside buffer. Each TLB entry covers one page of memory, normally 4 KB.

A program touching more memory than the TLB can cover therefore pays a slow translation on nearly every access. The next block asks how bad that is here: how many 4 KB pages the books occupy, and what fraction of them a typical 1,536-entry TLB can hold at once.

4 KB pages needed to map every book
  192,000,000 / 4,096                    =  46,875
share of that covered by a 1,536-entry TLB
  1,536 / 46,875                         =  0.033

A 1,536-entry TLB covers 3.3% of the books, so a deployment on 4 KB pages takes a translation miss on essentially every switch from one symbol to another.

Huge pages are the option to make each page much larger. At 1 GB per page, one TLB entry covers 1,073,741,824 / 4,096 = 262,144 times as much memory as a 4 KB entry, so the entire 192 MB of books fits inside a single entry and the misses disappear.

That is one flag on the mmap call that maps the memory, worth about 100 nanoseconds per message.

Where the array loses

The array has one case where it fails, worth naming.

An instrument with no fixed tick grid, or one whose price can move by a factor of a hundred — a cryptocurrency, or a ladder of option strikes — would need millions of array slots to cover its range, and 64 KB per symbol becomes gigabytes.

The fix is a hybrid: keep an array covering a window of prices anchored near the last traded price, put anything outside that window in a hash map, and move the anchor during a quiet moment. Never move it mid-burst, because moving it means copying the whole array — a memcpy — inside the matching hop.

Working code

The listing below is the complete book. It runs, and its assertions are the specification.

Read it in this order; the first two pieces explain the rest:

1. Order and Book.__init__ — the fields. head/tail are the FIFO queue per price level, depth is the running L2 total, index is the order-id map that makes cancel O(1), and words/summary are the two-level occupancy bitmap from Data model the order book.
2. _mark and _scan — the bitmap. _mark sets or clears one level’s bit; _scan reads the best occupied level back out. These two are what the whole section is arguing for.
3. _append, _unlink, _repair — the three primitives that mutate the book.
4. limit — the matching loop, and the only place a fill is produced.
5. ioc, market, fok — the other three order types from Functional, each built on limit.
6. replay and the __main__ block — the fold, and a six-event log that exercises price priority, time priority and cancel.

Two conventions to know before you start. Prices are integer ticks, so 10_000 means $100.00 and the array index is px - base. A fill is the tuple (resting_order_id, aggressor_order_id, price, quantity).

"""Price-time priority: array of levels, FIFO per level, O(1) cancel.
Integer ticks, integer quantities, no floats -- see section 7a."""
BUY, SELL = 0, 1
WORD = 64


class Order:
    __slots__ = ("oid", "side", "px", "qty", "prev", "nxt")

    def __init__(self, oid, side, px, qty):
        self.oid, self.side, self.px, self.qty = oid, side, px, qty
        self.prev = self.nxt = None


class Book:
    def __init__(self, base_tick, n_ticks):
        self.base, self.n = base_tick, n_ticks
        self.head = [[None] * n_ticks, [None] * n_ticks]
        self.tail = [[None] * n_ticks, [None] * n_ticks]
        self.depth = [[0] * n_ticks, [0] * n_ticks]     # aggregate qty, for L2
        self.best = [-1, n_ticks]                       # best bid idx, ask idx
        self.index = {}                                 # oid -> Order
        # Two-level occupancy bitmap: one bit per price level, plus one
        # summary bit per 64-level word. This is what makes _repair O(1).
        n_words = (n_ticks + WORD - 1) // WORD
        assert n_words <= WORD, "one summary word covers 4,096 levels"
        self.words = [[0] * n_words, [0] * n_words]
        self.summary = [0, 0]

    def _mark(self, s, i, occupied):
        w, bit = i // WORD, 1 << (i % WORD)
        if occupied:
            self.words[s][w] |= bit
            self.summary[s] |= 1 << w
        else:
            self.words[s][w] &= ~bit
            if not self.words[s][w]:
                self.summary[s] &= ~(1 << w)

    def _scan(self, s):
        """Best occupied level, in constant time: one find-set-bit on the
        summary word, one on the level word it names. In C those are two
        `lzcnt`/`tzcnt` instructions and two loads, whatever the book
        looks like -- no loop over the level array at all."""
        m = self.summary[s]
        if not m:
            return -1 if s == BUY else self.n
        if s == BUY:                                    # highest set bit
            w = m.bit_length() - 1
            return w * WORD + self.words[s][w].bit_length() - 1
        w = (m & -m).bit_length() - 1                   # lowest set bit
        v = self.words[s][w]
        return w * WORD + (v & -v).bit_length() - 1

    def _append(self, o):
        i, s = o.px - self.base, o.side
        if self.tail[s][i] is None:
            self.head[s][i] = self.tail[s][i] = o
            self._mark(s, i, True)
        else:
            o.prev, self.tail[s][i].nxt = self.tail[s][i], o
            self.tail[s][i] = o
        self.depth[s][i] += o.qty
        self.best[s] = max(self.best[s], i) if s == BUY else min(self.best[s], i)

    def _unlink(self, o):
        i, s = o.px - self.base, o.side
        if o.prev:
            o.prev.nxt = o.nxt
        else:
            self.head[s][i] = o.nxt
        if o.nxt:
            o.nxt.prev = o.prev
        else:
            self.tail[s][i] = o.prev
        self.depth[s][i] -= o.qty
        if self.head[s][i] is None:
            self._mark(s, i, False)

    def _repair(self, s):
        """Recompute `best` after a level may have emptied. O(1) -- not
        amortized, always.

        The tempting alternative is to walk the level array down from `best`
        until an occupied slot turns up. That costs O(levels crossed), and no
        amortization argument rescues it: `_append` sets `best` with a plain
        max/min, so it never pays into an account the walk could draw on.
        Rest one order 500 ticks off the base and cancel it, and the walk
        reads 501 slots to return to an empty book. The sustained cost is
        measured below the class.
        """
        self.best[s] = self._scan(s)

    def limit(self, oid, side, px, qty):
        """Cross first, rest the remainder. Returns fills in match order."""
        fills, other = [], SELL if side == BUY else BUY
        while qty:
            b = self.best[other]
            if side == BUY and (b >= self.n or b > px - self.base):
                break
            if side == SELL and (b < 0 or b < px - self.base):
                break
            resting = self.head[other][b]
            if resting is None:            # unreachable: the bitmap is exact
                self._repair(other)
                if self.best[other] == b:
                    break
                continue
            traded = min(qty, resting.qty)
            fills.append((resting.oid, oid, self.base + b, traded))
            qty -= traded
            resting.qty -= traded
            self.depth[other][b] -= traded
            if resting.qty == 0:
                self._unlink(resting)
                del self.index[resting.oid]
                self._repair(other)
        if qty:
            o = Order(oid, side, px, qty)
            self.index[oid] = o
            self._append(o)
        return fills

    def cancel(self, oid):
        o = self.index.pop(oid, None)
        if o is None:
            return False
        self._unlink(o)
        self._repair(o.side)
        return True

    # ---- the other three order types section 2 promised ------------------

    def ioc(self, oid, side, px, qty):
        """Immediate-or-cancel: cross what is resting, cancel the rest."""
        fills = self.limit(oid, side, px, qty)
        self.cancel(oid)
        return fills

    def market(self, oid, side, qty):
        """A market order is an IOC limit at the worst representable price.

        Deliberately not a second matching rule: a second rule is a second
        thing that can disagree with the first on replay, and determinism is
        the product. Against an EMPTY book it fills nothing, rests nothing,
        and rejects nothing -- the order is simply cancelled, which is a
        defined outcome rather than an undefined one.
        """
        worst = self.base + self.n - 1 if side == BUY else self.base
        return self.ioc(oid, side, worst, qty)

    def available(self, side, px):
        """Resting quantity this order could take at `px` or better."""
        other, lim, total = SELL if side == BUY else BUY, px - self.base, 0
        i = self._scan(other)
        if side == BUY:
            while i < self.n and i <= lim:
                total += self.depth[other][i]
                i += 1
        else:
            while i >= 0 and i >= lim:
                total += self.depth[other][i]
                i -= 1
        return total

    def fok(self, oid, side, px, qty):
        """Fill-or-kill: all of it now, or none of it and no book change.

        The only order type here that is not O(1): `available` has to count
        the levels it would sweep before it is allowed to trade any of them.
        That is the honest price of an all-or-nothing guarantee, and it is
        why FOK is the rare order type rather than the default one.
        """
        if self.available(side, px) < qty:
            return []
        return self.ioc(oid, side, px, qty)

    def bbo(self):
        return (self.base + self.best[BUY] if self.best[BUY] >= 0 else None,
                self.base + self.best[SELL] if self.best[SELL] < self.n else None)


OPS = {"L": "limit", "M": "market", "I": "ioc", "F": "fok", "C": "cancel"}


def replay(log, base=9_500, n=1_000):
    """The engine IS a fold over the log. Recovery is this function."""
    book, out = Book(base, n), []
    for ev in log:
        out.append(getattr(book, OPS[ev[0]])(*ev[1:]))
    return out, book.bbo()


if __name__ == "__main__":
    log = [("L", 1, BUY, 10_000, 500),    # bid 100.00 x 500, first in queue
           ("L", 2, BUY, 10_000, 300),    # same price, behind order 1
           ("L", 3, BUY, 9_999, 900),
           ("L", 4, SELL, 10_002, 400),
           ("C", 2),
           ("L", 5, SELL, 10_000, 700)]   # takes order 1 whole, rests 200

    out, bbo = replay(log)
    assert out[4] is True
    assert out[5] == [(1, 5, 10_000, 500)]     # time priority: order 1, in full
    assert bbo == (9_999, 10_000)              # the 10,000 bid level emptied
    assert replay(log) == (out, bbo)           # determinism: same fold, same state
    print("fills:", out[5], " bbo:", bbo)

Four Python idioms in that listing that carry real weight

• __slots__ on Order tells Python to lay out the object’s fields in a fixed layout with no per-object dictionary. It is smaller and faster, and it is the closest Python gets to the fixed-offset structs Api sketch specified.
• x.bit_length() returns the position of the highest set bit in an integer. That finds the highest occupied level in one step, which is the best bid.
• v & -v isolates the lowest set bit of v. Negating a two’s-complement integer flips every bit above the lowest set one, so the AND leaves exactly that bit standing. Combined with .bit_length() it finds the lowest occupied level in one step, which is the best offer.
• getattr(book, OPS[ev[0]])(*ev[1:]) in replay is table-driven dispatch. The first element of each log entry is a one-letter opcode, OPS maps it to a method name, and the rest of the entry is unpacked as that method’s arguments.

The middle two are _scan, and they are why the code claims constant time. In C they compile to the single instructions lzcnt and tzcnt — count leading zeros and count trailing zeros — so the best price is two instructions and two loads, not a loop.

Two things the code makes concrete

Both are the point of the chapter rather than details of the listing.

replay is not a test harness, it is the production recovery path. 10c recovery is replay restarts an engine by calling exactly this function, and it folds every order type rather than just limits.

The line assert replay(log) == (out, bbo) is the property the entire chapter exists to protect. The same bytes go in, the same book comes out, and there is nothing in between that could disagree.

Why walking the level array is O(n), measured

Instrumenting the level array and counting how many slots a repair actually reads turns “walking the array is slow” from an adjective into a number.

The alternative that _repair rejects — stepping down the array until an occupied level turns up — is usually defended as “amortized O(1): the pointer only walks past levels it emptied”. Amortized analysis means averaging an operation’s cost over a whole sequence, so an occasional expensive step is acceptable if cheap steps paid for it in advance, like a savings account you draw down.

Amortization needs that credit account, and this structure has none. _append sets best with a plain max/min, so the add path never pays in for the walk that _unlink later makes necessary. Nothing funds the withdrawal.

To measure it rather than argue about it, wrap the level array in a list subclass that counts every read. The three test blocks that follow do, in order: one add far from the base plus one cancel; a sustained quote-and-cancel loop with one deep order that stops the hypothetical walk at the far end; and a correctness check that the bitmap still finds the right best price walking both down and up. The assert CountingList.reads <= ... lines are the measurement — they cap what the bitmap implementation actually reads, and the comment beside each names what a walking implementation would have read instead.

class CountingList(list):
    """A level array that reports how many slots were read, so 'walks the
    array' is a number rather than an adjective."""
    reads = 0

    def __getitem__(self, i):
        CountingList.reads += 1
        return list.__getitem__(self, i)


def counted_book(base=9_500, n=1_000):
    bk = Book(base, n)
    bk.head = [CountingList(bk.head[0]), CountingList(bk.head[1])]
    return bk


# One add 500 ticks off the base, one cancel. A walking repair reads 501
# slots to get back to an empty book; the bitmap reads two words.
bk = counted_book()
bk.limit(1, BUY, 9_500 + 500, 100)
CountingList.reads = 0
assert bk.cancel(1) is True
assert CountingList.reads <= 4, CountingList.reads

# The pattern that makes it permanent rather than occasional: quote at the
# top of the book, cancel, requote. One deep resting bid stops the walk at
# slot 0, so a walking repair pays 999 steps on EVERY cancel, forever.
bk = counted_book()
bk.limit(0, BUY, 9_500, 1)                       # the deep bid
CountingList.reads = 0
for k in range(1, 1_001):
    bk.limit(k, BUY, 9_500 + 999, 1)
    bk.cancel(k)
assert CountingList.reads <= 6 * 1_000, CountingList.reads   # walking: ~999,000
assert bk.bbo() == (9_500, None)

# ...and it is still the right answer, walking down and up.
bk = Book(9_500, 1_000)
for i in (10, 500, 999):
    bk.limit(i, BUY, 9_500 + i, 1)
assert bk.bbo()[0] == 9_500 + 999
bk.cancel(999)
assert bk.bbo()[0] == 9_500 + 500
bk.cancel(500)
assert bk.bbo()[0] == 9_500 + 10
bk.cancel(10)
assert bk.bbo() == (None, None)
for i in (10, 500, 999):
    bk.limit(1_000 + i, SELL, 9_500 + i, 1)
assert bk.bbo()[1] == 9_500 + 10
bk.cancel(1_010)
assert bk.bbo()[1] == 9_500 + 500
bk.cancel(1_500)
assert bk.bbo()[1] == 9_500 + 999
bk.cancel(1_999)
assert bk.bbo() == (None, None)

A walking repair would read 501 slots for one add and one cancel, and take 999 steps per cancel under a sustained quote loop. The bitmap implementation reads at most 4 and at most 6 per operation respectively, which is what the assertions cap.

501 and 999 are O(n) in the width of the book, on the exact operation Data model the order book bolds as the one that must be O(1) because it is the traffic. At 427,350 messages a second, 19 of every 20 of them a cancel-and-replace, a 999-step walk inside a 470-nanosecond hop is not a rare tail event. It is the hop.

The two honest ways out

Choosing between them is the answer an interviewer is listening for.

1. Correct the claim. State that repairing best is O(levels crossed), note that it is fine when the book is dense around the touch and catastrophic when it is not, and monitor the number.
2. Fix the structure so the O(1) claim holds. One bit per price level, one summary bit per 64 levels, best price is a find-set-bit on each. That is what the code above does.

Option 2 costs 2 x 17 x 8 = 272 bytes per symbol — two sides, sixteen occupancy words plus one summary word, eight bytes per word — against a 64 KB book. 0.4% of the level array, and those bitmap words stay in L1 cache for the whole session.

For an exchange, option 2 is the only defensible one. Option 1 leaves you with a cancel path whose cost is decided by how far the last quote happened to sit from the rest of the book, and that is a number no operator controls.

The other three order types

Functional promises limit, market, immediate-or-cancel and fill-or-kill, and the code above implements all four. One of them has a behaviour no requirements list ever specifies: what a market order does against a completely empty book.

The rule that makes it well defined is that a market order is an IOC limit order priced at the worst representable price. That is why market in the code is three lines that delegate to ioc.

Against an empty book it therefore fills nothing and cancels. Two other outcomes were available and both are wrong:

• Not a rejection, because the member did nothing wrong. Rejecting a valid order because the book happened to be empty at that microsecond is an error the member cannot act on.
• Not resting. A resting market order is an order at an arbitrary price sitting in the book waiting for someone to hit it, which is precisely how a flash crash print happens — a trade recorded at an absurd price because a stale order was the only thing left to match against.

The four blocks below check one behaviour each: a market order sweeping two levels and never resting, a market order against an empty book, IOC cancelling its remainder, and FOK either taking everything or leaving the book untouched. The last block is the one to read closely — it checks that time priority holds through a sweep, with orders 7, 8 and 9 filling in exactly that order.

# A market order sweeps price levels in order and never rests.
bk = Book(9_500, 1_000)
bk.limit(1, SELL, 10_000, 300)
bk.limit(2, SELL, 10_001, 400)
assert bk.market(10, BUY, 500) == [(1, 10, 10_000, 300), (2, 10, 10_001, 200)]
assert 10 not in bk.index
assert bk.bbo() == (None, 10_001)

# Against an empty book: cancelled. Not rested, not rejected, not an error.
empty = Book(9_500, 1_000)
assert empty.market(11, BUY, 100) == []
assert empty.market(12, SELL, 100) == []
assert empty.index == {} and empty.bbo() == (None, None)

# IOC takes what is resting and cancels the remainder.
bk = Book(9_500, 1_000)
bk.limit(1, SELL, 10_000, 100)
assert bk.ioc(20, BUY, 10_000, 250) == [(1, 20, 10_000, 100)]
assert 20 not in bk.index and bk.bbo() == (None, None)

# FOK is all-or-nothing, and "nothing" must leave the book untouched.
bk = Book(9_500, 1_000)
bk.limit(1, SELL, 10_000, 100)
bk.limit(2, SELL, 10_005, 200)
assert bk.fok(30, BUY, 10_000, 250) == []       # only 100 at 10,000 or better
assert bk.depth[SELL][500] == 100 and 30 not in bk.index
assert bk.fok(31, BUY, 10_005, 250) == [(1, 31, 10_000, 100),
                                        (2, 31, 10_005, 150)]
assert bk.depth[SELL][505] == 50

# Time priority survives every path: same price, earlier order fills first.
bk = Book(9_500, 1_000)
for oid in (7, 8, 9):
    bk.limit(oid, BUY, 10_000, 100)
assert bk.market(50, SELL, 250) == [(7, 50, 10_000, 100),
                                    (8, 50, 10_000, 100),
                                    (9, 50, 10_000, 50)]
assert bk.index[9].qty == 50 and bk.depth[BUY][500] == 50

Proving the bitmap changed nothing the engine does

The bitmap changes how best is found. It must not change what the engine does — a claim worth proving with a randomised test rather than asserting.

The test runs two hundred thousand operations across all five entry points. The mix is weighted so that cancels dominate the way they do in real traffic, and prices cluster near the touch the way real quotes do — that is what the rng.gauss(0, 6) is doing, drawing an offset from the mid-price that is usually small and occasionally large.

It checks three families of property:

• Price-time priority. Within a sweep, each successive fill must be at a price no better than the last, and at one price the earlier order must fill first.
• Quantity conservation. Total bought must equal total sold at every step, and the quantity the engine believes is resting must equal the sum of what is actually in the book.
• Structural invariants. The audit function walks the level array directly and checks that every bitmap bit, every summary bit, every queue’s head and tail pointer, every depth total and every index entry agrees with what is physically there. It is deliberately slow and deliberately independent of _scan, so a bug in the bitmap cannot hide behind the bitmap.

Read audit first; it is the specification of what “the book is intact” means. Then read the loop, which generates traffic to try to break it.

import random


def audit(book):
    """Every invariant the occupancy bitmap could falsify, checked directly
    against the level array it summarizes."""
    counted = 0
    for s in (BUY, SELL):
        for i in range(book.n):
            node, prev, total = book.head[s][i], None, 0
            while node is not None:
                assert node.prev is prev and node.side == s
                assert node.px - book.base == i
                assert book.index.get(node.oid) is node
                total += node.qty
                counted += 1
                prev, node = node, node.nxt
            assert book.tail[s][i] is prev
            assert book.depth[s][i] == total, (s, i)
            bit = bool(book.words[s][i // WORD] >> (i % WORD) & 1)
            assert bit == (book.head[s][i] is not None), (s, i)
        assert book.best[s] == book._scan(s)
        assert book.summary[s] == sum(
            1 << w for w, v in enumerate(book.words[s]) if v)
    assert counted == len(book.index)


rng = random.Random(20240719)
bk, live, position, booked, deepest = Book(9_500, 1_000), [], {}, 0, 0
MID = 500

for oid in range(1, 200_001):
    roll = rng.random()
    if live and roll < 0.30:                       # cancels dominate, as ever
        victim = live.pop(rng.randrange(len(live)))
        booked -= bk.index[victim].qty if victim in bk.index else 0
        bk.cancel(victim)
        continue
    side = BUY if rng.random() < 0.5 else SELL
    qty = rng.randrange(1, 100)
    off = abs(int(rng.gauss(0, 6)))                # quote near the touch,
    px = 9_500 + MID + (-off if side == BUY else off) + rng.randrange(-3, 4)
    px = min(max(px, 9_500), 9_500 + 999)          # ...sometimes crossing it
    if roll < 0.38:
        fills = bk.market(oid, side, qty)
    elif roll < 0.46:
        fills = bk.ioc(oid, side, px, qty)
    elif roll < 0.54:
        fills = bk.fok(oid, side, px, qty)
    else:
        fills = bk.limit(oid, side, px, qty)
        if oid in bk.index:
            live.append(oid)

    filled, last_px = 0, None
    for resting_id, aggressor_id, fill_px, fill_qty in fills:
        assert aggressor_id == oid and resting_id != oid   # no self-trade
        position[aggressor_id] = position.get(aggressor_id, 0) + (
            fill_qty if side == BUY else -fill_qty)
        position[resting_id] = position.get(resting_id, 0) + (
            -fill_qty if side == BUY else fill_qty)
        if last_px is not None:                    # price priority: a sweep
            assert fill_px >= last_px if side == BUY else fill_px <= last_px
        last_px = fill_px
        filled += fill_qty

    # quantity conservation, per operation
    booked += (bk.index[oid].qty if oid in bk.index else 0) - filled
    lo, hi = bk.bbo()
    assert lo is None or hi is None or lo < hi, (oid, lo, hi)   # never crossed
    live = [o for o in live if o in bk.index]
    deepest = max(deepest, len(bk.index))
    if oid % 20_000 == 0:
        assert booked == sum(o.qty for o in bk.index.values()), oid
        audit(bk)

bought = sum(v for v in position.values() if v > 0)
sold = -sum(v for v in position.values() if v < 0)
assert bought == sold > 1_000_000
assert deepest > 100, deepest          # the book carried real depth throughout

Bought equals sold at every one of 200,000 steps, the book never crossed — meaning no bid was ever left priced above an offer, which would be two orders that should have matched and did not — and the bitmap agreed with the level array at every audit. That is the claim the section needs: repairing the best price is O(1), and the matching rule it sits underneath is unaffected.

9. Deep dive 3: the latency budget, in microseconds

The 11.55-microsecond round trip is built here one line at a time, from the speed of light in glass up through switches, network cards and the matching hop — and against it, each of the three big alternatives (using the operating system’s network stack, sitting a kilometre away, tolerating jitter) can be priced exactly. Every constant is either taken from the hardware latency table in Latency numbers and what each one forbids, derived earlier in this chapter, or stated as an assumption on the line where it appears.

9a. How fast light actually is

The budget starts with physics, because the one term nothing in the design can reduce is the time light takes to cross a cable.

Light travels more slowly in glass than in vacuum by a factor called the refractive index, about 1.47 for the single-mode fiber used in a datacenter. Dividing by it converts the vacuum speed into the fiber speed.

The unit m/us is metres per microsecond. Light does 300 metres per microsecond in vacuum, which is the familiar 300,000 km/s written in the units this chapter works in.

speed of light in vacuum, m/us                           300
refractive index of single-mode fiber                    1.47
signal speed in fiber, m/us
  300 / 1.47                             =  204
a 10 m colocation cross-connect, us
  10 / 204                               =  0.049

9b. The inbound path: member NIC to matched

This is the eight-line sum from the member’s network card to the moment the order has been matched. Three terms in it need defining first:

• A NIC is a network interface card, the hardware that puts bytes on and takes bytes off the wire.
• A cut-through switch starts forwarding a packet as soon as it has read the destination address in the header, rather than waiting for the whole packet to arrive. That is why a hop costs 0.3 microseconds here instead of the several microseconds a store-and-forward switch would take.
• A busy-spin ring buffer is a fixed-size circular queue in shared memory where the reading thread loops continuously checking for new entries instead of going to sleep. It trades a permanently busy core for the elimination of a wake-up delay.

Two lines in the block are rounded up rather than measured, and it is worth knowing which. Matching is budgeted at 1.0 us even though 7b why threading the engine is a trap sums the hop to 470 ns — the extra is headroom. The risk check is budgeted at 1.0 us even though 12a five checks and what they cost prices five checks at 500 ns worst case, for the same reason. Both round-ups make the total pessimistic, which is the right direction for a number you publish.

fiber, member cabinet to exchange switch, us
  10 / 204                               =  0.049
two cut-through switch hops at 0.3 us each
  2 x 0.3                                =  0.6
gateway NIC receive with kernel bypass, us               1.0
binary decode at fixed offsets, us                       0.05
pre-trade risk check, section 12a, us                    1.0
sequencer: assign, append, majority ack, section 10b, us 4.5
handoff to the engine over a busy-spin ring buffer, us   0.5
matching, 470 ns from section 7b, us                     1.0
inbound total, us
  0.049 + 0.6 + 1.0 + 0.05 + 1.0 + 4.5 + 0.5 + 1.0  =  8.70

9c. The outbound path: match to the subscriber’s application

The return leg is shorter because there is no sequencer on it — the sequence number was assigned on the way in and is merely carried back out. Adding the two halves gives the tick-to-trade figure the whole design is accountable to.

encode the market-data message, us                       0.2
publisher NIC send with kernel bypass, us                1.0
two switch hops
  2 x 0.3                                =  0.6
fiber back to the member cabinet, us
  10 / 204                               =  0.049
subscriber NIC receive with kernel bypass, us            1.0
outbound total, us
  0.2 + 1.0 + 0.6 + 0.049 + 1.0          =  2.85
tick-to-trade round trip, us
  8.70 + 2.85                            =  11.55

11.55 microseconds, of which the sequencer accounts for 4.5 — 39% of the budget spent on not losing an order. That is the first thing to point at when an interviewer asks what you would optimise.

The round trip as a pipeline, with each stage’s cost in microseconds:

flowchart LR
    M["Member algo"] -->|"fiber 0.049"| SW1["Switches 0.6"]
    SW1 --> GW["Gateway NIC + decode 1.05"]
    GW --> RISK["Risk check 1.0"]
    RISK --> SEQ["Sequencer majority ack 4.5"]
    SEQ --> RING["Ring handoff 0.5"]
    RING --> ENG["Match 1.0"]
    ENG -->|"inbound leg 8.70"| MD["Publisher encode + NIC 1.2"]
    MD --> SW2["Switches 0.6"]
    SW2 -->|"fiber 0.049"| SUB["Subscriber NIC 1.0"]
    SUB -->|"outbound leg 2.85"| M

The table below regroups the same thirteen lines by layer, so the shares are visible. It sums to the same 11.55: three NIC crossings at 1.0 each, four switch hops at 0.3 each, and the 0.35 bottom row is the two fiber runs plus the encode and the decode. The fourth column names the only lever available on each layer, and three of the seven levers are “none”.

9d. Why the kernel is not an option

The ordinary way of doing networking — letting the operating system kernel receive the packet and hand it to your program — exceeds the entire budget on its own.

The four costs below are what the kernel does between the wire and your code — work the bypass path skips entirely:

• A hardware interrupt is the signal the network card raises to say a packet has arrived. A softirq is the deferred kernel routine that then processes it.
• An skb, or socket buffer, is the kernel’s internal representation of a packet. It has to be allocated and then copied into memory your program can see.
• A scheduler wakeup is the work of finding a blocked thread, marking it runnable, and getting a core to actually run it.
• A syscall is the controlled transition from your program into kernel code.

Those four are the receive cost, one direction. The block doubles it because a round trip crosses the kernel twice, then divides by the 11.55 us budget.

hardware interrupt and softirq, us                       3.0
skb allocation and copy to userspace, us                 1.0
scheduler wakeup of the blocked thread, us               2.5
syscall boundary, us                                     0.1
one-way kernel receive cost, us
  3.0 + 1.0 + 2.5 + 0.1                  =  6.6
both directions, us
  2 x 6.6                                =  13.2
as a share of the 11.55 us budget
  13.2 / 11.55                           =  1.14

The kernel network stack alone costs 114% of the entire budget. Doing nothing but receiving and sending the packet would blow the number before any matching happened.

And the mean understates it. A scheduler wakeup onto a busy core is 50 us or more, so the kernel path’s p99.9 is many times its p50. Kernel bypass is bought for the jitter, not the average.

The price is explicit and worth stating in an interview: one core spinning at 100% per polled receive queue, forever, whether or not a packet arrives.

9e. Why colocation is not an optimization

Distance dominates everything the exchange controls, which is why colocation — renting rack space inside the exchange’s own building — is a product rather than a tweak, and why an entire microwave-tower industry exists.

RTT below is round-trip time, the there-and-back delay. Each line takes a distance, doubles it for the return leg, and divides by the 204 m/us fiber speed from 9a how fast light actually is. Compare every answer against the 11.55 us the exchange controls.

a member 1 km away, round trip added, us
  2 x 1,000 / 204                        =  9.8
a member 50 km away, round trip added, us
  2 x 50,000 / 204                       =  490
cross-continent RTT from ch 02, us                       150,000
as a multiple of the whole internal budget
  150,000 / 11.55                        =  12,987

One kilometer of fiber costs 9.8 us round trip, which is 85% of everything the exchange controls. A member across the street is beaten by a member in the building before either algorithm runs.

That is why colocation exists. It is also why it is sold as a regulated equal-length product: every cabinet gets the same physical cable length to the matching engine regardless of where it sits in the hall, so the 0.049 us is identical for everyone and the exchange can honestly say the last hop is fair. Cabinets nearer the engine get their cable coiled up to match.

The same arithmetic explains an entire industry

The two big US equity trading centres are Chicago and northern New Jersey. The great circle distance between them — the shortest path over the earth’s surface — is 1,200 km.

Fiber does not run along that path, because conduits follow roads and railways, so the real cable is about 1.4 times longer. Microwave signals through air do run along it, and they travel at very nearly the vacuum speed of light rather than the slower speed in glass.

So microwave wins twice: a shorter path and a faster medium. The block below prices both wins by computing each route’s one-way time and subtracting.

Chicago to northern New Jersey, great circle, m          1,200,000
fiber route factor -- conduits do not run straight       1.4
fiber path, m
  1,200,000 x 1.4                        =  1,680,000
over fiber, us
  1,680,000 / 204                        =  8,235
line-of-sight microwave through air, us
  1,200,000 / 300                        =  4,000
advantage, one way, us
  8,235 - 4,000                          =  4,235

4.2 milliseconds one way, from a shorter path through a faster medium. That is 366 times the entire exchange’s internal budget, and it is why microwave towers were built between those two cities.

9f. Jitter, which is what you are actually selling

The mean delay is the number members quote at each other; the variation in it is the number their algorithms actually have to hedge against. Seven sources of variation matter, each with a cost when it fires and a control that removes it.

Several of the controls in the table are operating-system settings rather than code:

• mlockall is the system call that locks all of a process’s memory into physical RAM so it can never be paged out to disk.
• isolcpus is a boot option that tells the kernel a set of cores is off-limits for ordinary scheduling, leaving them for the engine threads.
• IRQ affinity decides which cores are allowed to handle hardware interrupts. The point is to steer them away from engine cores.
• NUMA, non-uniform memory access, is the fact that on a multi-socket machine each processor has its own attached memory and reading the other socket’s memory is nearly twice as slow. The fix is to pin both thread and memory to the same socket.

Read the middle column of the table against the 11.55 us budget. Three of the seven rows cost more than the entire budget every time they fire, and a fourth can — which is why the last column is mostly about preventing the event rather than recovering from it.

One major page fault is 100 us, nearly nine times the whole budget. The controls above are not micro-optimizations; each one removes a source of variance that is one to four orders of magnitude larger than the thing being measured.

10. Deep dive 4: the sequencer, and the log that is the exchange

One component consumes 39% of the latency budget: the single process that decides what order things happened in. Around it sit the log it writes — which, rather than the order book, is what the exchange actually stores — and recovery, which turns out to be nothing more than replaying that log.

10a. The sequencer is the total order

Fairness is not something the network provides. It is something one counter defines.

One process assigns a strictly increasing sequence number and a timestamp to every accepted message, appends it to the log, and only then releases it downstream. That assignment is the definition of arrival order.

A total order is a single agreed sequence in which every message has a definite position relative to every other one. The network by itself cannot supply one: two packets that leave different cabinets at the same instant have no fact of the matter about which was first. Asking “which really arrived first” is not a question with an answer at that resolution.

The sequencer creates the fact. And because engines, standbys, market-data publishers, the audit trail and the members’ own reconstructions of the book all read the same numbered stream, they all agree with one another without ever having to talk.

The log is the state, not a buffer

The log behaves exactly as described in Why a log beats a queue 328 devices or one: append-only, each entry at a permanent numbered offset, each reader tracking its own position, replay possible from any offset.

One difference is worth stating loudly. Here the log is not a buffer sitting between services. It is the authoritative state of the business.

The order book is a materialized view of the log: a derived structure kept in memory purely because reading it is faster than recomputing it. Nothing about the book is persisted except as an optimisation for recovery. Delete every book in the exchange and nothing has been lost.

10b. The 4.5 microseconds, derived

The sequencer’s cost is the largest single line in 9b the inbound path member nic to matched’s budget, so it deserves a derivation rather than an assertion.

An order is acknowledged only once its log entry has reached a majority of replicas: more than half of the machines holding copies of the log.

A majority is the smallest group with a useful property — any two majorities of the same set must share at least one member. So an entry a majority has accepted cannot be missing from the next majority that forms, which is what makes it safe to lose a machine.

The cost is one network round trip to the replica rack and back. Read the block as an out-and-return journey: fiber out, two switch hops out, the replica’s receive, the append, the replica’s send, two hops back, fiber back, the sequencer’s receive.

fiber to the replica rack, us
  10 / 204                               =  0.049
two switch hops out
  2 x 0.3                                =  0.6
replica NIC receive with bypass, us                      1.0
append to the memory-mapped log, us                      0.2
replica NIC send, us                                     1.0
two switch hops back
  2 x 0.3                                =  0.6
fiber back, us
  10 / 204                               =  0.049
sequencer NIC receive, us                                1.0
sequencer replication cost, us
  0.049 + 0.6 + 1.0 + 0.2 + 1.0 + 0.6 + 0.049 + 1.0  =  4.50

Two consequences follow, and the second is the one an interviewer will push on.

Replicas must be in the same building. A replica a kilometre away adds the 9.8 microseconds derived in 9e why colocation is not an optimization, which nearly doubles the tick-to-trade.

The log is not flushed to disk before the acknowledgement is sent. An fsync — the system call that forces buffered writes all the way onto durable storage before returning — costs 10 to 20 microseconds even on NVMe, the fastest class of solid-state drive. That one call alone would roughly double the 11.55 us budget.

So durability here comes from three copies in three separate machines on independent power supplies, with the disk write happening asynchronously behind them. Losing all three simultaneously is the failure this design accepts.

This is a deliberate trade of one durability mechanism (disk flush) for another (replication), not an oversight.

10c. Recovery is replay

Because the log is the state and the engine is a fold over it, recovery needs no special machinery: it is the same replay function from Working code. The only question is how long it takes.

A snapshot below is a periodic dump of the current book, taken so that recovery can start from a recent point rather than from the beginning of the day. Recovery is then: load the last snapshot, then replay every log entry after it.

The block sizes both halves. The write cost decides how often you can afford a snapshot; the replay cost decides how long a restart takes given that spacing.

Two unit notes so the arithmetic reads cleanly. The / 1,000,000 on the snapshot-write line is bytes per millisecond, because 1 GB/s is one million bytes per millisecond — so the answer is in milliseconds. The / 1,000,000 on the replay line is messages per second at 1 microsecond each, so that answer is in seconds.

resting orders across the market, assumed                500,000
bytes per order in a snapshot: id 8 + account 4 + px 4 + qty 4 + flags 4
  8 + 4 + 4 + 4 + 4                      =  24
snapshot bytes
  500,000 x 24                           =  12,000,000
snapshot write at 1 GB/s, ms
  12,000,000 / 1,000,000                 =  12
messages in a 60-second replay tail
  8,547 x 60                             =  512,820
replay at 1 us per message, seconds
  512,820 / 1,000,000                    =  0.51

A snapshot costs 12 milliseconds, so take one every minute, and a cold restart is then half a second of replay — inside the one-second recovery target from Requirements.

Note what this path is not for. Failover during the trading day does not use it at all: the hot standby has been folding the same log continuously and is already current, so promoting it is a routing change and nothing more. The replay number matters for a restart before the market opens, and for the regulator, who reconstructs any moment of any day by folding the log up to that sequence number.

The divergence check is the part candidates miss

A standby that has quietly drifted out of agreement with the primary, and then takes over, is far worse than an outage. It produces a book that no member can reconstruct from the feed they were given, and nobody finds out until reconciliation.

So the standby hashes its own output for every message and the primary compares hashes. On a mismatch the exchange halts the affected symbol rather than failing over to a machine it can no longer trust. Halting is the correct response: an outage is recoverable, a book no member can reconstruct is not.

11. Deep dive 5: market data fanout, and why TCP unicast fails

The obvious way to publish market data — open a reliable connection to each subscriber and write to all of them — fails for a reason that has nothing to do with bandwidth. The alternative accepts packet loss, so it also has to give subscribers a way to recover from it.

One match produces one change to the book, and every one of 500 subscribers needs it.

TCP is the standard reliable network protocol. It maintains a connection per peer, numbers the bytes, and retransmits anything that goes missing, which is why it is the default for almost everything. Using it here means one connection per subscriber and therefore one copy of every message per subscriber.

Back of the envelope already priced that at 188 gigabits per second against 376 megabits for multicast. The bandwidth is not the reason unicast loses.

The real reason is in the block below. sendmsg is the system call that hands one message to one connection, and it has to be made once per subscriber, in some order. There is no way to make 500 of them happen at once, so the block simply asks: how far behind is the last one?

cost of one sendmsg per subscriber copy, us              1
the last subscriber's copy leaves, us after the first
  500 x 1                                =  500
as a multiple of the entire internal budget
  500 / 11.55                            =  43

Serialising 500 writes leaves the last subscriber 500 microseconds behind the first — 43 times the exchange’s entire internal latency — and the order in which they are served is whatever order the loop happens to iterate in.

That is not a performance problem. It is the exchange systematically advantaging some members over others by 43 whole budgets, with the winner decided by a data structure nobody thought of as a policy. A faster network card does not fix it and a faster processor does not fix it, because the copies are inherently sequential.

What multicast fixes, and what it costs

Multicast fixes it structurally rather than incrementally. The publisher sends one packet and the switch fabric itself replicates it, so every subscriber’s copy leaves the final switch at the same instant. The exchange does not know and does not need to know who is listening.

Three consequences follow, and they are the whole engineering content of this section:

• UDP does not retransmit, so every message carries the sequencer’s seq number. Noticing a gap becomes the subscriber’s job rather than the network’s. This is not a downgrade forced on the design — that sequence number was already there for determinism, so the feature was free.
• Publish two identical feeds, A and B, over physically disjoint network paths. A subscriber watches both, matches them up by sequence number, and takes whichever copy of each message arrives first. A packet dropped on one path therefore costs zero recovery time. The cost is one extra copy: 2 x 0.376 = 0.752 gigabits per second of publisher output, which still fits inside a single 1-gigabit card’s line rate.
• Retransmission and snapshots live in a separate service with its own machines and its own bandwidth. A packet dropped at a shared uplink is missed by all 500 subscribers at once, so a naive design receives 500 simultaneous requests for the same sequence number. Serve them by re-multicasting the missing range, which satisfies all 500 with one send, and rate-limit the per-subscriber fallback so no single one can monopolise it (Distributed rate limiting and what synchronization costs).

The snapshot channel, for subscribers who join mid-day

A subscriber that connects at 11am cannot replay the whole session from the open. So a dedicated channel continuously cycles through per-symbol images of the book, and a newcomer waits for its symbols to come around.

The question is how long a full cycle takes, because that is the worst case for how long a newcomer sits blind. The block below sizes one symbol’s image, multiplies by 3,000 symbols, and divides by the dedicated bandwidth.

resting orders per symbol on average
  500,000 / 3,000                        =  167
snapshot bytes per symbol at 24 B/order
  167 x 24                               =  4,008
full cycle over 3,000 symbols, bytes
  3,000 x 4,008                          =  12,024,000
at 100 Mbps of dedicated capacity, seconds
  12,024,000 x 8 / 100,000,000           =  0.96

A subscriber that joins at a random moment is fully in sync within about one second, using 100 megabits per second of a channel that is otherwise idle.

Publish the snapshot at L3 — every individual resting order, rather than aggregated quantities. L3 is what lets a member rebuild the exchange’s book exactly, and exact reconstruction is the thing determinism was bought for in the first place. An L2 snapshot would leave the member with totals they cannot decompose back into a queue, so time priority would be invisible to them.

12. Deep dive 6: pre-trade risk, and the fairness of speed bumps

Every order must pass a set of checks before it is allowed to trade. One of those checks cannot be made local, and some venues also insert a deliberate delay into the order path — one common version of which destroys the design’s core property.

12a. Five checks, and what they cost

Five checks run on every single order, on the hot path, inside a one-microsecond budget. The table pairs each check with the specific disaster it exists to stop.

Three terms from that table are worth fixing before the arithmetic:

• The notional value of an order is quantity times price: the money at stake, as opposed to the share count. It is what a size cap should really be expressed in, because 1,000 shares means something very different in a $2 stock and a $2,000 one.
• A fat-finger order is one where a human typed an extra zero. It is the single most common way a firm loses a large amount of money in one second.
• Self-trade prevention stops one account’s buy order from matching its own sell order. Such a trade transfers nothing, but it does move the published price, so it is treated as manipulation whether or not it was intended.

Now the cost. The block prices the worst case — all five checks missing the processor caches and going to main memory at 100 ns each — and then compares it to what 9b the inbound path member nic to matched actually budgeted.

checks per order                                         5
each: one indexed load into a pinned per-account array, ns
  100
worst case, all five missing L1 and L2, ns
  5 x 100                                =  500
budgeted in section 9b, us                               1.0
as a share of the 11.55 us round trip
  1.0 / 11.55                            =  0.087

Notice the gap between the last two inputs: the worst case is 500 nanoseconds and the budget line is 1.0 microsecond. The budget is deliberately double the worst case, so the published number stays true even if a check grows a branch or an account’s state straddles two cache lines.

8.7% of the budget, and it is not optional. An exchange without pre-trade risk is one runaway algorithm away from a market-wide incident.

The checks are cheap for a specific reason: the state they read is pinned in RAM, reachable by array index, and never allocated on the fly. They would not be cheap against a database.

12b. Buying power is shared state, which the sharding rule forbids

Four of the five checks are per-order and purely local. The fifth is not — a requirement that violates the design’s own sharding rule, so something has to give.

Buying power is the amount of money an account is currently allowed to commit, and it is one number per account. Orders for a single account arrive at many gateways at once, so that number is exactly the cross-shard mutable state 7c therefore shard by symbol and by nothing else said could not exist.

Decrementing one shared counter would serialise the gateways behind each other and add a network round trip to every order. That is 9.8 microseconds per order at best (9e why colocation is not an optimization), on a check budgeted at 1.

The alternative is to lease the credit. Each gateway is handed a slice of the account’s buying power in advance and checks orders against its own slice, with no coordination and no lock at all.

The block below is three lines, and its point is the failure mode rather than the answer:

gateways                                                 8
an account's buying power, $                             10,000,000
lease per gateway if split evenly, $
  10,000,000 / 8                         =  1,250,000

An order for $2 M is rejected by a gateway holding a $1.25 M lease while $8.75 M of the same account’s money sits idle on the other seven gateways. The account had the money. The gateway did not know.

That is the inherent cost of leasing, and the fix is the usual one:

• Size the leases by observed usage rather than splitting evenly.
• Refresh them asynchronously in the background, off the hot path.
• Keep a slow path that reclaims credit from peer gateways — roughly a 50-microsecond round trip — for the rare large order.

This is structurally the same tradeoff as dividing a rate limit across several nodes (Distributed rate limiting and what synchronization costs).

12c. Speed bumps, and the version that is defensible

A speed bump is a deliberate delay inserted into the inbound order path, and its stated purpose is to make a microsecond of speed advantage worth less. Whether it achieves that — and whether it is even compatible with the rest of the design — depends entirely on whether the delay is random or fixed.

The random bump destroys price-time priority

Suppose each order’s delay is drawn uniformly at random from the range 0 to 3,000 microseconds (3 milliseconds). Two orders arriving a microsecond apart then get independent random delays, and the later one can easily land first.

The block computes how often. Order A arrives at time 0 and waits dA; order B arrives at time 1 us and waits dB. B overtakes A when 1 + dB < dA, and for two independent uniform draws on 0..T that probability is (1 - 1/T)^2 / 2.

P(the later of two orders 1 us apart overtakes the earlier)
  (1 - 1 / 3,000) ^ 2 / 2                =  0.4997
P(the earlier order still wins)
  1 - 0.4997                             =  0.5003

A one-microsecond advantage that wins 100% of races without the bump wins 50.03% of them with it. That is a coin flip with a rounding error attached.

That is not “reducing the value of speed”. It is replacing price-time priority with price-lottery priority. And worse for this design, it is nondeterministic: two replays of the same input produce different books, which breaks 7a what determinism costs on the hot path outright and takes regulatory reproduction and standby verification down with it.

The fixed bump preserves ordering exactly

Add a constant 350 microseconds to every incoming order that would take liquidity. Every arrival shifts by the same amount, so relative order is untouched, replay stays deterministic, and the matching engine does not change at all.

What a fixed bump changes is one specific race, between the market maker’s quotes and a taker — whoever crosses the maker’s posted gap to trade against it.

When news breaks, the maker’s posted price is instantly stale, and two orders race each other:

1. The taker’s order, rushing to hit the stale price before it moves.
2. The maker’s own cancel, rushing to pull it.

Apply the bump to takers and not to cancels, and the maker gets 350 microseconds of warning. At that point the latency arbitrage trade — profiting purely from reaching a known-stale quote first — stops being profitable.

The honest critique, which you should volunteer

An asymmetric bump does not make the venue neutral. It transfers the value of speed from takers to makers.

It is a policy choice about who the venue is for. Makers can quote more aggressively when they are protected, so spreads narrow — and that narrowing is paid for by takers who can no longer capture stale quotes.

Say which side you are choosing and why. Do not present a speed bump as a fairness improvement with no counterparty, because there is always a counterparty.

13. Bottlenecks and scaling

Each tier of the system has a thing that actually limits it — in five of the six cases, not throughput — and a point past which the obvious scaling move stops working.

The second column is the point: “binding constraint” almost never says throughput in this design.

Two entries there need expanding:

• Receive-side scaling, usually written RSS, is a network-card feature that hashes each arriving packet’s header fields to pick which of several receive queues it lands in, so several cores can pull packets in parallel. Steering by account rather than by the default hash is what keeps one member’s traffic from crowding another member’s queue.
• Pipelining the sequencer means assigning the sequence number and releasing the message downstream immediately, then confirming the majority acknowledgement afterwards. It removes the 4.5 microseconds from the critical path, at the cost of having released something not yet known to be durable — which is a durability decision wearing a latency costume.

Symbol rebalancing is the operation nobody plans for. Moving a symbol from one engine to another means draining its book and transferring its state, and doing that during the trading day means a window in which the symbol has no single consistent owner. That is precisely the thing the whole design refuses to allow.

So do it between sessions, and provision each engine for the growth of its busiest symbol instead.

14. Failure modes

Each way the system can break is paired below with the symptom an operator would actually see and the response that is correct rather than instinctive. Twice, the correct response is to stop trading.

The middle column is the one worth studying: several of these failures have almost no symptom at all, which is what makes them dangerous.

Two responses in that table are worth spelling out:

• A bust is the exchange formally cancelling a trade after the fact, under published “clearly erroneous execution” rules. They exist because a trade at an absurd price is better undone than honoured, and the log is what makes the decision reviewable.
• The last row’s distinction between prevented and handled is the point of that row. A 100-millisecond garbage-collection pause cannot be recovered from inside a 470-nanosecond hop — the pause is 200,000 times the hop. So the design removes the possibility rather than adding a response to it.

15. Alternatives rejected

Each of these is a choice a reasonable engineer would make in almost any other system, together with the number that rules it out here. Being able to state the number rather than the preference is what the round is testing.

Every row’s third column contains an arithmetic fact and a link to where it was derived. That is the shape of a good answer: not “trees are slow” but “ten pointer chases at 100 ns each triples a 470 ns hop”.

Two rows lean on terms defined elsewhere:

• A write-ahead log, or WAL, is the durability mechanism inside every serious database. The change is written to a sequential log and flushed to disk before the data pages are touched, so a crash can always be replayed forward. It is that mandatory disk flush — the same fsync 10b the 45 microseconds derived refused — that costs the ~100 microseconds.
• Raft is a well-known consensus algorithm that keeps a replicated log consistent across machines, including electing a leader and adding or removing members while running. This design keeps Raft’s majority-acknowledgement idea and rejects the rest, because leader election and membership changes involve memory allocation and unbounded delays that do not fit inside a 4.5-microsecond window.

16. Interviewer pushback

Seven questions that separate a memorised answer from a derived one. The italics are the spoken answer, and every one leads with a number.

“Your cancel is O(1). Prove it, including what happens to the best price.”

Unlinking the order is O(1) — hash to the node, splice a doubly-linked list. The part that is easy to get wrong is what comes after: if that was the last order at the best price, best is now stale, and the obvious repair steps along the level array until it finds an occupied slot. That is O(levels crossed), not amortized O(1), because nothing ever pays into the account — the add path sets best with a max, so it never funds the walk the cancel makes necessary. On a 1,000-level book I instrumented it: a walking repair reads 501 array slots for a single add plus a single cancel, and takes 999 steps per cancel for a market maker quoting at the touch and requoting, which is the traffic. So I keep one bit per price level and one summary bit per 64 levels: the best price is a find-set-bit on the summary and a find-set-bit on the word it names, two instructions, independent of the book’s shape. It costs 272 bytes per symbol against a 64 KB level array, and it is what makes the O(1) claim true rather than aspirational.

“Why is a single-threaded matching engine not a bottleneck?”

Because the arithmetic says it is not. Peak market-wide load is 427,350 messages per second and the matching hop is about 470 nanoseconds, so the whole market is 43% of one core. I shard by symbol anyway, but for latency rather than capacity: one engine at 43% utilization contributes 0.75 microseconds of queueing delay, and thirty engines at 1.4% contribute 0.014. Utilization is a latency knob in this system, and low utilization is something I am buying deliberately, not something I am wasting.

“You have one sequencer. That is a single point of failure.”

It is a single point of ordering, which is the product. If two processes could both assign sequence numbers there would be no total order and price-time priority would be undefined. It is made available rather than plural: three replicas, majority ack before the order is released, and failover promotes the replica with the highest contiguous sequence. If there is a gap the exchange halts instead of guessing — an outage is recoverable and a book that no member can reconstruct is not.

“Where does your 11.55 microsecond number come from? It sounds made up.”

It is a sum of eight lines, each with a source. 0.049 microseconds of fiber from light speed over the refractive index of glass, 0.6 for two cut-through switch hops, 1.0 per NIC crossing under kernel bypass, 0.05 to decode a fixed-offset binary message, 1.0 for five risk checks against pinned memory, 4.5 for the sequencer’s majority ack, 0.5 for the ring-buffer handoff, and 1.0 for matching. The largest term is the replication, which is 39% of the budget, so that is where I would look first — and every way of shrinking it trades durability for latency, which is a business decision rather than an engineering one.

“Why not colocate the replicas in a second datacenter for disaster recovery?”

Because a 1 km hop adds 9.8 microseconds round trip, which nearly doubles the tick-to-trade, and 50 km adds 490. Synchronous cross-site replication is not compatible with this budget. The design is synchronous majority replication within the building, plus asynchronous shipping of the log offsite. A site loss therefore costs the last few milliseconds of unshipped log, and the recovery procedure is a market halt and a reconciliation — which is what real venues do, because the alternative is being permanently slower than every competitor.

“A member complains they are 500 microseconds behind another member on market data. What happened?”

If it is consistent, it is almost certainly a unicast or per-subscriber path somewhere — that number is suspiciously close to 500 sequential socket writes. The whole point of multicast is that one packet leaves the publisher and the fabric replicates it, so any per-subscriber work reintroduces exactly this. I would check whether they are on the A feed, the B feed, or arbitrating both, then check the switch path for an extra hop, then check whether their own receive path blocks in the kernel. And I would look at whether the retransmit service is unicasting where it should be re-multicasting.

“Would you add a speed bump?”

Only a fixed, asymmetric one, and I would be honest about what it does. A random bump reorders arrivals — with a uniform 0-3 millisecond delay, a one-microsecond advantage wins 50.03% of races instead of 100% — and it makes replay nondeterministic, which breaks the property the entire exchange is built on. A fixed delay applied to taking orders and not to cancels preserves ordering exactly, stays deterministic, and specifically kills stale-quote arbitrage. But it is not neutral: it transfers the value of speed from takers to makers. That is a legitimate product decision about who the venue serves, and it should be argued as one rather than sold as fairness.

17. The assumption ledger

Every number in this chapter rests on something that was assumed rather than measured, and an interviewer’s most effective question is “what happens if that is wrong?” Collected in one place, the assumptions let you state the design’s foundations in about twenty seconds and say what replaces the design when each one fails.

Sort each assumption into one of three bins:

• State it — you are free to pick a value, and being wrong costs you a re-derivation and nothing else.
• Ask it — the answer changes the architecture, so it is worth spending an interviewer’s time on.
• Load-bearing — if the assumption is wrong, the design is not merely suboptimal, it is invalid.

Those are the same three bins used in the GenAI framework chapter.

The table is sorted by bin, load-bearing first. Read the last column of the load-bearing rows: each one describes a different design, not a tuning change.

The sentence that makes this visible to an interviewer: “This design rests on three things. One, that a message really costs about a microsecond in the engine — which is what makes the whole market fit on half a core and turns this into a latency problem rather than a capacity problem. Two, that members are in the building and the replicas are too, because a kilometre of fiber is 9.8 microseconds and would swamp everything I just optimised. Three, that no single symbol ever outgrows one core, because a symbol is the one thing this design cannot split.”

Cheat sheet

Everything above, compressed to what you would want on one page the morning of the interview. Each row is a claim plus the number that backs it — if a row does not trigger the derivation for you, that is the section to reread.

Next: 23 — Hotel Reservation is the same track with the opposite binding constraint, and 25 — Object Storage is the third corner: durability at exabyte scale, where the budget is dollars per petabyte-month rather than microseconds. The log semantics under section 10 are 20 — Distributed Message Queue.