Price-Time Priority Matching

An incoming order is marketable (it crosses the spread) when it can trade immediately: a buy priced at or above the best ask, a sell at or below the best bid. A market order is always marketable while the other side has liquidity. The engine then:

1. Takes the best opposite level (lowest ask for a buy, highest bid for a sell), as long as it still crosses the incoming order's limit.
2. Trades against that level's orders oldest first, each trade for min(incoming remaining, resting remaining).
3. Prices every trade at the resting order's price. A buy limit at 105 that meets an ask at 100 trades at 100: the aggressor gets the price improvement, and the resting order gets exactly what it asked for.
4. Removes fully filled resting orders, leaves a partially filled one at the front of its queue with its time priority intact, and moves to the next level when one empties.
5. Stops when the incoming order is filled, or the next level no longer crosses, or the side is empty. What is left over rests on the book (limit) or is cancelled (market).

The resting order is the maker (it provided liquidity), the incoming one the taker. Many venues charge them different fees, which is why the distinction appears in every trade record.

Not every market uses time as the second rule. Some interest-rate futures have historically used pro-rata allocation, where a level's fill is split in proportion to resting size, sometimes with a priority slice for the first order or for designated market makers. Pro-rata rewards size rather than speed and changes trading behaviour completely. Your exchange is FIFO; know that the alternative exists and why.

The core loop has two nested walks: across price levels in priority order, and within a level across orders in time order. The common bugs are all at the boundaries:

• comparing with < where the rule is <= (an order at exactly the best ask does cross);
• forgetting to remove a level once its last order is gone, so the next best-price read returns an empty level;
• removing a partially filled maker (it must stay at the front with reduced quantity);
• using the incoming limit as the trade price.

BTreeMap::first_entry and last_entry give you a mutable handle on the best level that you can also remove() through, which keeps the loop free of repeated lookups.

use std::collections::{BTreeMap, VecDeque};

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Side {
    Buy,
    Sell,
}

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct Fill {
    pub maker_id: u64,
    pub price: i64,
    pub qty: u64,
}

/// Resting orders: price → FIFO of (order id, remaining qty), oldest first.
pub struct Book {
    pub bids: BTreeMap<i64, VecDeque<(u64, u64)>>,
    pub asks: BTreeMap<i64, VecDeque<(u64, u64)>>,
}

impl Book {
    pub fn new() -> Self {
        Book { bids: BTreeMap::new(), asks: BTreeMap::new() }
    }

    /// Place a passive order at the back of its level (no matching).
    pub fn rest(&mut self, side: Side, id: u64, price: i64, qty: u64) {
        let levels = match side {
            Side::Buy => &mut self.bids,
            Side::Sell => &mut self.asks,
        };
        levels.entry(price).or_default().push_back((id, qty));
    }

    /// Match an incoming limit order against the opposite side.
    ///   Buy:  take asks from the lowest price up, while ask ≤ limit.
    ///   Sell: take bids from the highest price down, while bid ≥ limit.
    /// Within a level, oldest first. Every fill prints at the maker's
    /// (resting) price. Fully filled makers leave the book; a level with no
    /// orders left is removed from the map.
    /// Returns the fills in order and the unfilled remainder (NOT rested).
    pub fn match_order(&mut self, side: Side, limit: i64, qty: u64) -> (Vec<Fill>, u64) {
        todo!()
    }
}

The drill uses VecDeque levels to keep the focus on the rules. In the repo you run the same loop over the w06 book through its trait: front(side) is the oldest order at the best price, and fill_front(side, qty) fills it, removing the order once it is done and the level once it empties, so the engine never touches the level map.

The engine's output is a stream of events, and the rest of the exchange is built from it: execution reports to the two clients involved, the public market-data feed (week 10), position and risk updates (weeks 15 and 45), and the audit trail. Your internal events can be much simpler than FIX, but they must carry enough to produce all of those views.

This week's event set:

• Accepted { id } — the engine took responsibility for the order.
• Trade { taker, maker, price, qty } — one per maker touched, in the order they traded. One event names both sides, so the maker's fill report and the taker's fill report are derived from the same fact and can never disagree.
• Rested { id, side, price, qty } — the unfilled remainder of a limit order joined the book.
• Cancelled { id, qty } — quantity left the book or never reached it: a market order's unfilled remainder, or an explicit cancel of a resting order.

For each submitted order the sequence is fixed: Accepted, then zero or more Trades, then at most one of Rested or Cancelled. That shape is what makes the stream checkable.

