Order Book Data Structures: Price-Time Priority in One Sorted Set

An order book holds resting buy and sell orders for one market. A price-time engine needs the highest bid, the lowest ask, first-in-first-out (FIFO) order within each price, insertion of a new resting order, quantity reduction after a partial fill, and cancellation by order ID — all while preserving one authoritative command sequence.

No single data structure does all of that well, because ordered price lookup and direct order lookup have different keys. A practical book is a small system of indexes: an ordered price-level index per side, a FIFO queue inside every level, and a hash from order ID to the live order or queue node.

The design succeeds when each invariant has exactly one owner. Price ordering, time priority, and identity lookup are three separate responsibilities. Force them into one clever container and at least one common operation becomes unpredictable — usually cancellation, usually under load, usually during a burst.

Bids run highest price to lowest; asks run lowest to highest. Each price key points at 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 empties, it removes the price key and advances.

FIFO has to be explicit. A plain collection of orders at one price is not enough, because iteration order is an implementation detail and exchange priority is a promise to customers. This is worth stating as an invariant in its own right: equal-price ordering must use an explicit sequence, never a container’s incidental ordering.

Linked queues give constant-time removal when the cancellation index stores node references. Ring buffers improve locality for append-and-pop workloads but get awkward when arbitrary cancellation leaves holes. Which one wins depends on your cancel pattern, which you should measure rather than assume.

Redis sorted sets have exactly one numeric score, and a price-time book needs two ordering keys. The tempting move — packing price and sequence into one float — is a good way to lose orders to precision at the far end of the range. The alternative is to use the score for price and exploit the tie-break rule: at equal scores, Redis orders members lexicographically.

So the member string carries the time priority as a fixed-width, zero-padded prefix. That makes lexicographic order and time order the same thing:

private bookMember(order: Pick<Order, 'id' | 'side' | 'timestamp'>): string {
  const priority =
    order.side === OrderSide.Ask
      ? order.timestamp
      : Number.MAX_SAFE_INTEGER - order.timestamp;   // note the inversion

  return `${priority.toString().padStart(16, '0')}:${order.id}`;
}

The inversion is the part that looks like a bug and is not. Asks are read with ZRANGEBYSCORE — ascending score, and ascending member within a score — so a plain timestamp gives oldest-first. Bids are read with ZREVRANGEBYSCORE, which walks descending score and descending member within a score. A plain timestamp there would return the newest order first and quietly invert your queue. Subtracting from MAX_SAFE_INTEGER makes the oldest bid the lexicographically largest member, so descending traversal returns it first.

// asks: lowest price first, oldest first within a price
ZRANGEBYSCORE    book:<pairId>:ask:rates -inf <takerPrice> WITHSCORES LIMIT 0 64

// bids: highest price first, oldest first within a price
ZREVRANGEBYSCORE book:<pairId>:bid:rates  inf <takerPrice> WITHSCORES LIMIT 0 64

The payoff is that candidate retrieval is a single bounded read that arrives already sorted by exchange priority, and paging through a deep sweep with LIMIT offset stays correct. The cost is that the encoding is load-bearing and non-obvious — the padding width, the inversion, and the traversal direction have to agree, and a mismatch produces an engine that is subtly unfair rather than visibly broken. It gets a comment, a test, and a mention in the runbook.

Balanced trees handle sparse price spaces with logarithmic insertion and removal while exposing min and max keys directly. Skip lists give similar expected complexity and are often simpler to implement with ordered traversal. Both pay in pointer chasing — their asymptotics look excellent while cache misses and allocation dominate the short operations inside a matching loop.

A direct price array maps integer ticks to slots. Best-price lookup becomes constant time when the active range is bounded or paired with a bitmap that finds the next occupied slot. Excellent for dense, predictable markets; wasteful when prices span a huge sparse range. A radix tree or segmented array sits between the extremes. There is no universally fastest book, only a fastest book for a measured shape.

Without an order-ID index, cancellation scans price levels and queues until it finds the target. That turns one of the most common commands into work proportional to book size, and produces tail-latency spikes exactly during cancel bursts — when a market maker is replacing thousands of quotes and you can least afford it.

A hash should resolve the order ID directly to its side, price level, and removable node or slot. In our case that is the order record itself, and removal touches both the record and the price index in one commit:

removeOrder(order, partition, transaction) {
  transaction.zrem(this.bookKey(order.pairId, order.side, partition),
                   this.bookMember(order));
  transaction.del(this.orderKey(order.id, partition));
}

