交易系统：撮合引擎当中的限价订单簿

撮合引擎实质上是一个单线程、确定性的订单簿状态机

它按顺序接收 NEW 或 CANCEL 请求，修改某个交易品种的订单簿，同时产生两类结果：

私有结果只发送给相关客户
公开结果用于构建市场数据流

本篇笔记先讨论撮合引擎最核心的部分：订单簿。此处覆盖订单簿整体架构、代表订单的 MEOrder 结构体、添加新订单和撤单、撮合规则

订单簿整体架构

撮合引擎当中最核心的部分莫过于限价订单簿，下图展示了订单簿的设计：

撮合引擎内部限价订单簿的设计

订单簿是用两类链表来表示的：价格档位链表和同价订单链表。选择链表的原因是订单簿当中的操作主要是插入/删除，链表的插入/删除代价较低。代价是插入一个全新价格档位时，可能需要遍历价格链表寻找位置。但是这个代价是值得的，因为价格档位数量有限，且有哈希表来加速定位。

价格档位链表，顾名思义，节点是一个个价格档位，也就是 MEOrdersAtPrice 结构体。这样的链表有两个，bids_by_price_ 和 asks_by_price_ 。前者实质是指向买方最高价档位的指针，后者实质是指向卖方最低价档位的指针。在 bids_by_price_ 内部，价格档位节点按照从高价到低价链接；在 asks_by_price_ 内部，价格档位节点按照从低价到高价链接；为了让价格档位链表更加高效，有 OrdersAtPriceHashMap 这个哈希表。它的 key 是价格，value 是 MEOrdersAtPrice*，由此可以直接通过价格数值找到价格档位结构体，无需遍历链表。

同价订单链表的构成：MEOrdersAtPrice 包含指向该价格档位下排名最优的订单的指针，是 MEOrder* 类型的指针。MEOrder 对象之间再按照到达的先后顺序，FIFO 地连接成同价订单链表。也就意味着同价订单链表没有单独的链表对象。

上述设计已经解决了通过 Side 和 Price 找到所有挂单的问题，但是没有解决找到某个客户的某张挂单的问题。因此引入 ClientOrderHashMap 和 OrderHashMap。ClientOrderHashMap 的 key 是 client_id，value 是 OrderHashMap；OrderHashMap 的 key 是 client_order_id，value 是 MEOrder*。因此 ClientOrderHashmap 本质上是一个二维数组，可以通过 cid_oid_to_order_[client_id_][client_order_id_] 这样访问到某个客户的某张订单。

引申一下，这里“链表 + 哈希表”的方案，是一种常用的让链表更高效的做法，因为哈希表弥补了链表不能随机访问的短板。例如 LRU Cache 也使用 “哈希表+双向链表”。代价是需要额外内存，并且每次修改时必须保证两个结构保持一致。

综上所述，订单簿持有以下这些状态（价格档位和客户订单两张哈希表、买卖两个价格档位链表、存放价格档位和订单的两个内存池）。注意其中内存池的使用：两个链表当中的节点的内存不是在 heap 上分配的，而是直接在内存池中获取预分配好的内存块。

总结一下这个 unit 要着重关注的类/结构体，接下来逐个分析：

MEOrder：表示一张订单。 MEOrdersAtPrice：表示一个价格档位，以及该档位的订单链表。 MEOrderBook：整个订单簿，管理买卖价格链表、订单和撮合。

MEOrder 表示一张订单

MEOrder 是用于表示限价订单的结构体

struct MEOrder {
    TickerId ticker_id_ = TickerId_INVALID;
    ClientId client_id_ = ClientId_INVALID;
    OrderId client_order_id_ = OrderId_INVALID; // 这两个有什么区别？
    OrderId market_order_id_ = OrderId_INVALID;
    Side side_ = Side::INVALID; // 因为这是一个 enum
    Price price_ = Price_INVALID;
    Qty qty_ = Qty_INVALID;
    Priority priority_ = Priority_INVALID;
    MEOrder *Prev_order_ = nullptr; // 这是一个双向链表，要链接到上一个/下一个订单
    MEOrder *Next_order_ = nullptr;
}

