新的 Maven 依赖解析算法

介绍

Maven 在 eBay 被广泛用作 Java 项目构建工具。作为 Maven 的重要组成部分， 行家解决 解析声明的依赖关系，计算依赖图，调解冲突并形成编译和部署的类路径。这就是所谓的依赖解析过程。

软件开发快速迭代的主要障碍之一是构建时间过长。作为 eBay 对速度和构建改进的承诺的一部分，我们开发了一个名为 Zeus 的 Maven 扩展，旨在收集和可视化 Kibana 报告中的 Maven 构建数据。我们惊讶地发现，在解析复杂的依赖项时，Maven 解析器存在严重的性能瓶颈。在这种情况下，Maven 依赖项解析可能要为大多数构建时间负责，从而降低开发效率。

为了加快速度，我们实施了一种新算法：BF（广度优先遍历）和 Skipper（跳过不必要的依赖解析），这有助于将 eBay 大型 Java 应用程序的纯构建时间缩短 30% 到 70%！借助此算法，无论依赖关系图有多复杂，Maven 都可以突破瓶颈，在最短的时间内以最少的计算完成依赖解析。

问题分析

注意：本文提到的测试数据基于纯构建，相当于在本地存储库已完全填充时运行的 Maven 构建（mvn clean install -DskipTests）。它不涉及下载任何 Maven 工件或测试执行。

Maven 构建由 4 个部分组成：依赖项下载、依赖项解析、插件执行和测试执行。依赖项解析时间与运行 mvn dependency:tree 的总时间差不多。

从 Zeus 收集的构建数据中，我们知道 eBay 的一些项目在依赖项解析步骤中遇到了严重的缓慢（5 到 10 分钟）。特别残酷的例子可能需要 30 分钟以上和 20GB 内存才能打印出依赖项树。这种延迟显然是不可接受的，但要解决这个问题，我们首先需要知道 Maven 如何解析依赖项。

Maven 依赖解析

Maven 依赖项默认为编译范围，它会递归传播所有子依赖项。

上图显示了 X 依赖项及其传递依赖项。Maven 将按如下方式解析依赖项：

• 为了调解冲突，Maven 采用了树深度最近的传递依赖和解决率第一的方法。最终获胜者是紫色 Z 2.0，因为它最接近根；黄色 Z 2.0 节点是重复冲突失败者，棕色 Z 1.0 是版本冲突失败者。

通过运行 mvn dependency:tree -dverbose ，Maven 会针对每个传递依赖项指出它被省略的原因，并从下列冲突中选择一个：

随着 eBay 业务的增长，实现各种功能时会用到越来越多的依赖，传递依赖也会呈几何级数增长，最终的依赖图会非常复杂，并带来大量冲突。解决冲突的方法有两种：

Maven 推荐前者，但实际上后者更易于用户理解，使用也更为广泛。如此广泛地使用排除可能会导致以下性能问题。

7500 万个内存节点 vs 1500 多个最终依赖项

以下图中最慢的项目为例，当 Maven 尝试构建项目的依赖关系树时，在内存中创建了大约 7500 万个节点。

7500 万个节点表明，在企业级项目中，依赖关系图可能非常复杂。尽管如此，依赖关系树输出中仅保留了 1500 个左右的依赖关系。

因此，我们可以得出，这些节点大部分都是冲突节点，在冲突调解后会被截断，不会出现在依赖关系树中。然而，这些节点的计算是不可避免的，这会导致严重的性能问题。

为了找到根本原因，我们运行了 mvnDebug dependency:tree 并将 Maven 源代码导入 IDE 进行远程调试。在调试过程中，我们发现由于以下行为创建了 7500 万个节点：

如果必须遍历所有节点的全路径，那我们想，有没有像GAV一样，通过key来保存解析结果的缓存，以便Maven可以重用，加快解析速度？

答案是肯定的。但通过检查 行家解决，我们知道Maven使用的缓存键非常复杂，并且排除（下面的DependencySelector）也是键的一部分。

在 Maven 的世界里，排除是可以继承的。Maven 需要追溯所有父节点定义的排除，这意味着当树上的排除不同时，同一个工件的缓存解析结果不会被重用，需要重复计算。我们认为这是 Maven 依赖解析的致命弱点。

排除问题——Maven 解析器缓存的致命弱点

在上图中：

• 在左侧，B 和 C 都依赖于 D，并且 D 及其子项只会在缓存命中时被解析一次。

• 在右侧，B 未定义任何排除项，而 C 排除了 F。由于排除项不同，D 及其子节点 E 将被解析两次。想象一下，如果 D 是一个重度依赖项，可能会引入许多传递依赖项。在这种情况下，D 的所有子节点都需要重新计算！

