Order Book Data Structures for a Matching Engine

An order book holds resting buy and sell orders for one market. A price-time engine needs the highest bid, lowest ask, FIFO order at each price, insertion of a new resting order, quantity reduction after a partial fill, and cancellation by order ID. It must perform those operations while preserving one authoritative command sequence. No single data structure solves the whole problem. Ordered price lookup and direct order lookup have different keys. A practical book combines an ordered price-level index on each side, a FIFO queue inside every level, and a hash index from order ID to the live order or queue node. The design succeeds when each invariant has one obvious owner. Price ordering, time priority, and identity lookup are separate responsibilities, so forcing them into one container usually makes at least one common operation unpredictable.

The book is a small system of indexes, not one clever container.

Bids are ordered from highest price to lowest; asks from lowest to highest. Each price key points to aggregate quantity and a queue of resting orders. When an incoming buy crosses, the engine reads the lowest ask and consumes the oldest order in that queue. When the level becomes empty, it removes the price key and advances to the next ask.

FIFO must be explicit. A plain collection of orders at one price is not enough because iteration order may not express exchange priority. Linked queues allow constant-time removal when the cancellation index stores node references. Ring buffers improve locality for append-and-pop workloads but become harder when arbitrary cancellation leaves holes. The expected cancel pattern matters.

Balanced trees handle sparse price spaces with logarithmic insertion and removal while exposing minimum or maximum keys. Skip lists provide similar expected complexity and can be simpler to implement with ordered traversal. Both pay for pointer chasing. Their asymptotic behavior looks good, but cache misses and allocation often dominate the short operations inside a matching loop.

A direct price array maps integer ticks to slots. Best-price lookup can be constant time when the active range is bounded or paired with a bitmap that finds the next occupied slot. It is excellent for dense, predictable markets and wasteful when prices span a huge sparse range. A radix tree or segmented array can sit between those extremes. There is no universally fastest book.

Without an order-ID index, cancellation scans price levels and queues until it finds the target. That turns a common command into work proportional to book size and creates tail-latency spikes during cancel bursts. A hash map should resolve the order ID directly to its side, price level, and removable node or slot.

Index updates belong in the same mutation as book updates. Insert the queue node and index entry together. On full fill or cancel, remove both. On partial fill, update the remaining quantity without changing time priority. Property tests should assert that every indexed order exists in exactly one queue and every queued order has exactly one index entry.

Store price and quantity as integers in the market’s declared tick and lot units. A BTC-USD price of 100.25 with a one-cent tick becomes 10025. Integer comparison preserves price ordering without binary floating-point surprises. Validation at the gateway should reject values that cannot be represented by the market configuration.

Overflow and conversion rules still need attention. Notional calculations multiply price by quantity and may require a wider integer type. Fees can introduce a different precision from the traded asset. Define rounding direction for charges, rebates, and released reserves. “We use integers” is the start of a financial model, not the end.

The classic design—tree of price levels, linked queue per level, hash map by ID—is easy to explain and often sufficient. It also spreads nodes across memory. Every comparison, next pointer, and hash lookup can miss cache. Pools or arenas can reduce allocator pressure and keep nodes closer together. Intrusive queues avoid separate wrapper allocations by storing links with the order.

Measure with the real command mix. A test containing only new limit orders at one price says nothing about crossing several levels, partial fills, mass cancellation, or a market-maker burst that replaces thousands of quotes. Report p50 through p99.9, queue depth, allocations, book shape, persistence policy, CPU model, and test duration. One peak throughput number is not an engineering result.

One market normally needs one ordered writer. Letting several threads mutate the same book makes arrival priority a synchronization problem and complicates replay. A single writer can process commands quickly because the hot state stays local and the loop does little blocking work. Parallelize across markets, gateways, risk calculations, persistence batches, and event consumers.

Partitioning by market is simple until commands span markets or accounts. Global risk limits, shared collateral, and multi-leg orders introduce coordination outside one book. Keep that coordination explicit rather than placing locks throughout the matching structure. The core should receive an accepted ordered command, decide executions, and emit sequenced facts.

The in-memory structure is disposable only if accepted commands or resulting events are durable. A snapshot captures price levels, FIFO order, remaining quantities, sequence position, and the cancellation index state needed for verification. Recovery loads the snapshot and replays later records in order. It should reconstruct the same best bid, best ask, aggregate depth, and queue membership as the uninterrupted engine.

Do not serialize raw pointers or allocator-specific layout. Persist domain state: market configuration, order identity, side, integer price, original and remaining quantity, priority sequence, and status. Rebuild runtime indexes from that state, then verify counts and checksums before reopening the market. This keeps storage compatible when the in-memory representation changes.

Create several book shapes: a tight dense book, a wide sparse book, thousands of orders at one price, and many shallow levels. Run mixes of passive limits, aggressive orders crossing one or many levels, partial fills, cancellations at the touch, cancellations far from the touch, duplicate requests, and market-maker quote replacement bursts. Hold the mix constant when comparing structures.

Warm-up, persistence, CPU affinity, runtime settings, and reporting boundaries must be declared. Measure command throughput together with p50, p95, p99, and p99.9 latency. Record allocations, resident memory, queue depth, journal delay, and recovery time. Then repeat long enough to expose allocator cycles, compaction, thermal changes, and consumer backpressure. Short synthetic peaks hide the failures operators inherit.

• Use deterministic command traces so implementations receive identical work.
• Verify final book state after every benchmark, not only elapsed time.
• Separate engine time from gateway, network, journal, and settlement time.
• Publish hardware, compiler, runtime, persistence, and dataset details.

At Bitsten, I led the architecture of a Node.js and TypeScript engine processing more than 4,000 orders per second with sub-millisecond engine latency. The difficult failures were not tree rotations. They were state-boundary errors: ensuring order updates, trades, downstream balances, market data, and OHLCV projections all agreed on sequence and source of truth.

A durable journal and verified snapshots make the in-memory book reconstructable. Replay must produce the same queues, aggregate quantities, best prices, and order index. Useful invariants include equal executed quantity on both trade sides, non-negative remainder, FIFO preservation inside a level, no empty indexed level, and no live order missing from the cancellation index. Kill the process between persistence, mutation, publication, and acknowledgement. Then prove recovery.