用 C++20 构建亚微秒级订单撮合引擎
三层数据结构如何实现 O(1) 撤单和亚微秒级延迟。
每家交易所的核心系统
NYSE、NASDAQ、CME 等电子交易所都以撮合引擎为核心，在最优可用价格上配合买卖订单。从系统层面构建它，需要掌握价格时间优先、关键路径内存分配和亚微秒延迟工程。
NanoMatch 是我使用现代 C++20 从零实现的撮合引擎，在单线程合成基准中每秒处理 1M+ 订单，延迟低于一微秒。
三层数据结构
简单实现可能只使用一个优先队列。它能以 O(1) 找到最优价格，但撤单需要 O(n)。在本实现中，直接查找索引和每个价格层级的订单队列使撤单达到 O(1)。
NanoMatch 使用三种协作的数据结构：
| 层 | 结构 | 用途 |
|---|---|---|
| 价格层级 | std::map<Price, PriceLevel> | 按价格排序。买单用 std::greater（高价优先），卖单用 std::less（低价优先）。插入 O(log M)，通过 begin() 以 O(1) 获取最优价格。 |
| 订单队列 | 每层一个 std::list<Order> | 同价格下使用 FIFO；追加 O(1)，按迭代器删除 O(1)。 |
| 查找索引 | std::unordered_map<OrderID, Iterator> | 撤单 O(1)；哈希查找返回列表迭代器，再以常数时间删除。 |
整数价格：避免浮点陷阱
价格以分为单位存储为 int32_t（$101.50 = 10150）。浮点比较（==）存在表示误差，并不可靠。在撮合引擎中，可能导致本该合并的价格层级仍分开，或在错误价格撮合订单。整数运算使比较精确且确定。
内存池分配器
关键路径上的每次 malloc / free 都可能带来内核调用、分配器锁竞争和缓存污染。NanoMatch 使用自定义空闲链表内存池：
- 预先分配固定容量、连续存储的
std::vector<T> allocate()= 取出空闲链表头 = O(1)，无系统调用deallocate()= 放回链表头 = O(1)，无系统调用- 所有内存位于同一块连续区域，对缓存友好
基准显示内存池消除了造成尾延迟尖峰的分配抖动。
正确处理订单类型
四种订单类型采用适用于生产系统的语义：
- Limit：撮合可成交部分，其余留在订单簿
- Market：将价格设为
MAX/MIN以确保跨价成交，绝不挂留 - IOC（立即成交或取消）：类似限价单，但取消未成交余量
- FOK（全部成交或取消）：用
can_fill_completely()原子预检查，执行前扫描所有可成交层级。若流动性不足，则完全不成交
改单通过撤单再新增实现。修改后的订单会像在 NYSE 或 NASDAQ 一样失去时间优先级。
延迟分布
| 百分位 | 延迟 |
|---|---|
| p50 | 84 ns |
| p99 | 625 ns |
| p99.9 | 1,250 ns |
p99.9 结果约为 p50 的 15 倍。在这次基准测试中，延迟尖峰来自新增价格层级时的红黑树重平衡、订单跨越多个层级，以及冷价格层级的缓存未命中。