从FIFO到Pro-Rata：深度解析高性能撮合引擎中的订单分配算法

作者： /

本文旨在为中高级工程师与技术负责人，系统性地拆解在金融交易等高性能场景下，从经典的“价格优先、时间优先”（FIFO）撮合算法，演进到更为复杂的“按比例分配”（Pro-Rata）算法的全过程。我们将深入探讨Pro-Rata算法背后的市场动因、核心原理、数据结构设计、实现细节、性能瓶颈以及架构演进路径，最终目标是让你不仅知其然，更知其所以然，并能将这些知识应用于实际的系统设计中。

现象与问题背景

在绝大多数我们初次接触的交易系统中，撮合引擎（Matching Engine）遵循一个简单而公平的原则：价格优先、时间优先（Price-Time Priority），也就是我们常说的FIFO（First-In, First-Out）。在同一个价格档位上，谁的订单先到，谁就优先成交。这个模型直观、易于实现，并且在许多市场中运行良好。例如，股票市场的连续竞价大多采用此规则。

然而，在某些特定市场，尤其是流动性高度依赖于专业做市商（Market Maker）的衍生品市场（如期货、期权）或部分数字货币市场，纯粹的FIFO机制会暴露出一些问题。做市商通过在买卖双向持续挂出大量订单来提供流动性，他们的收益来自于买卖价差（Spread）。在一个严格的FIFO市场中，做市商的大额、静态的报价单，很容易被高频交易（HFT）的“抢跑”订单（俗称“fast finger”）插队。HFT可以利用其低延迟的系统优势，在做市商报价后，以同样价格下一个极小的订单排在队列最前，从而“窃取”成交机会。这使得做_市商提供流动性的意愿下降，导致市场深度变差、价差扩大，最终损害整个市场的有效性。

为了激励做市商等大型流动性提供者，Pro-Rata（按比例分配）算法应运而生。其核心思想是，在同一价格档位，当一笔吃单（Taker Order）过来时，不再严格按照时间顺序成交，而是按照该档位上所有挂单（Maker Orders）的数量大小，按比例分配成交份额。简单来说，谁的挂单量大，谁就能获得更多的成交量。 这种机制显著地保护了大型流动性提供者的权益，因为他们的巨额挂单确保了他们在成交分配中占据主导地位。

关键原理拆解

在进入实现细节前，我们必须从计算机科学的基础原理出发，理解Pro-Rata算法对系统核心数据结构和算法复杂度的根本性改变。这部分内容，需要我们暂时切换到严谨的“教授”视角。

  • FIFO的算法本质：队列（Queue）

    在FIFO模型中，一个订单簿（Order Book）的某个价格档位（Price Level）在数据结构上可以被抽象为一个双向链表（Doubly Linked List）。当新订单进入时，被添加到链表尾部（Enqueue），时间复杂度为 O(1)。当撮合发生时，从链表头部开始逐个移除订单进行成交（Dequeue），时间复杂度也为 O(1)。整个过程清晰、高效。查询总深度需要遍历，但核心的增、删、撮合操作非常快。

  • Pro-Rata的算法本质：集合与聚合计算

    Pro-Rata打破了严格的队列结构。它不再关心单个订单的先后次序，而是将同一价格档位的所有订单视为一个集合（Set）。撮合时，需要对这个集合进行一次聚合计算。其数学表达为：

    单个订单成交量 = 对手方订单总量 × (该订单数量 / 该价格档位所有订单总数量)

    这个公式揭示了两个关键的计算需求：

    1. 必须能够瞬时获取某价格档位所有订单的总量（TotalVolumeAtPrice）。
    2. 撮合时，需要遍历该价格档位上的所有订单，为每个订单计算其应分配的成交量。

    这就意味着，与FIFO的O(1)头部撮合不同，Pro-Rata的单次撮合操作，其时间复杂度变成了O(N)，其中N是该价格档位上的订单数量。这在订单密集的价格档位上，可能会成为严重的性能瓶颈。

  • 核心挑战：余数处理（The Remainder Problem）

    由于计算机中的整数除法会产生截断，按比例计算出的每个订单的成交量之和，几乎总是小于吃单的总量。例如，一个100手的吃单，分配给三个分别为300手、300手、400手的挂单。总挂单量1000手。按比例分配：

    • 订单1应得: 100 * (300 / 1000) = 30手
    • 订单2应得: 100 * (300 / 1000) = 30手
    • 订单3应得: 100 * (400 / 1000) = 40手

    这个例子很完美。但如果吃单是99手呢？

    • 订单1应得: floor(99 * 0.3) = 29手
    • 订单2应得: floor(99 * 0.3) = 29手
    • 订单3应得: floor(99 * 0.4) = 39手

    总成交 = 29 + 29 + 39 = 97手。还有 99 – 97 = 2 手的余数没有分配。如何公平地分配这2手余数？这是一个必须在算法设计之初就明确的业务规则。常见的余数分配策略有：

    • 时间优先：将余数按照FIFO原则，每次分配1手，分给队列头部的订单。这是最常见的“Pro-Rata + Time”混合模式。
    • 规模优先：将余数分配给挂单量最大的订单。
    • 随机分配：在严肃的金融系统中极少使用，因为其不确定性。

