How would you design an order book, and what makes it hard?

What the structure has to satisfy

Start from the operations, because they dictate the layout. You need the best bid and best offer in constant time, since every decision made downstream reads them. You need to add an order at the back of a price level in constant time. You need to cancel an arbitrary order, identified only by its ID, in constant time, because the venue tells you "order 8471 is gone" and nothing else. You need to reduce an order's size in place. And you need to match: repeatedly take the head of the opposite side's best level until either the aggressor is exhausted or the price no longer crosses.

Two of those requirements are what kill the obvious designs. A cancel arrives with an ID, not a price, so any structure that requires you to search for the order is wrong. And matching always works from the head of a level, never the middle, so within a level you want a queue, not an indexable container.

Why a naive sorted list is wrong

A sorted list or array of orders looks appealing because the best price is at index zero. It fails on mutation. Inserting an order in the middle shifts every element after it, and cancelling does the same. That is O(n) per message on a book that can hold tens of thousands of resting orders, and it is O(n) on the two operations that arrive most often.

A single sorted structure also conflates two different orderings. Price ordering is between levels; time ordering is within a level. Flattening both into one list means every insert has to find its position by price and then by arrival time, and it destroys the property that makes matching cheap, namely that the next order to trade is always the head of a known queue.

The correct shape is two-tier. Levels are held in price order. Each level holds a doubly linked, intrusively threaded FIFO of orders, so appending is a tail write and unlinking is a pointer swap. A hash map from order ID to the order node gives you the O(1) entry point for cancels, and the node carries a back-pointer to its level so unlinking never requires a search.

How you hold the levels themselves is the one genuine trade-off. For an instrument with a bounded, meaningful tick range you can use a flat array indexed by tick offset, which makes level lookup a single subtraction and keeps levels contiguous in cache; you then track the best price as a cursor and walk outwards when a level empties. Where the price range cannot be bounded, or memory per instrument matters because you run thousands of books, use a balanced tree or skip list keyed by price for O(log L) level lookup where L is the number of occupied levels, which is small. Either way the per-order operations stay O(1); only the level lookup differs.

The core structure

// Prices are integer ticks throughout. A double is a defect here: price is a
// key you compare and index on, not a measurement, and 0.1 + 0.2 does not
// compare equal to 0.3. Convert once at the codec boundary and never again.
final class Order {
    long id;
    int  priceTicks;
    long remainingQty;
    Order prev, next;   // intrusive FIFO links: no wrapper nodes to allocate
    PriceLevel level;   // back-pointer, so cancel never searches for the level
}

final class PriceLevel {
    final int priceTicks;
    Order head, tail;   // head is the oldest order: time priority is positional
    long  aggregateQty; // maintained incrementally; recomputing it is O(n)
    int   orderCount;
}

final class BookSide {
    private final PriceLevel[] levels;  // indexed by (priceTicks - minTick)
    private final int minTick;
    private final boolean bid;
    private int bestIdx = -1;           // cursor to the best occupied level

    void add(Order o) {
        int idx = o.priceTicks - minTick;
        PriceLevel lvl = levels[idx];
        if (lvl == null) lvl = levels[idx] = new PriceLevel(o.priceTicks);
        o.level = lvl;
        if (lvl.tail == null) { lvl.head = lvl.tail = o; }
        else { lvl.tail.next = o; o.prev = lvl.tail; lvl.tail = o; }
        lvl.aggregateQty += o.remainingQty;
        lvl.orderCount++;
        // A better price only ever improves the cursor: no scan on the hot path.
        if (bestIdx < 0 || (bid ? idx > bestIdx : idx < bestIdx)) bestIdx = idx;
    }

