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

An order book holds the resting buy and sell orders for one market. The order book data structures underneath a matching engine have to answer a small number of questions fast: what is the best bid, what is the best ask, which order at that price arrived first, and where is order X so I can cancel it. They also have to survive a partial fill without reordering the queue, and survive a crash without losing anything the exchange already promised.

No single container does all of that, because ordered lookup by price and direct lookup by order ID have different keys. Every real book I have seen is a small system of two or three indexes that are kept consistent by a single writer. This article is about the one we run at Bitsten, which lives in Redis and uses one sorted set per side of each market. I will walk one order through it first, then explain each structure, then cover the parts that only show up in production: cancellation cost, rounding, the reconcile check, and what to measure.

One piece of vocabulary. Bitsten is a cryptocurrency exchange. The service that owns a partition of markets and is the only process allowed to change those books is called the conductor. Everything below is the conductor talking to Redis.

The clearest way to see the data structures is to follow a limit buy through stagePlaceOrder in conductor.service.ts. Assume a bid for 2 BTC at 100.25 arrives on a book with two asks at 100.20 and one at 100.30. Everything that happens is staged into one Redis MULTI and committed at the end, so the book is never visible in a half-updated state.

1. The conductor checks a permanent accepted-order marker for this order ID. If one exists, this is a client retry and the order is skipped and counted as a duplicate. Otherwise the marker is staged into the transaction.
2. It asks the ask-side sorted set for candidates: every member with a score up to 100.25, in ascending order, sixty-four at a time. The reply contains member strings and prices, not the orders themselves.
3. It fetches the order records for that page with one pipelined HGETALL per ID. A member whose record is missing is logged as a stale candidate and skipped.
4. For each maker in the page, in order, it calls calculateDeal. The first ask at 100.20 fills for its full volume, so its record is deleted and its member removed from the sorted set (one ZREM plus one DEL in the transaction). A deal event and an order-closed event are appended.
5. The second ask at 100.20 is larger than what remains of the taker. The maker record is rewritten with the new remaining volume. Its sorted-set member is not touched, so it keeps its place in the queue.
6. The taker is now fully filled, so its own record is removed and the loop returns. The ask at 100.30 was never read, because the candidate query stopped at the taker price.

If instead the taker had volume left after the last candidate, one of two things happens. A market order is closed with an insufficient-liquidity rejection and never rests. A limit order gets its role flipped to maker, its record is written with HSET, and its member is added to the bid-side sorted set with ZADD. That last step is the only place a new entry enters the book.

if (taker.type === OrderType.Market) {
  taker.closedTimestamp = now;
  taker.closedByEngine = true;
  this.ordersStorage.removeOrder(taker, partition, transaction);
  events.orderRejected(taker, 'insufficient-liquidity');
  return;
}

taker.role = OrderRole.Maker;
this.ordersStorage.saveOrder(taker, partition, transaction);
this.ordersStorage.addMaker(taker, partition, transaction);
events.orderRested(taker);

A page of sixty-four candidates costs two round trips: one range query on the sorted set and one pipeline of record reads. A sweep through a deep book pages with an increasing offset until a page comes back short. The batch size is a constant called CANDIDATE_BATCH_SIZE and I have not tuned it; sixty-four was a guess that turned out to be well above the number of levels a typical taker crosses on our markets.

Per market there are three things in Redis, all under the same partition hash tag so they can go into one MULTI.

• A sorted set of asks, keyed book:<pairId>:ask:rates. Score is price, member is a priority-prefixed order ID.
• A sorted set of bids, keyed book:<pairId>:bid:rates. Same shape, but the priority prefix is inverted (next section).
• One hash per order, keyed order:<orderId>, holding the full record: side, type, price as a decimal string, remaining volume, quote volume, the decimals for the pair, the submission timestamp, and the user ID.

There is no separate structure for price levels and no per-level queue. The sorted set is flat: one entry per resting order. A "level" is just the run of members that share a score, and it disappears on its own when the last member at that score is removed. The classic textbook layout (tree of levels, linked queue inside each level, hash map by ID) exists to make in-memory operations cheap. In Redis the sorted set already gives ordered traversal and range queries, so the level abstraction would only add round trips.

The record hash is the source of truth for anything with precision. The sorted-set score is a double, because that is what Redis stores, and the conductor passes Number.parseFloat(taker.price) as the range bound. That is fine for ordering. It would not be fine for arithmetic, which is why every calculation in calculateDeal reads the price string from the hash and runs it through decimal.js.

A price-time book needs two ordering keys and a sorted set has one numeric score. The first idea most people have, mine included, is to pack price and sequence into the score: integer part for price, fractional part for arrival order. A double has 53 bits of mantissa. Once prices need eight decimals and sequence numbers pass a few million, the fraction bits run out and two orders at the same price become indistinguishable, or worse, swap places. We never shipped that version.