系统架构总览

在深入代码前，我们先拉高视角，看一个典型的低延迟撮合系统架构，Pro-Rata算法正是其核心部分。这套架构追求的是极致的确定性和低延迟，而非高并发。

用文字描述其核心组件流：

  1. 接入网关（Gateway）：负责处理客户端的TCP长连接，通常采用FIX/FAST等二进制协议。网关将协议解析后的业务指令（如下单、撤单）封装成统一的内部事件对象。
  2. 定序器（Sequencer）：这是系统的入口咽喉。所有来自不同网关的事件，都在这里被赋予一个严格递增的全局唯一序号。定序器的存在，保证了整个系统处理事件的顺序是完全确定的，这是状态机复制和系统可恢复性的基石。在实现上，这通常是一个单点的、内存中的组件，例如LMAX Disruptor中的Ring Buffer。
  3. 撮合引擎（Matching Engine）：系统的核心。它是一个单线程的事件循环（Event Loop）。它从定序器消费事件，并严格按顺序处理。单线程的设计是为了彻底避免锁竞争，保证在任何时刻对订单簿的操作都是串行的、无锁的，从而获得极致的性能和确定性。我们的Pro-Rata算法就实现在这个线程内部。
  4. 行情与回报总线（Market Data & Execution Report Bus）：撮合引擎处理完一个事件后，会产生输出，如成交回报（Fill）、订单确认（Ack）、行情快照更新（Snapshot Update）等。这些输出被发布到内部总线上。
  5. 下游服务：例如行情发布服务、清结算服务、风控服务等，它们订阅总线上的消息，并将信息推送给用户或进行后续处理。

这个架构的核心在于，通过“单线程处理核心逻辑”的方式，将一个复杂的并发问题，转化为一个简单的单线程队列消费问题，从而在内核态与用户态切换、线程上下文切换、锁竞争等开销上做到最小化。

核心模块设计与实现

现在，让我们戴上“极客工程师”的帽子，直接看代码和实现中的坑点。

数据结构设计

要高效实现Pro-Rata，数据结构是关键。下面是一个简化的Go语言示例，展示订单簿的核心结构。


// Order 代表一个订单
type Order struct {
	ID        uint64
	Price     int64  // 使用int64避免浮点数精度问题，例如 Price=10005 代表 100.05
	Size      int64  // 订单数量
	Side      Side   // BUY or SELL
	Timestamp int64  // 纳秒级时间戳，用于余数分配
	// ... 其他字段
}

// PriceLevel 代表一个价格档位
type PriceLevel struct {
	TotalVolume int64              // 该价格档位总订单量，必须O(1)更新
	Orders      map[uint64]*Order  // 使用map方便O(1)按ID查找和删除
	OrderQueue  *list.List         // 使用双向链表维护订单的时间顺序，用于余数分配
}

// OrderBook 撮合引擎的核心
type OrderBook struct {
	Bids *treemap.Map // 使用红黑树或跳表等有序结构存储买单，Key: Price, Value: *PriceLevel
	Asks *treemap.Map // 存储卖单
}

// PriceLevel的辅助方法
func (pl *PriceLevel) AddOrder(order *Order) {
	pl.TotalVolume += order.Size
	pl.Orders[order.ID] = order
	pl.OrderQueue.PushBack(order.ID) // 仅存储ID以节省空间
}

func (pl *PriceLevel) RemoveOrder(order *Order) {
	// ... 在map和list中移除订单，并更新TotalVolume ...
	// 细节：在链表中找到并删除一个元素是O(N)，需要优化。
	// 优化：在map中存订单指针的同时，也存其在链表中的*list.Element指针，实现O(1)删除。
}

