“Match buy and sell orders” sounds like a database join. Then you look at the constraints. A million orders a second arrive from thousands of members. Two orders for the same stock at the same price must fill in the exact order they arrived - not roughly, exactly - because that ordering is money and it is legally auditable. The same stream of orders replayed on a backup machine must produce byte-for-byte the same trades, or your failover invents fills that never happened. A single mismatched fill is a broken trade, a regulatory incident, and a lawsuit. This is not a CRUD service with a queue in front. It is a deterministic state machine that happens to be one of the most latency-sensitive pieces of software people build.

The core of this problem is that the matching engine must be correct, fast, and deterministic all at once, and those three pull against each other. Correctness means strict price-time priority and no lost or duplicated orders. Fast means single-digit microseconds per match at 1M orders/sec. Deterministic means the same input sequence always produces the same output sequence, on any machine, at any time - which is what makes replication, replay, audit, and recovery even possible. Every decision in this design exists to hold those three together. Let me build it properly.

Functional Requirements (FR)

In scope:

  • Accept orders. Members submit limit orders (buy/sell at a price or better) and market orders (buy/sell at the best available price) for a given symbol, with a quantity.
  • Cancel and modify. A member can cancel a resting order or modify it (price/quantity). A modify that changes price or increases quantity loses time priority; a pure quantity decrease keeps it.
  • Match on price-time priority. The engine matches incoming orders against the opposite side of the book: best price first, and within a price level, the order that arrived earliest fills first. This is the heart of the system.
  • Maintain the limit order book. Per symbol, keep every resting (unfilled) order organized by side, price level, and arrival time.
  • Emit execution reports. Every fill, partial fill, cancel, and reject produces a message back to the owning member (a “drop copy” / execution report).
  • Publish market data. Every book change produces a market-data update: trades (last price, size) and book depth (bid/ask levels). This feed drives every downstream consumer.
  • Be deterministic. Given the same ordered sequence of inbound messages, the engine produces exactly the same sequence of trades and book states, every time, on every replica.

Explicitly out of scope (name it so you own the scope):

  • Clearing and settlement. Once a trade is matched, moving the actual securities and cash (T+1/T+2 settlement, the clearing house) is a separate system. I match; I do not settle.
  • Pre-trade risk and margin checks. Whether a member is allowed to place this order (buying power, position limits, fat-finger checks) is a gateway/risk concern upstream of matching. I treat the risk decision as an input: an order that reaches the engine is already authorized.
  • Auth, membership, and KYC. Sessions are authenticated at the gateway; the engine trusts what it receives.
  • Complex order types and derivatives. Iceberg, stop, pegged, auction crosses, and the options/futures book are real but I design the core continuous limit-order book first and name the extensions.
  • Regulatory reporting internals. I produce the immutable audit journal that reporting is built on; I do not build the reporting pipeline itself.

The decision that drives everything: the matching engine is a single-threaded, in-memory, deterministic state machine per symbol. No database in the hot path, no locks, no wall-clock, no randomness. Every hard requirement - price-time priority, microsecond latency, and reproducibility - follows from that one choice, and the rest of the system exists to feed it an ordered input and to make it survive a machine failure.

Non-Functional Requirements (NFR)

  • Scale: ~1,000,000 orders/sec aggregate across all symbols at peak (open/close bursts run higher). A liquid market has ~5,000-10,000 symbols, but volume is heavily skewed - a few hundred symbols carry most of the flow. Peak per hot symbol can be 50K-100K orders/sec.
  • Latency: the tick-to-trade path the member cares about - order received at the engine to execution report out - should be single-digit microseconds at the median and low tens of microseconds at p99 for the matching step itself. End to end including network and gateway is tens to low hundreds of microseconds. This is a system where p99 and p99.99 matter more than the median; a 1ms GC pause is a catastrophe.
  • Availability: 99.99%+ during market hours, with sub-second failover. The market cannot go dark. But availability here is subordinate to correctness - it is better to halt a symbol than to double-fill an order.
  • Consistency: strict sequential consistency per symbol. Every order is processed in one total order, and that order is the truth. Across symbols there is no ordering requirement (they are independent books), which is exactly what lets us shard.
  • Durability: every accepted order and every resulting trade is durably journaled before it is acted on visibly. A crash must never lose a trade or replay one. Recovery reconstructs the exact book state.
  • Determinism: the non-negotiable one. Same input sequence in, same output sequence out, bit for bit, independent of machine, thread scheduling, time of day, or replica. This is what makes replication, hot-standby failover, end-of-day replay for audit, and testing possible at all.

The tension to state up front: latency wants everything in one thread in memory with no I/O; durability and availability want replication and persistence, which are I/O. We resolve it by making the engine a pure deterministic function of an ordered input log, persisting and replicating the input log (cheap, sequential, off the hot path) rather than the engine’s internal state, and reconstructing state by deterministic replay. Determinism is not a nice-to-have here - it is the mechanism that lets a low-latency in-memory engine also be durable and highly available.

Back-of-the-Envelope Estimation (BoE)

Real numbers with the arithmetic, because they dictate the architecture.