The approach we use instead relies on a documented Redis rule: when two members have the same score, ZRANGEBYSCORE returns them in lexicographic order of the member string. So the member carries the time priority as a fixed-width, zero-padded prefix, and lexicographic order becomes time order for free.

private bookMember(order: Pick<Order, 'id' | 'side' | 'timestamp'>): string {
  const priority =
    order.side === OrderSide.Ask
      ? order.timestamp
      : Number.MAX_SAFE_INTEGER - order.timestamp;
  return `${priority.toString().padStart(16, '0')}:${order.id}`;
}

The inversion for bids is the part that looks like a bug. Asks are read with ZRANGEBYSCORE from -inf up to the taker price: ascending score, and ascending member within a score, so a plain timestamp puts the oldest ask first. Bids are read with ZREVRANGEBYSCORE from inf down to the taker price, which walks descending score and, within a score, descending member. A plain timestamp there would return the newest bid first and invert the queue. Subtracting the timestamp from MAX_SAFE_INTEGER makes the oldest bid the lexicographically largest member, so the descending walk returns it first.

# asks: lowest price first, oldest first within a price
ZRANGEBYSCORE    matching:{matching-p3}:book:12:ask:rates -inf 100.25 WITHSCORES LIMIT 0 64

# bids: highest price first, oldest first within a price
ZREVRANGEBYSCORE matching:{matching-p3}:book:12:bid:rates  inf 100.25 WITHSCORES LIMIT 0 64

Sixteen digits of padding covers millisecond timestamps until well past any date I care about, and MAX_SAFE_INTEGER minus a millisecond timestamp is also sixteen digits, so both sides pad to the same width. The width, the inversion, and the traversal direction have to agree. A mismatch does not crash anything. It produces a book that is unfair in one direction, which is the kind of bug you find out about from a customer. This encoding has a comment above it, two tests in test/conductor/conductor.service.spec.ts (one asserts that the oldest ask and the oldest bid come first in their respective ranges, the other places sixty-five makers at one price and checks that the oldest one, sitting on the second page, is still filled first), and a line in the runbook.

One leftover from before the encoding existed: removeOrder issues ZREM with both the encoded member and the bare order ID, and orderIdFromBookMember accepts members with or without the sixteen-digit prefix. Those two lines let the change roll out without draining the books. They are still there because removing them would be a migration, and there has not been a reason to run one.

Without a direct index, cancelling an order means scanning the price index until you find the member with that ID. That turns one of the most common commands into work proportional to book size, and it spikes tail latency during quote-replacement bursts, when a market maker is cancelling and re-placing hundreds of orders a second.

In our layout the order hash is the index. A cancel reads order:<id> to learn the side and the timestamp, reconstructs the member string from those two fields, and removes record and member in the same transaction. Nothing scans.

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

The one case that is slower is a cancel for an order the conductor has never seen, which can happen when the users service and the matching partition disagree about where an order lives. stageCancelOrder falls back to asking the users service for the record over RPC. If it comes back already closed, the cancel is a no-op.

When a maker is partially filled, the conductor calls saveOrder, which is an HSET of the whole record with the new remaining volume. It does not call addMaker again. The sorted-set member, and therefore the time priority, is untouched.

The tempting shortcut is to delete and re-add the member so the code path is the same as a new order. That resets the maker's position to the back of the queue for the crime of having been partially filled, and it also changes the observable behaviour of the book between two runs of the same trace. Any design that lets a fill or a retry alter time priority is wrong regardless of throughput.

A resting remainder of a taker is different. It never had a position in the book before, so addMaker uses the order's submission timestamp and it joins its level behind everything that was already there. That is what price-time priority says should happen.

Every pair carries its own priceDecimals, amountDecimals, and quoteDecimals, stored on each order record. calculateDeal in matching.domain.ts does all arithmetic in decimal.js, never in doubles. The executed volume is the smaller of maker and taker remaining volume, rounded to the pair's amount decimals. Quote amounts are volume times the maker price, rounded to the quote decimals.

The rounding direction is a policy, not a default. Asks round up and bids round down, so a rounding step can only move value toward the resting side of the book and never manufacture it. The function that decides is five lines.

function quoteRounding(order: Pick<Order, 'side'>): Decimal.Rounding {
  return order.side === OrderSide.Ask ? Decimal.ROUND_UP : Decimal.ROUND_DOWN;
}

The same function asserts a few things and throws a MatchingInvariantError if they fail, which aborts the whole command before EXEC: neither side may go negative, the maker's volume change must equal the taker's volume change after rounding, and two orders with no user ID (bot against bot) may not match at all. I would rather reject a command than commit a trade where the two legs disagree by one unit in the last decimal.

If you are building the book in a language with native integers, the equivalent is to store price and quantity as integers in tick and lot units (100.25 with a one-cent tick is 10025) and to validate at the gateway, rejecting anything the market configuration cannot represent rather than rounding it into something plausible. Notional still needs a wider type, and fees can carry a different precision from the traded asset.

