使用机器学习更有效地测试Firefox

浏览器是一款极其复杂的软件。面对如此巨大的复杂性，保持快速开发速度的唯一方法是通过一个广泛的CI系统，该系统可以让开发人员相信他们的更改不会引入错误。考虑到我们CI的规模，我们一直在寻找在保持高标准产品质量的同时减轻负荷的方法。我们想知道是否可以使用机器学习来达到更高的效率。

在Mozilla，我们有大约50,000个独特的测试文件。每个测试函数都包含许多测试函数。这些测试需要在我们所有支持的平台(Windows、Mac、Linux、Android)上针对各种构建配置(PGO、DEBUG、ASAN等)以及一系列运行时参数(站点隔离、WebRender、多进程等)运行。

虽然我们不会针对上述所有可能的组合进行测试，但我们仍会针对90多种独特的配置进行测试。换句话说，对于开发人员推送到存储库的每个更改，我们可能会运行全部50k测试90次不同的次数。在平均工作日，我们看到近300个推送(包括我们的测试分支机构)。如果我们在每次推送时简单地在每个配置上运行每个测试，那么我们每天将运行大约13.5亿个测试文件！虽然我们在某种程度上确实在这个问题上投入了资金，但作为一个独立的非营利性组织，我们的预算是有限的。

那么，我们如何保持CI负载可管理呢？首先，我们认识到，在这90种独特的配置中，有一些比其他配置更重要。许多不太重要的测试只运行一小部分测试，或者每天只运行几次推送，或者两者兼而有之。其次，在我们的测试分支的情况下，我们依赖我们的开发人员来指定哪些配置和测试与他们的更改最相关。第三，我们使用集成分支。

基本上，当补丁被推送到集成分支时，我们只对其运行一小部分测试。然后，我们定期运行所有内容，并雇佣代码警长来确定是否遗漏了任何回归。如果是这样的话，他们就会退出令人不快的补丁。一旦一切正常，集成分支就会定期合并到主分支。

我们在单个Mozilla中心推送上运行的任务子集。当缩放到适合一张图像时，整个任务集太难区分了。

这些方法多年来一直很好地服务于我们，但事实证明它们仍然非常昂贵。即使有了所有这些优化，我们的CI仍然每天运行大约10个计算年限！部分问题在于，我们一直在使用天真的启发式方法来选择在集成分支上运行哪些任务。启发式根据任务在过去失败的频率对任务进行排序。排名与补丁的内容无关。因此，修改自述文件的推送将运行与打开站点隔离的推送相同的任务。此外，确定在测试分支上运行哪些测试和配置的责任已经转移到开发人员自己身上。这浪费了他们宝贵的时间，并倾向于过度选择考试。

大约一年前，我们开始问自己：我们怎样才能做得更好？我们意识到，目前我们的CI的实施在很大程度上依赖于人的干预。如果我们可以使用历史回归数据将补丁与测试关联起来，会怎么样？我们可以使用机器学习算法来计算出要运行的最佳测试集吗？我们假设我们可以同时通过运行更少的测试来节省资金，更快地得到结果，并减轻开发人员的认知负担。在这个过程中，我们将建设必要的基础设施，以保持我们的CI管道高效运行。

基于机器学习的解决方案的主要前提是收集足够大且足够精确的回归数据集。从表面上看，这似乎很容易。我们已经将所有测试执行的状态存储在一个名为ActiveData的数据仓库中。但在现实中，这是很难做到的，原因如下。

因为我们只对任何给定的推送运行测试的子集(然后定期运行所有测试)，所以当引入回归时并不总是显而易见的。请考虑以下场景：

很容易看出，“测试A”失败被补丁2退回了，因为这是它第一次开始失败的地方。然而，由于“测试B”失败，我们不能真正确定。它是由补丁2还是补丁3引起的？现在假设在最后一次通过和第一次失败之间有8个补丁。这增加了很多不确定性！