同价订单也形成双向环形链表
最先到达的订单与最后到达的订单始终相连
如果同价订单链表中只有一个订单，该订单的 Next_order_ 和 Prev_order_ 都指向自己

ticker_id 用于区分合约，每一个合约有自己的订单簿

client_order_id_ 只在该客户自己的范围内唯一。market_order_id_ 是交易所收到订单后自己生成的 ID。客户不直接使用 market_order_id_ 的原因：客户在发送新订单时，market_order_id_ 还不存在，因此客户只能记录一个自己知道的标识号。一张 MEOrder 会保存两者：

client_id_ + client_order_id_

客户用来提交取消请求
交易所用来定位该客户的订单

market_order_id_

交易所生成，在公共市场数据中标识订单

此处的 side, price 和 qty 都无需多言，由客户的交易意图决定

priority 表示订单在当前价格档位中的到达次序。新被动订单在插入同价订单链表时自动获得 priority。

MEOrdersAtPrice 表示一个价格档位

MEOrdersAtPrice 表示一个价格档位

struct MEOrdersAtPrice {
    Side side_;                  // BUY 或者 SELL
    Price price_;                // 价格
    MEOrder* first_me_order;     // 该价格档位上最先到达的订单
    MEOrdersAtPrice prev_entry_; // 上一个价位档（更优的一个价位档）
    MEOrdersAtPrice next_entry_; // 下一个价位档（更次的一个价位档）
}

如此会形成一个双向环形链表。
最优价位和最劣价位相连
但是 bids_by_price_ 和 asks_by_price_ 这两个代表整个链表的指针始终指向最优价位档。

MEOrderBook 的成员对象

class MEOrderBook {
private:
    TickerId ticker_id_ = TickerID_INVALID;
    
    MatchingEngine* matching_engine_ = nullptr;    // 订单簿不拥有撮合引擎，只是有指向它的指针

    ClientOrderHashMap cid_oid_to_order_;          // 客户+订单ID -> MEOrder

    MemPool<MEOrdersAtPrice> orders_at_price_pool;

    MEOrdersAtPrice* bids_by_price_ = nullptr;     // 买一档
    MEOrdersAtPrice* asks_by_price = nullptr;      // 卖一档

    OrdersAtPriceHashMap price_orders_at_price_;   // 价格 -> 价格档

    MemPool<MEOrder> order_pool_;

    MEClientResponse client_response_;  // 客户私有回调和公开市场更新信息由订单簿管理。
    MEMarketUpdate market_update_; // 且这两个变量是标量，意味着它们经常更新到最新的值

    OrderId next_market_order_id_ = 1;

    std::string time_str_;
    Logger* logger_ = nullptr;
}

MatchingEngine 对象持有 MEOrderBook 对象；MEOrderBook 对象持有指向 MatchingEngine 的指针。

OrdersAtPriceHashMap price_orders_at_price_ 这里，由于有以下两个 typedef，所以 price_orders_at_price_ 本质上是 std::array<std::array<MEOrder*, ME_MEX_ORDER_IDS>, ME_MAX_NUM_CLIENTS> 类型的二维数组。因此可以使用 cid_oid_to_order_[client_id_][client_order_id_] 这样的两个下标来访问订单指针。

typedef std::array<MEOrder *, ME_MAX_ORDER_IDS> OrderHashMap;
typedef std::array<OrderHashMap, ME_MAX_NUM_CLIENTS> ClientOrderHashMap;

client_response_ 和 market_update_ 成员之所以存在，即之所以要持有 MEMarketUpdate 和 MEClientResponse 类型的对象，而不是在需要发送市场更新/客户响应的时候临时构造一个对象，是为了减少在热路径创建临时对象。缺点是每次发送市场更新/客户响应的时候需要完整覆盖所有字段，否则会残留上一次的数据（这也是为什么我们每次更新这两个对象的时候都要写很冗长的 {} ，覆盖结构体当中的每个字段，即使不需要的字段也要用 *_INVALID 来占位）。

