The Matching Engine: Order Matching Algorithms

The matching engine is the heart of an exchange — it's the system that pairs buy and sell orders. Speed is critical: a single microsecond delay can mean losing a trade.

Price-Time Priority

Most exchanges use price-time priority: the highest bid and lowest ask match first, and at the same price, the earliest order gets priority.

Bids (buyers)           Asks (sellers)
100.05 × 100  ← t=2    100.06 × 50   ← t=1
100.04 × 200  ← t=1    100.07 × 100  ← t=3

If a market order to buy 150 shares arrives:

1. Matches 50 shares at 100.06 (best ask)
2. Matches 100 shares at 100.07 (next ask)
3. Total fills: 50 at 100.06 + 100 at 100.07

Time priority means orders at the same price level are filled in arrival order (FIFO).

Data Structures

Limit Order Book

The order book is typically implemented as:

• A balanced binary search tree (e.g., red-black tree) or skip list keyed by price
• A FIFO queue at each price level for time priority
• Lock-free concurrent data structures (CAS operations, hazard pointers)

struct PriceLevel {
  double price;
  std::queue<Order> orders;  // FIFO at this price
};
 
struct OrderBook {
  std::map<double, PriceLevel> bids;  // sorted highest first
  std::map<double, PriceLevel> asks;  // sorted lowest first
};

Matching Algorithms

FIFO (First-In, First-Out)

Orders at the same price are matched in arrival order. Most common in equity exchanges.

Pro-Rata

Orders at the same price are matched proportionally to their size. Common in futures markets (e.g., CME).

Random

Orders at the same price are matched randomly. Used to prevent gaming in some markets.

Performance Considerations

Modern matching engines process millions of orders per second. Key optimizations:

1. Colocation — Servers in the same data center as the exchange (reduces network latency)
2. Kernel bypass — Using DPDK or Solarflare's Onload to avoid kernel syscall overhead
3. FPGA — Hardware-level matching for maximum speed
4. Memory pools — Pre-allocate order objects to avoid malloc overhead
5. Cache-friendly layout — Store data contiguously to minimize cache misses

The fastest matching engines achieve sub-microsecond latencies — but the algorithms themselves are straightforward. It's the systems engineering that makes the difference.

Order Lifecycle

New Order → Risk Check → Book Insertion → Match Check → Trade → Confirmation

Every step adds latency. The matching engine must make decisions faster than other market participants can react.