撮合引擎架构，基于内存的订单簿如何实现微秒级匹配

在金融交易系统里，撮合引擎是心脏，订单来了，必须匹配，必须快，每个微秒的延迟都可能意味着滑点、套利失败、甚至系统崩溃，我们讨论的不是理论，是现实——基于内存的订单簿设计,把匹配时间压到微秒级。

一 为什么内存是唯一的战场

磁盘太慢，哪怕SSD，一次随机读写也要几十微秒，撮合引擎每秒处理几万笔订单，磁盘IO会变成死结，内存的延迟主要来自CPU缓存和内存总线，通常几个纳秒到几十纳秒，内存里的数据是易失的，但交易系统有备份机制：日志、快照、WAL，订单簿本身不需要持久化到磁盘，真正的状态变化通过日志记录,内存是撮合引擎的自然栖息地。

订单簿本质是一个数据结构，存储所有未成交的买单和卖单，按价格排序，同价订单按时间排序，插入、删除、查询必须O(1)或O(logN)，性能瓶颈不在内存容量，而在内存访问模式，缓存行命中、分支预测、内存对齐,这些细节决定微秒级的差距。

二 内存订单簿的核心结构

价格队列是最常见的设计，每个价格点是一个链表，链表里挂着该价格的订单，订单按到达顺序排列，当新订单进入，撮合引擎按价格优先进去匹配，买单从最高价卖单开始，卖单从最低价买单开始，价格队列用红黑树或跳表组织,按价格排序。

红黑树支持O(logN)的查找、插入、删除，跳表实现简单，但缓存局部性差，实际生产中，红黑树更常见，比如Linux内核就广泛使用，但红黑树的旋转操作有常数开销，在微秒级竞争里,这个常数不能被忽略。

有些系统用直接寻址，比如价格精度固定到小数点后两位，价格范围0-9999，就能用一个数组映射价格，订单簿是数组，索引是价格，值是订单链表，插入和删除是O(1)，没有树旋转，缺点：价格范围有限，动态扩展难，但对于加密货币期货或外汇做市，价格范围通常可控，牺牲灵活性换速度,值。

还有一个关键数据结构是价格级别指针，每次撮合不需要遍历所有价格，而是维护一个指向当前最佳买价和最佳卖价的指针，当最佳价格被吃掉，指针下移或上移到相邻价格，这个指针的更新用原子操作,无锁。

订单ID用递增序列，不重复，订单结构的字段：价格、数量、方向、时间戳、下一个订单指针，所有这些数据放在连续内存里，避免指针跳跃，订单池预分配，用对象池，每次新订单从池里拿一个，释放时归还，避免动态内存分配,减少页错误。

三 微秒级匹配的关键技术

无锁设计是核心，传统多线程用互斥锁保护订单簿，互斥锁的上下文切换成本在微秒级别，锁争用导致CPU忙等，无锁用CAS compare-and-swap 或内存屏障，对订单簿的插入、删除、匹配操作都用原子指令，修改价格队列的链表头，用CAS，如果CAS失败，重试,大多数操作在几十个纳秒内完成。

批量处理，单笔订单匹配可能只产生一次成交，但微秒级系统不会一笔一笔处理，新订单在内存中暂存，累积到一个微批次，比如每100微秒或每1000个订单处理一次，批量匹配能利用CPU缓存，减少分支预测失败，但批量处理引入额外延迟，不适合高频做市，所以有些系统采用双缓冲：一个缓冲区接收订单，另一个缓冲区进行匹配，切换缓冲区用原子指针交换,接近无锁。

批量合并价格队列，如果多个订单触发同一个价格，可以一次性处理整个价格队列，比如一个市价买单进来，需要吃掉所有卖单，传统做法是循环弹出队列头部，每次更新成交量，优化做法是：把整个价格队列的成交量聚合起来，一次性计算总成交量，然后直接修改队列指针，这个需要价格队列的订单结构支持批量移除，好比一个链表片段的头部和尾部指针，整个片段被替换，这减少了循环次数,减少锁持有时间。

