摘要
一台单核 CPU 在子微秒的中位端到端响应延迟下，能够维持每秒 3200 万个订单消息的处理速度，比现有的开源匹配引擎快 4.7-11 倍。扩展后，单台 96 核商品服务器（约 $1,630/月）能够在 10,000 个符号上处理约 6.4 亿条消息每秒，超过美国合并报价源提供的容量 20 倍。我们通过解决设定匹配延迟的存储层问题，实现了这些数字。
技术细节
主流的订单簿实现使用了通过平衡树链接的链表，这在每次操作中产生了两个成本：插入点的指针追踪遍历和从根到叶子的搜索以定位目标价格水平。在微突发情况下，这些成本会导致尾部延迟的峰值，降低在流动性最需要时的市场质量。
我们提出了两种数据结构的贡献，以消除这些问题。
优先指示节点 (PIN)
第一种是优先指示节点（PIN），它是一个优先级队列，其中条目占用固定容量、连续可寻址的槽，并通过指示器编码条目的全局优先级状态。与堆（每个操作需要 O(log n) 次比较）不同，PIN 直接通过指示器解析插入位置，无需比较条目；指示器更新为 O(1)，与队列大小无关。
邻居感知插入与删除
第二个针对更广泛的低效问题：平衡搜索树在每次插入和删除时都从根到叶进行搜索，即使调用者已经知道键的有序邻居，这在电子交易中是零成本的。邻居感知插入和删除利用已知邻居引用以 O(1) 的引用写入附加或移除节点，随后在红黑树、AVL 树和 B+ 树变体中进行单路径的重新平衡。
博主点评： 该算法的创新之处在于通过改进数据结构，显著降低了匹配延迟，提升了交易系统的性能。这为高频交易等对延迟敏感的应用提供了强有力的支撑，值得在实际系统中推广应用。