返回题库

完整撮合引擎

Full Matching Engine

专题
Systems & Architecture / 系统与架构
难度
L4
来源
MyntBit

题目详情

撮合引擎是电子交易所的核心基础设施，要求确定性执行、严格的价格-时间优先规则和健壮的边界条件处理。实现低延迟撮合引擎需要管理复杂订单类型（如 IOC 和 FOK）、维护买卖双侧价格-时间优先队列，并正确处理部分成交和订单过期。

任务：实现 MatchingEngine 类，维护买卖双侧优先队列，支持新增、取消和 IOC/FOK 等订单类型。成交按价格优先、时间优先匹配。

英文原题

Matching engines form the core infrastructure of electronic exchanges, requiring deterministic execution, strict price-time priority rules, and robust edge-case handling. Implementing a low-latency matching engine involves managing complex order types like Immediate or Cancel (IOC) and Fill or Kill (FOK), alongside Self-Trade Prevention (STP). Understanding these microstructure mechanics is crucial in quantitative finance for developing high-frequency trading strategies that interact directly wi

解析

问题分析

撮合引擎是交易所的核心，需要确定性执行和严格的价格-时间优先级。低延迟撮合引擎管理限价单和市价单，支持 IOC（立即成交或取消）和 FOK（全部成交或取消）等复杂订单类型。

实现

class MatchingEngine {
    struct Order { uint64_t id; double price; int qty; bool is_buy; uint64_t ts; };
    struct Level { double price; std::list<Order> orders; int total_qty{0}; };
    std::map<double, Level, std::greater<>> bids_;
    std::map<double, Level> asks_;
    uint64_t seq_{0};
public:
    struct Fill { uint64_t order_id, counter_id; double price; int qty; };
    
    std::vector<Fill> place(Order order) {
        order.ts = ++seq_;
        auto& book = order.is_buy ? asks_ : bids_;
        std::vector<Fill> fills;
        for (auto it = book.begin(); it != book.end() && order.qty > 0; ) {
            if ((order.is_buy && it->first > order.price) ||
                (!order.is_buy && it->first < order.price)) break;
            auto& level = it->second;
            while (!level.orders.empty() && order.qty > 0) {
                auto& head = level.orders.front();
                int fill_qty = std::min(order.qty, head.qty);
                fills.push_back({order.id, head.id, it->first, fill_qty});
                order.qty -= fill_qty; head.qty -= fill_qty;
                level.total_qty -= fill_qty;
                if (head.qty == 0) level.orders.pop_front();
            }
            if (level.orders.empty()) it = book.erase(it); else ++it;
        }
        if (order.qty > 0) {
            auto& level = (order.is_buy ? bids_ : asks_)[order.price];
            level.orders.push_back(order);
            level.total_qty += order.qty;
        }
        return fills;
    }
};

复杂度与边界

  • 时间复杂度：撮合 O(扫过的价格档位数)，通常 ≤ 5 档
  • 空间复杂度：O(活跃订单数)
  • 边界条件：(1) 自成交检测与拒绝 (2) 价格<=0 拒绝 (3) qty<=0 拒绝 (4) 同价格按时间戳排序

英文解析

Analysis

The matching engine is the core of an exchange, requiring deterministic execution and strict price-time priority. A low-latency matching engine manages limit and market orders, supporting complex order types like IOC (Immediate Or Cancel) and FOK (Fill Or Kill).

Solution

class MatchingEngine {
    struct Order { uint64_t id; double price; int qty; bool is_buy; uint64_t ts; };
    struct Level { double price; std::list<Order> orders; int total_qty{0}; };
    std::map<double, Level, std::greater<>> bids_;
    std::map<double, Level> asks_;
    uint64_t seq_{0};
public:
    struct Fill { uint64_t order_id, counter_id; double price; int qty; };
    
    std::vector<Fill> place(Order order) {
        order.ts = ++seq_;
        auto& book = order.is_buy ? asks_ : bids_;
        std::vector<Fill> fills;
        for (auto it = book.begin(); it != book.end() && order.qty > 0; ) {
            if ((order.is_buy && it->first > order.price) ||
                (!order.is_buy && it->first < order.price)) break;
            auto& level = it->second;
            while (!level.orders.empty() && order.qty > 0) {
                auto& head = level.orders.front();
                int fill_qty = std::min(order.qty, head.qty);
                fills.push_back({order.id, head.id, it->first, fill_qty});
                order.qty -= fill_qty; head.qty -= fill_qty;
                level.total_qty -= fill_qty;
                if (head.qty == 0) level.orders.erase(level.orders.begin());
            }
            if (level.total_qty <= 0) it = book.erase(it); else ++it;
        }
        if (order.qty > 0) addRestingOrder(order);
        return fills;
    }
};

Complexity & Edge Cases

  • Time complexity: O(fills at crossed levels) + O(log N) for resting order insertion
  • Space complexity: O(active orders + price levels)
  • Edge cases: (1) IOC cancels unfilled quantity (2) FOK rejects if total cannot fill (3) Self-match prevention (4) Same-price orders processed in arrival order (price-time priority)

Key Considerations

  1. Price-time priority: Orders at same price level are matched in arrival order; FIFO queue must be strictly maintained for fairness and regulatory compliance
  2. Self-trade prevention: Matching engine must detect and reject trades where buyer and seller are the same participant; configurable per exchange rule
  3. Partial fill semantics: Partially filled orders retain remaining quantity at original price level; must not reorder in priority queue
  4. Throughput requirement: Matching engine must process 100K+ orders/sec; data structure choice (red-black tree vs skip list) impacts latency at scale