Matching engine

Deep dive

How it works

Parts:

• Sequencer — assigns each command a sequence number and timestamp
• Input journal — appended and fsynced or replicated before results go out
• Matcher — single thread, in-RAM book, pure function of (state, command)
• Order book — price levels of FIFO queues (limit order book)
• Event publisher — seq-stamped acks, fills and book changes
• Standbys — replay the same commands and take over at a known sequence

gateways ─► risk ─► sequencer ─► [input journal + replicate] ─► matcher (1 thread) ─► events ─► market data, drop copy, gateways
                          seq, timestamp                          book state in RAM      seq-stamped

1. Sequence. A single sequencer assigns each command a monotonically increasing sequence number and a timestamp. From here on, nothing may read a clock or any other non-input state.
2. Journal. Append commands to the input log; fsync or replicate to standbys in batches (group commit). Only then are results allowed out.
3. Match (buy shown; sell mirrors): while qty > 0 and best ask ≤ limit: take the head order at the best ask, fill min(qty, head.qty) at the ask price, emit a fill, remove the head when done, drop the level when empty.
4. Residual. Good-till-cancel: rest at the tail of its level (time priority). IOC: cancel the remainder. FOK: check available crossing quantity first, all or nothing. Market order: limit = worst possible price, IOC.
5. Publish events tagged with the input sequence number: acks, fills (both sides), book changes for market data.
6. Recover: load the latest snapshot (book state + last applied seq), replay journal entries after it. Standbys run the same commands live and take over at a known seq.

Code

use std::collections::{BTreeMap, HashMap, VecDeque};
use std::fs::File;
use std::io::{self, BufWriter, Write};

#[derive(Clone, Copy, PartialEq, Eq, Debug)] pub enum Side { Buy = 0, Sell = 1 }
#[derive(Clone, Copy, PartialEq, Eq, Debug)] pub enum Tif { Gtc = 0, Ioc = 1 }

#[derive(Clone, Copy, Debug)]
pub enum Cmd { New { id: u64, side: Side, px: u32, qty: u64, tif: Tif }, Cancel { id: u64 } }

#[derive(Clone, Copy, Debug)]
pub enum Event {
    Accepted { id: u64 }, Rejected { id: u64, reason: u8 },
    Fill { taker: u64, maker: u64, px: u32, qty: u64 },
    Rested { id: u64, px: u32, qty: u64 }, Cancelled { id: u64, qty: u64 },
}

struct Resting { id: u64, qty: u64 }

#[derive(Default)]
pub struct Engine {
    pub seq: u64,
    bids: BTreeMap<u32, VecDeque<Resting>>,   // best = last key
    asks: BTreeMap<u32, VecDeque<Resting>>,   // best = first key
    loc: HashMap<u64, (Side, u32)>,           // live order id -> level
}

impl Engine {
    pub fn process(&mut self, cmd: Cmd, out: &mut Vec<(u64, Event)>) {
        self.seq += 1;
        let s = self.seq;
        match cmd {
            Cmd::New { id, side, px, mut qty, tif } => {
                if qty == 0 || self.loc.contains_key(&id) { out.push((s, Event::Rejected { id, reason: 1 })); return; }
                out.push((s, Event::Accepted { id }));
                let opp = if side == Side::Buy { &mut self.asks } else { &mut self.bids };
                while qty > 0 {
                    let best = if side == Side::Buy { opp.first_entry() } else { opp.last_entry() };
                    let Some(mut level) = best else { break };
                    let lpx = *level.key();
                    if (side == Side::Buy && lpx > px) || (side == Side::Sell && lpx < px) { break; }
                    let q = level.get_mut();
                    while qty > 0 {
                        let Some(head) = q.front_mut() else { break };
                        let n = qty.min(head.qty);
                        out.push((s, Event::Fill { taker: id, maker: head.id, px: lpx, qty: n })); // maker's price
                        qty -= n;
                        head.qty -= n;
                        if head.qty == 0 { let m = head.id; q.pop_front(); self.loc.remove(&m); }
                    }
                    if q.is_empty() { level.remove(); }
                }
                if qty > 0 && tif == Tif::Gtc {
                    let own = if side == Side::Buy { &mut self.bids } else { &mut self.asks };
                    own.entry(px).or_default().push_back(Resting { id, qty });   // tail = time priority
                    self.loc.insert(id, (side, px));
                    out.push((s, Event::Rested { id, px, qty }));
                } else if qty > 0 {
                    out.push((s, Event::Cancelled { id, qty }));                 // IOC remainder
                }
            }
            Cmd::Cancel { id } => {
                let Some((side, px)) = self.loc.remove(&id) else {
                    out.push((s, Event::Rejected { id, reason: 2 })); return;   // unknown or already filled
                };
                let book = if side == Side::Buy { &mut self.bids } else { &mut self.asks };
                let q = book.get_mut(&px).expect("loc and book agree");
                let i = q.iter().position(|r| r.id == id).expect("order in level");
                let qty = q.remove(i).expect("index valid").qty;
                if q.is_empty() { book.remove(&px); }
                out.push((s, Event::Cancelled { id, qty }));
            }
        }
    }
}

/// Fixed 32-byte input records: seq | kind | side | tif | pad | px | id | qty (little endian).
pub struct Journal { w: BufWriter<File> }