MEOrderBook 处理报单的方法

MEOrderBook::add() 报单接口

添加新订单 add() 的顺序如下：

生成 market_order_id
向客户返回 ACCEPTED
调用 checkForMatch() 尝试将新订单与对手盘撮合
若有剩余数量，调用 addOrder() 将其作为被动订单挂入订单簿

如果有同价档位：追加到该档位 FIFO 尾部（然后更新哈希表）
如果无同价档位：创建 MEOrdersAtPrice 档位，插入价格档位链表。然后插入订单（然后更新哈希表）
发布 ADD 市场更新消息

auto MEOrderBook::add(ClientId client_id, OrderId client_order_id, TickerId ticker_id, Side side, Price price, Qty qty) {
    // 生成新的 market_order_id
    const auto new_market_order_id = generateNewMarketOrderId();

    // 书中示例没有展示完整的风控、余额、价格范围、数量范围等校验，直接 ACCEPTED 了
    // 真实交易系统通常会在进入 MEOrderBook 之前拒绝非法订单
    client_response_ = {ClientResponseType::ACCEPTED, client_id, ticker_id, client_order_id, new_market_order_id, side, price, 0, qty};

    matching_engine_->sendClientResponse(&client_response_);

    const auto leaves_qty = checkForMatch(client_id, client_order_id, ticker_id, side, price, qty, new_market_order_id);

    // 这里处理订单没有全部成交的情况。需要让剩余量进入订单簿
    // 如果新订单直接全部成交了，根本不进入订单簿
    if (LIKELY(leaves_qty)) {
        // 获取次序
        const auto priority = getNextPriority(price);

        // 在内存池当中创建一个 MEOrder 对象，拿到其指针，然后添加到订单簿
        auto order = order_pool_.allocate(ticker_id, client_id, client_order_id, new_market_order_id, side, price, leaves_qty, priority, nullptr, nullptr);

        // 这是私有方法
        addOrder(order);

        market_update_ = { MarketUpdateType::ADD, new_market_order_id, ticker_id, side, price, leaves_qty, priority};

        // 此处的市场更新只负责表示向订单簿新增了一个挂单
        matching_engine_->sendMarketUpdate(&market_update_);
    }
}

MEOrderBook::checkForMatch() 循环检查新订单能否继续成交

MEOrderBook::checkForMatch() 只有在 MEOrderBook::add() 添加新订单的时候被调用，负责循环检查新订单能否继续成交，即新订单仍有剩余量，且对手盘仍存在的时候，循环检查价格是否相交。退出循环的条件有三个，是或的关系：

新订单剩余量为 0
整个对手盘没了（asks_by_price_ 或则和 bids_by_price 没了）
新订单的价格与对手盘口价没有相交

auto MEOrderBook::checkForMatch(ClientId client_id, OrderId client_order_id, TickerId ticker_id, Side side, Price price, Qty qty, Qty new_market_order_id) {
    // 剩余未成交量初始化为原始量
    auto leaves_qty = qty;

    // 买方单
    if (side == Side::BUY) {
        // 只要还有未成交量，且整个订单簿上有卖单，就继续循环
        while (leaves_qty && asks_by_price_) {
            // 获取卖一价位最前面订单的指针
            const auto ask_itr = asks_by_price_->first_me_order_;

            if (LIKELY(price < ask_itr->price_)) {
                break;
            }

            // 价位能够成交
            match(ticker_id, client_id, side, client_order_id, new_market_order_id, ask_itr, &leaves_qty);
        }
    }

    if (side == Side::SELL) {
        while (leaves_qty && bids_by_price_) {
            // 获取买一价最前面订单的指针
            const auto bid_itr = sell_by_price_->first_me_order_;

            // 卖单价格太高，不成交
            if (LIKELY(price > bid_itr->price_)) {
                break;
            }

            // 能成交
            match(ticker_id, client_id, side, client_order_id, new_market_order_id, bid_itr, &leaves_qty);
        }
    }

    return leaves_qty;
}