此处的排除对缓存命中率起着决定性的作用。许多冲突节点可能需要重新计算，因为从所有父节点继承的排除通常不同。这导致：

回到上面的项目！由于依赖关系图太复杂，难以理解，开发人员必须广泛使用排除来消除冲突，以解决各种运行时异常。但这会导致持续的缓存未命中。Maven 不得不浪费大量的构建时间来解析这些不必要的节点。

算法实现：BF+Skipper

要解决解析缓慢的问题，关键是避免不必要的计算。我们可以在父 POM 中管理传递依赖版本和排除项，以确保相同的依赖项始终具有相同的排除项。这样的更改确实可以显著提高构建性能，但通常包括相当多的依赖项更改，这些更改容易出错，并且需要不必要的测试。

eBay 几十年来一直致力于开源贡献。本着这种精神，我们决定修改 行家解决因为我们今天面临的依赖关系解决缓慢并不是 eBay 独有的，而是所有开发企业应用程序的 Maven 用户的共同问题。

前面提到过，maven-resolver 负责计算项目编译部署所需的最终依赖项，任何对该组件的错误修改都会导致使用 M​​aven 的任何项目编译或部署失败。

因此，在考虑“新算法”时，首要考虑的当然是性能，但也要考虑 100% 的兼容性。罗马不是一天建成的，实现这样的算法需要多次尝试和验证。本文将展示最终的实现：BF + Skipper。

如下图所示：

• 为了实现 100% 兼容性，新算法不会触及 Maven 的冲突调解部分。

• 为了实现更好的性能，我们将全路径遍历转换为选择性遍历，以避免对大量冲突节点进行不必要的计算。依赖图因此可以大大简化，同时仍能得到一致的依赖树输出。

主要流程如下：

• 将 Maven 依赖解析策略从 DF 转换为 BF。

• 通过预测当前正在解决的节点是否属于以下冲突之一来跳过某些节点的解决：

• 如果该节点属于版本冲突，则直接跳过解决。

• 如果节点属于重复冲突，则确定是否需要保留冲突路径以与冲突调解算法兼容。如果是，则强制解决，否则跳过解决。

为了容易理解这一点，让我们比较一下这两种方法：

BF：预测冲突

Maven 按照 DF 算法遍历所有依赖节点，然后按照距离根节点的顺序和深度进行冲突调解。BF 算法是从上到下、从左到右遍历节点，与 Maven 调解冲突的顺序完全一致。

也就是说，在BF算法中，对于任何具有相同GA（groupId+artifactId）的节点，最先被解决的永远是赢家，而后被解决的必定是冲突输家。

通过将遍历策略从 DF 改为 BF，我们可以预测当前节点是重复冲突还是版本冲突，并通过检查具有相同 GA 的节点是否已解决来有选择地跳过。

Skipper：避免不必要地解决冲突节点

为了避免不必要地解析冲突节点，我们创建了一个 skipper。Skipper 可以根据以下原则在当前已解析的节点中进行匹配，判断当前节点是否可以被跳过：

• 如果已经解析了具有相同 GAV（GroupId + ArtifactId + Version）的节点，则当前节点一定是重复的，可能会被跳过。

• 如果具有相同GA的节点已经被解析，而当前节点的版本不同，那么当前节点一定是版本冲突，可以安全地忽略。

跳过版本冲突节点的解决

在上图中：

• 紫色 D:1（版本为：1、#4 的 D）位于树的深度 2 中，D:1 已经是赢家。

• 当解析 D:2（D 的版本为 2，#5）时，D:2 与 D:1 的版本不同，并且必须是冲突失败者，则可以安全地跳过 D:2 及其所有子项。

跳过重复节点的解析

为了比较树节点的深度和顺序，我们需要在解析之前计算当前节点的坐标。图中的坐标 2,2 代表树中的第 2 个深度和给定深度中的第 2 个节点。

在上图中：

• 紫色 R#3 在树的深度 2 处得到解决，这已经是赢家。

• 蓝色 R#5 是 R#3 的重复。R#5 位于 (3,1)，位于 R#3 (2,2) 的左侧；这意味着在根节点 A 的 POM 中，R#5 的父节点（深度 2 中的 B#2）在 R#3 之前声明。在这种情况下，我们必须强制解析 R#5。

• 由于 R#3 已经是赢家，棕色的 R#8 和 R#11 是冲突输家，它们都位于最近强制解决的蓝色 R#5 的右侧。在这种情况下，可以跳过 R#8、R#11 及其子节点（棕色虚线的 S 节点）。

