当一个 Monorepo 每月要接收超过 65,000 次变更时，“测试通过后合并”已经不再是一条简单规则，而是一个持续运行的调度问题。提交之间可能修改同一文件，构建时间相差数十倍，某个失败任务还可能阻塞整条队列。
Uber 的 SubmitQueue 方案把合并过程视为预测与调度系统：利用二叉推测树提前验证可能的提交组合，通过冲突分析避免明显不兼容的变更进入同一批次，再用机器学习模型预测构建成功率和执行时间。一个尤其值得注意的结果是，将大型 diff 从常规推测路径中分流后，CI 资源消耗下降了 53%，PR 落地主干的速度提高了 37%。
合并队列真正要优化什么
传统合并队列通常按先来先服务处理 PR：取队首变更，在最新主干上运行测试，通过后合并，然后处理下一个。这种方式容易理解，但在高吞吐量仓库中会暴露三个问题：
- 队首阻塞：一个需要数小时验证的大变更会挡住后面几十个小修复。
- 组合失败：两个 PR 单独测试都成功，组合到同一个主干状态后却可能失败。
- 计算浪费：如果队列前部的提交失败，基于该提交推测执行的后续构建可能全部失效。
因此，目标不能只有“让单个 PR 尽快完成”，还要同时考虑：
- 主干在任何可见提交点都保持绿色；
- 单位 CI 资源能够验证更多可落地变更；
- 失败的影响范围可以被快速缩小；
- 大任务不能长期占据关键执行槽位。
这更像一个带约束的任务调度器，而不是简单的 FIFO 队列。
二叉推测树如何缩短等待时间
如果队列中依次有 A、B、C、D 四个变更，串行系统需要等待 A 完成后才知道 B 应该基于哪个主干版本运行。推测执行则可以提前测试若干可能的组合，例如：
main
└── A
├── A+B
│ ├── A+B+C
│ └── A+B+D
└── A+C
这类树并不意味着要无限启动构建。系统需要控制树的深度、并发数和错误推测成本。二叉结构还有一个实用价值：当一个批次失败时，可以把候选变更拆成两半继续验证，用类似二分搜索的方式定位造成失败的变更或组合。
不过，推测越激进，浪费风险也越高。一个高失败概率的 PR 如果被放在树根附近，可能使大量后继节点失效。因此 SubmitQueue 还需要两类输入：
- 冲突分析：识别文件重叠、依赖关系或其他已知的不兼容信号；
- 预测模型：估计构建成功概率与执行时长，辅助决定批次顺序和推测预算。
预测不需要完美才有价值。即使模型只能较稳定地区分“短且大概率成功”和“长且风险较高”的任务，也能改善队列吞吐量。
大型 diff 应分流，而不是跳过验证
“绕过大型 diff”容易被误解为不运行测试。更安全的理解是：不要让大型变更进入面向普通 PR 优化的推测批次，而是给它单独的验证路径和资源配额。
大型 diff 往往具备以下特征：
- 修改文件多，与其他 PR 发生冲突的概率高；
- 测试选择范围大，构建耗时难预测；
- 一旦失败，会让基于它生成的大量推测结果失效；
- 它可能是机械式重构，文件数量很大，但业务风险未必同样高。
把这类变更分流后，普通队列可以继续处理小而独立的 PR，大型变更则在隔离通道中完成完整验证。Uber 分享的数据表明，这一策略使 CI 资源使用下降 53%，同时让 PR 落地时间改善 37%。这说明优化的关键未必是“启动更多构建”，而可能是停止进行高成本、低收益的推测。
可以这样实践：做一个最小调度器
下面的 Python 示例不是 Uber SubmitQueue 的实现，而是一个可运行的简化模型。它展示三条策略：大型 diff 单独分流、文件冲突的 PR 不进入同一批次、其余 PR 按“成功概率 ÷ 预计时长”排序。
将代码保存为 submit_queue.py，再运行 python3 submit_queue.py。实际接入时，需要把示例中的 PR 数据替换为代码托管平台、CI 历史数据和冲突分析服务的输出。
from dataclasses import dataclass
@dataclass(frozen=True)
class PullRequest:
number: int
changed_lines: int
files: frozenset[str]
success_probability: float
predicted_minutes: float
@property
def scheduling_score(self) -> float:
return self.success_probability / max(self.predicted_minutes, 1.0)
def conflicts(left: PullRequest, right: PullRequest) -> bool:
return bool(left.files & right.files)
def plan_queue(prs: list[PullRequest], large_diff_limit: int = 1000):
regular = [pr for pr in prs if pr.changed_lines < large_diff_limit]
isolated = [pr for pr in prs if pr.changed_lines >= large_diff_limit]
regular.sort(key=lambda pr: pr.scheduling_score, reverse=True)
batch: list[PullRequest] = []
deferred: list[PullRequest] = []
for candidate in regular:
if any(conflicts(candidate, selected) for selected in batch):
deferred.append(candidate)
else:
batch.append(candidate)
return batch, deferred, isolated
def main() -> None:
prs = [
PullRequest(101, 40, frozenset({'api/user.py'}), 0.98, 6),
PullRequest(102, 120, frozenset({'web/login.ts'}), 0.91, 12),
PullRequest(103, 35, frozenset({'api/user.py'}), 0.96, 5),
PullRequest(104, 4200, frozenset({'build/deps.lock'}), 0.78, 80),
PullRequest(105, 70, frozenset({'docs/auth.md'}), 0.99, 3),
]
batch, deferred, isolated = plan_queue(prs)
print('Speculative batch:', [pr.number for pr in batch])
print('Deferred by conflict:', [pr.number for pr in deferred])
print('Isolated large diffs:', [pr.number for pr in isolated])
if __name__ == '__main__':
main()
预期输出类似：
Speculative batch: [105, 101, 102]
Deferred by conflict: [103]
Isolated large diffs: [104]
这个示例还没有处理间接依赖、测试不稳定性和多个执行池，但已经可以用于验证策略。下一步可以逐渐加入：
- 从历史 CI 记录计算每个目录的失败率和耗时分位数；
- 把文件重叠升级为构建目标或依赖图冲突；
- 为预测结果设置置信区间，低置信度任务采用保守策略；
- 批次失败后进行二分拆分，而不是逐个重新测试；
- 为普通 PR、大型 diff 和紧急修复分别设置并发配额。
上线时不要只看平均耗时
推测式提交队列会改变 CI 的资源分配方式，落地时应先以影子模式运行：让调度器产生计划，但暂时不影响真实合并顺序，然后比较预测结果与实际结果。
建议至少跟踪以下指标：
- PR 从进入队列到落地主干的 P50、P95 时间；
- 每个成功合并所消耗的 CPU 时间和构建次数；
- 被取消或因祖先失败而失效的推测任务比例；
- 批次失败后定位责任变更所需的时间；
- 大型 diff 的等待时间、成功率和资源占用；
- 主干变红次数以及恢复时间。
机器学习模型也不应拥有最终安全裁决权。它适合决定优先级、批次和推测深度，但是否允许合并仍应由确定性的必需检查、审批规则和分支保护控制。对于多语言 Monorepo，还要避免只按代码行数判断风险：锁文件更新、构建系统变更和跨语言接口修改，可能比普通的大型代码 diff 更值得隔离。
保持主干绿色的核心，不是把所有 PR 都塞进更大的并发池，而是识别哪些组合值得提前验证，哪些冲突应该尽早隔离，以及哪些大型任务不该成为整条队列的根节点。