Order throughput:

Peak aggregate: 1,000,000 orders/sec
Assume ~40% of orders are cancels/modifies (very typical - HFT churns quotes):
  ~600K new orders/sec, ~400K cancel/modify/sec
Each new order that crosses generates >= 1 trade; many generate several
  (it sweeps multiple price levels). Assume ~0.5 trades per inbound message avg.
  => ~500K trades/sec at peak.

A single order must therefore be handled in well under a microsecond of CPU on average on the busiest engine, which is only possible with tight in-memory data structures and no I/O in the critical path.

Order book memory (per symbol, then aggregate):

A resting order: order_id 8B, member_id 4B, price 8B, qty 8B,
  remaining_qty 8B, timestamp/seq 8B, side 1B, prev/next ptrs 16B
  => ~60-80 bytes, round to ~100B with allocator overhead.

A hot symbol might rest ~1M live orders (deep book, heavy quoting):
  1M * 100B = ~100 MB for one very deep symbol.
Most symbols rest far fewer, say ~10K-50K live orders:
  50K * 100B = ~5 MB.

Whole market: dominated by the hot names. Even 200 deep symbols * 100MB
  = ~20 GB, plus the long tail. Comfortably fits in RAM on modern servers,
  and it MUST - the book never touches disk in the hot path.

The headline: the entire live order book for the whole market is tens of GB. It fits in memory, sharded across engines. That is the whole reason an in-memory single-threaded design is viable.

Journal (input log) storage:

Per inbound message (order/cancel) journaled: ~64 bytes packed binary
  (seq, session, symbol, side, price, qty, type, checksum).
1M msg/sec * 64B = 64 MB/sec = ~3.8 GB/min
Trading day ~6.5 hours = 23,400 sec:
  1M * 64B * 23,400 = ~1.5 TB/day of input journal.
Plus the output trade/exec journal, similar order of magnitude:
  ~500K trades/sec * ~64B * 23,400 = ~750 GB/day.

~2-3 TB/day of sequential journal, retained for years for audit (regulators want 7+ years). This is append-only sequential writes - the friendliest possible disk pattern - and it rolls to cheap cold storage after the day closes.

Market data bandwidth:

Every book change fans out to thousands of subscribers.
Say each update is ~50B and there are ~1.5M book-changing events/sec at peak.
Raw feed: 1.5M * 50B = ~75 MB/sec = ~600 Mbps for the full-depth feed.
Fanned out to 5,000 subscribers, that is 5,000 * 600 Mbps if unicast = 3 Tbps.

That number is why market data is multicast, not unicast - the exchange publishes once to a multicast group and the network replicates. Unicasting full depth to every subscriber is physically impossible; multicast turns 3 Tbps back into ~600 Mbps on the wire.

The takeaway: raw order throughput (1M/sec) is high but the per-message work is tiny and in-memory. The book fits in RAM. The genuinely hard parts are matching correctly on price-time priority at that rate, doing it deterministically, fanning out market data without melting the network, and surviving a failover without losing or duplicating a single trade. That is where the design earns its keep.

High-Level Design (HLD)

The spine is a set of stateless gateways that terminate member sessions and normalize orders, a sequencer that stamps every inbound message with a global per-symbol sequence number and writes it to a durable, replicated input log, a fleet of matching engines (one active writer per symbol) that consume the log in sequence and mutate the in-memory order book, and a publisher that emits execution reports and market data. Because the engine is a deterministic function of the sequenced log, a hot standby replays the same log and is ready to take over.

   Members (brokers / HFT / algos)
        │  FIX / binary order entry (order, cancel, modify)
        ▼
 ┌──────────────────────────┐
 │   Order Gateways          │  authN, session, rate/risk gate,
 │   (stateless, N of them)  │  normalize to internal binary msg
 └───────────┬──────────────┘
             │  normalized order messages
             ▼
 ┌──────────────────────────┐        writes ordered log
 │   Sequencer               │───────────────────────────────┐
 │  assigns global seq per   │                                │
 │  symbol; SINGLE point of  │                                ▼
 │  ordering. Deterministic. │                    ┌────────────────────────┐
 └───────────┬──────────────┘                     │  Input Log (journal)    │
             │ sequenced stream (partitioned       │  append-only, replicated│
             │ by symbol)                          │  the SOURCE OF TRUTH    │
   ┌─────────┼───────────────────────┐             └────────────┬───────────┘
   ▼         ▼                       ▼                          │ replay
