How to 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.

In this lesson, we’ll build one end to end. By the end you’ll be able to lay out the order book that matching runs on, explain why the engine stays single-threaded, defend the sequencer that decides whose order arrived first, and size the whole round trip against a hard latency budget. Four pieces carry it:

• 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.

The design is unusual in one way that shapes everything: it is not a throughput problem. The whole market fits comfortably on a fraction of one processor core. What is hard is being exactly right inside a round-trip budget of about 11.55 microseconds, and every decision below is bought with latency or with variance, never with capacity.

What goes in and what comes out

The input is a stream of small fixed-size binary messages from 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”.

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

• Execution reports go only to the member who sent the order: accepted, partly filled, filled, cancelled, rejected. Nobody else sees these.
• The market data feed is a public broadcast of every change to the visible pool of unmatched orders. It carries no member identities at all.

Vocabulary

We’ll lean on these terms throughout, so pin them down once 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 buyers sorted dearest-first and sellers cheapest-first. An order waiting in the book is resting.
• A bid is a resting buy order and its price; an offer (also called an ask) is a resting sell order and its price.
• 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 now. A market order names no price: it takes whatever the book offers and never rests.
• A quote is a bid and an offer posted together by the same firm. A market maker continuously posts quotes and earns the gap between its buy and sell prices. Market makers generate most of the traffic, because moving a quote means cancelling the old order and adding a new one.
• A price level is one price plus the FIFO queue of resting orders at it. A book is a sorted array of price levels, each holding a queue.

Matching

• The matching engine reads each arriving order and pairs it against resting orders on the opposite side. A pairing is a fill: 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. One large enough to trade through several price levels sweeps them. The arriving order is the aggressor; the order it trades against was already resting.
• Price-time priority is the pairing rule the exchange sells as its product: best price first, and among orders at the same price, the earliest arrival first. That second half is a plain FIFO queue.

The properties the design protects

• 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, not 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 take over mid-session.
• Latency is the delay between an event and the response to it. Jitter is how much that delay varies from message to message. An exchange is judged on both, and jitter is the harder one.

