Orderbook Update 2: Implementing the Matching Engine

Implementing a C++ Matching Engine: Deep Dive into Orderbook Design

In this post, we'll explore the implementation of an orderbook's matching engine, focusing on data structure choices and algorithmic efficiency. Let's break down the key components and design decisions that make up an efficient matching system.

Core Data Structures

The heart of our orderbook lies in three main data structures:

std::map<Price, OrderPointers, std::greater<Price>> bids_;
std::map<Price, OrderPointers, std::less<Price>> asks_;
std::unordered_map<OrderId, OrderEntry> orders_;

This design showcases several key considerations:

  1. Price Level Organization: Using std::map for bids and asks provides automatic price-time priority through ordered storage. Note the different comparators - std::greater for bids (highest price first) and std::less for asks (lowest price first).
  2. Order Access: The unordered_map provides O(1) lookup for order management operations using order IDs as keys.
  3. Memory Management: Orders are stored as shared_ptr (OrderPointer) to handle memory automatically while maintaining references across containers.

The Matching Algorithm

The core matching logic demonstrates how to efficiently pair orders:

Trades MatchOrders() {
    Trades trades;
    trades.reserve(orders_.size());  // Optimization to prevent reallocation

    while (true) {
        if (bids_.empty() || asks_.empty())
            break;

        auto& [bidPrice, bids] = *bids_.begin();
        auto& [askPrice, asks] = *asks_.begin();

        if (bidPrice < askPrice)
            break;

This implementation:

  • Maintains price-time priority naturally through container ordering
  • Uses structured bindings for cleaner code
  • Pre-reserves trade vector space for performance

Order Lifecycle Management

Order management involves three main operations:

1. Adding Orders

Trades AddOrder(OrderPointer order) {
    if (orders_.contains(order->GetOrderId()))
        return { };

    if (order->GetOrderType() == OrderType::FillAndKill && 
        !CanMatch(order->GetSide(), order->GetPrice()))
        return { };

The addition process:

  • Validates order uniqueness
  • Handles FillAndKill orders specially
  • Maintains iterator stability through careful container management

2. Cancelling Orders

void CancelOrder(OrderId orderId) {
    if (!orders_.contains(orderId))
        return;

    const auto& [order, iterator] = orders_.at(orderId);
    orders_.erase(orderId);

Cancellation ensures:

  • Clean removal from all containers
  • Proper price level cleanup when empty
  • Iterator validity maintenance

3. Order Modification

Trades MatchOrder(OrderModify order) {
    if (!orders_.contains(order.GetOrderId()))
        return { };

    const auto& [existingOrder, _] = orders_.at(order.GetOrderId());
    CancelOrder(order.GetOrderId());
    return AddOrder(order.ToOrderPointer(existingOrder->GetOrderType()));
}

Modification is implemented as cancel-replace, which:

  • Maintains fairness in price-time priority
  • Simplifies the implementation
  • Provides clean order history

Market Data Generation

The system can efficiently generate market data snapshots:

OrderbookLevelInfos GetOrderInfos() const {
    LevelInfos bidInfos, askInfos;
    // ... aggregation logic ...
    return OrderbookLevelInfos { bidInfos, askInfos };
}

This provides:

  • Efficient level aggregation
  • Clean separation of market data from matching logic
  • Easy integration with market data distribution systems

Performance Considerations

Several optimizations are worth noting:

  1. Iterator Stability: Using std::list for OrderPointers ensures iterators remain valid during modifications.
  2. Memory Pre-allocation: Strategic use of reserve() reduces reallocations.
  3. Reference Usage: Careful use of references prevents unnecessary copying.
  4. Efficient Lookups: O(1) order lookups via unordered_map combined with O(log n) price level access.

Next Steps

Future enhancements could include:

  • Multi-threaded order processing
  • More sophisticated order types
  • Improved market data generation
  • Performance benchmarking infrastructure

The current implementation provides a solid foundation for these additions while maintaining clean, efficient code structure. Thank you for following along on this journey. Stay tuned for more updates on the Order book.