┌────────┐┌────────┐            ┌────────┐                      ▼
│Engine A││Engine B│    ...     │Engine K│              ┌────────────────┐
│symbols ││symbols │            │symbols │              │ Hot Standby     │
│0..N    ││N..2N   │            │ ...    │              │ engines (replay │
│single- ││single- │            │        │              │ same log, warm) │
│thread  ││thread  │            │        │              └────────────────┘
│in-mem  ││in-mem  │            │        │
│ BOOK   ││ BOOK   │            │        │
└───┬────┘└───┬────┘            └───┬────┘
    │ trades + book deltas          │
    ▼                               ▼
 ┌──────────────────────────────────────────┐
 │   Publisher                                │
 │  - Execution reports -> owning member       │
 │    (drop copy, unicast, reliable)           │
 │  - Market data -> MULTICAST groups          │
 │    (trades + depth, to all subscribers)     │
 └───────────────────┬────────────────────────┘
                     │
        ┌────────────┴─────────────┐
        ▼                          ▼
  Member drop copies        Market data subscribers
  (fills/cancels)           (thousands, via multicast)
                     │
                     ▼
         ┌────────────────────────────┐
         │  Downstream (off hot path)  │
         │  clearing/settlement,       │
         │  surveillance, audit store  │
         └────────────────────────────┘

Order flow (a limit order that partially fills):

  1. A member sends a new order over a FIX or binary session to a gateway. The gateway authenticates the session, applies the pre-trade risk gate (position/fat-finger - treated as an input decision here), and normalizes the order into a compact internal binary message tagged with symbol, side, price, qty, type, and the member’s session/order id.
  2. The gateway forwards the normalized message to the sequencer. The sequencer is the single point that decides “this message is the Nth message for this symbol.” It stamps a monotonic per-symbol sequence number and a logical timestamp, and appends the message to the input log, which is durably persisted and replicated before the message is released downstream. This log, in sequence, is the entire truth of the system.
  3. The sequenced message is delivered to the matching engine that owns that symbol. The engine, running the symbol’s book single-threaded in memory, processes messages strictly in sequence: it looks at the opposite side of the book, matches against the best-priced, earliest-arrived resting orders until the incoming order is filled or no more crossing liquidity exists, and rests any remainder on the book.
  4. Each fill produces a trade (matched buy id, sell id, price, qty, seq). The engine hands trades and the resulting book deltas to the publisher.
  5. The publisher sends execution reports back to the two owning members (you filled 300 @ 101, 200 resting) and emits market-data updates (a trade print and new bid/ask depth) to the multicast feed. Downstream clearing, surveillance, and audit consume from the journals off the hot path.

Recovery flow: the hot standby for each engine consumes the same input log and applies the same deterministic logic, so its in-memory book is identical to the primary’s (modulo a tiny lag). If the primary dies, the standby - already warm and caught up to the last sequenced message - takes over and continues from the next sequence number. Because both are pure functions of the same ordered log, no trade is lost or invented.

The structural insight: the sequencer + input log turn matching into deterministic state-machine replication. The engine holds no truth that is not derivable from the log; the log is the durable, replicated, ordered source of truth; and every replica, standby, and end-of-day audit replay is just “apply the log again.” Latency lives in the tiny in-memory engine; durability and availability live in the cheap sequential log around it.

Component Deep Dive

The hard parts, naive-first then evolved: (1) the order book data structure and price-time matching, (2) determinism, (3) scaling to 1M orders/sec, (4) fault tolerance and failover without losing or duplicating trades.

1. The order book and price-time priority

The job: given a stream of orders, match each incoming order against the opposite side at the best price, and within a price level fill the earliest-arrived resting order first - at up to 1M orders/sec.

Naive approach: one sorted list of orders per side

Keep all buy orders in one list and all sell orders in another, sorted so the best price is at the front. To match an incoming sell, walk the buy list from the front taking orders while the buy price >= sell price.

buys  = sorted list of orders, best (highest) price first
sells = sorted list of orders, best (lowest)  price first

def match(incoming_sell):
    while incoming_sell.qty > 0 and buys and buys[0].price >= incoming_sell.price:
        resting = buys[0]
        fill = min(resting.qty, incoming_sell.qty)
        trade(resting, incoming_sell, resting.price, fill)
        resting.qty -= fill; incoming_sell.qty -= fill
        if resting.qty == 0: buys.pop(0)
    if incoming_sell.qty > 0:
        insert_sorted(sells, incoming_sell)   # rest the remainder

Where it breaks:

  • Insertion is O(n). Resting a new limit order means inserting into a sorted list of possibly a million orders - O(n) shifting. At a million orders/sec on a deep book, this is dead on arrival.
  • Cancel is O(n). A cancel arrives with an order id; finding it in the list is a linear scan. With 40% of traffic being cancels, this dominates and collapses.
  • Price-time priority is fragile. Keeping the list sorted by price and by time-within-price requires a stable sort and careful insertion; it is easy to get subtly wrong, and “subtly wrong ordering” is a mismatched fill.
  • Cache-hostile. A list of scattered order objects thrashes the CPU cache; at microsecond budgets, cache misses are the whole cost.

A single flat sorted list conflates two different lookups (by price, by id) and makes both slow.

Evolved approach: price levels of FIFO queues, plus an order-id index

