Order Book Mechanics

Prerequisite: The Ledger

Your matching engine fills a market buy for 50 BTC against the best ask. The best ask is 10 BTC at $64,200. The engine fills 10, advances to the next price level — 15 BTC at $64,201 — fills 15, advances again to 25 BTC at $64,202, and fills the remaining 25. The customer’s average fill price is $64,201.40, not the $64,200 they saw on the screen. The $1.40 difference across 50 BTC is $70 of slippage — and if the book was thin, that number could be $700 or $7,000. The order book’s depth, structure, and matching rules determine who gets filled, at what price, and how much it costs.

Order Types

Three order types handle the vast majority of exchange volume. Every other order type — iceberg, fill-or-kill, immediate-or-cancel, good-til-cancelled — is a modifier on one of these three.

Limit orders specify a price and a quantity. A limit buy at $64,200 for 10 BTC means “buy up to 10 BTC, but pay no more than $64,200 per unit.” If the best ask is above $64,200, the order rests on the book as passive liquidity. If the best ask is at or below $64,200, the order matches immediately against resting asks. Limit orders that rest provide liquidity. Limit orders that match immediately consume it.

Market orders specify only a quantity. A market buy for 10 BTC means “buy 10 BTC at whatever the current best price is.” Market orders always execute immediately and always consume liquidity. They walk the book — matching against the best available price, then the next best, until the quantity is filled. Market orders guarantee execution. They do not guarantee price.

Stop orders are dormant until a trigger price is reached. A stop-loss sell at $63,000 sits inactive until the market trades at or below $63,000, at which point the stop converts to a market order and executes. Stop orders are not visible on the book until triggered. A cascade of stop orders triggering at the same level can drain liquidity in milliseconds — each triggered stop becomes a market order that pushes the price further, triggering the next layer of stops.

Order type	Price guarantee	Execution guarantee	Book visibility
Limit	Yes — fills at limit or better	No — may never fill	Visible while resting
Market	No — fills at whatever is available	Yes — fills immediately	Never rests
Stop	No — becomes market on trigger	Yes — after trigger	Invisible until triggered

Price-Time Priority

When multiple limit orders rest at the same price, the matching engine must decide which order fills first. The dominant allocation rule is price-time priority (also called FIFO): among orders at the same price, the order that arrived first fills first.

Price-time priority creates two guarantees. First, aggressive orders always trade at the best available price — the engine matches against the lowest ask or highest bid before any worse-priced order. Second, at each price level, the earliest order has priority — no later order at the same price can be filled before it.

Bid side (sorted best → worst):
  $64,200  |  10 BTC  (arrived 09:00:01.000)
  $64,200  |   5 BTC  (arrived 09:00:01.003)
  $64,199  |  20 BTC  (arrived 09:00:00.500)

Incoming market sell for 12 BTC:
  → Fills 10 BTC at $64,200 from the first order
  → Fills  2 BTC at $64,200 from the second order
  → Second order has 3 BTC remaining at $64,200

The 20 BTC bid at $64,199 arrived earlier in absolute time than both $64,200 orders, but price takes precedence over time. Among orders at $64,200, the one that arrived at 09:00:01.000 fills before the one at 09:00:01.003.

Some exchanges use pro-rata allocation at the same price level — each order receives a share proportional to its size. CME uses pro-rata for certain products (Eurodollar futures historically used this). Pro-rata rewards larger orders. Price-time rewards faster orders. The choice shapes participant behavior: pro-rata incentivizes posting large resting orders, while price-time incentivizes speed.

Price-time priority means microseconds determine who earns the spread. This is the root cause of the latency arms race in traditional markets — the first order at a price level captures all fills until it is exhausted.

The Data Structure

A central limit order book (CLOB) is two sorted collections: bids sorted descending by price, asks sorted ascending by price. At each price level, a queue of orders sorted by arrival time. The matching engine must support four operations:

Operation	Frequency	Latency target
Add order	Every new order	< 1μs
Cancel order	~40–60% of all messages	< 1μs
Match (find best price)	Every aggressive order	< 1μs
Modify order (price change)	Cancel + re-add at new price	< 2μs

Cancel volume dominates. On Nasdaq, approximately 95% of submitted orders are cancelled before filling. On a typical trading day, the exchange processes 4–6 billion order messages, of which 200–300 million result in trades. The data structure must make cancellation fast, not just insertion and lookup.

Sorted map + doubly-linked lists. The standard implementation uses a sorted map (red-black tree or B-tree) keyed by price, where each node points to a doubly-linked list of orders at that price level. Adding an order at an existing price is O(1) — append to the list. Adding an order at a new price is O(log P) where P is the number of distinct price levels (typically 500–2,000 for an actively traded instrument). Cancelling an order is O(1) if you maintain a hash map from order ID to the order’s node in the linked list — look up the node, unlink it, done.

Price Tree (Red-Black):
  $64,202 → [Order A (25 BTC)] → [Order B (10 BTC)]
  $64,201 → [Order C (15 BTC)]
  $64,200 → [Order D (10 BTC)] → [Order E (5 BTC)]

Cancel Index (Hash Map):
  order_id_A → pointer to Order A node
  order_id_B → pointer to Order B node
  ...

Skip lists. An alternative to balanced trees. A skip list provides O(log P) expected insertion and lookup with simpler implementation — no rotations, no rebalancing. LMAX Exchange uses a skip list variant for their order book. The probabilistic balancing trades worst-case guarantees for lower constant factors and better cache locality in practice.

