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

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

它按顺序接收 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*。想象成一个拥有三层节点的树，根节点就是指向订单的指针。于是可以有 cid_oid_to_order_[client_id_][client_order_id_] 这个方法，通过 client_id_ 和 client_order_id_ 即可找到某个客户的某张订单。

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

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

ClientOrderHashMap cid_oid_to_order_;     // 客户+订单ID -> MEOrder
OrdersAtPriceHashMap price_orders_at_price_; // 价格 -> 价格档
MEOrdersAtPrice* bids_by_price_;          // 买一档
MEOrdersAtPrice* asks_by_price_;          // 卖一档

MemPool<MEOrder> order_pool_;
MemPool<MEOrdersAtPrice> orders_at_price_pool_;

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_ 这两个代表整个链表的指针始终指向最优价位档。

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;

    // 构造函数
    MEOrder() = default;
    MEOrder(TickerId ticker_id, ClientId client_id, OrderId client_order_id,
            OrderId market_order_id, Side side, Price price,
            Qty qty, Priority priority, MEOrder *prev_order, MEOrder *next_order) noexcept
        : ticker_id_(ticker_id), client_id_(client_id),
        client_order_id_(client_order_id), market_order_id_(market_order_id),
        side_(side), price_(price), qty_(qty), priority_(priority),    
        prev_order_(prev_order), next_order_(next_order) {}

}

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

订单属于哪个订单簿：ticker_id

ticker_id 本质上是区分合约的。每一个合约有自己的订单簿

标识一张订单：client_id_, client_order_id_ 和 market_order_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

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

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

添加新订单和撤单

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

客户提交带有 client_id 和 client_order_id 的请求
交易所生成 market_order_id
交易所向客户返回 ACCEPTED
尝试将新订单与对手盘撮合
若有剩余数量，将其作为被动订单挂入订单簿

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

发布 ADD

撤单的顺序如下：

先找到订单：

cid_oid_to_order_[client_id][client_order_id];

找到后：

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

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

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

撮合

买单的成交条件：买价 >= 卖一价
卖单的成交条件：卖价 <= 买一价
严格遵守先最优价格成交，再同价 FIFO
每次成交量为：fill_qty = min(激进单量, 满足条件的挂单量)
激进单剩余量进入订单簿成为挂单