If the book lives in process memory rather than in Redis, the same three responsibilities are usually split across different containers. A balanced tree or a skip list keyed by price gives ordered traversal and min/max in logarithmic time and handles sparse price ranges well. Both pay in pointer chasing; the asymptotics look excellent while cache misses dominate the short operations inside a matching loop.

A direct array indexed by tick makes best-price lookup constant time when the active range is bounded, often paired with a bitmap to find the next occupied slot. It is wasteful when prices span a huge sparse range and awkward when the tick size changes. A radix tree or a segmented array sits between the extremes. Inside each level, a linked queue gives constant-time removal if the ID index stores node references; a ring buffer has better locality for append-and-pop but leaves holes under arbitrary cancellation.

Which one wins depends on cancel rate, tick range, and how many levels a typical taker crosses. Those are things you measure on your own traffic, not things you pick from a table. The comparison at the end of this article is a starting point, not an answer.

Two structures that must agree will eventually disagree. A member can exist in the sorted set with no record behind it, or a record can say ask when its member sits in the bid set. Neither should be possible when every mutation goes through one transaction. An earlier version of the conductor used separate pipelines for deletes and for updates, and that version could leave a member behind when a delete pipeline failed after the update pipeline had already gone through.

So the conductor exposes the check as a live endpoint. GET /reconcile?pairId=<id> reads both sorted sets, fetches every record, and reports the two failure modes separately, because they have different repairs.

{
  "pairId": 12, "partition": 3,
  "indexedOrders": 8412, "scannedOrders": 8412,
  "truncated": false, "healthy": false,
  "issues": [
    "ask:7f3a…:missing-order",   // member in the index, no record hash
    "bid:91c2…:index-mismatch"   // record says a different pair or side
  ]
}

A truncated result is reported as unhealthy even with zero issues, because a scan that stopped early has not checked the book. Match time also has to tolerate a stale member: getMatchingMakerPages logs and skips a candidate whose record is gone instead of aborting the command. The alternative is one orphaned member wedging a market until someone runs the reconcile.

The invariants I would put in a property test for any book, in Redis or in memory: every member in a price index has a record, every open record has one member on the correct side, executed buy volume equals executed sell volume per trade, no remaining volume is negative, and orders at one price come back in submission order. Ours run in Jest against a fake storage that records every staged operation, which is enough to check ordering and transaction membership. The sorted-set encoding itself is only exercised against a real Redis by the reconcile endpoint and by the load generator in apps/conductor-tester.

The Redis book is authoritative for us, which is why the conductor waits on WAITAOF for a local and a replica fsync before acknowledging any command. A rebuild after a total loss would come from the order records in the users database, replayed in accepted order, with the sorted sets reconstructed from each record's side, price, and timestamp. Because the member string is a pure function of the record, the rebuilt index is identical to the one that was lost.

That is the general rule for any book: persist domain state (market, order ID, side, price, original and remaining volume, timestamp, status), never the runtime layout. Rebuild the indexes from that, then run the reconcile and compare best bid, best ask, and per-level counts against the last known snapshot before reopening the market. The in-memory representation will change at some point, and storage that encodes pointers or allocator layout does not survive that.

Before optimising any of this, check whether the book is the bottleneck. In our engine the pure matching function, calculateDeal in a loop with no I/O, runs at over 100,000 calculations per second. The full command path with durable commit and confirmed event delivery runs at roughly 106 commands per second on the same laptop. The data structure had three orders of magnitude of headroom, and the time went to Redis round trips and RabbitMQ confirms. The benchmark write-up linked below has the numbers per boundary.

When you do measure the book, use the real command mix. A test that only places limit orders at unique prices never crosses a level and never cancels; it measures your hash function. Build several book shapes (tight and dense, wide and sparse, thousands of orders at one price, many shallow levels) and run mixes of passive limits, takers crossing one and many levels, partial fills, cancels at the touch and far from it, duplicate submissions, and quote-replacement bursts.

• Feed both implementations the same deterministic trace with fixed IDs and timestamps, so the work is byte-identical.
• Verify the final book after every run: compare best prices, per-level counts, and a digest of the event sequence. Elapsed time alone will reward an implementation that drops orders.
• Report p50 through p99.9, not just throughput. Cancel bursts show up in the tail and nowhere else.
• Separate engine time from gateway, network, journal, and settlement time. Otherwise you are profiling whichever one is slowest that day.
• Run long enough to hit allocator cycles, persistence, and consumer backpressure. Three-second samples measure the gaps between them.

One last thing from running this in production. Of the difficult failures we had, none was about the data structure. They were state-boundary problems: the book, the trade events, the balances, and the candle projections disagreeing about sequence or about which one was the source of truth. The book itself was the easy part. Getting one writer, one transaction, and one reconcile check around it was where the time went.