MEOrderBook::match() 计算新订单与一张挂单的成交量

ticker_id, client_id, side, client_order_id, new_market_order_id 这几个都是新订单（也就是主动单）的情况；而 passive_order 是订单簿中的一张被动单。当前方法由 MEOrderBook::checkForMatch() 调用，调用时已经确认新订单与传入的挂单能成交。当前方法只是计算成交量。

注意这里的 leaves_qty 是一个 Qty* 类型的指针，因此在 match() 方法内可以直接修改其值

auto MEOrderBook::match(TickerId ticker_id, ClientId client_id, Side side, OrderId client_order_id, OrderId new_market_order_id, MEOrder* passive_order, Qty* leaves_qty) {
    // 参数表示新订单的情况

    // 一次只处理新订单与一张挂单的成交。如果还有剩余量可以成交，由外层循环处理

    const auto order = passive_order;  // 指向一张挂单
    const auto order_qty = order->qty; // 挂单的剩余量

    // 这 3 行处理了两种成交情况（全部成交/部分成交）
    const auto fill_qty = std::min(*leaves_qty, order_qty); 
    *leaves_qty -= fill_qty;
    order->qty_ -= fill_qty;

    // 需要 **分别** 向新订单与挂单的客户端发送成交回调
    // 1. 向新订单的客户发送回调
    client_response_ = {ClientResponseType::FILLED, client_id, ticker_id, client_order_id, new_market_order_id, side, itr->price_, fill_qty, *leaves_qty};

    matching_engine_->sendClientResponse(&client_response);

    // 2. 向挂单的客户发送回调
    client_response_ = {ClientResponseType::FILLED, order->client_id_, order->ticker_id_, order->client_order_id_, order->market_order_id_, order->side_, order->price_, fill_qty, order->qty_};

    matching_engine_->sendClientResponse(&client_response);

    // 发送公开市场更新，包括 TRADE 信息，以及 CANCEL 或 MODIFY 信息
    // 发送 TRADE 信息
    market_update_ = {MarketUpdateType::TRADE, OrderId_INVALID, ticker_id, side, order->price_, fill_qty, Priority_INVALID}

    matching_engine_->sendMarketUpdate(&market_update_);


    if (!order->qty_) { // 挂单全部成交，把它从订单簿上撤掉并且发送 CANCEL
        market_update_ = {MarketUpdateType::CANCEL, order->market_order_id_, ticker_id, order->side_, order->price_, order_qty, Priority_INVALID};
        
        matching_engine_->sendMarketUpdate(&market_update_);
        removeOrder(order);
    }
    else { // 挂单只是部分成交，修改它的剩余量并发送 MODIFY
        market_update_ = {MarketUpdateType::MODIFY, order->market_order_id_, ticker_id, order->side_,  order->price_, order->qty_, order->priority_};
        
        matching_engine->sendMarketUpdate(market_update_);
    }

}

MEOrderBook::addOrder() 把新订单加入订单链表和哈希表

负责把 MEOrder 最终加入订单簿当中。需要判断是否出现新价位

auto MEOrderBook::addOrder(MEOrder* order) noexcept {
    const auto orders_at_price = getOrdersAtPrice(order->price_);

    if (!orders_at_price) { // 新订单的价格没有价格档位，需要创建一个价格档位
        order->next_order_ = order->prev_order_ = order;
        
        // 在内存池上为这个价格档位分配内存块
        auto new_orders_at_price = orders_at_price_pool_.allocate(order->side_, order->price_, order, nullptr, nullptr);

        // 在链表和哈希表上新增这个价格档位
        addOrdersAtPrice(new_orders_at_price);
    }
    else {
        auto first_order = orders_at_price->first_me_order_;

        // 把新订单链接到同价位订单链表尾部
        first_order->prev_order_->next_order_ = order;
        order->prev_order_ = first_order->prev_order_;
        order->next_order_ = first_order;
        first_order->prev_order_ = order;
    }

    // 这个 at() 就是 [] 下标访问的安全版本，不会越界
    cid_oid_to_order_.at(order->client_id_).at(order->client_order_id_) = order;
}

