用 Rust 设计 matching engine：没有 GC 停顿的 price-time priority

现货交易所的 matching engine 职责很窄。它接收一条有序的指令流——下单、撤单、改单——按 price-time priority 应用到 order book 上，并输出一条有序的事件流：成交、账本更新、拒单、确认。

它的全部难点，来自叠加在这项职责上的三条约束：同一输入每次回放的结果必须完全一致；部分成交订单的剩余量必须保住它在队列中的位置；突发到来时延迟长尾不得抬头。

order book 是建立在 FIFO 队列之上、按价位排序的索引

账本由两侧组成，每侧是按价格排序的价位集合。价位不是一个数字——它是该价格上按到达顺序排列的挂单队列。撮合频繁触碰最优价位、极少触碰深处价位，所以结构是按这种访问模式挑的，而不是按优雅程度挑的。

• 价格是以 tick 为单位的整数，绝不用浮点——tick 是该合约的最小单位，而整数的比较和运算是精确的
• 每一侧按价格顺序保存价位，最优价无需查找即可取到——每一条指令都要读一次盘口顶端
• 每个价位持有一个挂单的 FIFO 队列，外加聚合后的挂单数量，这样聚合值不必靠遍历队列重新算出
• 订单存放在预分配的 slab 中，通过索引句柄引用，队列是侵入式的：前后链接就住在订单记录本身里面
• 一张从客户订单号到 slab 句柄的独立映射，使撤单和改单成为直接查表，因此撤单从不扫描账本
• 从队列中移除靠句柄而不是查找——撤掉一笔深处的挂单，代价与撤掉盘口顶端的挂单相同

侵入式队列与索引句柄带来的结果是：挂单在其存活期间从不在内存中移动。它的队列位置是其链接的属性，而不是它恰好坐在哪里的属性，这正是后面部分成交能做得廉价的原因。

price-time priority 就是先遍历价位、再遍历队列的一个循环

到来的主动单从最优价起，向内遍历对手方。在每个价位上，它从队首开始遍历 FIFO 队列。当该价位的价格对来单不再可接受，或来单数量归零时，它就停下。

• 取对手方最优价位；若它的价格与来单的限价不交叉，就停止
• 取该价位队列的队首订单——它是这个价格上最早的一笔，时间优先意味着它先成交
• 成交数量取双方剩余量中较小的那一个；成交价取挂单的价格，因为条件是挂单先定下的
• 扣减双方的剩余量，发出成交事件，并扣减该价位的聚合量
• 若挂单的剩余量归零，就把它从队列中摘下并归还它的 slab 槽位；若该价位变空，就移除这个价位
• 重复这一过程，直到来单数量归零，或不再有可接受的价位

订单类型的语义，是在这个循环的边界上做出的决定，而不是在循环内部。Immediate-or-cancel 丢弃剩余量而不把它挂出。Fill-or-kill 先做一次空跑，要么整单执行，要么拒单。Post-only 在订单到达即会交叉时拒单。把这些放在循环之外，意味着循环仍是唯一改变账本状态的地方。

自成交防范、最小数量，以及 tick 与手数校验，同样属于循环之前的事。抵达撮合的订单已被证明格式良好，因此循环里没有会拖慢它、也没有会引发分歧的错误分支。

确定性让长尾可预测，而内存分配会打破它

平均延迟很少是问题。问题在于突发期间最差的那次观测值，而那正是引擎最要紧、也最可能撞上 stop-the-world 停顿的时刻。在带 garbage collector 的托管运行时下，这个停顿由收集器而不是由你来安排，并且它恰好落在制造了垃圾的那波突发中间。

手动分配只是同一问题的缩小版。通用分配器可能遍历空闲链表、加锁，或者向内核要更多内存，而做这件事的那次调用，正是出现在长尾里的那次调用。两种情况的解法是一样的：热路径上根本不做分配。

• 订单记录、价位记录和事件缓冲，都来自启动时定好大小的 arena——稳态下撮合路径上的分配次数为零
• 释放的槽位回到 arena 内的空闲链表，因此活跃合约整个会话都在复用同一块内存
• 结构的形状固定、大小固定，容量上限以拒单的方式执行，而不是触发一次扩容
• 外发事件写入一个预分配的环形缓冲，由另一个线程消费——撮合线程永不因消费者而阻塞
• 撮合线程是账本的唯一写入者，因此账本状态上没有锁，也没有次序歧义需要化解
• 输入在到达引擎之前就已排好序，决定次序的是序号而不是到达时间