内存对齐，CPU缓存行一般是64字节，如果两个不同的订单结构位于同一缓存行，一个线程修改一个订单会导致另一个线程的缓存行失效，这叫假共享，解决方案：订单结构按缓存行对齐，填充到64字节，代价是内存浪费，但值得，同样,价格队列的头指针和尾指针也要在不同缓存行。

分支预测优化，撮合逻辑里有很多条件分支，比如判断价格是否匹配、成交量是否满、订单方向，用likely和unlikely宏引导编译器优化，或者用位运算替代分支，订单方向用0和1表示，匹配逻辑用异或：if (bid_direction ^ ask_direction) 是匹配，代替if (order1.side == BUY && order2.side == SELL)，位运算没有分支,CPU流水线更高效。

预取指令，CPU有预取指令，_builtin_prefetch，当遍历价格队列时，提前把下一个订单结构的内存加载到缓存，这个用得好，能减少缓存缺失，但需要知道走哪条路径，有时提前预取失败反而有害，动态预取：根据当前订单数量级调整预取深度。

延迟绑定的ID生成，订单ID不用全局原子递增，而是每个线程有自己的ID缓存，线程从全局池拿一段连续ID，比如0-1023，用完了再取一段，这避免了全局CAS竞争,ID生成几乎是零开销。

四 内存管理的禁忌

内存分配是万恶之源，每个新订单都malloc，一次malloc几十纳秒到几微秒，用内存池，预先分配一大块连续内存，比如1MB的订单池，池中的对象用空闲链表管理，释放不是free，而是把订单结构放回空闲链表，这个链表也是无锁的，每个线程有自己的本地缓存,减少全局竞争。

垃圾回收，如果撮合引擎用Java或C#，GC暂停是噩梦，即使暂停几毫秒，订单堆积可能导致系统崩溃，所以必须用C或C++，手动管理内存，或者用Rust，所有权系统保证内存安全,GC暂停在微秒级系统不可接受。

TLS 线程局部存储，每个线程的订单缓存、临时变量都放在TLS，避免全局互斥，TLS访问比全局变量快,编译器优化也更直接。

原子操作的选择，不是所有变量都需要原子操作，比如订单的成交量只被一个线程修改时，用普通赋值，多线程共享的价格队列指针必须用原子，但原子操作有内存屏障，带顺序保证，比如memory_order_acq_rel，如果不需要顺序，用memory_order_relaxed,这个差别在微秒级系统里明显。

五 匹配算法的核心流程

当一个买单到达，撮合引擎先检查买单价格是否等于或高于当前最低卖价，是，则匹配，匹配过程：从最低卖价队列开始，取出队首卖单，比较数量，如果买单数量大于卖单数量，成交整个卖单，买单剩余数量继续匹配下一个卖单，如果买单数量小于卖单数量，成交买单全部，卖单剩余数量修改，修改卖单数量时，用原子减法，而不是替换整个订单结构,原子减法更便宜。

价格优先，买单按价格降序排列，卖单按价格升序排列，同价订单按时间优先，时间戳用单调递增的计数器，不用系统时钟，系统时钟可能回拨，计数器每纳秒递增一次，用CPU的TSC指令，TSC每个核心不同，所以时间戳需要带上核心ID，或者用全局单调计数器，但中心化计数器有性能瓶颈，实际方案：每个核心独立维护计数器，订单带上核心ID和本地计数器，比较时先比核心ID，再比计数器，核心ID的顺序可以按启动顺序，这样不同核心的订单视为按时间顺序,这个技巧减少了全局同步。

部分成交与撤销，订单簿必须处理撤销，撤销操作：在价格队列中找到对应订单，删除节点，删除用CAS修改前驱节点的next指针，如果前驱节点也被其他线程修改，CAS可能失败，重试，为了提高撤销效率，订单结构可以包含前驱指针，或者用双链表，双链表删除简单，但双链表维护成本高，实践中，单链表加延迟删除更常见，订单标记为已撤销，不真正删除，匹配时跳过,定期清理已撤销订单。