MEOrdeBook::addOrdersAtPrice() 把新价格档位加入价格档位链表和哈希表

在 addOrder() 在发现新订单的价格没有价格档位时，先从内存池上分配一个 MEOrdersAtPrice 结构体，然后当前方法：把这个价格档位结构体插入价格档位链表和 price_orders_at_price_ 哈希表

要处理整个订单簿当中买方或卖方价格档位为空的状况

还要区分以下三种情况：

新添加的价格档位位于最优档位之前
位于中间
位于最次档位之后

auto MEOrderBook::addOrdersAtPrice(MEOrdersAtPrice* new_orders_at_price) noexcept {
    price_orders_at_price_.at(priceToIndex(new_orders_at_price->price_)) = new_orders_at_price;

    // 获取指向盘口价格档位的指针
    const auto best_orders_by_price = (new_orders_at_price->side == Side::BUY ? bids_by_price_: asks_by_price_);

    // 订单簿中，买方或者卖方的价格档位完全为空，那就创建一个新指针
    // 三元表达式的两个分支都是左值，因此整个表达式可以当作左值使用
    if (UNLIKELY(!best_orders_by_price)) {
        (new_orders_at_price->side == Side::BUY ? bids_by_price_ : asks_by_price_) = new_orders_at_price;
    }

    else {
        // target 表示新价格档位的目标位置（如果目标位置在最末尾，则 target 表示目标位置前面的位置）
        // 初始化为盘口价
        auto target = best_orders_by_price;

        // 是否要把 target 向后挪。取决于价格。

        const auto should_add_after = [&](MEOrdersAtPrice* target){ return ((new_orders_at_price->side_ == Side::SELL && new_orders_at_price->price_ > target->price_) || (new_orders_at_price->side == Side::BUY && new_orders_at_price->price < target->price_)) }; 

        bool add_after = should_add_after(target);

        if (add_after) {
            target = target->next_entry_;
            add_after = should_add_after(target);
        }

        // target != best_orders_at_price 用来确保在环形链表中的比较没有回到起点
        while (add_after && target != best_orders_at_price) {
            add_after = should_add_after(target);
            if (add_after) {
                target = target->next_entry_;
            }
        }

        if (add_after) {
            target->next_entry_->prev_entry_ = new_orders_at_price;
            new_orders_at_price->next_entry_ = target->next_entry_;
            target->next_entry_ = new_orders_at_price;
        }
        else { // 在 target 之前防止 new_orders_at_price
            new_orders_at_price->prev_entry_ = target->prev_entry_;
            new_orders_at_price->next_entry_ = target;
            target->prev_entry_->next_entry_ = new_orders_at_price;
            target->prev_entry_ = new_orders_at_price;

            if (should_add_after(best_order_by_price)) {
                target->next_entry_ = (target->next_entry_ == best_orders_by_price ? new_orders_at_price : target->next_entry_);
                (new_orders_at_price->side_ == Side::BUY ? bids_by_price_ : asks_by_price_) = new_orders_at_price;
            }
        }
    }
}

MEOrderBook 处理撤单的方法

MEOrderBook::cancel() 撤单接口

撤单的顺序如下：

先找到订单：

cid_oid_to_order_[client_id][client_order_id];

找到后：

从同价订单链表删除（将对应槽位改为 nullptr）
在订单哈希表当中把这张订单删掉
归还 MEOrder 给内存池

如果该订单是档位中最后一张订单，还需要

在价格档位链表中删除对应价格档位
更新价格档位哈希表
如果买一价或卖一价变动，需要修改 bids_by_price_ 或 asks_by_price_
归还 MEOrdersAtPrice 给内存池