Model the book the way the priority rules actually decompose: price first, then time. So structure it as a map from price to a FIFO queue of orders at that price, per side, plus a direct index from order id to its node for O(1) cancel.

  • Per side, a collection of price levels sorted by price. The best bid is the highest buy price; the best ask is the lowest sell price. Store levels in a structure that gives O(1) access to the best and O(log n) insert of a new level - a balanced tree keyed by price, or for a bounded tick range, a flat array indexed by price (“book as an array of buckets”), which is O(1) and cache-friendly.
  • Each price level is a FIFO queue (a doubly linked list) of orders in arrival order. This is time priority: the head of the queue arrived first and fills first. Resting an order is an O(1) append to the tail of its level. Filling takes from the head.
  • A hash map order_id -> node so a cancel is O(1): jump to the node, unlink it from its level’s queue (doubly linked, so O(1) unlink), done. No scan.
Side (bids or asks):
  levels: price -> PriceLevel        # tree or array-of-buckets by price
  best:   pointer/index to best price level

PriceLevel:
  price
  fifo: doubly linked list of OrderNode (head = oldest = highest time priority)
  total_qty                          # cached sum for fast depth reporting

Global:
  order_index: order_id -> OrderNode  # O(1) cancel/modify lookup

def match(incoming):                  # incoming is a buy, symmetric for sell
    while incoming.qty > 0 and ask_side.best exists
                              and ask_side.best.price <= incoming.price:
        level = ask_side.best
        resting = level.fifo.head          # earliest at best price -> time priority
        fill = min(resting.remaining, incoming.qty)
        emit_trade(resting, incoming, level.price, fill)  # trade at RESTING price
        resting.remaining -= fill; incoming.qty -= fill; level.total_qty -= fill
        if resting.remaining == 0:
            level.fifo.pop_head(); order_index.remove(resting.id)
            if level.fifo.empty: ask_side.remove_level(level); advance best
    if incoming.qty > 0 and incoming.type == LIMIT:
        level = bid_side.get_or_create_level(incoming.price)
        level.fifo.append(incoming)        # O(1), preserves time priority
        order_index[incoming.id] = incoming.node

Why this is right:

  • Price-time priority falls out of the structure. “Best price level” gives price priority; “head of the FIFO at that level” gives time priority. There is no sort to get wrong - the data structure is the rule.
  • Every hot operation is O(1) or O(log n). Match takes from the head; rest appends to the tail; cancel unlinks by id. Nothing is a linear scan. A modify that only reduces quantity mutates in place (keeps time priority); a modify that raises quantity or changes price is a cancel + re-add (loses time priority), matching exchange rules.
  • The trade price is the resting order’s price, not the incoming order’s - the resting order set the standing quote and gets price improvement. This is a real matching rule that the structure makes natural (you fill against the resting node, at its level’s price).
  • Cache-friendly at the top of book. Where it matters most - the best few levels that almost every order touches - the array-of-buckets layout keeps the hot data contiguous, so the common case stays in L1/L2 cache and inside the microsecond budget.
  • Market orders and sweeps are the same loop. A market buy just has an effectively infinite price limit; it walks levels best-first until filled or the book is empty. Sweeping multiple price levels is the same while-loop advancing best.

This structure, the “limit order book” as price levels of FIFO queues with an id index, is what every real matching engine uses, because it is the direct encoding of the matching rules and it makes all four hot operations cheap.

2. Determinism

The job: the same ordered sequence of inbound messages must always produce exactly the same sequence of trades and book states, on any machine, at any time. Without this, you cannot replicate, fail over, replay for audit, or even reproduce a bug.

Naive approach: match concurrently and use the system clock

The obvious performance instinct: use threads to parallelize matching, and stamp each order with System.now() for time priority. Sort by that timestamp.

on_order(order):
    order.ts = wall_clock_now()        # for time priority
    submit_to_thread_pool(match, order)  # parallel matching

Where it breaks:

  • Concurrent matching is non-deterministic. Two orders for the same symbol handled on two threads race. Which one takes the resting liquidity depends on thread scheduling, which varies run to run and machine to machine. Two replicas fed the identical input produce different fills. Failover is now unsafe because the standby’s book disagrees with the primary’s.
  • Wall-clock time is non-deterministic. now() returns different values on different machines and on replays. If time priority depends on the wall clock, a replay for audit produces a different order of fills than the original run. Two orders that arrived “at the same time” tie-break differently on the standby.
  • Any hidden non-determinism poisons it: hash-map iteration order, floating-point summation order, a random tie-break, thread-local state. Any of these makes two runs diverge, and divergence in a matching engine means invented or lost trades.

Concurrency and wall-clocks feel like the way to go fast and to order by time, but they destroy the one property the whole fault-tolerance story depends on.

Evolved approach: single writer per symbol, sequence-as-time, pure function of the input log