市场深度，订单簿需要提供市场深度数据，一般用快照方式，每几毫秒生成一次，生成时遍历所有价格队列，计算每个价格的成交量，这个遍历如果同步进行，会阻塞撮合，异步方案：用双缓冲，撮合线程维护一个当前订单簿，深度快照线程读取另一个只读副本，当撮合完成一批操作，原子交换指针，让只读副本更新，这个交换延迟极低,几个纳秒。

六 实际案例：某加密货币交易所

去年我参与过一个小型加密货币交易所的撮合引擎设计，需求是每秒十万笔订单，90%的订单在10微秒内完成匹配，我们用了C++，订单池提前分配，每个价格队列用数组链表，价格范围0-100000，直接寻址，最佳价格指针用原子变量，每个核心只有一个撮合线程，没有锁，订单池预分配10万个订单结构，用空闲链表管理，空闲链表用无锁栈实现，每个线程从栈顶取对象,释放时用CAS压回栈。

匹配逻辑里，市价单批量处理，比如一个市价买单进来，先把所有卖单队列的成交量算出来，然后一次性修改队列指针，这个操作需要原子交换整个价格队列的头指针，卖单队列的头指针指向新的头部，旧头部指向的订单全部成交,这个批量操作在微秒级完成。

测试结果：在单核心上，平均匹配延迟5微秒，99百分位12微秒，系统能处理二十万笔订单每秒，瓶颈不在内存访问，而在CPU的指令执行，我们用perf工具分析发现，大部分时间花在原子CAS和分支预测失败上，后来我们用位运算替代部分分支，性能提升15%。

还有一个问题：订单撤销，撤销操作如果频繁，会导致订单池碎片化，我们用了延迟清理：每处理10万笔订单，运行一次垃圾收集，把撤销的订单标记为可重用，这个收集过程在后台线程进行，不影响主线程,主线程只在空闲时检查一次标记。

七 微秒级匹配的极限

能到纳秒级吗？理论上有，用FPGA实现撮合逻辑，订单簿全部在FPGA片上RAM，匹配逻辑硬件化，延迟可以压到几十纳秒，但FPGA开发成本高，迭代慢,大多数交易系统用CPU。

CPU的寄存器远比内存快，关键交易数据放在寄存器，比如当前最佳价格，但寄存器数量有限，另一个极限是CPU缓存，L1缓存访问延迟1纳秒，L2 4纳秒，L3 10纳秒，如果订单结构全部塞进L1，匹配延迟可能在几十纳秒，但订单簿规模大，必须用L2或L3，所以内存布局必须优化,保证热点数据在缓存中。

有一个概念叫缓存局部性，价格队列的订单结构连续存放，遍历时CPU把一段内存预取到缓存，如果订单结构随机分布，缓存缺失严重，所以订单池必须是连续数组，每个订单结构大小固定,索引就是内存地址偏移。

NUMA 非统一内存访问，多路服务器上，每个CPU有自己的内存控制器，跨NUMA节点访问内存，延迟翻倍，撮合引擎必须绑定到同一个NUMA节点，订单池分配在该节点内存上,线程也绑定到该节点上的核心。

八 写在最后

微秒级撮合引擎不是靠单一技术，是系统级的优化，从数据结构选择，到无锁设计，到内存布局，到分支优化，每个环节都节省几个纳秒，积少成多。内存订单簿是基石，无锁CAS是催化剂，连续内存是血脉，所有微秒级系统的本质是对计算机体系结构的深刻理解：不要依赖操作系统，不要依赖运行时,直接操作硬件。

订单簿不是DB，不是KV store，它是一组精心排布的内存，每次读、写、比较、跳跃，都落在预先设计的轨道上，微秒级匹配不是神话,是工程师对每一比特的掌控。

最后一句：延迟是敌人，但内存是朋友。