间歇性(也称为薄片)故障也使收集回归数据变得困难。有时，由于各种不同的原因，同一代码库上的测试既可能通过，也可能失败。事实证明，我们最终不能确定补丁2倒退了上表中的“测试A”！这就是说，除非我们将失败重复足够多的次数，以便在统计上有信心。更糟糕的是，补丁本身可能在一开始就导致间歇性故障。我们不能仅仅因为一次失败是间歇性的就认为它不是一次倒退。

为了解决这些问题，我们建立了一套相当大而复杂的启发式算法来预测哪些回归是由哪个补丁引起的。例如，如果补丁程序稍后被回退，我们将检查回退推送的测试状态。如果它们仍然失败，我们可以非常确定失败不是由于补丁造成的。相反，如果他们开始通过，我们可以非常确定补丁是有问题的。

有些故障是按人类分类的。这对我们是有利的。代码警长的部分工作是注释故障(例如，对于稍后修复的故障，“间歇性”或“通过提交修复”)。面对缺失或间歇性的测试，这些分类对查找回归有很大帮助。不幸的是，由于大量的补丁和故障不断发生，无法达到100%的准确性。所以我们甚至有启发式方法来评估分类的准确性！

处理丢失数据的另一个技巧是回填丢失的测试。我们选择在最初没有运行的旧推送上运行测试，目的是找出哪个推送导致了回归。目前，警长们都是手工完成这项工作。然而，有计划在未来的某些情况下将其自动化。

我们还需要收集有关补丁本身的数据，包括修改的文件和差异。这允许我们与测试失败数据相关联。通过这种方式，机器学习模型可以确定对于给定补丁最有可能失败的测试集。

收集有关补丁的数据要容易得多，因为它完全是确定性的。我们遍历Mercurial存储库中的所有提交，使用rust-parsepatch项目解析补丁，并使用rust-code分析项目分析源代码。

现在我们已经有了补丁和相关测试(包括通过和失败)的数据集，我们可以构建一个训练集和一个验证集来教我们的机器如何为我们选择测试。

90%的数据集用作训练集，10%用作验证集。拆分必须仔细进行。验证集中的所有补丁必须在训练集中的补丁之后。如果我们随机拆分，我们会将来自未来的信息泄露到训练集，导致结果模型有偏差，并人为地使其结果看起来比实际情况更好。

例如，考虑一项直到上周才失败的测试，自那以后已经失败了几次。如果我们用随机挑选的训练集训练模型，我们可能会发现自己处于这样的情况：训练集中有几个失败，验证集中也有几个失败。该模型可能能够正确地预测验证集中的故障，因为它在训练集中看到了一些示例。

然而，在现实世界中，我们不能展望未来。模型不能知道下周会发生什么，但只能知道到目前为止发生了什么。为了正确评估，我们需要假装我们是在过去，并且未来的数据(相对于训练集)必须是不可访问的。

我们使用来自测试、补丁和它们之间的链接的特性来训练XGBoost模型，例如：

在过去，当相同的文件被触摸时，此测试失败的频率是多少？

在VCS历史记录中，源文件与测试文件一起修改的频率是多少？

模型的输入是一个元组(测试、补丁)，标签是二进制FAIL或NOT FAIL。这意味着我们有一个能够处理所有测试的单一模型。此体系结构允许我们以一种简单的方式利用测试选择决策之间的共性。正常的多标签模型，其中每个测试都是一个完全独立的标签，将不能推断关于给定测试的信息并将其应用于另一个完全不相关的测试。

考虑到我们有数以万计的测试，即使我们的模型是99.9%准确的(这是相当准确的，每1000次评估只有一个错误)，我们仍然会在几乎每个补丁中犯错误！幸运的是，在我们的领域中，与假阳性(由模型为给定补丁选择的测试，但不会失败)相关的成本并不像我们试图识别人脸以用于警务目的那样高。我们付出的唯一代价就是做一些无用的测试。同时，我们避免了运营数百家这样的公司，因此最终的结果是节省了大量资金！

随着开发人员定期切换他们在数据集上所做的工作，我们所训练的数据集也在不断演变。因此，我们目前每两周对模型进行一次重新培训。