当同一输入序列在另一台机器上、在一年之后仍逐字节产生同一输出序列时，引擎才是确定性的。撮合路径内任何读取墙上时钟、线程调度或哈希遍历顺序的东西，都会破坏这个性质。

因此时间戳是一种输入，而不是引擎自己去读的东西。定序器在接受指令时为它打上时间戳，撮合循环把这个戳当作数据。若确实需要随机性，它来自一个带种子的生成器，而种子是日志的一部分。

日志才是引擎状态，账本只是它的一份缓存

恢复不是撮合跑通之后再拴上去的功能。引擎按序号顺序，把已接受的指令写入只追加的日志，而内存中的账本不过是折叠这份日志的结果。崩溃后的重建，就是把它重放一遍。

• 指令在撮合之前已写入日志并完成持久化，因此已被接受的订单不会因确认与执行之间的崩溃而丢失
• 日志记录的是输入序列，而不是输出——输出是派生出来的，而回放做的正是重新派生它们
• 账本的周期性快照带着自己被拍下时的序号，因此恢复只需加载一份快照，再回放日志的尾部
• 快照与回放是否一致要检查，而不是假定：从上一份快照回放，必须重现出下一份
• 事件流携带同样的序号，因此下游消费者——风控、结算、行情——可以从一个已知的点续上，而不必人工重新同步

引擎负责写日志，但持久性取决于存储路径，以及在确认发出之前有多少台机器已经拿到这条记录。那是复制与硬件层面的决定，恢复时间真正的胜负也在那里。

测试就是确定性回放，加上必须始终成立的不变量

确定性正是引擎可测试的前提。因为同一输入给出同一输出，录下的一段会话就是一个回归测试，发现过一次的故障可以被精确复现，而不用去追。

• 回放框架：喂入录制好的指令序列，把发出的事件流与存档的那份对比，在第一处分歧就带着序号失败
• 测试构建中，每条指令之后都做不变量检查——队列按到达顺序排列、价位聚合量等于其队列之和、账本不交叉、每笔成交前后总量守恒
• 基于属性的测试：生成随机但格式良好的指令序列，断言的是不变量，而不是具体结果
• 差分参考模型：一个用朴素数据结构写成、缓慢但显然正确的实现，用同样的输入运行，任何不一致都视为快速实现中的缺陷
• 在解码器边界做 fuzzing，畸形输入正是从那里进来的，而一次 panic 会把撮合线程带崩
• 在你真正担心的那种突发形态下测量延迟，记录分布而不是平均值，因为决定设计的数字是长尾

Rust 在这里给了你什么，又没给你什么

Rust 消除的是一类问题，而不是它本身让循环跑得更快。这里没有 garbage collector，所以不会有停顿在你背后被安排。所有权让单写者纪律成为编译器强制的事，而不是代码评审必须留意的事。slab 句柄和侵入式链接在没有生命周期的语言里很容易出错，在这里则是可检查的。调试构建下整数溢出会触发 panic，能抓住一类会悄悄弄坏账本的缺陷。

诚实的边界在于：决定长尾延迟的绝大部分因素并不是语言：

• 内核调度、中断处理、CPU 绑核与电源管理对长尾的影响，比撮合代码本身更大
• 网卡、是否使用内核旁路，以及通往交易场所的物理链路，划定了引擎无法突破的下限
• 边界上的序列化和传输协议，常常才是成本的大头，而不是撮合本身
• 撮合语义、订单类型、费率与返佣规则以及市场阶段，都是业务决策——快速实现出来的错误规则，依然是错的
• 风控检查、持仓限额和结算路径都住在引擎之外，有各自的延迟和各自的失败模式
• 运维——部署、监控、回放失败时的处置手册——决定这些保证能否在生产事故面前存活

Rust 也是有代价的。在设计还在变动的头几周，借用检查器会拖慢进度；交易所专有协议的生态比老牌语言更薄；围绕无锁结构的 unsafe 块，需要与别处等价代码同样严格的评审纪律。选择它，是关于延迟长尾、以及单写者内核中内存安全的决定，不是关于开发者舒适度的决定。

amBrain 自 2019 年起在亚美尼亚埃里温做交易基础设施，热路径用 Rust 编写——行情数据在 5 ms 以内送达，交易前风控检查在 1 ms 以内完成。如果你正在设计 matching engine，想一起过一遍账本结构、日志格式或回放框架，这样的交流值得在写下热路径第一行代码之前进行。