An Order Book Is a State Machine

A matching engine consumes an ordered command stream and produces a deterministic sequence of state changes and trades.

Part Market MechanicsModel Price-time priorityGoal Make every transition explainable

The visualization processes one input at a time. Notice that an incoming order is not automatically inserted into the book. It first trades against compatible resting orders. Only an unfilled remainder becomes resting state.

That leads to the chapter’s central model:

previous state + one valid input
    → next state + ordered outputs

If the same initial state and the same ordered inputs can produce different results, the matching engine is not deterministic.

The book is state, not a picture

A displayed order book is usually drawn as bids on one side and asks on the other. That picture is only a projection of deeper state:

• Live orders and their remaining quantities.
• Price levels and their aggregate quantities.
• Queue order within each price level.
• Stable order identities.
• The sequence in which commands became authoritative.
• Instrument state such as open, halted, or auctioning.

For a basic continuous limit order book:

• Bids are ranked from highest price to lowest.
• Asks are ranked from lowest price to highest.
• The highest bid is the best bid.
• The lowest ask is the best ask.
• At one price, an earlier accepted order precedes a later order under time priority.

These are not merely display conventions. They determine who trades.

Commands and events are different

A participant sends a command:

Add order B1: buy 5 at 100
Cancel order B1
Replace order B1

The venue decides whether that command is valid, applies it to canonical state, and emits events:

Order accepted
Trade: 5 at 100
Order partially filled
Order rested
Order canceled
Command rejected

Keeping commands separate from events prevents a common systems mistake: treating a client’s intention as though it were already authoritative venue state.

An add command might produce:

• A rejection and no state change.
• One trade and no resting order.
• Several trades across price levels.
• Several trades followed by a resting residual.
• No trade and one new resting order.

The input is singular. The output can be a sequence.

The smallest useful state

A clear reference model can use standard structures:

#![allow(unused)]
fn main() {
use std::cmp::Reverse;
use std::collections::{BTreeMap, HashMap, VecDeque};

type Price = i64;     // integer ticks, never floating point
type Quantity = u64;
type OrderId = u64;

struct Order {
    id: OrderId,
    price: Price,
    remaining: Quantity,
    accepted_sequence: u64,
}

struct Book {
    bids: BTreeMap<Reverse<Price>, VecDeque<OrderId>>,
    asks: BTreeMap<Price, VecDeque<OrderId>>,
    orders: HashMap<OrderId, Order>,
}
}

This representation makes the semantics visible:

• The tree orders price levels.
• The deque expresses FIFO priority at one price.
• The hash map resolves an identity to live order state.
• Prices use integer ticks, avoiding ambiguous floating-point equality.

It is a good specification model. It is not automatically the fastest production representation.

Processing an add

Consider an incoming buy limit order with limit price P and remaining quantity Q.

It can trade while both conditions hold:

Q > 0
best ask exists
best ask price <= P

At each step:

1. Select the best ask.
2. Select the first order at that price.
3. Execute the smaller of taker remaining quantity and maker remaining quantity.
4. Decrement both quantities.
5. Remove a fully filled maker.
6. Remove an empty price level.
7. Continue until the taker is filled or no compatible ask remains.
8. If quantity remains, append the residual to its bid-price queue.

The sell path is symmetric.

incoming buy crosses when limit >= best ask
incoming sell crosses when limit <= best bid

In the model above, each trade occurs at the resting order’s price. That is a common continuous-book convention, but an actual venue’s rulebook is authoritative.

Price priority before time priority

Suppose the ask book contains:

101: S1(4), S2(3)
102: S3(8)

An incoming buy for five units with a limit of 102:

1. Trades four with S1 at 101.
2. Trades one with S2 at 101.
3. Never reaches S3.

Price priority selects the 101 level before 102. Time priority selects S1 before S2.

The taker’s limit is a constraint, not a request to pay exactly that price.

Partial fills create residual state

If a buy for ten units finds only six compatible units, two things happen:

executed quantity = 6
remaining quantity = 4

If its order instructions allow the residual to rest, four units join the bid queue at the order’s limit price. If the instruction is immediate-or-cancel, those four units are canceled instead. The matching algorithm therefore cannot be separated completely from order instructions.

A production event stream must make the distinction explicit. “Order accepted” does not imply “order fully executed,” and “trade occurred” does not imply “order is terminal.”

Canceling by identity is the first representation trap

The hash map can find order B2 in expected constant time. That does not mean the order can be removed from the middle of a VecDeque in constant time.

HashMap lookup                 expected O(1)
find/remove inside VecDeque    O(n) in that price-level queue

A strict constant-time cancel path needs a stronger representation, such as:

• Stable nodes in a slab or arena.
• Intrusive previous/next links within each price queue.
• A map from order ID to stable node handle.
• Lazy tombstones with bounded cleanup.

This is the same structural issue encountered in strict LRU caches. A lookup table provides identity resolution; it does not automatically provide constant-time structural mutation.

