Inside the Matching Engine: How Orders Become Trades

The matching engine is the core of any exchange — the software system responsible for receiving orders, maintaining the order book, and executing trades when buy and sell orders are compatible.

The fundamental function: When a new buy order arrives, the matching engine checks whether any existing sell orders can be matched (sell price ≤ buy price). If a match is found, a trade executes. If not, the order rests in the book waiting for a counterparty.

Performance requirements: - Latency: Sub-millisecond order processing (Binance processes in ~20 microseconds) - Throughput: Binance: 1.4 million orders/second at peak. Even a mid-tier exchange needs 100,000+ TPS - Consistency: Every match must be deterministic — two instances of the engine given the same input must produce the exact same output - Fairness: Price-time priority must be strictly enforced — no favoritism

Why matching engines are in memory, not databases: A PostgreSQL INSERT takes ~1 millisecond. Processing 1.4 million orders/second requires 700 nanoseconds per order — 1,000× faster than any database write. The matching engine maintains the entire order book in RAM using optimized data structures. Database writes happen asynchronously — the engine emits events to a message queue (Kafka) which consumers persist to storage.

The order book data structure must support three operations efficiently: 1. Insert a new order at a price level: O(log n) 2. Cancel an order by ID: O(1) with hash map 3. Match incoming order against best opposing price: O(1) for price access

The design: ```typescript interface Order { id: string; userId: string; side: 'buy' | 'sell'; price: number; originalQty: number; remainingQty: number; timestamp: bigint; // nanosecond precision }

interface PriceLevel { price: number; totalQty: number; orders: Queue<Order>; // FIFO queue for price-time priority }

// Two sorted maps — bids sorted descending, asks sorted ascending const bids = new SortedMap<number, PriceLevel>(reverseComparator); const asks = new SortedMap<number, PriceLevel>(forwardComparator);

// Hash map for O(1) order lookup by ID (for cancellations) const orderIndex = new Map<string, { side: 'buy'|'sell'; price: number }>(); ```

The sorted map (typically a Red-Black Tree or Skip List) maintains price levels in sorted order, enabling O(1) access to best bid (bids.max()) and best ask (asks.min()) with O(log n) insertions and deletions.

Why Java/C++ for production engines: Memory layout matters at nanosecond latency. Java garbage collection pauses can cause millisecond spikes (catastrophic for HFT). Binance's engine is written in Java with careful GC tuning. Dedicated HFT exchanges use C++ for deterministic latency.

Here is a simplified but accurate matching algorithm for a limit order:

function matchOrder(newOrder: Order): Trade[] {
  const trades: Trade[] = [];
  const opposingSide = newOrder.side === 'buy' ? asks : bids;
  
  while (newOrder.remainingQty > 0) {
    const bestLevel = newOrder.side === 'buy'
      ? asks.min()    // Lowest ask for buy orders
      : bids.max();   // Highest bid for sell orders
    
    if (!bestLevel) break; // No counterparty available
    
    // Price compatibility check
    if (newOrder.side === 'buy' && bestLevel.price > newOrder.price) break;
    if (newOrder.side === 'sell' && bestLevel.price < newOrder.price) break;
    
    // Match against first order in this price level (FIFO)
    const restingOrder = bestLevel.orders.peek();
    const matchQty = Math.min(newOrder.remainingQty, restingOrder.remainingQty);
    const matchPrice = restingOrder.price; // Passive order sets the price
    
    // Record trade
    trades.push({
      buyOrderId: newOrder.side === 'buy' ? newOrder.id : restingOrder.id,
      sellOrderId: newOrder.side === 'sell' ? newOrder.id : restingOrder.id,
      price: matchPrice,
      qty: matchQty,
    });
    
    // Update quantities
    newOrder.remainingQty -= matchQty;
    restingOrder.remainingQty -= matchQty;
    bestLevel.totalQty -= matchQty;
    
    // Remove fully filled resting order
    if (restingOrder.remainingQty === 0) {
      bestLevel.orders.dequeue();
      if (bestLevel.orders.isEmpty()) opposingSide.delete(bestLevel.price);
    }
  }
  
  // If new order has remaining qty and it's a limit order, add to book
  if (newOrder.remainingQty > 0 && newOrder.type === 'limit') {
    addToBook(newOrder);
  }
  
  return trades;
}

Price-time priority (FIFO): At the same price level, the earliest order fills first. This is why high-frequency traders pay for co-location — being physically closer to the exchange server reduces network latency, getting orders into the queue earlier.

Market orders are more complex than limit orders — they match against multiple price levels until fully filled or the book is exhausted.

Market order walkthrough: Order book state (asks): - $65,000 → 0.3 BTC (order A) - $65,005 → 0.5 BTC (order B) - $65,020 → 1.2 BTC (order C)

Incoming: BUY 1.0 BTC at market.

Match 1: 0.3 BTC at $65,000 (fully fills order A) Match 2: 0.5 BTC at $65,005 (fully fills order B) Match 3: Need 0.2 BTC more → partially fill order C at $65,020

Final result: 1.0 BTC purchased. - Average price: (0.3×$65,000 + 0.5×$65,005 + 0.2×$65,020) / 1.0 = $65,006.50 - Slippage: $6.50 (0.01%) from the original best ask of $65,000

Slippage calculation for large orders: For a $1M market buy of BTC against a typical Binance order book (2% depth = $50M), slippage is approximately (order size / depth) × 2 = (1M / 50M) × 2% = 0.04%. Negligible for most. For a $1M buy on a small-cap token with $100K depth: slippage = 1M/100K × 50% = 500% — the order would move price dramatically before filling.

Slippage protection: Most DEXs require setting a slippage tolerance (e.g., 0.5%). If actual slippage exceeds this, the transaction reverts — protecting against sandwich attacks where bots front-run large trades.

High-Frequency Trading (HFT) firms operate matching engine strategies that exist because of the microstructure advantages available to ultra-low-latency participants.

Co-location: HFT firms pay exchanges $10,000-$100,000/month to place their servers in the same data center as the matching engine. Round-trip latency: 0.05 milliseconds (co-located) vs 50-200 milliseconds (regular internet). This time advantage enables strategies impossible for distant traders.

Market making: HFT firms continuously post bids and asks 0.01% apart, capturing the spread on every trade. At $1 billion daily volume × 0.01% spread = $100,000/day in pure spread capture. The firm earns "maker rebates" (typically 0.01-0.02%) from the exchange for providing liquidity.

Statistical arbitrage: Price discrepancies between venues exist for milliseconds. HFT bots detect and exploit them before the market corrects: BTC is $65,000.10 on Binance and $65,000.05 on Coinbase → buy on Coinbase, sell on Binance, capture $0.05 per BTC × 1,000 BTC = $50 before the gap closes.

Impact on retail traders: - Tighter spreads: HFT market makers compete aggressively, which reduces spreads for everyone - Better price discovery: Arbitrage keeps prices consistent across venues - "Front-running" concern: In theory, HFT can detect large orders and trade ahead, though most crypto exchanges prevent this through matching queue randomization

Crypto-specific HFT: Cross-exchange arbitrage, funding rate arbitrage, and liquidation hunting are major crypto HFT strategies not found in traditional markets.