Two abbreviations recur: us means microseconds (a millionth of a second) and ns means nanoseconds (a billionth, 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.

Every microsecond figure below traces back to a hardware latency table (how long a memory read, an SSD seek, or a network round trip takes). The full table lives in the estimation chapter. Another idea borrowed here is the append-only log: a file you may only add to, where each entry has a permanent position number called an offset, so any number of readers can independently replay the same entries from any point. It is developed in the message-queue chapter.

Framing: a state machine wrapped in a network

An exchange is a deterministic state machine wrapped in a network, 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 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, and tell five hundred parties the outcome simultaneously.

The design has four properties it is not allowed to trade away, and each one forbids a technique that is normal, sensible engineering somewhere else.

Four terms from that table:

• p99.9 is the 99.9th percentile: the delay 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 core drops into when it has nothing to do. Climbing back out costs tens of microseconds.
• Garbage collection is the pause a runtime such as Java’s or Go’s takes to reclaim unused memory. Invisible in most systems, fatal here.
• An ack (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, not an operational one.

The single idea the whole design rests on: the matching engine is a single-threaded deterministic state machine per symbol, the sequencer’s log is the exchange’s state, and everything else exists to feed that log or to fan out what it emits. A symbol is the short ticker code for one tradable stock, such as AAPL, and it is the unit everything here is partitioned by: per symbol, not per exchange.

What actually breaks in production is never steady load, always a burst: the opening auction (the whole overnight backlog released in about a second, into queues sized for the daily average), one dropped market-data packet (all 500 subscribers notice the gap and request the missing data at the same instant), and a member’s algorithm stuck in a loop cancelling and re-placing the same order forever. A system sized for the average handles none of them.

Requirements

Functional

The exchange accepts four order types plus cancel and cancel-replace. The four differ only in what happens to the part that cannot be filled immediately:

• Limit rests the unfilled remainder in the book at its stated price.
• Market takes whatever is available at any price and discards the remainder.
• Immediate-or-cancel (IOC) fills what it can right now and cancels the rest.
• Fill-or-kill (FOK) fills the entire quantity in one go, or does nothing and leaves the book untouched.

All four are the same matching rule with different remainder handling, and the code below implements them that way, including what a market order does against a completely empty book, a case requirements lists never mention but an exchange must answer.

The rest of the functional list: match by price-time priority; send execution reports to the order’s owner; publish market data at three levels of detail (below); run pre-trade risk checks on every order before it can trade (size limits, per-account exposure caps, price bands that reject mistyped prices, and self-trade prevention); and run opening/closing auctions and enforce halts and limit-up/limit-down bands.

The three market-data levels are named constantly from here on:

• L1 is the best price on each side, the best bid and offer (BBO).
• L2 aggregates: for each price, the total quantity resting there, without saying who owns it.
• L3 is every individual resting order: what a member needs to rebuild the exchange’s own book exactly.

(An unrelated collision: the order book’s memory uses L1 and L2 CPU caches too. Same letters, unrelated. This lesson says “L2 cache” whenever it means the hardware one.)

Out of scope: clearing and settlement (the slower system that actually moves shares and cash, usually one business day later, written T+1); the smart order router (which venue to send to; that belongs to the member); and options combination books.

Non-functional — the targets that decide the design

Three terms:

• Tick-to-trade is the round trip that matters commercially: from a price change leaving the exchange, through the member’s reaction, to that reaction being matched and published again. It covers the exchange’s two legs plus the member’s think time; this lesson budgets the exchange’s two legs.
• p50 is the median: half of all messages are faster. Both percentiles are quoted because the design must hit both, and the tail 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; why it can be sold is derived under the latency budget.

Back of the envelope

Assume 3,000 symbols, a 6.5-hour session, 200 million inbound messages per day, 20 inbound messages per trade, 500 market-data subscribers, and a 100-byte market-data message.

Average rate. 200M messages over a 6.5-hour (23,400-second) session is about 8,547 messages/s. At 20 messages per trade that is 10 million trades/day. Each accepted order emits one market-data event and each trade two more (one per fill side), so events slightly exceed inbound messages: about 220 million events/day, a ratio of 1.1.

Average to peak. The workload is bursty: the first second after the open carries the overnight backlog, and measured opening bursts run 30 to 100 times the session mean. Taking 50x as the sizing figure gives a peak of 8,547 x 50 ≈ 427,350 messages/s, or about 470,000 market-data events/s.

Fanout. One market-data message to 500 listeners can be sent two ways:

• Unicast sends a separate addressed copy to each listener, 500x the work and bytes.
• Multicast sends one copy to a group; the network switches duplicate it on the way out, so the sender’s cost does not depend on the number of listeners.

At 470,000 events/s of 100-byte messages, multicast is about 0.376 Gbps; unicast to 500 subscribers is 500 times that, about 188 Gbps, a 500x difference, and it is only the second-worst thing about unicast (the first is a fairness problem, covered later).

The finding that reframes everything. The matching step for one message is about 470 ns (broken down later); round it up to 1 us. So one core does about 1,000,000 messages/s, and the peak of 427,350 is 43% of one core.

There is no throughput problem. The whole market fits on less than half a core. Every design decision below is therefore paid for in latency or variance, not capacity.

Wire format

Every message is binary with fixed offsets and no memory allocation:

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

Order entry at a public venue is often FIX (Financial Information eXchange), an industry-standard text format where each field is a numeric tag, an equals sign, and a value. The internal representation here is deliberately not FIX.

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 }

u32/u64 are unsigned 32-/64-bit integers, i32 a signed one, u8 a single byte. Every field is an integer: no strings, no floats. tif is time in force, the byte that selects one of the four remainder policies. leaves is quantity still resting, cum_qty quantity filled so far. order_ref is the exchange’s public handle for one resting order. It 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 layout matter:

• Prices are i32 in ticks, never floating point. A tick is the smallest price increment, one cent for a typical US stock, so $100.02 travels the wire as the integer 10,002. The reason is determinism: 0.1 has no exact binary representation, so two implementations of the same matching rule can round differently and build two different books from one input stream.
• Fixed offsets, so decoding is a cast. Parsing a 200-byte FIX message costs 1–2 us (scanning text, splitting on delimiters); reading fields at known offsets costs about 50 ns. It is those 1.5 us added to every order that are unaffordable, because the entire matching step is 1 us.
• seq is on every outbound message. It is the sequencer’s number, and putting it everywhere solves three problems with one mechanism: a subscriber detects a lost packet by a missing number, replays history by asking for a range, and reconciles two redundant feed copies 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 OS for the time would not be deterministic, because a replay tomorrow would stamp different times.

Data model: the order book

The whole exchange is built around one structure, and four of its six operations must be O(1): a number of steps that does not grow as the book gets bigger. The layout, per symbol and 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 side there is a plain array of price levels, indexed by how many ticks the price sits above a fixed base. A $100.00 order in a book based at $95.00 with a one-cent tick lands in slot 500. Each slot holds a FIFO queue plus two running totals, depth (total quantity at that price) and count (number of orders), kept up to date on every write so that publishing L2 is free on the read.

The two bitmaps. A bitmap is an array of single bits used as a compact yes/no index. occupancy sets one bit per price level that has at least one order, packed 64 to a word; summary sets one bit per occupancy word that is not all zeros. Their job is to answer “what is the best non-empty price?” without ever scanning the array.

flowchart TD
    subgraph BOOK["Order book, one side, per symbol"]
      SUM["summary<br/>1 bit per occupancy word"]
      OCC["occupancy words<br/>1 bit per price level"]
      LVL["levels[]<br/>price to FIFO queue + depth + count"]
      SUM -->|"find-set-bit"| OCC
      OCC -->|"find-set-bit"| LVL
    end
    IDX["index<br/>order_id to node (O(1) cancel)"] --> LVL

Best price is two find-set-bit operations: one on summary to find the occupied word, one on that word to find the level, independent of how big or sparse the book is.

The two global structures. index maps an order id straight to the memory location of its node, so cancelling never searches for the order it is cancelling. accounts is an array of per-account risk state, pinned (locked into physical RAM, never swapped to disk), so a risk check is always a fast local read.

Intrusive, in “intrusive list node”, means the linking pointers live inside the Order object itself instead of in separate container nodes (Python’s list and C++‘s std::list allocate a wrapper node per element). It matters for one reason: adding an order to a queue allocates no memory at all, and allocation on this path is forbidden.

What each operation must cost

Two rows carry 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 20 never fill. Most are quote updates, a market maker moving its price, which on the wire is a cancel followed by an add. So the single hottest operation is a cancel. A design whose cancel path walks a price level looking for the right order is O(queue depth) on that hottest operation. The index map avoids it: hash the order id, get the node’s address, unlink.

Repairing the best price after a cancel must also be O(1). Removing the last order at the best price makes the cached best stale. The obvious repair steps along the array until an occupied level turns up, but that is O(empty levels crossed), and the number crossed depends on how far the last quote sat from the rest of the book, which the exchange does not control. Instrumenting the book shows a walking repair reads 501 array slots to return to an empty book after one add 500 ticks off the base and one cancel, and takes 999 steps per cancel for a market maker quoting and requoting at the top. The occupancy bitmap replaces the walk with two word operations, whatever the book looks like. It costs about 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.

High-level architecture

The clearest way to see the design is to follow one order through it. 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

Stage 1: member algo. The member’s trading program, racked in the exchange’s building, sends a binary order over roughly 10 m of fiber to the exchange’s switch.

Stage 2: gateway. Two jobs: it pulls the packet off the network card using kernel bypass (the application reads the network hardware directly instead of going through the OS networking code), and it decodes the fixed-offset message, which is a cast, not a parse.

Stage 3: pre-trade risk. Checks the order against the account’s limits before it reaches 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, not a network round trip.

Stage 4: sequencer. Assigns one strictly increasing sequence number and one timestamp, by exactly one process for the whole exchange. That single assignment is what makes arrival order a fact, not an opinion.

Stage 5: event log. The sequencer appends the stamped message and waits for a majority ack (more than half the log’s replicas confirm they hold it) before releasing it downstream. The log is the authoritative record; the order book is merely something rebuilt from it.

The three readers below the log are all fed the identical byte stream:

• The matching engines. Each runs one thread over a disjoint slice of the 3,000 symbols (Engine A symbols 1–100, Engine B 101–200, and so on in blocks of 100), sharing no mutable state with any other engine.
• 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 surfaces in microseconds instead of at end-of-day reconciliation.
• The market data publisher. It emits one copy of each event as UDP multicast on two feeds, A and B. UDP does not retransmit lost packets; A and B are identical copies over physically separate paths, so a subscriber takes whichever arrives first. Alongside it, a retransmit and snapshot service runs on its own machines and bandwidth so a burst of recovery requests cannot slow the live feed.

Three assertions the picture makes: the sequencer is a single point by design, because being single is what a total order means; the engines read the log, not the network, which is what lets a primary and standby be the same program on the same bytes with no replication protocol between them; and market data leaves through a publisher that sends exactly one copy, never one connection per subscriber.

Determinism, and why “just shard it” has one answer

The workload fits on half a core, so the question is not how to get more throughput but what the right way to split the work is. Only one split is legal. Sharding means splitting data across independent machines so each owns a disjoint slice; the shard key is the field you split on.

What determinism costs on the hot path

Determinism means state = fold(apply, log): two machines folding the same log produce byte-identical state and output. A fold walks a sequence from the start, applying a function to each element to update an accumulated value (here: the log, apply, and the order book). The hot path is the code every order must pass through.

That rules out most of what a normal server does:

The table bans iterating a hash map, not looking up in one: the order-id index is a hash map and is fine, because it is only ever asked about one key at a time. malloc is banned twice over: the addresses it returns vary, and it can occasionally block while the allocator reorganises.

The payoff 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 and no leader-follower negotiation, because both machines fold identical input and so hold identical state by construction. Failover correctness collapses to one question: does the standby’s output hash match the primary’s at this sequence number?

Why threading the engine is a trap

The tempting move is to parallelise matching across cores. It does not pay. First, the work is almost entirely serial. The matching hop for one message is six pieces:

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

A cache line is the 64-byte block that is the smallest unit a CPU moves between memory and its caches. That 470 ns is the number the whole lesson runs on; the back-of-envelope rounded it to 1 us for headroom.

Only one of those six pieces (building the market-data message, 100 ns) does not touch the shared book, so the serial share is 370/470 ≈ 79%. Amdahl’s law (that a fraction s of serial work caps speedup at 1 / (s + (1-s)/n) no matter how many cores n) then says even eight threads buy only about 23%. And that is the ceiling before coordination cost. Threads coordinate with atomic operations (a single instruction no other core can interleave with); an uncontended one is ~20 ns, but a contended one, where the cache line bounces between cores, is ~200 ns. Every thread wants the same book, so contention is the case that matters: adding 200 ns to a 470 ns hop is a 43% regression, against a 23% ceiling on the gain.

The locking costs about twice what the parallelism returns, and determinism is gone. This is structural: a book update is a read-modify-write on one shared structure whose inputs already have a total order over them. There is no parallelism inside it to find.

Therefore: shard by symbol, and by nothing else

An order in AAPL can never match an order in MSFT, so symbols are the only independent axis and the only legal shard key. Partition the 3,000 symbols across engines, each one thread pinned to one core (the OS is instructed never to move it), owning its symbols exclusively with no shared mutable state.

If throughput was never the constraint, what does sharding buy? It buys low utilisation, which in a latency system is a knob, not a waste. The M/M/1 queueing model (one server, random arrivals, random service times) says the mean wait before service is rho / (1 - rho) service times, where rho is the fraction of time the server is busy. One engine for the whole market runs at rho = 0.427, so it waits 0.427/0.573 ≈ 0.745 service times. Split thirty ways, each engine runs at rho = 0.0142 and waits ≈ 0.014, a 52x reduction in queueing delay, on a system that was never short of capacity. The second reason to shard is blast radius: a crashed engine halts 100 symbols instead of 3,000. In a latency system, utilisation is a number you choose, not one you tolerate.

The one real cost is cross-symbol atomicity: two things in different symbols happening together or not at all. A spread order wants exactly that: buy one instrument while selling another (both legs or neither), because the trader wants the price difference. Two independent engines cannot guarantee it without a two-phase commit (a coordinator asks every participant to prepare, waits for all to agree, then tells them to commit), whose round trip is several times the whole 11.55 us budget. Real venues instead either make the combination its own instrument on a single engine that also owns the legs (so one thread’s private state matches atomically), or refuse the guarantee and let the member carry the risk. Most equity venues do the latter.

The order book, in code

The book’s layout can be derived from first principles, and the textbook answer loses to it.

Why not a tree

A book must answer two questions: the best price on each side, and the orders at a given price in arrival order. A balanced tree or skip list answers both, finding a key in about log2(n) pointer-following comparisons, and both are what a textbook reaches for. Both lose here.

Size the array first. Covering ±5% of a $100 stock at a one-cent tick is about 500 levels per side; with headroom, 1,000 levels. At 32 bytes per level that is 64 KB per symbol, and 3,000 symbols is about 192 MB for the whole market.

Now compare one price-level lookup. The array does one subtraction and one indexed load, about 100 ns, one main-memory reference. The tree chases log2(1,000) ≈ 10 pointers to scattered addresses, about 1,000 ns. Substituting the tree into the 470 ns hop (470 - 100 + 1,000 = 1,370) triples it, on every message. The array wins for three compounding reasons:

1. Indexing is arithmetic, not search. One subtraction and one shift replace ten comparisons.
2. 64 KB fits in the L2 cache. CPUs keep a hierarchy of small fast memories: L1 (~1 ns), L2 (~4 ns), main memory (~100 ns). A 1 MB L2 holds an active symbol’s whole level array, so the “main-memory reference” is usually a ~4 ns L2 hit. The tree’s nodes are scattered, so no prefetcher (the hardware unit that fetches memory it predicts you will want) can guess them.
3. The hot levels are physically adjacent. Trading concentrates at the touch, the boundary between best bid and best offer, and the gap between them is the spread. Laid out in price order, the levels either side of the spread share cache lines and arrive together. In a tree they are wherever the allocator put them.

The same 192 MB argues for huge pages. A CPU translates program addresses to physical ones using a cache of recent translations called the TLB, each entry covering one page (normally 4 KB). The 192 MB of books needs about 47,000 pages, of which a typical 1,536-entry TLB covers only ~3.3%, so a 4 KB deployment takes a translation miss on nearly every symbol switch. At 1 GB per page, one TLB entry covers the entire 192 MB and the misses disappear. That is one flag on the mmap call, worth about 100 ns per message.

The array fails for an instrument with no fixed tick grid, or one whose price can move by 100x (a cryptocurrency, or a ladder of option strikes), where 64 KB per symbol becomes gigabytes. The fix is a hybrid: an array covering a window anchored near the last trade, a hash map for anything outside it, and moving the anchor only during a quiet moment (moving it means copying the whole array inside the hop).

The implementation

The listing below is the complete book; it runs, and its assertions are the specification. Read it in order: Order and __init__ are the fields; _mark and _scan are the bitmap (_mark sets or clears a level’s bit, _scan reads the best occupied level back out); _append, _unlink, _repair mutate the book; limit is the matching loop and the only place a fill is produced; ioc, market, fok build on it; replay is the fold. Prices are integer ticks (10_000 is $100.00, index is px - base), and 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 -- determinism."""
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) always --
        two find-set-bit ops, not a walk down the array. A walking repair is
        O(levels crossed) and nothing amortizes 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 a walk
        reads 501 slots to return to an empty book."""
        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

    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.
        Not a second matching rule: a second rule is a second thing that can
        disagree with the first on replay. Against an EMPTY book it fills
        nothing, rests nothing, rejects nothing -- it is simply cancelled,
        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 and no book change. The only
        type here that is not O(1): `available` must count the levels it would
        sweep before trading any of them. That is the honest price of an
        all-or-nothing guarantee, and why FOK is rare rather than default."""
        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[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

A few idioms carry weight. __slots__ gives Order a fixed field layout with no per-object dictionary, the closest Python gets to a fixed-offset struct. x.bit_length() returns the position of the highest set bit, finding the highest occupied level (the best bid) in one step; v & -v isolates the lowest set bit, finding the best offer in one step. In C these compile to the single instructions lzcnt and tzcnt (count leading and trailing zeros), so the best price is two instructions and two loads, not a loop.

The last assert is the property the whole design exists to protect: the same bytes go in, the same book comes out. And replay is not a test harness: it is the production recovery path, the same function an engine calls to rebuild its book from the log.

Walking the array is O(n): the measurement

The alternative _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 averages cost over a sequence, so an occasional expensive step is fine if cheap steps paid in advance. But amortization needs a 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 a later cancel makes necessary.

Instrumenting the level array to count reads makes it concrete. A walking repair reads 501 slots for one add 500 ticks off the base plus one cancel, and takes 999 steps per cancel under a market maker quoting at the top with one deep resting order stopping the walk at the far end. The bitmap implementation reads at most a handful of words per operation instead, whatever the book shape. At 427,350 messages a second, 19 of 20 of them a cancel-and-replace, a 999-step walk inside a 470 ns hop is not a rare tail. It is the hop.

There are two honest ways out: correct the claim (state that repairing best is O(levels crossed), fine when the book is dense around the touch and catastrophic when it is not, and monitor it), or fix the structure so the O(1) claim holds (the occupancy bitmap, ~272 bytes per symbol against a 64 KB book, whose words stay in L1 cache all session). For an exchange the bitmap is the only defensible choice, because the walking cost is decided by how far the last quote sat from the book, a number no operator controls.

Order types, including the case no requirements list mentions

The code implements all four types. One has a behaviour requirements never specify: 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 at the worst representable price, which is why market is three lines delegating to ioc. Against an empty book it therefore fills nothing and cancels. The two other outcomes are both wrong:

• Not a rejection: the member did nothing wrong, and rejecting a valid order because the book happened to be empty at that microsecond is an error they cannot act on.
• Not resting: a resting market order is an order at an arbitrary price waiting to be hit, 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.

A randomised test of 200,000 operations across all five entry points, weighted so cancels dominate and prices cluster near the touch, confirms the invariants that matter: within any sweep each fill is at a price no better than the last and the earlier order fills first (price-time priority); total bought equals total sold at every step (quantity conservation); the book never crossed (no bid was ever left priced above an offer); and an independent audit walking the level array directly agreed with every bitmap bit, depth total, and index entry. Repairing the best price is O(1), and the matching rule it sits under is unaffected.

The latency budget

The 11.55 us round trip is built from physics up. The one term nothing can reduce is the time light takes to cross a cable: light does 300 m/us in vacuum but slower in glass by the refractive index, about 1.47 for datacenter fiber, giving 204 m/us. A 10 m colocation cross-connect is therefore about 0.049 us.

Inbound leg: member NIC to matched. A few terms first: a NIC is the network interface card that puts bytes on the wire; a cut-through switch starts forwarding a packet as soon as it has read the destination in the header, so a hop costs ~0.3 us instead of several; a busy-spin ring buffer is a fixed-size circular queue in shared memory whose reader loops checking for new entries instead of sleeping, trading a busy core for no wake-up delay.

fiber, member cabinet to exchange switch            0.049 us
two cut-through switch hops at 0.3 us               0.6 us
gateway NIC receive with kernel bypass             1.0 us
binary decode at fixed offsets                     0.05 us
pre-trade risk check                               1.0 us
sequencer: assign, append, majority ack            4.5 us
handoff to the engine over a ring buffer           0.5 us
matching (470 ns rounded up)                       1.0 us
                                    inbound  =      8.70 us

Outbound leg: match to the subscriber. Shorter, because there is no sequencer on the return: the sequence number was assigned inbound and is merely carried back.

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

The risk check and matching lines are rounded up (five checks worst-case ~500 ns; the hop 470 ns) so the published number stays pessimistic. The sequencer’s 4.5 us is 39% of the whole budget, spent entirely on not losing an order.

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

Grouped by layer, the only lever available on each is narrow, and three of the seven are “none”:

Why the kernel is not an option

The ordinary way of doing networking (letting the OS kernel receive the packet and hand it to your program) exceeds the entire budget on its own. The four costs the kernel adds, which bypass skips, are a hardware interrupt and deferred softirq to process the packet (~3.0 us), allocating and copying an skb (socket buffer) into your program’s memory (~1.0 us), a scheduler wakeup to run the blocked thread (~2.5 us), and the syscall boundary (~0.1 us): about 6.6 us one way, 13.2 us both, which is 114% of the 11.55 us budget before any matching happens.

And the mean understates it: a scheduler wakeup onto a busy core is 50 us or more, so the kernel path’s tail is many times its median. Kernel bypass is bought for the jitter, not the average. Its price is explicit: one core spinning at 100% per polled receive queue, forever.

Why colocation is not an optimization

Distance dominates everything the exchange controls. A member 1 km away adds about 9.8 us round trip (85% of everything the exchange controls), so a member across the street is beaten by a member in the building before either algorithm runs. That is why colocation (renting rack space in the exchange’s building) is a product, and why it is sold as a regulated equal-length product: every cabinet gets the same physical cable length to the engine regardless of position, cabinets nearer the engine getting their cable coiled to match, so the last hop is fair for everyone.

The same arithmetic explains the microwave-tower industry. The two big US equity centres, Chicago and northern New Jersey, are about 1,200 km apart great-circle. Fiber conduits follow roads and railways, so the real cable is ~1.4x longer and runs at the slower speed in glass: about 8,235 us one way. Line-of-sight microwave through air runs the straight path at nearly vacuum light speed: about 4,000 us. Microwave wins twice, a shorter path and a faster medium, by about 4.2 ms one way, which is why the towers were built.

Jitter, which is what you are actually selling

The mean is the number members quote at each other; the variation is what their algorithms hedge against. Seven sources matter, and several controls are OS settings: mlockall locks all of a process’s memory into RAM so it is never paged out; isolcpus tells the kernel a set of cores is off-limits for ordinary scheduling; IRQ affinity steers hardware interrupts away from engine cores; NUMA (non-uniform memory access) is the fact that on a multi-socket machine reading the other socket’s memory is nearly twice as slow, fixed by pinning thread and memory to one socket.

Three of the seven cost more than the entire budget every time they fire, and one can. These are not micro-optimizations: each removes a source of variance one to four orders of magnitude larger than the thing being measured.

The sequencer, and the log that is the exchange

One component consumes 39% of the budget: the single process that decides what order things happened in.

The sequencer is the total order. Fairness is not something the network provides but something one counter defines. A total order is a single agreed sequence in which every message has a definite position relative to every other. The network cannot supply one: two packets leaving different cabinets at the same instant have no fact of the matter about which was first. The sequencer creates the fact, and because engines, standbys, publishers, the audit trail, and members’ own reconstructions all read the same numbered stream, they all agree without ever talking.

The log is the state, not a buffer. It is append-only, each entry at a permanent offset, each reader tracking its own position, but here it is the authoritative state of the business, not a buffer between services. The order book is a materialized view of the log, kept in memory only because reading it is faster than recomputing it. Delete every book in the exchange and nothing is lost.

The 4.5 us. An order is acked only once its log entry has reached a majority of replicas (more than half the machines holding copies). A majority has a useful property: any two majorities of the same set share at least one member, so an entry a majority 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 (fiber, two switch hops, the replica’s receive and append, its send, two hops back, fiber, the sequencer’s receive), summing to about 4.5 us.

Two consequences follow. Replicas must be in the same building: a replica a kilometre away adds 9.8 us and nearly doubles the tick-to-trade. And the log is not flushed to disk before the ack: an fsync (the call that forces buffered writes onto durable storage) costs 10–20 us even on NVMe, the fastest solid-state drive, and would roughly double the budget. So durability comes from three copies in three machines on independent power, with the disk write happening asynchronously behind them. This is a deliberate trade of one durability mechanism (disk flush) for another (replication), and the accepted failure is losing all three at once.

Recovery is replay. Because the log is the state and the engine is a fold over it, recovery is the same replay function: load the last snapshot (a periodic dump of the book, so recovery starts from a recent point) and replay every entry after it. A 500,000-order market snapshot at 24 bytes per order is 12 MB, written at 1 GB/s in about 12 ms, so take one every minute; replaying a 60-second tail (about 513,000 messages at 1 us each) is about 0.51 s, inside the one-second target. Intraday failover does not use this path at all: the hot standby has been folding the same log continuously and is already current, so promoting it is a routing change. Replay matters for a pre-open restart, and for the regulator reconstructing any moment of any day.

The part that is easy to miss is the divergence check. A standby that has quietly drifted and then takes over is worse than an outage: it produces a book no member can reconstruct from the feed they were given, and nobody finds out until reconciliation. So the standby hashes its output for every message and the primary compares; on a mismatch the exchange halts the affected symbol instead of failing over to a machine it can no longer trust. An outage is recoverable; a book no member can reconstruct is not.

Market data fanout, and why TCP unicast fails

One match produces one change, and every one of 500 subscribers needs it. TCP is the standard reliable protocol (a connection per peer, numbered bytes, automatic retransmission), which here means one copy of every message per subscriber. The bandwidth (188 Gbps vs 0.376 Gbps for multicast) is not even the reason unicast loses.

The real reason: sendmsg, the call that hands one message to one connection, must be made once per subscriber, in some order. There is no way to make 500 happen at once, so at ~1 us each the last subscriber’s copy leaves 500 us after the first, 43 times the exchange’s entire internal budget, and the order served is whatever order the loop iterates in. That is not a performance problem but 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 card or CPU cannot fix it, because the copies are inherently sequential.

flowchart TD
    subgraph U["Unicast: publisher copies once per subscriber"]
      P1["Publisher"] -->|"copy 1"| S1["Sub 1"]
      P1 -->|"copy 2"| S2["Sub 2"]
      P1 -->|"copy 500, 500 us late"| S3["Sub 500"]
    end
    subgraph MC["Multicast: switch fabric copies"]
      P2["Publisher"] -->|"one packet"| SW["Switch fabric"]
      SW --> T1["Sub 1"]
      SW --> T2["Sub 2"]
      SW --> T3["Sub 500, same instant"]
    end

Multicast fixes it structurally: the publisher sends one packet, the switch fabric replicates it, and every subscriber’s copy leaves the final switch at the same instant. Three consequences are the engineering content:

• UDP does not retransmit, so every message carries seq. Noticing a gap becomes the subscriber’s job. That sequence number was already there for determinism, so the feature is free.
• Publish two identical feeds, A and B, over disjoint paths. A subscriber watches both, matches by sequence number, and takes whichever arrives first, so a drop on one path costs zero recovery time. The cost is one extra copy, about 0.752 Gbps total, still inside a single 1-gigabit card.
• Retransmission and snapshots live in a separate service with its own machines and bandwidth. A drop at a shared uplink is missed by all 500 at once, so serve them by re-multicasting the missing range (one send satisfies all 500) and rate-limit the per-subscriber fallback so no one can monopolise it (the same idea as distributed rate limiting).

A subscriber that joins mid-day cannot replay from the open, so a dedicated channel continuously cycles per-symbol images of the book. Averaging 167 resting orders per symbol at 24 bytes, a full cycle over 3,000 symbols is about 12 MB, and at 100 Mbps a newcomer is fully in sync within about one second. Publish the snapshot at L3 (every individual order), because L3 is what lets a member rebuild the book exactly, and exact reconstruction is what determinism was bought for; an L2 snapshot would leave totals a member cannot decompose back into a queue, so time priority would be invisible.

Pre-trade risk, and speed bumps

Every order must pass a set of checks before it can trade. Five run on every order, on the hot path:

The notional value is quantity times price (the money at stake, not the share count); a fat-finger order is one where a human typed an extra zero; self-trade prevention stops one account matching its own order, which transfers nothing but moves the published price and so is treated as manipulation. Five indexed loads into pinned per-account arrays cost ~500 ns worst case (all missing cache), budgeted at 1.0 us, about 8.7% of the round trip, and not optional: an exchange without pre-trade risk is one runaway algorithm away from a market-wide incident. The checks are cheap only because their state is pinned in RAM and reached by array index; they would not be cheap against a database.

Four of the five checks are per-order and local. The fifth is not. Buying power (the money an account is currently allowed to commit) is one number per account, but orders for one account arrive at many gateways at once, so it is exactly the cross-shard mutable state the sharding rule forbids. Decrementing one shared counter would serialise the gateways and add a network round trip (9.8 us) to a check budgeted at 1. The fix is to lease the credit: each gateway is handed a slice of the account’s buying power in advance and checks against its own slice, with no coordination. The failure mode is the price: split $10 M evenly across 8 gateways and a legitimate $2 M order is rejected by a gateway holding a $1.25 M lease while $8.75 M sits idle on the other seven. The usual mitigations apply: size leases by observed usage, refresh them asynchronously off the hot path, and keep a slow path (~50 us) that reclaims credit from peers for the rare large order. It is structurally the same tradeoff as dividing a rate limit across nodes.

A speed bump is a deliberate delay inserted into the inbound path, meant to make a microsecond of speed advantage worth less. Whether it works, and whether it fits this design at all, depends on whether the delay is random or fixed.

A random bump destroys price-time priority. If each order’s delay is drawn uniformly from 0 to 3,000 us, two orders arriving a microsecond apart get independent delays and the later one can land first. For a one-microsecond gap the earlier order wins only about 50.03% of the time, a coin flip. That is not “reducing the value of speed”, it is replacing price-time priority with price-lottery priority, and it is nondeterministic: two replays of the same input produce different books, which breaks determinism and takes regulatory reproduction and standby verification down with it.

A fixed bump preserves ordering exactly. Add a constant delay (say 350 us) to every order that would take liquidity; every arrival shifts by the same amount, so relative order is untouched, replay stays deterministic, and the engine does not change. What it changes is one race: when news breaks, a market maker’s posted price is instantly stale, and the taker (whoever crosses to hit it) races the maker’s own cancel. Apply the bump to takers and not to cancels, and the maker gets 350 us of warning, at which point latency arbitrage (profiting purely from reaching a known-stale quote first) stops being profitable.

But an asymmetric bump does not make the venue neutral. It transfers the value of speed from takers to makers: makers protected this way can quote more aggressively, so spreads narrow, and that narrowing is paid for by takers who can no longer capture stale quotes. It is a policy choice about who the venue is for, and it should be argued as one, not presented as fairness with no counterparty.

Bottlenecks and scaling

In five of the six tiers the binding constraint is not throughput.

Receive-side scaling (RSS) is a network-card feature that hashes each packet’s header to pick which receive queue it lands in, so several cores pull packets in parallel; steering by account instead of the default hash keeps one member’s traffic from crowding another’s queue. Pipelining the sequencer means releasing the message downstream immediately and confirming the majority ack afterwards. It removes 4.5 us from the critical path at the cost of having released something not yet known durable, which is a durability decision in a latency costume.

Symbol rebalancing is the operation nobody plans for. Moving a symbol between engines means draining its book and transferring its state, and doing that intraday means a window with no single consistent owner, precisely what the design refuses to allow. So do it between sessions, and provision each engine for the growth of its busiest symbol.

Failure modes

Several of these have almost no symptom, which is what makes them dangerous. Twice, the correct response is to stop trading.

A bust is the exchange formally cancelling a trade after the fact under published “clearly erroneous execution” rules; the log is what makes the decision reviewable. The last row’s prevented, not handled is the point: a 100-ms garbage-collection pause is 200,000 times a 470 ns hop and cannot be recovered from inside it, so the design removes the possibility instead of adding a response.

Alternatives rejected

Each is a choice a reasonable engineer would make in almost any other system, with the number that rules it out here.

Two rows lean on terms defined elsewhere. A write-ahead log (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 replays forward. It is that mandatory fsync that costs the ~100 us (see database internals). Raft is a consensus algorithm that keeps a replicated log consistent, including leader election and live membership changes; this design keeps its majority-acknowledgement idea and rejects the rest, because election and membership changes involve allocation and unbounded delays that do not fit a 4.5 us window.

The assumptions the design rests on

Every number here rests on an assumption. Some you are free to pick (being wrong costs a re-derivation); some are load-bearing: if wrong, the design is not merely suboptimal, it is a different design.

Conclusion

An exchange is a deterministic state machine wrapped in a network. The state machine (a sorted book and price-time priority) is easy; the wrapper is the whole engineering problem.

• It is a latency problem, not a throughput one. The peak fits on 43% of one core, so every choice is paid for in latency or variance, not capacity.
• Shard by symbol and nothing else. Symbols are the only independent axis; sharding buys low utilisation (a 52x cut in queueing delay) and blast-radius isolation, not throughput. Threading the engine buys 23% at best and costs determinism.
• The book is an array of price levels with a FIFO per level, a hash from order id to node, and a two-level occupancy bitmap. Add, cancel, and best-price repair are O(1); walking the array instead is O(n) on the hottest operation in the system.
• The sequencer’s log is the exchange’s state. It defines the total order, and it is 39% of the 11.55 us budget, spent on replicating to a majority so no acked order is ever lost. The book is a materialized view; recovery is replay.
• Market data goes out by multicast, because unicast leaves the 500th subscriber 43 budgets late regardless of bandwidth. Fairness of publication, not capacity, is the constraint.
• Determinism forbids wall-clock reads, floating point, hash iteration order, allocation on the path, threads, and randomness. In return it makes a hot standby free: the same program on the same log, checked by a per-message hash.

One line to remember: the exchange is a fold over one numbered log; get the order and the layout right and every hard part after that is spent buying down latency and variance, never capacity.

Further reading

• Nasdaq TotalView-ITCH and OUCH protocol specifications: real, published market-data and order-entry wire formats, and a concrete example of the fixed-offset binary design discussed here.
• The FIX Protocol specification (fixtrading.org): the tag-value text format used for order entry at the public edge of many venues.
• The LMAX Disruptor (Thompson, Farley, Barker, Gee, Stewart): the technical paper behind a production exchange’s single-threaded business-logic core and ring-buffer handoff.
• Aeron (Real Logic): an open-source reliable UDP/multicast messaging system built for the low-jitter fanout problem in this lesson.
• “Latency Numbers Every Programmer Should Know” (Jeff Dean / Peter Norvig): the hardware-latency figures every microsecond estimate here traces back to.
• The estimation chapter and the message-queue chapter: the latency table and the append-only-log semantics reused throughout.