On a partial fill, update remaining quantity without touching the member string — rewriting it would reset time priority, which is the same as taking a customer’s place in the queue away for the crime of being partially filled.

Property tests should assert that every indexed order exists in exactly one queue and every queued order has exactly one index entry. We also expose it as a live endpoint, because the two can drift in ways a test suite will not see:

"ask:7f3a…:missing-order"    // in the price index, no order record
"bid:91c2…:index-mismatch"   // record disagrees with the index it sits in

A stale index member also has to be survivable at match time. Ours logs and skips a candidate whose record has vanished rather than aborting the command — the alternative is one orphaned member wedging a market until someone notices.

Store price and quantity as integers in the market’s declared tick and lot units, or as arbitrary-precision decimals — but never as binary floats. A BTC-USD price of 100.25 with a one-cent tick becomes 10025. Integer comparison preserves price ordering with no floating-point surprises. Validate at the gateway and reject values the market configuration cannot represent, rather than rounding them silently into something plausible.

Overflow and conversion still need attention. Notional multiplies price by quantity and may need a wider type. Fees can carry a different precision from the traded asset. Every pair needs its own priceDecimals, amountDecimals, and quoteDecimals, and every rounding operation needs a declared direction — ours rounds in the book’s favour, asks up and bids down, so rounding can never create value.

“We use integers” is the first sentence of a financial model, not the last one.

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

Before optimising any of that, check whether the book is the bottleneck at all. In our engine the pure matching function runs at over 100,000 calculations per second; the full command pipeline runs at roughly 106. The arithmetic and data structure had three orders of magnitude of headroom. More cache-locality work would have moved nothing. Measure the boundary first.

When you do measure the book, use the real command mix. A test containing only new limit orders at one price tells you nothing about crossing several levels, partial fills, mass cancellation, or a quote-replacement burst. Report median latency (p50), tail latency through p99.9, queue depth, allocations, book shape, persistence policy, CPU model, and duration. One peak throughput number is not an engineering result.

One market needs one ordered writer. Letting several threads mutate one book turns arrival priority into a synchronisation problem and makes replay non-deterministic. A single writer runs fast precisely because the hot state is local and the loop blocks on very little. Parallelise across markets, gateways, risk calculations, persistence batches, and event consumers instead.

Partitioning by market is simple until commands span markets or accounts. Global risk limits, shared collateral, and multi-leg orders need coordination outside any single book. Keep that coordination explicit and outside the matching structure rather than sprinkling locks through it. The core’s job is narrow: receive an accepted, ordered command, decide executions, 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 enough of the cancellation index to verify the result. Recovery loads it and replays later records in order, and must reconstruct the same best bid, best ask, aggregate depth, and queue membership as an uninterrupted engine.

Never serialise raw pointers or allocator-specific layout. Persist domain state: market configuration, order identity, side, price, original and remaining quantity, priority sequence, status. Rebuild runtime indexes from that, then verify counts and checksums before reopening the market. This is what keeps storage compatible when the in-memory representation changes — and it will change.

Build 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 and many levels, partial fills, cancels at the touch, cancels far from the touch, duplicate requests, and quote-replacement bursts. Hold the mix constant when comparing structures, or you are comparing workloads.

Declare warm-up, persistence, CPU affinity, runtime settings, and reporting boundary. Measure throughput together with p50, p95, p99, and p99.9. Record allocations, resident memory, queue depth, journal delay, and recovery time. Then run long enough to expose allocator cycles, compaction, thermal behaviour, and consumer backpressure — short synthetic peaks hide precisely the failures operators inherit.

• Use deterministic command traces so implementations receive identical work.
• Verify final book state after every run, 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 that sustained more than 4,000 orders per second at the engine boundary. That boundary measured the matching function itself, before the durable commit and confirmed event delivery. Those later stages run two to three orders of magnitude slower. Not one difficult production failure was about a data structure. They were state-boundary errors: order updates, trades, downstream balances, market data, and open-high-low-close-volume (OHLCV) candle projections disagreeing about sequence or source of truth.

So the invariants that earn their keep are the boundary ones. Executed quantity equal on both sides of a trade. Non-negative remainder. FIFO preserved within a level. No empty indexed level. No live order missing from the cancellation index. No order record without an index entry, and no index entry without a record.

Then go and break it on purpose. Kill the process between persistence, mutation, publication, and acknowledgement — all four, separately. A durable journal and verified snapshots make the book reconstructable in principle. Proving that replay produces the same queues, aggregate quantities, best prices, and order index is the only thing that makes it true.