    void remove(Order o) {                 // the cancel path, O(1)
        PriceLevel lvl = o.level;
        if (o.prev != null) o.prev.next = o.next; else lvl.head = o.next;
        if (o.next != null) o.next.prev = o.prev; else lvl.tail = o.prev;
        lvl.aggregateQty -= o.remainingQty;
        // Only an emptied best level costs a scan, and it walks one tick at a
        // time towards the other side, so the amortised cost stays low.
        if (--lvl.orderCount == 0 && (o.priceTicks - minTick) == bestIdx) {
            advanceCursor();
        }
        o.prev = o.next = null; o.level = null;
    }
}

The order ID map lives above both sides. Use a primitive-keyed map (long to object) rather than HashMap<Long, Order>, because the latter boxes every key on every lookup, which is an allocation on the single most frequent operation in the system.

Sequencing and gap detection

A book built from a market-data feed is only as correct as the feed handling. Incremental feeds carry a monotonically increasing sequence number per channel. Your handler keeps the expected next value and compares on every message. Equal, apply it. Lower, discard it as a duplicate, which happens routinely when you consume the venue's A and B lines and arbitrate between them for redundancy. Higher, you have a gap, and the book is now untrustworthy.

The one thing you must not do is apply the message anyway. An increment says "remove 300 from this level"; applying it against a level whose earlier updates you missed produces a book that is wrong in a way nothing later will correct, and wrong books generate confident bad orders. The correct response is bounded and explicit: mark the instrument stale and stop trading it, attempt recovery, and only resume when the book is provably whole again. Recovery is either a retransmission request for the missing range where the venue supports it, or a resynchronise from the periodic snapshot channel: buffer incoming increments, take a snapshot, discard buffered increments up to and including the snapshot's last-applied sequence, then apply the remainder in order.

Deterministic replay

Auditors, regulators and your own incident reviews all ask the same thing: given the same inputs, does the system produce the same outputs? That is a design property, not a logging feature, and it is cheap only if you decide on it up front.

The requirements are concrete. Everything that influences a decision must arrive as a sequenced input and be journalled before it is processed, including timer ticks, so business logic never reads the clock directly; time becomes an event. There is one writer thread per book, so there is no interleaving to reproduce. No iteration order can depend on hash layout or object identity. No randomness, and no floating-point arithmetic whose result depends on the order of accumulation. And the logic itself must be versioned, because replaying last quarter's journal through this quarter's matching rules answers a question nobody asked.

Get that right and replay becomes genuinely useful: you can re-run a trading day against a modified strategy, reproduce a customer's disputed fill exactly, and prove which input caused a given output.

Cancels, not trades, dominate

Here is the thing that separates a strong answer. Candidates instinctively optimise the matching path, because matching is the interesting part conceptually. On a real feed, far more messages add and remove liquidity than execute against it, so the operations that determine your throughput are add and cancel, and the pointer discipline that makes cancel O(1) matters more than any cleverness in the match loop. A design that is elegant about matching and O(n) about cancels is a design that has optimised the rare case.

Why allocation and garbage collection matter here specifically

The usual advice about not micro-optimising memory is correct in most systems and wrong in this one, for a reason worth stating precisely. Allocation rate on this path is proportional to message rate, and message rate is not uniform: it spikes exactly at the open, the close, and on news, which are the moments when your latency matters most and when being late is most expensive. So a design that allocates per message schedules its own garbage collection for the worst possible instant. It is a correlation problem, not a throughput problem, and it is why average latency is the wrong metric and the tail is the right one.

The remedies are ordinary once the goal is clear. Recycle Order objects through a free list rather than allocating and dropping them, since order churn is the dominant source. Decode incoming messages with a flyweight positioned over the receive buffer instead of materialising a message object per update. Use primitive collections to avoid boxing. Prefer arrays and intrusive links over node-allocating containers, which also buys cache locality: a linked list of separately allocated wrappers is a chain of cache misses, whereas contiguous levels are prefetched. On the JVM, pair that with a collector chosen for pause behaviour rather than throughput, and treat any steady-state allocation on the hot path as a bug with an owner, because it is measurable and therefore fixable.