auto MEOrderBook::cancel(ClientId client_id, OrderId client_order_id, TickerId ticker_id) {
    // 确保订单可撤的第 1 步：确保 client_id 不越界
    // TODO：作者把指针命名为 itr 是不准确的，这不是迭代器。可以考虑重构重命名
    auto is_cancelable = (client_id < cid_oid_to_order_.size());

    MEOrder* exchange_order = nullptr;

    if (LIKELY(is_cancelable)) {
        // 确保订单可撤的第 2 步：确保订单指针有效
        exchange_order = cid_oid_to_order_.at(client_id).at(order_id);
        is_cancelable = (exchange_order != nullptr);
    }

    if (LIKELY(is_cancelable)) { // 订单可撤
        // 客户私有响应
        client_response_ = {ClientResponseType::CANCELED, client_id, ticker_id, order_id, exchange_order->market_order_id_, exchange_order->side_, exchange_order->price_, Qty_INVALID, exchange_order->qty_};

        // 市场状态更新
        market_update_ = {MarketUpdateType::CANCEL, exchange_order->market_order_id_, ticker_id, exchange_order->side_, exchange_order->price_, 0, exchange_order->priority_};

        removeOrder(exchange_order);

        matching_engine_->sendMarketUpdate(market_update_);
    }
    else {
        client_response_ = {ClientResponseType::CANCEL_REJECTED, client_id, ticker_id, order_id, OrderId_INVALID, Side::INVALID, Price_INVALID, Qty_INVALID, Qty_INVALID};
    }

    matching_engine_->sendClientResponse(&client_response_);
}

MEOrderBook::removeOrder() 把订单从订单链表和哈希表上删除，并释放内存块

auto MEOrderBook::removeOrder(MEOrder* order) noexcept {
    auto orders_at_price = getOrdersAtPrice[order->price_];

    if (order->prev_order_ == order) { // 当前订单是这个档位上唯一的订单
        removeOrdersAtPrice(orders_at_price);
    }
    else {
        // 把该订单从订单链表上删除
        const auto order_before = order->prev_order_;
        const auto order_after = order->next_order_;

        order_before->next_order_ = order_after;
        order_after->prev_order_ = order_before;

        if (order == orders_at_price->first_me_order) {
            orders_at_price->first_me_order = order_after;
        }
        order->prev_order_ = order->next_order_ = nullptr;
    }

    // 把该订单从哈希表上删除
    cid_oid_to_order_.at(order->client_id_).at(order->order_id_) = nullptr;

    // 释放内存块
    order_pool_.deallocate(order);
}

MEOrdeBook::removeOrdersAtPrice() 把订单档位从订单档位链表和哈希表上删除，并释放内存块

auto MEOrderBook::removeOrdersAtPrice() {
    const auto best_orders_by_price = (side == Side::BUY ? bids_by_price_ : asks_by_price_);
    auto orders_at_price = getOrdersAtPrice(price);

    // 把订单档位从订单档位链表上删除
    if (UNLIKELY(orders_at_price->next_entry == orders_at_price)) {// 当订单簿该侧只剩下最后一个价格档位
        (side == Side::BUY ? bids_by_price_ : asks_by_price_) = nullptr;
    }
    else {
        orders_at_price->prev_entry_->next_entry_ = orders_at_price->next_entry_;
        orders_at_price->next_entry_->prev_entry_ = orders_at_price->prev_entry_;

        if (orders_at_price == best_orders_by_price) {
          (side == Side::BUY ? bids_by_price_ : asks_by_price_) = orders_at_price->next_entry_;
        }

        orders_at_price->prev_entry_ = orders_at_price->next_entry_ = nullptr;
    }

    // 把订单档位从订单档位哈希表上删除
    price_orders_at_price_.at(priceToIndex(price)) = nullptr;

    // 释放内存块
    orders_at_price_pool_.deallocate(orders_at_price);
}