The reference model should stay simple until profiling shows that cancel behavior matters. The optimized model must preserve exactly the same externally visible transitions.

Core invariants

An implementation should check invariants after every command in tests and debug builds.

Ordered price levels

bids: strictly descending price
asks: strictly ascending price

Positive live quantities

Every order stored in a price queue has remaining quantity greater than zero. Empty price levels do not exist.

No crossed resting book

After one command has been completely processed:

best_bid < best_ask

If the two sides are compatible, matching work remains. A locked or crossed book may appear in feeds for venue-specific reasons, but it should not appear accidentally in this simple matching model.

FIFO within one price

The accepted sequence numbers in a price queue are increasing. Canceling an order does not change the relative order of its surviving neighbors.

Index agreement

Every live order is reachable through both:

• Its order-ID index.
• Exactly one side and price queue.

No queue entry points to a missing order, and no indexed order is absent from the book.

Quantity conservation

For every accepted order:

original quantity
    = executed quantity
    + canceled quantity
    + live remaining quantity

This equation is useful in unit tests, replay validation, and production reconciliation.

Deterministic replay

A deterministic matcher is naturally event-sourced:

snapshot + commands after snapshot → current state

Replay supports:

• Recovery after process failure.
• Reproducing disputed executions.
• Comparing two implementations.
• Testing optimized code against a reference model.
• Building historical books from authoritative events.

The ordering input must itself be authoritative. Wall-clock timestamps alone are insufficient when two messages can share a timestamp or arrive through different paths. A venue normally needs a total sequence, a single serialization point, or rules that produce an equivalent ordering.

For each processed command, record enough information to reproduce:

• The command and participant identity.
• Its authoritative sequence.
• Validation outcome.
• Generated trades in order.
• Resting or terminal outcome.

Why the matching core is usually a single writer

The critical state is small but tightly coupled. Matching one command can touch:

• The best price level.
• Several maker orders.
• Aggregate quantity.
• The ID index.
• The trade sequence.
• The incoming order’s residual.

Allowing several threads to mutate these structures concurrently makes ordering and recovery much harder. A common architecture therefore uses one logical writer per partition:

network receive
    → parsing and validation
    → sequenced command queue
    → single matching-state owner
    → execution and market-data outputs

“Single writer” does not mean “the whole venue uses one CPU.” Instruments can be partitioned, and parsing, persistence, risk, and publication can run elsewhere. The design constraint is that one canonical order stream has one unambiguous mutation order.

This is an architectural starting point, not a universal law. Measure before adding coordination to the matching path.

Correctness before representation

Two implementations can expose the same state machine:

Do not optimize by silently changing semantics. The fast implementation should be tested against the reference implementation using generated command streams.

The companion systems chapters explain the machinery:

• BTreeMap
• VecDeque
• Slabs and Arenas
• Parsers and State Machines
• Matching Engines

This book owns the market semantics. The systems book owns representation, CPU behavior, networking, and measurement.

Failure cases worth testing

A useful test suite includes:

• Duplicate order ID.
• Unknown cancel.
• Zero or overflowing quantity.
• Invalid tick price.
• Add that walks several levels.
• Partial maker and partial taker fills.
• Cancel of the head, middle, and tail of a queue.
• Disconnect after the command becomes authoritative but before acknowledgment.
• Replay containing a duplicate or missing sequence.
• Snapshot taken between output publication steps.
• Instrument halt while commands are queued.

Tests should assert the final book and the exact ordered output events.

What you should internalize

1. The book is canonical state; its visual ladder is only a projection.
2. Commands express intent. Events describe authoritative outcomes.
3. An incoming order matches before any residual rests.
4. Price priority chooses the level; time priority chooses within the level.
5. Partial execution changes quantity without necessarily terminating an order.
6. Fast identity lookup does not guarantee fast removal from a FIFO queue.
7. Invariants turn matching rules into executable correctness conditions.
8. Deterministic replay requires an authoritative total input order.
9. A single logical writer makes mutation order and recovery easier to reason about.
10. Optimize the representation only after preserving the reference state machine.

Retrieval drill

Using the event sequence in the visualization:

1. Why does S2 trade with B1 before B2?
2. Why does two units of B2 remain after S2 finishes?
3. At what price does B3 trade with S1, and why?
4. Which invariant would detect a zero-quantity order left in a queue?
5. What additional structure would make cancellation from a long price queue constant time?

Sources

• Larry Harris, Trading and Exchanges: Market Microstructure for Practitioners, Oxford University Press, 2002, chapters 4 and 6.
• Thierry Foucault, Marco Pagano, and Ailsa Röell, Market Liquidity: Theory, Evidence, and Policy, first edition, Oxford University Press, 2013, chapter 1.

Exact order types, amendment rules, precedence, and execution prices are venue-specific. Later venue chapters will use current rulebooks and protocol specifications as primary sources.