impl Journal {
    pub fn new(f: File) -> Self { Journal { w: BufWriter::with_capacity(1 << 20, f) } }
    pub fn append(&mut self, seq: u64, c: &Cmd) -> io::Result<()> {
        let mut r = [0u8; 32];
        r[0..8].copy_from_slice(&seq.to_le_bytes());
        match *c {
            Cmd::New { id, side, px, qty, tif } => {
                r[8] = 1; r[9] = side as u8; r[10] = tif as u8;
                r[12..16].copy_from_slice(&px.to_le_bytes());
                r[16..24].copy_from_slice(&id.to_le_bytes());
                r[24..32].copy_from_slice(&qty.to_le_bytes());
            }
            Cmd::Cancel { id } => { r[8] = 2; r[16..24].copy_from_slice(&id.to_le_bytes()); }
        }
        self.w.write_all(&r)
    }
    pub fn commit(&mut self) -> io::Result<()> { self.w.flush()?; self.w.get_ref().sync_data() }
}

/// Journal a batch, make it durable, then apply it. Nothing is published before commit.
pub fn step(e: &mut Engine, j: &mut Journal, batch: &[Cmd], out: &mut Vec<(u64, Event)>) -> io::Result<()> {
    for (i, c) in batch.iter().enumerate() { j.append(e.seq + 1 + i as u64, c)?; }
    j.commit()?;
    out.clear();
    for c in batch { e.process(*c, out); }
    Ok(())
}

The BTreeMap<u32, VecDeque> book keeps the reference short; production engines use the O(1) array-indexed book with intrusive lists, which also makes cancel O(1) instead of a scan of the level.

Complexity and constants

• Matching: O(1) per fill plus O(1) to rest with an array book; O(log L) with a tree of levels.
• Software matching of one order is order of 100 ns to 1 µs on one core; the end-to-end exchange latency is dominated by network, gateways and journaling.
• Journal: 32 B/command here; a 1 MB batch holds about 32k commands. fsync on NVMe with power-loss protection is order of 10-100 µs, so batching turns it into a small per-order cost. Replicating to a standby in the same rack costs order of 10-50 µs RTT.

Efficiency

Cost: the bound is durability and network, not matching. Matching one order is order of 100 ns to 1 µs on one core; a journal fsync on NVMe with power-loss protection is order of 10-100 µs; a same-rack standby round trip order of 10-50 µs. The journal costs 32 B per command here.

Levers

• Group commit (group commit) — one fsync per batch; a 1 MB batch holds about 32k commands — always on the durable path.
• One thread, no locks — LMAX reported about 6 million orders/s on one business-logic thread (3 GHz Nehalem, Fowler 2011) — scale by sharding symbols.
• Gateways, risk, journaling and publishing on other cores behind SPSC rings — the matcher never blocks.
• Array book — O(1) cancel and best price (limit order book).
• Journal inputs only, snapshot at sequence N — bounded replay.

Naive → standard → state of the art

• Naive: locks around a shared book, one fsync per order · contention and fsync-bound
• Standard: single-threaded matcher, group-committed input journal · order of 1 µs match, batched durability
• State of the art: Raft-replicated deterministic service (Aeron Cluster) with array books · same loop, replicated standbys Cheaper without durability (simulators, backtests): same loop in memory. Non-continuous markets: batch auction.

Implementation notes

• Determinism checklist: no wall-clock reads (use the sequencer timestamp in the command); no floats; no iteration over HashMap (Rust's RandomState gives a per-process random order, so replicas would diverge); no thread-dependent behaviour; pre-sized collections so capacity growth cannot change timing-sensitive decisions.
• Input vs output journal: journaling inputs is enough for recovery because the matcher is deterministic; also journal outputs (or their hash per seq) to verify replicas and to replay market data to clients without recomputing.
• Threading around the core: gateways, risk, journaling, replication and publishing run on other cores, connected by SPSC rings (the Disruptor pattern). The matcher thread never blocks.
• Self-trade prevention: before filling, compare the taker's and maker's account/firm; policies are cancel-newest, cancel-oldest, or cancel-both. It changes matching outcomes, so it lives inside the matcher.
• Pro-rata: instead of FIFO, split the fill across the level proportionally to resting size, with integer rounding and a deterministic tie-break; often with a FIFO top-order allocation first.
• Price bands and circuit breakers: reject or halt when a fill would trade beyond a band around a reference price; must also be computed from inputs only.
• Replication: either primary/standby with the sequenced input stream, or a consensus log (Raft) as the journal; each node runs the same matcher. Snapshots of the book at seq N shorten replay.

Pitfalls

• Publishing fills before the input is durable or replicated: after a crash the exchange "forgets" trades clients already saw.
• Using the incoming order's price as the trade price: it must be the resting order's price.
• Market orders with no opposite liquidity resting as "price = infinity": they must be IOC.
• A cancel racing a fill: the cancel arrives after the order was fully filled; reply "unknown order" (too late to cancel), never panic.
• A Vec<Event> or VecDeque that allocates per order in the hot path; reuse buffers and preallocate levels.
• Rebuilding state on restart from output events produced by an older engine version: replays must use the same code version or versioned matching rules.

Variants and alternatives

In production

LMAX Exchange (Java, one business-logic thread fed by the Disruptor, input journaled and replicated); Aeron Cluster (Raft-replicated deterministic services, used for matching engines); partitioning by symbol with one matcher thread per partition is the usual exchange design.

Implementations

Sources

• Martin Fowler, The LMAX Architecture, martinfowler.com, 2011. article
• Martin Thompson, Dave Farley, Michael Barker, Patricia Gee, Andrew Stewart, Disruptor: High performance alternative to bounded queues for exchanging data between concurrent threads, LMAX technical paper, 2011. paper · code
• Larry Harris, Trading and Exchanges: Market Microstructure for Practitioners, Oxford University Press, 2003.
• Eric Budish, Peter Cramton, John Shim, The High-Frequency Trading Arms Race: Frequent Batch Auctions as a Market Design Response, Quarterly Journal of Economics, 2015. paper