Designing an order book

A limit order book holds all resting orders for one instrument, grouped by side and price. Each price with at least one order is a level, with a total quantity. On each side, orders at the same price are queued in time order: the first to arrive trades first. That rule is price-time priority: better price first, then earlier time.

A market-by-order feed sends events for individual orders. The book must support:

Two observations drive the design. Most activity is near the top of the book: adds, cancels and fills cluster within a few ticks of the best prices. And every event except add identifies the order only by its id, so finding an order by id must be fast.

A hash map from exchange order id to the order's handle in a pool (Modules 2 and 3). Open addressing, reserved for the expected peak number of live orders. Every delete, execute and modify starts here.

Prices are integers in ticks (Module 10). Near the touch, levels are dense: almost every tick has orders. So each side can keep its levels in an array indexed by price - base, where base is a reference price near the current market:

struct Level {
    std::int64_t qty = 0;           // total resting quantity
    std::uint32_t count = 0;        // number of orders
    std::uint32_t head = NIL, tail = NIL;   // FIFO of orders, as pool indices
};

struct Side {
    std::int64_t base;              // price, in ticks, of levels_[0]
    std::vector<Level> levels_;     // fixed size, e.g. a few thousand ticks
    std::int64_t best = NONE;       // index of the best non-empty level
};

Finding a level is one subtraction and one array access. Iterating the top N levels walks the array from the best index, skipping empty slots. Keeping best up to date is the one subtle part: on an add at a better price, it moves; on deleting the last order at the best level, the code scans for the next non-empty level, which is usually a few slots away because the book is dense near the top.

Prices far from the market, outside the array, are rare. They go to an overflow structure, such as a sorted vector or a std::map, or the array is recentred when the market moves far enough.

Each order lives in a pool slot and carries its own prev and next links as pool indices:

struct Order {
    std::uint64_t exch_id;
    std::int64_t price;             // ticks
    std::int32_t qty;
    std::uint8_t side;
    std::uint32_t prev = NIL, next = NIL;   // links within its level
};

Adding appends at the level's tail: O(1). Deleting unlinks the order from wherever it is in the queue: O(1), given the handle from the id map. Executing reduces quantity and, at zero, deletes. No allocation, no scan.

void Book::add(std::uint64_t id, Side& s, std::int64_t px, std::int32_t qty) {
    std::uint32_t h = pool_.acquire();
    Order& o = pool_[h];
    o = Order{id, px, qty, s.id};
    Level& lv = s.level_at(px);           // array slot, or overflow if far away
    lv.append(h, pool_);                  // tail of the FIFO
    lv.qty += qty; lv.count++;
    s.maybe_improve_best(px);
    ids_.insert(id, h);
}

void Book::remove(std::uint64_t id) {
    std::uint32_t h = ids_.take(id);      // find and erase in the id map
    Order& o = pool_[h];
    Side& s = side_of(o);
    Level& lv = s.level_at(o.price);
    lv.unlink(h, pool_);
    lv.qty -= o.qty; lv.count--;
    if (lv.count == 0) s.on_level_emptied(o.price);   // may move best
    pool_.release(h);
}

Every operation is a constant number of array accesses, one hash lookup and no allocation. The hot data for the top levels and their recent orders fits in cache.

• A market-by-price feed sends level updates directly, so the book is just the level arrays, without orders or an id map.
• A trading strategy's own view may only need the top few levels, kept in a tiny fixed array.
• Some designs keep levels in a sorted vector of (price, qty) per side, best price at the end, which is simple and fast when depth is small.

Start from the operations and their frequencies, then design for them: hash map from id to pooled orders, tick-indexed level arrays near the touch with an overflow for the rest, intrusive FIFOs for time priority, and a tracked best index. Mention what you would measure, and that std::map<price, level> is a correct first version you would replace after profiling.