强制解决特定重复节点

这个算法的初始实现并没有涉及到上述的强制解析逻辑，在超过 500 个 eBay 应用程序的测试中准确率达到了 99%，这对于第一次尝试来说已经是一个非常成功的结果了。

最后 1% 的失败案例多种多样，可能包括错误的依赖范围（编译、运行时、提供等等）选择。解决 1% 的不兼容性是实现零失败率的最大障碍，需要深入了解 Maven 的冲突调解算法。我们面临的选择是：

方法一：针对每个故障情况分别处理。

方法二：适应两种算法在冲突调解方面的差异。

我们选择后者，因为前一种方法可能会使代码逻辑复杂化，并会在测试期间遗漏一些未发现的情况。

深入研究了Maven的冲突调解算法后，我们最终找到了问题所在：原DF实现中用于冲突调解的重复节点冲突路径数量比我们的BF方案中要多，这是因为我们跳过了大量节点计算，从而遗漏了一些同样用于冲突调解的辅助冲突路径。

Maven 的 DF 策略

左侧，Maven按照1-12的顺序，以深度优先的策略解析节点，所有R节点的解析顺序为：

在这个过程中，一共选出了3次胜利者：R#4 -> R#5 -> R#8。虽然R#8是最终的胜利者，但是Maven仍然把所有临时胜利者（R#4，R#5）的路径算作冲突调解的辅助路径。下面是最终参与调解的冲突路径：

• A->B->D->R

• A->B->R

• A -> R

我们的策略：BF + Skipper

右侧，Maven 按广度优先策略按照 1-12 的顺序解析节点。

如果不进行强制解决，第一个被解决的 R 节点是 R#3，这已经是最终的赢家。所有后续的 R 节点都被跳过，这意味着只有一条路径：A -> R，用于调解冲突。

通过强制解决，流程如下：

• 首先解决 R#3，它已经是赢家。

• 然后是R#6，R#6在R#3的左边，需要强制解析。

• 然后是 R#8，与最后强制解析的 R#6 相比，R#8 位于右侧，但与 R#3 冲突，因此跳过。

• 同样，R#10 需要进行强制解析，因为它位于最后一个强制解析的 R#6 的左侧。

• R#11 和 R#12 位于最后一个强制解析的 R#10 的右侧，可以跳过

这样冲突路径如下：

• A -> R

• A->B->R

• A->B->D->R

这里所有冲突的路径都被保留，尽管顺序相反，并且最后 1％ 的不兼容性通过这种方法解决。

结论

这个算法是 Zeus 的一个功能，几个月前 eBay 的大多数 Java 应用都启用了这个算法。由于这个改动是在 Maven 核心上进行的，而 Maven 核心对 Maven 构建的结果至关重要，因此我们在发布之前通过测试 2,000 到 3,000 个 Java 应用来验证这个解决方案，并使用自动化方法比较两种算法之间的依赖关系树。如此大量的应用提供了多种多样的 Maven 依赖使用场景，有助于我们保证这个算法的准确性和有效性。

现在这个算法已经在 eBay 被广泛采用，我们决定将其回馈给 Apache Maven 社区。我们与社区密切合作，不断重构代码、改进测试用例，最终 PR 在 2022 年 5 月被正式接受并纳入 maven-resolver (v1.8.0)。

发布后不久，阿里集团的工程师试用后反馈非常积极。以下是他们分享的评论：

该算法主要解决了依赖解析缓慢的问题，但依赖下载部分却很慢。Maven 天生就是按顺序下载 POM 的，当依赖项在本地缓存中不可用时，这会导致构建时间过长。为了解决这种下载缓慢的问题，我们继续致力于第二个贡献：在 BF 算法之上并行化依赖收集器，它将并行下载所有依赖项的 POM。社区已经接受了我们的更改并将其发布到 maven 解析器 (v1.9.x) 。

并行化的 Maven 依赖收集器与 BF 和 Skipper 的结合现在使 BF 算法成为实现快速而一致的 Maven 构建的最合适选择。2023 年 2 月发布的 Maven 3.9.0 已经提供了这两项贡献，您可以在官方产品页面找到简要介绍：

该算法源自 eBay 的大量 Maven 构建调优实践。我们收集并可视化数据，找出瓶颈，实施并验证算法，将我们的修复应用于数千个 eBay 应用程序，然后回馈社会。尽管开源之路充满障碍，但结果是值得的，充满希望的。eBay 应用程序框架团队为此方法的诞生投入了大量时间，值得称赞！这些实践体现了 eBay 人的开源精神：我们从社区获取，回馈社区。