Make the engine a deterministic state machine: its output depends only on the ordered input, nothing else.

  • One single-threaded writer per symbol. All messages for a symbol are processed by exactly one thread, strictly in sequence order. There is no concurrency within a symbol’s book, so there are no races and no scheduling-dependent outcomes. Parallelism comes from running different symbols on different threads/engines (they share no state), never from parallelizing one book. This is the key: independence across symbols gives us all the parallelism we need without sacrificing determinism within a symbol.
  • Sequence number is the clock. Time priority is defined by the sequencer’s monotonic sequence number, not the wall clock. The order with the lower sequence number for a symbol arrived “first,” by definition. The sequence is assigned once, durably, at the sequencer, so it is identical on the primary, the standby, and every future replay. The engine never calls now() in a way that affects matching; any timestamp it records is carried in the sequenced message, not read locally.
  • Ban every other source of non-determinism. No random() in matching logic (tie-breaks are always by sequence). No hash-map iteration where order matters (use ordered structures for anything that drives output). No floating-point where summation order could vary - prices and quantities are integers (ticks and lots / minor units), never floats, so arithmetic is exact and associative. No dependency on thread scheduling, memory addresses, or system state. The engine is a pure function apply(state, message) -> (state', outputs).
# The entire engine is this loop, per symbol, one thread:
state = empty_book(symbol)
for msg in input_log.stream(symbol):     # strictly in sequence order
    state, outputs = apply(state, msg)   # PURE: no clock, no random, no threads
    publish(outputs)                     # trades + book deltas + exec reports

# Determinism guarantee:
#   same input_log  ==>  same sequence of (state, outputs)
#   on the primary, the standby, and any replay tomorrow.

Why this is right:

  • Replication becomes trivial and safe. The standby runs the identical pure function over the identical sequenced log and gets the identical book. Failover is safe because there is no disagreement to resolve.
  • Replay for audit and debugging is exact. To answer “why did order X fill at that price,” or to reproduce a production bug, replay the day’s input log through the same binary and get bit-identical output. This is priceless for a regulated system.
  • Testing is deterministic. A recorded input log is a perfect, repeatable test case. No flaky tests, no “works on my machine.”
  • Sequence-as-time makes ties unambiguous. There is exactly one total order per symbol, decided once, so “who was first” is never in question and never varies.

Determinism is not a performance feature; it is the property that makes a fast in-memory engine also durable, replicated, auditable, and testable. You give up in-book concurrency (which you did not need - scale across symbols instead) and in return you get a system you can actually operate and prove correct.

3. Scaling to 1M orders/sec

The job: handle a million orders a second across the market when a single-threaded engine per symbol has a finite ceiling.

Naive approach: one big engine for all symbols

Run every symbol’s book in one process, one thread, matching everything in a single sequence.

Where it breaks:

  • One thread has a hard ceiling. A single core can match a few million trivial operations/sec, but real matching (multi-level sweeps, cancels, publishing) is heavier, and one thread cannot absorb 1M orders/sec across a busy market plus the market-data fanout. It saturates.
  • Head-of-line blocking across symbols. A burst in one hot symbol (say the index heavyweight at the open) stalls processing of every other symbol, because they share the one thread and the one sequence. Unrelated stocks should never wait on each other.
  • No horizontal headroom. You cannot add a machine to help, because it is one global sequence and one thread by construction.

A single global engine conflates symbols that are completely independent, turning that independence into contention instead of parallelism.

Evolved approach: shard by symbol across engines, per-symbol sequencing

Exploit the fact that different symbols are independent order books - a buy for AAPL never matches a sell for MSFT - so they can run fully in parallel with no coordination.

  • Shard key = symbol. Partition the ~10,000 symbols across a fleet of matching engines. Each engine owns a disjoint set of symbols and runs each of its books single-threaded. Within a symbol, strict sequence and determinism hold; across symbols, everything is embarrassingly parallel.
  • Per-symbol (per-partition) sequencing. The sequencer assigns sequence numbers per symbol, not globally, so there is no single global counter bottleneck and no cross-symbol ordering to maintain (there is no such requirement). The input log is partitioned by symbol; each partition is an independent ordered stream feeding one engine.
  • Balance by load, not by count. Because volume is wildly skewed - a few hundred symbols carry most of the flow - you place hot symbols carefully: a very hot name may get a dedicated engine/core, while thousands of quiet names share one. Rebalancing moves a symbol by draining it (stop accepting, let it quiesce, checkpoint, reassign) - rare and done between sessions where possible.
Sequencer partitions by symbol:
   hash/route(symbol) -> partition -> owning engine

Engine A: {AAPL}                  # so hot it gets its own core
Engine B: {MSFT, GOOG}
Engine C: {2,000 low-volume symbols round-robined across its cores}
...
Each engine: N single-threaded books, one thread per busy symbol,
             quiet symbols multiplexed on shared threads.

Aggregate throughput = sum of per-engine throughput.
1M orders/sec spread over, say, 20-50 engines = 20K-50K orders/sec each,
well within a single-thread-per-hot-symbol budget.

Why this is right:

  • Linear horizontal scale. Need more capacity? Add engines and move symbols onto them. Throughput is the sum across shards because shards share nothing.
  • No head-of-line blocking across symbols. A storm in one name is isolated to its engine/core; the rest of the market is unaffected.
  • Determinism is preserved per shard. Each symbol still has one writer and one sequence, so everything in deep dive 2 holds. Sharding buys scale without costing correctness, precisely because the shard boundary (symbol) is also the consistency boundary.
  • Hot-symbol handling is a placement problem, not an architecture change. The knob is “how many symbols per core,” tuned by observed load, not a redesign.

The whole scaling story rests on one observation: the natural shard key (symbol) is also the natural consistency boundary, so partitioning by it gives parallelism for free without ever needing a cross-symbol transaction in the hot path.

4. Fault tolerance and failover without losing or duplicating trades

The job: an engine machine will die mid-session. Recovery must produce a book identical to the instant before the crash, and must never lose an accepted order or replay a trade - all in sub-second failover while the market stays open.

Naive approach: periodically snapshot the book to disk

Every few seconds, serialize the in-memory book to disk. On crash, load the latest snapshot and resume.

Where it breaks:

  • You lose everything since the last snapshot. A snapshot 3 seconds old means every order and trade in those 3 seconds - millions of messages - is gone. At market speed, that is an unrecoverable hole.
  • Snapshotting stalls the hot path. Serializing a multi-GB book from the one matching thread introduces exactly the pauses (and GC pressure) the whole design fights to avoid.
  • It is not obviously consistent. A snapshot taken while messages are flowing can capture a torn, half-updated book unless you stop the world to take it, which you cannot afford.
  • Duplication on replay. If you resume from a snapshot and re-feed messages, without a precise “we processed up to sequence N” marker you re-apply orders already matched and duplicate trades.

Snapshots alone trade a huge data-loss window for a stall; neither is acceptable when the unit of loss is a real trade.

Evolved approach: state-machine replication over the replicated input log, plus periodic snapshots for fast start

Lean on determinism (deep dive 2): the engine is a pure function of the sequenced input log, so the log is the durable truth and the book is reconstructable by replay.

  • The input log is durably persisted and replicated before the engine acts. The sequencer writes each message to a replicated, append-only log (think a Raft/Paxos-backed sequence, or a synchronously replicated write to multiple journal nodes) and only releases it downstream once it is safely on a quorum. So no accepted, acknowledged order is ever lost - it is in the log before it is visible.
  • Hot standby by replay. For each engine there is at least one standby consuming the same partitioned log and applying the same deterministic logic. Its book tracks the primary within a few messages. On primary failure, the standby - already warm - takes over and continues from the next sequence number. No cold load, so failover is sub-second.
  • Sequence numbers make dedup exact. Every output carries the input sequence number that produced it. On failover, the standby knows the last sequence it applied; it resumes at the next one. Downstream consumers (publisher, clearing) dedupe on sequence, so a message straddling the failover is applied exactly once. No lost, no duplicated trades.
  • Snapshots exist only to bound replay time, not as the source of truth. Periodically (or on a dedicated non-hot-path replica), checkpoint the book state tagged with “as of sequence N.” On a full cold restart, load the latest snapshot and replay the log from N onward - seconds of replay instead of the whole day. The snapshot is an optimization on top of the log, never a substitute for it. It can be taken on the standby or a shadow replica so the primary’s hot path is never stalled.
Sequencer:  msg -> assign seq -> replicate to quorum (durable) -> release
                              (an order is never ACKed to the member until here)

Primary engine  : apply(log) -> book_P, outputs   (tagged with seq)
Standby engine  : apply(log) -> book_S            (identical, ~few msgs behind)

Failover:
   detect primary dead (heartbeat/lease timeout)
   standby is at seq = last_applied
   standby becomes primary, resumes at last_applied + 1
   downstream dedupe on seq  => exactly-once trades

Cold restart (both down):
   load snapshot@N  ->  replay log[N+1 ..]  ->  book rebuilt exactly

Why this is right:

  • No data loss: durability lives in the replicated log, and an order is acknowledged only after it is safely sequenced, so nothing accepted can vanish.
  • No duplication: sequence-tagged outputs plus downstream dedup make trades exactly-once across a failover, even for the in-flight message.
  • Fast failover: the standby is a warm, deterministic replay of the same log, so it is ready in sub-second time with an identical book - which is only possible because the engine is deterministic. A non-deterministic engine could not have a byte-identical standby.
  • Bounded recovery: snapshots cap cold-start replay to seconds, and are taken off the hot path so they never cost latency.
  • Correctness over availability, cleanly: if the standby ever diverges from the primary (a determinism bug), that is detectable by comparing output sequences, and the safe response is to halt the symbol rather than serve inconsistent fills. Halting one book is acceptable; a wrong fill is not.

Fault tolerance here is not a bolt-on; it is the direct payoff of determinism. Because book = fold(apply, log), replication is “share the log,” recovery is “replay the log,” and audit is “replay the log again” - one mechanism covering durability, availability, and provability at once.

API Design & Data Schema

Order entry API

Order entry is a low-latency binary or FIX protocol over a persistent session, not REST - REST/HTTP overhead alone would blow the microsecond budget. Shown here in a readable form; on the wire it is a fixed-layout binary message.

NEW ORDER   (member -> gateway)
{
  "session_id":    "MBR-042-S3",
  "client_ord_id": "c-88121",        // member's own id, echoed back
  "symbol":        "AAPL",
  "side":          "BUY",            // BUY | SELL
  "type":          "LIMIT",          // LIMIT | MARKET
  "price":         150250,           // integer ticks: 1502.50 (never float)
  "qty":           500,              // integer lots
  "tif":           "DAY"             // DAY | IOC | FOK | GTC
}
ACK (gateway -> member):
{ "client_ord_id": "c-88121", "order_id": "o-9f3a2", "status": "ACCEPTED",
  "seq": 880453120 }                 // engine sequence = time priority
REJECT: { "client_ord_id":"c-88121", "status":"REJECTED", "reason":"RISK_LIMIT" }

CANCEL   { "session_id", "order_id":"o-9f3a2", "symbol":"AAPL" }
         -> { "order_id", "status":"CANCELLED" | "TOO_LATE" }

MODIFY   { "session_id", "order_id":"o-9f3a2", "new_price", "new_qty" }
         -> { "order_id", "status":"REPLACED", "new_order_id":"o-9f3b7" }
         // price change or qty increase => new order_id, loses time priority

Execution reports (drop copy) and market data flow the other way:

EXECUTION REPORT (engine -> owning member, unicast, reliable)
{ "order_id":"o-9f3a2", "exec_type":"PARTIAL_FILL", "last_price":150250,
  "last_qty":300, "leaves_qty":200, "trade_id":"t-55021", "seq":880453121 }

MARKET DATA (engine -> ALL subscribers, MULTICAST)
  Trade:  { "symbol":"AAPL", "price":150250, "qty":300, "seq":880453121 }
  Depth:  { "symbol":"AAPL",
            "bids":[[150200, 1200],[150150, 900]],    // [price, total_qty]
            "asks":[[150250, 200 ],[150300, 1500]],
            "seq":880453121 }

Every message carries seq. That single field is what makes the whole system replayable, dedupable, and ordered.

Data model: mostly in-memory, journal is the store of record

The book itself is in-memory (deep dive 1); it is not a database. What is durably stored is the journal (input and output logs) plus periodic snapshots. Access patterns differ, so the stores differ.

1. Input journal - append-only sequential log, replicated. The source of truth. Not a relational database; a log (Kafka-like partitioned log, or a purpose-built replicated journal). Append-only sequential writes are the fastest durable pattern and match the access exactly: write once in order, read in order on replay.

Input log record (partitioned by symbol):
  seq            u64      # per-symbol monotonic sequence = time priority
  recv_ts        u64      # gateway receive time (carried, NOT used for matching)
  session_id     u32
  client_ord_id  u64
  symbol_id      u32      # interned symbol -> integer
  msg_type       u8       # NEW | CANCEL | MODIFY
  side           u8
  order_type     u8
  price          i64      # integer ticks
  qty            u64      # integer lots
  tif            u8
  checksum       u32
  Partition key: symbol_id      Ordering key: seq

2. In-memory order book - per engine, per symbol. The price-level FIFO structure from deep dive 1, plus the order_id -> node index. Volatile; reconstructed from snapshot + journal replay. Never touches disk in the hot path.

Book (in RAM):
  bids: price -> PriceLevel(fifo of OrderNode, total_qty)   # array-of-buckets or tree
  asks: price -> PriceLevel(...)
  order_index: order_id -> OrderNode
  last_applied_seq: u64

3. Output journal (trades + exec reports) - append-only log, replicated. Same log technology, separate stream. Feeds clearing, surveillance, and audit downstream, all off the hot path.

Trade record:
  trade_id  u64   seq u64   symbol_id u32
  price i64   qty u64
  buy_order_id u64   sell_order_id u64
  buy_session u32    sell_session u32
  aggressor_side u8              # which side crossed the spread
  ts u64

4. Snapshots - object storage, tagged by sequence. A serialized book “as of seq N,” written periodically off the hot path, used only to bound cold-start replay. Cheap blob storage; read rarely (only on recovery).

5. Reference / audit store - relational (Postgres) or a warehouse, off the hot path. End-of-day trades, order lifecycle, and reference data land here for reporting, regulatory queries, and dispute resolution. Relational because these are ad-hoc, joined, consistent queries - the opposite of the hot path’s needs.

Why a log for the truth and no SQL in the hot path: the matching engine needs microsecond, single-threaded, in-order processing with no I/O - a database call in the critical path is a non-starter (network + lock + disk = milliseconds, a thousand times the budget). The natural store of record for a deterministic state machine is its ordered input log, which is also exactly a partitioned append-only log’s strength. SQL earns its place downstream, where audit and reporting need joins and ad-hoc consistency and latency does not matter. Match the store to the access pattern: an append-only log for the hot deterministic core, relational for the analytical tail.

Bottlenecks & Scaling

Where it breaks first, in order, and the fix for each.

1. Single-thread ceiling on a hot symbol (breaks first on the busiest name). One book is one thread; the index heavyweight at the open can push 50K-100K orders/sec and saturate its core. Fix: give the hottest symbols dedicated engines/cores (deep dive 3), keep the per-symbol apply() path branch-light and allocation-free, and use the array-of-buckets book layout so top-of-book operations stay in L1/L2 cache. You cannot parallelize one book without losing determinism, so you make the one thread as fast as physically possible and isolate it.

2. The sequencer as a throughput bottleneck and single point of failure. Everything funnels through sequencing; if it is one global counter it is a bottleneck, and if it is one node it is a SPOF. Fix: partition the sequencer by symbol so there is no global counter - each partition sequences independently (no cross-symbol order is required). Make each partition’s sequencing fault-tolerant via consensus (Raft/Paxos or a synchronously replicated journal) so the durable, ordered log survives a node loss and the sequence never regresses or duplicates. The sequencer’s only job - assign seq, replicate to quorum, release - is deliberately tiny so it can be made both fast and reliable.

3. GC pauses and jitter in the hot path. A garbage-collection pause or a page fault of even 1ms is thousands of orders of latency - unacceptable at p99.99. Fix: allocation-free hot path - pre-allocated object/order pools, ring buffers instead of queues that allocate, primitive arrays instead of boxed collections; pin threads to cores (CPU affinity), disable frequency scaling, use huge pages, and busy-spin instead of blocking so there is no scheduler wakeup latency. In a managed runtime, size the heap so the hot path never GCs during a session, or use off-heap memory. Determinism helps here too: no now()/random() syscalls in the loop.

4. Market-data fanout melting the network. Full-depth updates to thousands of subscribers is terabits/sec if unicast (BoE). Fix: multicast the market-data feed - publish once to a group, let the network replicate. Offer tiered feeds (top-of-book vs full depth) so most subscribers take the cheap one. Sequence-number every update so a subscriber that drops a packet detects the gap and requests a retransmit from a replay server, keeping the hot publisher simple. Conflate/throttle depth updates for slow consumers rather than backpressuring the engine.

5. Cross-symbol operations (there should be almost none). Anything that needs two books atomically (e.g. a naive spread/pairs cross) would demand a distributed transaction and destroy the shared-nothing scaling. Fix: keep the core single-symbol. Multi-leg/spread instruments are modeled as their own synthetic book with their own single writer, or handled by a higher layer that legs into the individual books via normal orders - never a distributed transaction in the matching hot path. Preserve the invariant that one book = one writer = one shard.

6. Failover correctness (lost or duplicated trades). A crash mid-message is where trades get lost or double-counted. Fix: durable replicated input log written before ack, hot-standby replay, and sequence-tagged, deduped outputs (deep dive 4) give exactly-once trades across failover. Divergence between primary and standby is detected by comparing output sequences; the safe action is to halt the symbol, never to serve inconsistent fills.

7. Storage growth (~2-3 TB/day, retained for years). Regulatory retention forbids purging the journals. Fix: the journals are append-only sequential (cheap to write), rolled by day and archived to cold object storage after the session; snapshots bound how much must ever be replayed live. Reference/audit data lands in a warehouse partitioned by date for query.

8. Slow or misbehaving members / order storms. A runaway algo can flood a gateway and starve others. Fix: rate-limit and risk-gate at the gateway (per session), shed or throttle abusive sessions before they reach the sequencer, and keep gateways stateless and horizontally scaled behind the sequencer so member load spreads across many of them.

Shard keys, stated plainly: matching engines, input log, output log, sequencer partitions, and market-data grouping all shard by symbol - because symbol is simultaneously the unit of parallelism (independent books), the unit of ordering (one sequence per symbol), and the unit of consistency (one writer per book). Gateways are stateless (shard by session/connection for load only). Never shard the book itself internally - a book is one writer by design, and that single-writer property is what buys determinism.

Wrap-Up

The trade-offs that define this design:

  • Single-threaded per symbol, not concurrent. We deliberately refuse in-book parallelism and take all our scale from sharding across independent symbols. We trade the appeal of multi-threaded matching for determinism and simplicity, and lose nothing on throughput because symbols are independent.
  • Sequence-as-time, never the wall clock. Time priority is defined by the sequencer’s monotonic per-symbol sequence, so ordering is decided once, durably, and is identical on every replica and every replay. We give up “real” timestamps in the matching decision to get exact reproducibility.
  • The log is truth; the book is a replay. The durable, replicated input log is the source of record, and the in-memory book is a deterministic fold over it. This one idea gives us durability (log), availability (standby replay), recovery (snapshot + replay), and audit (replay again) from a single mechanism, while keeping the hot path in RAM with no I/O.
  • Correctness over availability, explicitly. When a replica diverges or a fault is ambiguous, we halt the symbol rather than risk a wrong fill. In a market, a halted book is recoverable; a mismatched trade is not.
  • A log for the hot core, SQL for the tail. The matching path stores nothing in a database; its store of record is an append-only log. Relational and warehouse stores live downstream where audit and reporting need joins and latency does not matter.

One-line summary: stateless gateways feed a symbol-partitioned sequencer that writes a durable, replicated input log, which single-threaded in-memory matching engines fold into a price-level FIFO order book to match on strict price-time priority - deterministically, so the same input always yields the same trades, letting a hot standby replay the same log for sub-second failover with exactly-once trades, while market data multicasts to thousands and the log is the one source of truth for scale, recovery, and audit.