工程坑点：

  • 价格和数量的类型：绝对不能使用浮点数（float64）。金融计算中的任何舍入误差都是灾难性的。必须使用定点数，通常是乘以一个固定的精度（如10^8）后用int64或decimal库来存储。

    • – PriceLevel的实现：上面示例中，同时用了map和list.List。map用于O(1)的按ID撤单，list.List用于维护时间顺序。这是典型的用空间换时间。为了实现O(1)的链表元素删除，map中应该存储一个包含订单指针和其在list.List中对应*list.Element指针的结构体。

  • TotalVolume的维护：每次新增、取消、修改订单时，都必须同步更新PriceLevel中的TotalVolume字段。这个操作必须是原子的，并且是核心逻辑的一部分，忘记更新会导致灾难性的撮合错误。

Pro-Rata撮合核心逻辑

下面是撮合函数的核心伪代码，我们选择“余数按时间优先”的策略。


func (ob *OrderBook) MatchProRata(takerOrder *Order) {
	// ... 根据takerOrder的Side，选择Bids或Asks进行撮合 ...
	
	for takerOrder.Size > 0 {
		// 1. 找到最佳价格档位 (bestPriceLevel)
		bestPriceLevel := ob.getBestPriceLevel(takerOrder.Side)
		if bestPriceLevel == nil {
			break // 没有可撮合的对手盘
		}

		// 2. 价格检查
		if !isPriceMatch(takerOrder.Price, bestPriceLevel.Price) {
			break // 价格不匹配
		}
		
		matchableSize := min(takerOrder.Size, bestPriceLevel.TotalVolume)
		if matchableSize == 0 {
			// 理论上不应该发生，但做好防御
			continue
		}

		// 3. 按比例计算（第一轮分配）
		var totalFilled int64 = 0
		makerOrders := bestPriceLevel.OrderQueue // 假设OrderQueue存的是*Order
		
		// 必须先拷贝一份进行计算，防止遍历时修改集合
		ordersToMatch := make([]*Order, 0, len(makerOrders))
		for e := makerOrders.Front(); e != nil; e = e.Next() {
			ordersToMatch = append(ordersToMatch, e.Value.(*Order))
		}

		for _, makerOrder := range ordersToMatch {
			// 使用高精度计算，避免过早的精度损失
			fillSize := (matchableSize * makerOrder.Size) / bestPriceLevel.TotalVolume
			if fillSize > 0 {
				executeMatch(takerOrder, makerOrder, fillSize) // 执行撮合，更新订单状态，生成成交回报
				totalFilled += fillSize
			}
		}

		// 4. 处理余数（第二轮分配）
		remainder := matchableSize - totalFilled
		if remainder > 0 {
			// 从链表头部开始，按时间优先分配余数
			for e := makerOrders.Front(); e != nil && remainder > 0; e = e.Next() {
				makerOrder := e.Value.(*Order)
				if makerOrder.Size > 0 { // 确保订单还有余量
					fillSize := int64(1)
					executeMatch(takerOrder, makerOrder, fillSize)
					remainder--
				}
			}
		}
		
		// 5. 更新takerOrder剩余数量，并继续循环或将剩余部分转为挂单
		takerOrder.Size -= matchableSize
	}

	if takerOrder.Size > 0 {
		ob.AddOrder(takerOrder) // Taker订单未完全成交，转为Maker单
	}
}

工程坑点：

  • 整数除法陷阱：在(matchableSize * makerOrder.Size) / bestPriceLevel.TotalVolume这个核心计算中，要小心整型溢出。matchableSize * makerOrder.Size可能会超过int64的范围。在实际生产代码中，可能需要使用128位整数（如C++的__int128_t）或大数库进行这个中间计算。
  • 遍历时修改：在遍历PriceLevel的订单列表进行撮合时，不能直接在循环中删除或修改被遍历的集合。正确的做法是先记录下需要成交的信息，循环结束后再统一进行状态变更，或者像伪代码中那样，先拷贝一份进行遍历计算。
  • 性能：当一个价格档位有成千上万个小订单时，O(N)的遍历开销会非常显著。每一次大额吃单都会导致一次CPU密集型计算，这会直接影响到整个系统的吞吐量和延迟。

性能优化与高可用设计

性能对抗与优化

