Building a limit order book

01The question

Every order on an exchange lands in a limit order book: a list of everyone willing to buy (bids) and sell (asks), sorted by price. When a new order comes in, a matching engine decides who trades with whom, at what price, and in what order. It has to do that correctly every time, and fast.

I wanted to understand that engine well enough to build one, so I wrote a single-instrument order book in C++17 with the order types real exchanges use: limit, market and immediate-or-cancel (IOC), plus cancels and quantity reductions.

02The rules

Matching follows price-time priority, the standard on most exchanges:

• Price first. A buy order matches the cheapest ask; a sell order matches the highest bid.
• Then time. At the same price, whoever arrived first fills first.
• Trades print at the resting order's price. If I'm willing to pay $101 and someone is already asking $100, I pay $100. The aggressive order gets the price improvement.

The order types differ only in what happens to quantity that doesn't fill: a limit order rests on the book, a market order trades at any price and drops the rest, and an IOC order trades up to its limit and cancels the rest.

03Choosing the data structures

This was the part I spent the most time on, because each operation has different needs.

• Sorted map of price levels. std::map keeps prices ordered, so the best price is always begin(). Bids use std::greater so both sides read best-first. Adding a new level is O(log L), where L is the number of levels on that side.
• A FIFO list at each level. std::list gives time priority for free: new orders go on the back, fills come off the front. Unlike a vector, removing an order from the middle doesn't invalidate pointers to the others.
• An id → iterator index. Cancels are the most common message on real exchanges, so I didn't want them to scan the book. A hash map from order id to the order's list iterator makes a cancel O(1).
• Integer prices. Prices are stored as ticks (cents), not floating point. In floating point, 100.10 + 0.20 isn't exactly 100.30, and a matching engine comparing prices can't afford that.

04The matching loop

Every order type runs through one loop. It keeps taking the best opposite level while prices cross, and fills orders at that level front to back:

while (incoming.qty > 0 && !book.empty()) {
    auto level = book.begin();               // best opposite price
    if (limit && !crosses(level->first, *limit)) break;

    while (incoming.qty > 0 && !level->second.orders.empty()) {
        Order& resting = level->second.orders.front();
        Qty fill = std::min(incoming.qty, resting.qty);
        trades.push_back({..., level->first, fill});   // resting price
        incoming.qty -= fill;  resting.qty -= fill;
        if (resting.qty == 0) { index_.erase(resting.id); level->second.orders.pop_front(); }
    }
    if (level->second.orders.empty()) book.erase(level);
}

Market orders pass no limit, so they cross at any price. Limit orders rest whatever is left afterward; market and IOC orders simply drop it.

05Testing it

A matching engine that's fast but occasionally wrong is useless, so I wrote 17 unit tests before trusting any benchmark. They cover full and partial fills, price priority, FIFO order within a level, orders that sweep several levels, market and IOC behavior, cancels at the front and middle of a queue, reductions keeping queue position, and bad input like duplicate ids or zero quantities.

The suite also runs under AddressSanitizer and UndefinedBehaviorSanitizer, which catch memory bugs like using an iterator after its order was erased. GitHub Actions builds and tests everything on every push.

06How fast it is

The benchmark replays 1,000,000 synthetic orders with a fixed seed: about 60% limit orders around a drifting price, 30% cancels and 10% market or IOC orders. Only the order book calls are timed.

Measured on a shared cloud Linux machine, so exact numbers vary. The tail is the interesting part: the median is fast, but the slowest 0.1% of orders take over 25 times longer. Most of that comes from memory allocation, since every new order and every new price level allocates a node on the heap, plus noise from the shared machine.

07What I'd do next

Getting it correct was the first half. Making the slow cases fast is the second.

• An object pool for orders, so placing one never calls the allocator. This should cut the tail latency the most.
• A flat array of price levels indexed by tick around the current price, turning level lookup from O(log L) into O(1).
• Multiple instruments behind a symbol router, closer to how a real exchange gateway works.