How a matching engine works

An incoming order is aggressive if it can trade immediately: a buy at or above the best ask, or a sell at or below the best bid. Otherwise it is passive and rests in the book.

An aggressive buy limit order walks the ask side from the best price upwards. At each level, it trades with the resting orders in time order, at the resting order's price, until either its quantity is exhausted or the next level is above its limit. Whatever remains then rests on the bid side at its limit price (for a day order), or is cancelled (IOC).

void Engine::on_buy(Order in) {
    Side& asks = book_.asks;
    while (in.qty > 0 && !asks.empty() && asks.best_price() <= in.price) {
        Level& lv = asks.best_level();
        while (in.qty > 0 && !lv.empty()) {
            Order& rest = lv.front();
            std::int32_t q = std::min(in.qty, rest.qty);
            emit_trade(in, rest, rest.price, q);     // trade at the resting price
            in.qty -= q; rest.qty -= q; lv.qty -= q;
            if (rest.qty == 0) { emit_done(rest); lv.pop_front(); }
        }
        if (lv.empty()) asks.remove_best_level();
    }
    if (in.qty > 0 && in.tif == Tif::Day) book_.bids.add(in);
    else if (in.qty > 0) emit_cancelled(in);         // IOC remainder
}

The rule that trades happen at the resting order's price is important: the aggressive order may get a better price than its limit, never a worse one.

• Market orders have no limit: they walk the book until filled or the book is empty. Exchanges usually protect against runaway prices with price bands.
• FOK needs a check before matching: is there enough quantity at acceptable prices? If not, nothing trades.
• Post-only orders must not trade on arrival: if they would, they are rejected (or repriced) so that the sender is always the maker.
• Hidden and iceberg orders show only part of their quantity; the hidden part usually has lower priority than displayed quantity at the same price.
• Stop orders wait outside the book until a trigger price trades, then enter as market or limit orders.
• Pro-rata matching, used in some futures markets, allocates fills at a level in proportion to resting size rather than strictly by time.

A real engine must produce exactly the same results from the same input, every time: the regulators, the participants and the exchange's own recovery depend on it. Common design features:

• A single sequencer. All incoming messages for a set of instruments are placed in one total order before matching. That order defines fairness: who was first.
• Single-threaded matching per instrument or partition. No locks, no nondeterministic interleaving; parallelism comes from partitioning instruments across engines.
• Event sourcing. The sequenced input is journaled. A backup engine consuming the same journal reaches the same state and can take over; any state can be rebuilt by replaying.
• No hidden nondeterminism: no reliance on hash map iteration order, uninitialised memory, wall-clock time read during matching, or floating point that differs across builds.

Matching engines face the same problems as the trading systems in this course, with tighter correctness requirements: the book data structures of the previous lesson, preallocated memory, cache-resident hot state, kernel bypass on the network side. Their latency is more consistent than fast; exchanges publish their internal latency and care about its jitter, because unpredictable delays make the market less fair.

Your interview version handles one instrument, one thread, limit orders, and trades at resting prices. A production engine adds the sequencer and journal, partitioned instruments, the full set of order types and validations, self-trade prevention (stopping a firm's orders from trading with each other), price bands and circuit breakers, auctions at the open and close, market-data publication of every change in the same sequence, and failover. Naming those additions is usually the second half of the answer.