Pro-Rata的O(N)复杂度是其天生的性能瓶颈，我们的优化也主要围绕于此。

  • CPU Cache 友好性：在C++/Rust等语言中，std::list或std::map的节点在内存中是散乱分布的。遍历它们会导致大量的Cache Miss。对于性能要求极致的场景，可以考虑使用连续内存的数据结构，例如将所有订单存放在一个巨大的数组（或内存池）中，PriceLevel里只存储索引。这样遍历时，数据在内存中是连续的，可以充分利用CPU的预取机制，提升缓存命中率。
  • 指令级并行：Pro-Rata的比例计算循环，在某种程度上可以利用SIMD（单指令多数据流）指令进行优化。虽然逻辑分支较多，但在特定硬件和编译器支持下，对一批订单进行计算仍有优化空间，但这属于非常底层的优化。
  • 业务规则简化：与业务方讨论，是否可以引入一个阈值。例如，小于某个数量的订单不参与Pro-Rata计算，直接按FIFO处理。或者引入“订单合并”功能，允许做市商将多个小订单合并为一个大订单，减少N的数量。

高可用设计

撮合引擎作为金融系统的核心，其可用性至关重要。

  • 主备复制（State Machine Replication）：如架构总览所述，撮合引擎是确定性的状态机。最经典的高可用方案是“主备”模式。主引擎处理所有请求，同时将经过定序器编码的指令流（Input Log）实时、同步地发送给备用引擎。备用引擎在内存中应用完全相同的指令流，从而保持与主引擎完全一致的内存状态（订单簿的每一个细节）。

    • – 故障切换（Failover）：当监控系统检测到主引擎故障（如心跳超时），会触发切换流程。网关将新的流量切换到备用引擎，备用引擎“晋升”为主。由于备用引擎的状态与主引擎完全一致，切换过程可以非常快，理想情况下对用户是无感知的。这个切换的协调通常需要一个独立的、高可用的组件，如基于ZooKeeper或etcd实现的分布式锁/领导者选举模块。

    – 数据持久化与恢复：为了防止主备同时宕机等极端灾难，需要对状态和指令流进行持久化。可以定期对内存中的订单簿状态做快照（Snapshot），并持续记录指令流日志。系统重启时，先加载最近的快照，然后重放（Replay）快照点之后的所有指令，即可恢复到宕机前的状态。

架构演进与落地路径

一个复杂的系统不是一蹴而就的。对于撮合算法的演进，我们建议采用分阶段的策略。

  1. 阶段一：实现健壮的FIFO引擎。作为起点，先构建一个功能完备、经过充分测试的Price-Time Priority撮合引擎。这是所有交易系统的基础，也是后续演进的基石。在这个阶段，重点是打磨好底层架构，包括网关、定序器、单线程模型和高可用框架。
  2. 阶段二：引入纯Pro-Rata能力。当业务发展需要时，在现有架构上增加Pro-Rata的逻辑。这通常意味着需要重构PriceLevel的数据结构和撮合函数。可以先在模拟环境中或针对特定交易对上线，收集性能数据，验证其对市场流动性的影响。
  3. 阶段三：实现混合模式（Hybrid Model）。根据市场的反馈，纯Pro-Rata可能过于偏向大玩家。此时可以引入更精细的混合模型。例如，芝加哥商业交易所（CME）就使用过多种复杂的混合算法。一种常见的模式是：
    • FIFO + Pro-Rata：一笔吃单过来，先按FIFO规则成交一定数量或比例（例如前10%），剩余部分再按Pro-Rata分配。这种方式兼顾了小订单的公平性和大订单的激励。
  4. 阶段四：引入权重（Weighted Pro-Rata）。这是更进一步的演进，为不同的做市商或账户设置不同的权重。算法公式变为：
    成交量 ∝ 订单数量 × 权重。
    权重可以根据做市商的等级、历史贡献度等动态或静态配置。这使得撮合规则成为一种精细化的运营工具，但同时也极大地增加了系统的复杂性，需要审慎评估。

最终，选择何种算法，并非一个纯粹的技术决策，而是技术、业务和市场博弈的综合结果。作为架构师和工程师，我们的职责是理解每种算法的原理、利弊和实现代价，为业务决策提供清晰、可靠的技术输入，并最终构建出稳定、高效且公平的交易系统。

延伸阅读与相关资源

  • 想系统性规划股票、期货、外汇或数字币等多资产的交易系统建设，可以参考我们的
    交易系统整体解决方案。
  • 如果你正在评估撮合引擎、风控系统、清结算、账户体系等模块的落地方式，可以浏览
    产品与服务
    中关于交易系统搭建与定制开发的介绍。
  • 需要针对现有架构做评估、重构或从零规划，可以通过
    联系我们
    和架构顾问沟通细节，获取定制化的技术方案建议。
滚动至顶部