Array-based books for tick-constrained instruments. When an instrument trades in fixed-size ticks (e.g., $0.01 increments between $60,000 and $70,000 — 1 million possible price levels), you can use a pre-allocated array indexed by tick. Lookup is O(1). Finding the best bid or ask requires scanning from the top, but maintaining a pointer to the current best makes this amortized O(1). This approach trades memory for speed and works when the price range is bounded.

The Matching Loop

When an aggressive order arrives — a market order, or a limit order whose price crosses the spread — the matching engine executes a tight loop:

fn match_order(book: &mut OrderBook, incoming: Order) -> Vec<Fill> {
    let mut fills = Vec::new();
    let mut remaining = incoming.quantity;

    while remaining > 0 {
        let best = book.best_opposite_side(&incoming.side);
        if best.is_none() { break; }
        if incoming.is_limit() && !incoming.price_crosses(best.price) { break; }

        let resting = best.front_order();
        let fill_qty = min(remaining, resting.quantity);

        fills.push(Fill {
            price: resting.price,
            quantity: fill_qty,
            maker: resting.id,
            taker: incoming.id,
        });

        remaining -= fill_qty;
        resting.quantity -= fill_qty;

        if resting.quantity == 0 {
            book.remove_order(resting.id);
        }
    }

    if remaining > 0 && incoming.is_limit() {
        book.insert_order(incoming.with_quantity(remaining));
    }

    fills
}

The loop runs single-threaded. Parallelizing the matching engine introduces ordering ambiguity — two orders arriving simultaneously could match differently depending on which thread processes which message first. Every production matching engine of note — LMAX, Nasdaq INET, CME Globex — runs its core matching loop on a single thread. Throughput comes from making each iteration fast (sub-microsecond), not from processing matches concurrently.

LMAX reports processing 6 million orders per second on a single thread with a median latency under 1 microsecond. The key: no allocation in the hot path, no locks, no system calls. The Disruptor pattern pre-allocates ring buffers and uses memory barriers instead of locks for inter-thread communication.

Partial Fills

An aggressive order that exhausts one price level and partially fills at the next produces multiple fill events for a single order. A market buy for 50 BTC that matches against three price levels generates three fills.

Each fill is an independent trade event with its own trade ID, price, and quantity. The exchange publishes these as separate entries in the trade feed. Your internal system must aggregate fills by order ID to compute the volume-weighted average price (VWAP) — the actual effective price the customer received.

SELECT order_id,
       SUM(quantity) AS total_filled,
       SUM(price * quantity) / SUM(quantity) AS vwap
FROM fills
WHERE order_id = $1
GROUP BY order_id;

The fill ratio — the percentage of an order’s quantity that actually executes — varies by order type and market conditions. Market orders fill 100% by definition (unless the book is empty). Limit orders at the best bid or ask fill roughly 10–30% of the time on liquid markets. Limit orders deeper in the book may rest for hours without filling.

Self-Trade Prevention

When the same entity has both a resting bid and an incoming ask at the same price — or vice versa — the engine would match the entity against itself. Self-trades create fictitious volume, trigger wash trading alerts, and in most jurisdictions violate market manipulation rules.

Exchanges implement self-trade prevention (STP) with several modes:

STP mode	Behavior	Use case
Cancel newest	Cancel the incoming order, resting order stays	Protect resting liquidity
Cancel oldest	Cancel the resting order, incoming order continues matching	Prefer new trading intent
Cancel both	Cancel both orders	Conservative compliance
Decrement	Reduce both orders by the overlap quantity	Preserve residual intent on both sides

STP requires identifying “same entity” — which is not the same as “same account.” A market maker operating three accounts as part of the same strategy must configure all three accounts under the same STP group. Missing a sub-account in the STP configuration produces self-trades that trigger exchange surveillance alerts and potential fines.

CME charges $5,000 per wash trade incident. Repeated violations escalate to trading suspensions. The STP check runs inside the matching loop, between finding a resting order and executing the fill — adding a hash-map lookup (STP group ID comparison) to each potential match. At 6 million orders per second, that lookup must complete in nanoseconds.

Self-trade prevention is not optional for any exchange or trading venue. Regulators treat self-trades as evidence of market manipulation unless the venue demonstrates active prevention measures. The STP mode selection — cancel newest vs cancel oldest — is a business decision with compliance implications that should be documented before launch.

Book Depth and Market Quality

The order book’s depth — total resting quantity across price levels — determines how much an aggressive order can trade before moving the price. A deep book absorbs large orders with minimal slippage. A thin book amplifies even moderate orders into significant price moves.

Metric	Liquid market (BTC/USD, major exchange)	Illiquid market (small-cap token)
Spread (best bid to best ask)	$1–5 (0.01%)	$50–500 (1–5%)
Depth within 0.1% of mid	$5–20M	$10–50K
Time to fill 100 BTC at < 0.1% slippage	< 1 second	Minutes to hours, if ever
Cancel-to-trade ratio	20:1 to 50:1	5:1 to 10:1

Market makers — participants who continuously post bids and asks to earn the spread — provide the majority of resting liquidity on most venues. A market maker’s strategy depends entirely on the order book’s matching rules. Under price-time priority, market makers compete to post first at the best price. Under pro-rata, they compete to post the largest order. The matching rule shapes the order book’s character: price-time books tend to be tighter (narrower spreads) with faster quote updates, while pro-rata books tend to be deeper (more resting quantity) with less aggressive cancellation.

The order book is not a passive data structure. It is the mechanism through which price discovery happens — every order, cancellation, and fill is a signal about what participants believe an asset is worth. The data structure’s performance determines whether that signal propagates in microseconds or milliseconds, and in markets where the spread is a single tick, that difference is the entire margin.