The repo's types::Event is the same design with a few more cases. The unfilled remainder of a market or IOC order is Expired { id, remaining }, and Cancelled { id, remaining } is kept for an explicit cancel of a resting order. Trade also carries taker_side, and Rejected { id, reason } and Reduced { id, remaining } cover the other outcomes. So in the repo a new order produces either a lone Rejected, or Accepted, then Trades, then at most one Rested or Expired. Its central invariant is conservation of quantity: for every order, quantity traded plus quantity rested plus quantity cancelled equals quantity submitted — the same invariant as FIX's CumQty + LeavesQty = OrderQty for a working order.

Now wrap matching in an engine that owns the book and speaks only in events. The drill adds market orders (which never rest; their remainder is Cancelled) and explicit cancels of resting orders (an id that is not resting — unknown, already filled or already cancelled — produces no events in the drill; in the repo it is already a typed reject this week, Rejected { id, reason: UnknownOrder }).

The harness checks exact event lists for scripted scenarios, then runs 3,000 random orders and cancels twice and requires identical streams, and replays your events into a shadow book built only from the events: every trade must hit an order that was resting at that price with enough quantity, quantity must be conserved for every order, and the shadow book must never be crossed.

use std::collections::{BTreeMap, HashMap, VecDeque};

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Side {
    Buy,
    Sell,
}

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum OrderType {
    Limit(i64),
    Market,
}

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Event {
    Accepted { id: u64 },
    Trade { taker: u64, maker: u64, price: i64, qty: u64 },
    Rested { id: u64, side: Side, price: i64, qty: u64 },
    Cancelled { id: u64, qty: u64 },
}

pub struct Engine {
    bids: BTreeMap<i64, VecDeque<(u64, u64)>>,
    asks: BTreeMap<i64, VecDeque<(u64, u64)>>,
    /// id → (side, price) of every resting order, so cancel can find its level.
    resting: HashMap<u64, (Side, i64)>,
}

impl Engine {
    pub fn new() -> Self {
        Engine { bids: BTreeMap::new(), asks: BTreeMap::new(), resting: HashMap::new() }
    }

    /// Process one new order; return every event it caused, in this order:
    ///   1. Accepted { id }
    ///   2. one Trade per maker touched, in price-time order, at the maker's price
    ///   3. then exactly one of:
    ///        Rested { .. }    a limit order with quantity left joins the book
    ///        Cancelled { .. } a market order with quantity left (it never rests)
    ///        nothing          fully filled
    /// Makers that are fully filled leave the book (and `resting`).
    pub fn submit(&mut self, id: u64, side: Side, kind: OrderType, qty: u64) -> Vec<Event> {
        todo!()
    }

    /// Cancel a resting order: `[Cancelled { id, qty: remaining }]`, or `[]`
    /// if `id` is not resting (unknown, already filled or already cancelled).
    /// Scanning the one level for the id is fine here — week 6 made it O(1).
    pub fn cancel(&mut self, id: u64) -> Vec<Event> {
        todo!()
    }
}

Determinism is a property you design in, not one you test in afterwards. The engine is a pure function of its input sequence if — and only if — nothing else leaks in:

• One thread per book. The sequencer's order is the processing order; there is no interleaving to vary.
• No clocks inside matching. If an event needs a timestamp, it is assigned when the command enters the sequenced stream and carried with it. Instant::now() inside the engine makes every replay different.
• No iteration over HashMap in anything that produces output. Std's HashMap uses a randomly seeded hasher, so iteration order differs between runs and processes. Use it for lookups; iterate BTreeMaps, Vecs or the book's own ordered structures.
• No floating point in prices or quantities, and no randomness that is not itself an input.
• No dependence on addresses, allocation order or thread scheduling.

Before profiling anything (week 26), you can predict most of the cost from structure:

• Allocation. Returning a fresh Vec<Event> per order allocates on every call. Have the caller pass a reusable buffer (submit(&mut self, order, out: &mut Vec<Event>), cleared by the caller) and the steady state allocates nothing.
• Lookups. A passive order costs a level lookup and an index insert; an aggressive one touches the best level, the front nodes and the index entries of every maker it fills. Each is a potential cache miss; with 100,000 resting orders, the index and the slab do not fit in L1 or L2.
• Branches. Most orders in a realistic flow do not cross. Make the "does it cross?" check the first thing the hot path does, so passive orders skip the matching loop entirely.
• Event size. Keep events small and Copy: the engine writes them, the journal and the market-data publisher read them, and every byte is copied at least twice.