在我们选择了要运行的测试之后，我们可以通过选择测试应该运行的位置来进一步改进选择。换句话说，它们应该运行的配置集。我们使用收集到的数据集来识别任何给定测试的冗余配置。例如，是否真的值得同时在Windows 7和Windows 10上运行测试？为了识别这些冗余，我们使用类似于频繁项集挖掘的解决方案：

计算“支持”为X和Y都失败的推送次数，超过它们都运行的推送次数。

计算“置信度”为X和Y都失败的推送次数，超过它们都运行且两个中只有一个失败的推送次数。

我们只选择支持率高(低支持率意味着我们没有足够的证据)且置信度高(低置信度意味着我们有很多不适用冗余的情况)的配置组。

一旦我们有了要运行的测试集、关于它们的结果是否依赖于配置的信息，以及要运行它们的一组机器(及其相关成本)，我们就可以用混合整数规划求解器来制定数学优化问题。这样，我们可以很容易地改变我们想要达到的优化目标，而不会对优化算法进行侵入性的改变。目前，优化目标是选择最便宜的配置来运行测试。

机器学习模型的用处取决于消费者使用它的能力。为此，我们决定在Heroku上托管一个服务，使用专用的worker dynos服务请求，使用Redis队列在后端和前端之间架起桥梁。前端公开了一个简单的REST API，因此消费者只需指定他们感兴趣的推送(由分支和最高版本标识)。后端将使用Mozilla-Central的克隆自动确定更改的文件及其内容。

根据推送的大小和要分析的队列中的推送数量，服务可能需要几分钟来计算结果。因此，我们确保对于任何给定的推送，我们永远不会排队超过一个作业。一旦计算出结果，我们就会将其缓存。这允许消费者异步启动查询，并定期轮询以查看结果是否已准备好。

我们目前在集成分支上调度任务时使用该服务。当开发人员运行特殊的mach try auto命令在测试分支上测试他们的更改时，也会使用它。将来，我们还可能使用它来确定开发人员应该在本地运行哪些测试。

从这个项目一开始，我们就觉得能够运行和比较实验，衡量我们的成功，并相信对我们算法的更改实际上是对现状的改进，这一点至关重要。在调度算法中，我们实际上关心两个变量：

回归检测率。也就是说，直接在导致它们的推送中捕获的引入回归的百分比。换句话说，我们不必依赖人来填补失败，找出哪个推送是罪魁祸首。

该度量越高，调度算法越有效。既然我们有了指标，我们就发明了“影子调度器”的概念。影子调度程序是在每次推送时运行的任务，它会影子实际的调度算法。只是它们不是实际安排事情，而是输出如果它们是默认的话它们会安排的内容。每个映像调度程序可能会稍微不同地解释我们的机器学习服务返回的数据。或者，他们可以在机器学习模型推荐的基础上运行额外的优化。

最后，我们编写了一个ETL来查询所有这些影子调度器的结果，计算每个影子调度器的效率度量，并将它们全部绘制在仪表板中。目前，我们正在监控和微调大约12个不同的映像调度程序，以找到可能的最佳结果。一旦我们确定了获胜者，我们就将其作为默认算法。然后我们重新开始这个过程，创造更多的实验。

这个项目的初步成果非常有希望。与我们以前的解决方案相比，我们的集成分支上的测试任务数量减少了70%！与没有测试选择的CI系统相比，几乎减少了99%！我们还看到我们的mach try自动工具被采用得相当快，这表明可用性得到了改善(因为开发人员不再需要考虑选择什么)。但是还有很长的路要走！

我们需要提高模型选择配置和默认配置的能力。我们的回归检测启发式算法和我们的数据集的质量需要改进。我们还没有实现可用性和稳定性修复，以mach try auto。

虽然我们不能做出任何承诺，但我们愿意以一种对Mozilla以外的组织有用的方式打包模型和服务。目前，这项工作是一个更大的项目的一部分，该项目包含最初为帮助管理Mozilla的Bugzilla实例而创建的其他机器学习基础设施。敬请关注！

如果您想了解更多关于这个项目或Firefox的CI系统的信息，请随时访问我们的Matrix频道，#Firefox-ci：mozilla.org。