1
缘 起
Maven作为程序员所熟悉的构建工具，在eBay内部同样被广泛使用。maven-resolver 是Maven的核心组件。它将项目声明的所有依赖 (dependency) 予以解析，算得依赖图 (dependency graph) 并调解冲突，最终整合成项目编译和部署所需的classpath，这个过程叫依赖解析 (dependency resolution)。在eBay开展的Build Velocity项目实践中，通过对Maven Build数据进行分解和可视化分析，我们惊讶地发现maven-resolver在解析复杂依赖时存在严重的性能瓶颈。
为突破瓶颈并加速Maven Build，我们对maven-resolver的依赖解析算法作了大幅改造，并实现了一个全新的算法：BF (广度优先遍历) + Skipper。其意义是Maven可以无视依赖图的复杂度，甚至有大量循环依赖的情况下，可通过最小运算量计算出项目所需的最终依赖项。经测试，该算法可以让依赖比较复杂的项目的纯build时间缩短30-70%！
目前该算法已被Apache Maven社区正式接受并纳入maven-resolver v1.8.0 (该组件将随Maven 3.9.0发布)。以下使用说明来自 Maven官方文档:
新算法甫一亮相，来自阿里的开发人员便试用并给出了以下反馈：
目前我们已经应用到5 - 6个需要花长时间build的工程，build时间可以缩短一半，后续我们会把这个算法应用到更多的工程并及时反馈。
这个算法的诞生可谓历经艰辛。从发现问题、解决问题到贡献回社区，每一步都倾注了eBay Applciation Framework 团队的心血。
本文将以算法的起源和演进为轴线，为大家重温个中细节。
注：本文提及的测试数据均基于纯build，指本地Maven repository有full cache并跳过全部测试的情况下跑的Maven Build (mvn clean install -DskipTests)，故不涉及任何Maven artifacts下载。
2
发 现
2021年3月，eBay启动Velocity项目，旨在加速开发迭代。其子项目Build Velocity的设立旨在加速开发周期的重要一环：Maven Build。其前期共60+ pilot 项目参与。eBay Application Framework Team负责技术攻关。
摆在我们面前的问题有两点：一是缺乏数据，二是不清楚Maven Build具体慢在哪里。
工欲善其事，必先利其器。我们首先打造了Zeus产品。该产品以一个Maven Extension为核心，实时参与用户build，收集数据并汇总成报表。通过分析报表、诊断热点（hotspot）、开发特性（feature）以解决热点、Extension自我升级并启用特性、再用新收集的数据体现优化效果，至此形成一个可持续运行的调优闭环。
每条数据量化了Maven Build的各个步骤，并统计以下指标：
Zeus应用到上述pilot项目后，我们发现有一个项目跑一次纯build竟然需要30+分钟才能完成。内存配置甚至需要20G，否则Maven Build会因内存溢出而终止。我们通过分析收集到的build数据，发现上述依赖解析部分时间（相当于跑一次mvn dependency:tree）几乎等同于纯build时间。通过Zeus报表发现，有不少项目在依赖解析上花了不少时间 (5～10分钟)，虽然没有上述项目严重，但至少说明Maven依赖解析慢是个共同的问题！
3
探 究
Maven 依赖解析过程简介
Maven 依赖的声明使用大家都很熟悉了，这里只作简单介绍，以便理解后续介绍的性能问题。详情可参见Maven官方文档。
Maven 依赖缺省为compile scope，默认传递所有子依赖，而其子依赖又会传递自己的子依赖，Maven称之为传递性依赖。随着业务逻辑的增长，依赖会声明越来越多，间接依赖也呈几何级增长，最终项目的依赖图变得非常复杂，并带来大量的冲突。
上图显示了X依赖及其间接依赖。Maven解析步骤如下：
全路径遍历（为了支持依赖传递）。即用深度优先算法按以下顺序遍历全部节点：
X -> Y -> Z 2.0 X -> G -> J -> Z 1.0 X -> H -> Z2.0 X -> Z 2.0 X -> D -> Z 2.0
调解冲突，得到最终生效的依赖项。冲突调解的原则是: 谁距离根节点路径最短，谁就优先选择。如果处于同一层（到根节点路径长度相同），那么看谁先声明。应用此原则，可推断出最终的winner是紫色的Z 2.0，其他黄色Z 2.0均为重复冲突，褐色Z 1.0为版本冲突。
通过跑mvn dependency:tree -Dverbose, 你可以看到Maven标记的两种冲突：
重复冲突 （Omitted for duplicate）
版本冲突（Omitted for conflict）
这个冲突选择的算法是固定的，但最终选择的依赖有可能不是你想要的。比如你实际需要Z1.0， 但Maven选择了Z2.0，结果导致了各类运行时异常。为了解决此类问题，Maven一般允许以以下方式来改变其抉择:
版本管理：
即DependencyManagement或BOM Import，可管理间接依赖的版本。
Exclusions：
可排除不想要的依赖版本。
Maven推荐前者，但实际后者更容易被用户理解，故使用更广泛。这就可能导致下面要说的性能问题。
约7500万内存节点 VS 1500+ 最终依赖项
使用JProfiler，我们发现Maven在构建该项目的dependency tree时，内存里创建了约7500万 Node节点，可见依赖图非常之复杂；然而dependency tree里最后只剩1500+依赖项 (参与编译和部署)，可见这7500万节点大多数是上述的重复冲突或版本冲突节点。所以说dependency tree显示的只是调解冲突后的结果，往往只是冰山一角 (大量的冲突节点已被剪除), 但诸多节点的计算缺一不可，故导致严重性能问题。
为了分析具体原因，我们用mvnDebug命令起了上述项目的Maven Build，在IDE里导入Maven源代码进行远程调试。在调试过程中，我们了解到7500万节点多是因为：
一些基础的类库依赖数个heavy dependencies (特指会带来几百上千间接依赖的Maven dependency)，而这些基础的类库又被上层业务类库广泛依赖。
一些类库基于过时的技术栈构建，其间接依赖无法被新技术栈的parent pom管理。
存在一些循环依赖（同一pattern累计达10次后续才会跳过）。
那么问题来了，虽然Maven是全路径遍历，难道Maven没有cache机制吗？如某依赖被解析过一次，就可以cache解析结果（即全部子依赖），下次再遇到GAV (GroupId + ArtifactId + Version) 相同的依赖就不必再计算了。Maven设计精湛，这个cache肯定是考虑到了，推测这里存在cache失效的问题。
经过深入调试，仔细分析后定位到了问题所在：
原来Maven在cache依赖的解析结果时采用的key非常复杂，由Artifact及继承自所有双亲节点的（Repositories定义、DependencySelector、DependencyManager、DependencyTraverser、VersionFilter）共六部分组成。其中ExclusionsDependencySelector就是根据exclusions来过滤相关依赖的。
这个key的设计会让Maven在exclusions不同的情况下，无法命中cache反复解析同一依赖，此谓Maven依赖解析的阿喀琉斯之踵。
Maven依赖解析的阿喀琉斯之踵
——决定性的Exclusions
从上图可知:
左边树中，B和C都依赖D，D只会被解析一次。
右边树中，B没有定义任何excusions而C排除了F依赖，exclusions不同，D及其子节点E都会被解析两次。由于exclusions是可以继承的，故Maven需要向上追溯所有双亲节点定义的exclusions。对D而言，第一次解析D时 ，A -> B -> D 一路没有定义任何exclusions，故cache计算结果时其key不含exclusions；第二次解析D时，A -> C -> D 这一路继承下来的exclusions不同，故无法命中cache需重算，相应的E也需重算。这意味着如果D足够复杂，带来了很多间接依赖，那么D的全部子节点都需要重算！
可见exclusions在cache的命中与否上起到了决定性作用，因为key的其他部分往往是一致的，但从根节点一路继承下来的exclusions 很难相同，故而大量的子节点也被重算。随之而来的便是：
依赖解析非常慢
大量重算的节点占用内存非常高，频繁触发GC甚至导致内存溢出。
回到上述项目，由于依赖图过于复杂，开发人员为解决各类运行时异常广泛使用了exclusions排除冲突, 从而导致cache频频未被命中，Maven不得不反复计算，疲于奔命。这个问题既不可归咎于开发人员，谁能想到依赖传递和exclusions会带来这么大的性能问题？也不可归咎于Maven，谁又能想到企业级应用里的依赖图会如此复杂？
4
诞 生
发现以上性能问题后, 我们调优了上述项目以及同样比较慢的6，7个pilot应用, 并给用户发PR。为达最大投入产出比，我们采取的多是调整heavy dependencies，核心是避免不必要计算:
为规避exclusions不同导致cache失效的问题：在parent pom里统一管理依赖的exclusions，确保在一个项目中同一依赖具有相同的exclusions。
为规避版本冲突计算：在parent pom统一管理依赖版本。
这些PR对build性能提升显著，但PR对依赖改动太多，需大量测试，耗时耗力；且调优仅针对heavy dependencies，无法达到最大收益。如果后面几千个应用都参与Velocity项目，一一调优显然难以为继。
算法前瞻：机会
回到上述项目，我们做了一个实验，即直接去修改maven-resolver，只要是同一节点（GAV相同）就直接重用cache，最终的build花费时间从30+来到了2-3分钟左右，内存占用降至正常水平。当然这种简单粗暴的改法最终导致项目build失败，但足以证明实现一个新算法意义之大。
算法前瞻：风险
前述maven-resolver 作为Maven的核心组件，负责计算项目编译和部署所需的最终依赖项。对其修改可谓充满风险，稍有不慎，就会导致项目编译不通过或部署失败，甚至引起极端情况下才会出现的运行时异常从而引发site issue。
细读maven-resolver的代码，其算法在Maven 3.0.x 系列就成型了，后面十几年几乎没有改动核心逻辑。并且:
逻辑复杂且分支众多
无详细文档且很少注释
虽然困难重重，但要想一劳永逸地解决Maven在依赖解析方面的性能问题，唯有华山一条路—— 修改maven-resolver的核心算法。
算法实现：BF + Skipper
新算法的需求，首先是100%兼容，其次才是快。一切为了加速导致用户编译和部署出现问题的所谓改进都是站不住脚的。实现这样的兼容算法并非一蹴而就，而是反复摸索出来的。限于篇幅，本文只介绍最终实现： BF + Skipper。
如图所示，为了100%兼容，新算法并未改变Maven冲突调解部分的逻辑。为了加速，把原算法中的全路径遍历改造成了预判式的选择性遍历。通过合理规避冲突节点，最大限度节省不必要计算，而原先复杂的依赖图可大幅精简并且不会影响最终的Maven输出结果。
算法的主要流程如下:
预判冲突：从深度优先转成广度优先以便准确预判。
规避计算：正如图右上方所示，在解析当前节点之前，我们先判断该节点是否属于下列冲突的一种：
为便于理解，将我们的算法和Maven原有的深度优先（DF）算法做以下对比:
BF - 预判冲突
前述Maven解决冲突的方式就是基于深度优先算法遍历全部节点后，再来根据离根节点的远近原则来排除冲突，而广度优先算法正是按照离根节点远近的顺序从上往下从左到右遍历节点的。也就是说，在广度优先算法里，对于相同GA (GroupId + ArtifactId) 的依赖，第一个解析的肯定是winner，后面遇到的一定是冲突的loser。
我们只需把节点遍历从深度优先改成广度优先，那么在计算一个节点时，只要相同GA的节点已被计算过，就可以断定当前节点或者是重复冲突，或者是版本冲突，从而可以选择性跳过。
Skipper - 规避冲突节点的重复解析
为了规避冲突节点的无谓计算，我们创建了一个Skipper。Skipper可以根据以下原则在当前已经解析完成的节点集合中匹配，来判断当前节点是否可以规避：
如已解析过GAV相同的节点，当前节点为重复冲突节点，可选择性规避。
如已解析过GA相同的节点，但版本不同，当前节点为版本冲突节点，可完全规避。
版本冲突节点的规避
从上图可以得知:
D:1 (D的版本为1, #4) 在树的第二层解析, 在广度优先的算法下D:1已经是winner.
当解析到D:2 (D的版本为2, #5)时, 我们知道D:2的版本与D:1不同，属于版本冲突的loser，所以D:2及其所有子节点都是不必计算的。
重复性冲突节点的规避与强制重算
由于涉及到节点的位置比较，节点的坐标信息不可或缺，所以我们需要在解析当前节点时实时计算其坐标。图中坐标(2,2)代表 (第二层, 第二层第2顺位)。
从上图可以得知：
紫色R#3节点是在树的第2层解析的,在广度优先算法里即最终winner。
蓝色R#5不是winner, 但R#5位于 (3,1)， R#3位于(2,2) 。R#5 在R#3的左侧，即R#5 的双亲节点（追溯至根节点的直接子节点，即第二层的B节点）在pom里先于R#3声明。这种情况下需要强制重算R#5，原因后表。
由于R#3早就确定是winner，褐色R#8和R#11均属于冲突loser，且均在上次重算的蓝色R#5右侧故不必再解析了，其子节点（虚线S节点）也同样跳过。
强制重算
该方案最开始的实现并没有上述强制重算的逻辑，测试500+eBay应用正确率已达99%，最后1%的failure cases情况多样，如依赖作用域 (scope) 选择错误等，细节不再赘述。
兼容最后的1%恰恰是最艰难的最后一公里。解决这类不兼容问题需要对Maven的冲突调解算法深入理解，而前面提到这块逻辑复杂，无文档且无注释。摆在我们面前的选择有：
方案一每个failure case分别作特殊处理。这种方案无疑会让最终的算法逻辑过于生硬。
方案二比较两种算法下调解冲突的不同，作一定的适配。这种方案更为直接、安全。即便出现一些Maven的单元测试、集成测试或者eBay的几千个应用无法覆盖到的case也能兼容。
我们选择的是后者。经过深入调试Maven源码，反复研读冲突调解部分的算法，比较两种模式下逻辑的不同，最后定位到：原算法用于调解冲突的重复性冲突节点的路径更多。这点正是因为我们规避了大量的节点计算，从而缺失了一些关键的冲突路径，而这些路径也是Maven需要用来辅助冲突裁决的。
让我们看看如何通过保留冲突路径的方式来兼容原算法的计算结果。以下为图解：
左图为Maven深度优先的算法
Maven按图中标记的数字依次解析节点。对于R节点，其解析顺序为：
在这个解析过程中，胜负关系总共更替了三次。凡是改变了胜负方的节点路径都是Maven最终需要参考的冲突路径，所以最终参与调解的冲突路径是：
A -> B -> D -> R
A -> B -> R
A -> R
右图为我们的算法，BF + Skipper
最先解析的是R#3，即最终的winner，后面所有R节点通通被规避掉，这意味着最后用于调解冲突的只有一条 A -> R。冲突路径的减少影响了Maven的冲突调解结果。我们来看看引入以下重算逻辑后Maven会怎么解析这些节点：
首先解析R#3，R#3即为winner
其次R#6，R#6在R#3的左侧，需重新解析
然后R#8，R#8在上次解析的R#6节点右测，并冲突于R#3，可跳过解析
同理R#10需重新解析, R#11和R#12均可跳过解析
这种方式下的冲突路径按顺序依次为：
A -> R
A -> B -> R
A -> B -> D -> R
可见这些路径和原算法下的冲突路径完全相同。我们通过上述保留冲突路径的方法彻底解决了最后1%的不兼容case。不必担心的是，这种重算并不会太多。即使重算，其大部分子节点仍然可以基于上述原则大量规避。
算法测试与发布
eBay几千个应用提供了各种复杂的依赖使用场景，使用团队现有的快捷测试工具，我们可以基于大量真实项目跑兼容性测试：
做一个精简版的Maven Extension，替换maven-resolver的实现类。
批量Fork用户项目，自动添加maven-exec-plugin配置, 在启用或不启用extension (-Dmaven.ext=xxx.jar) 的模式下分别跑以下命令：
mvn dependency:tree（决定编译结果）
mvn dependency:list（决定部署结果）
比较两种模式dependency tree 和dependency list输出结果的不同。
经过数轮测试，这个算法已趋稳定。在正式交付前我们测试了eBay几千应用。这个算法同样通过了Maven所有的单元测试，集成测试，达到了我们最初的需求设定：即新算法不仅大大加快了Maven依赖解析的速度而且100%兼容原算法。
数月之前，我们已经将上述算法包装成Zeus的一个feature，通过Zeus的自我升级发布到大量eBay项目中。我们惊喜地看到，这个算法对于一些复杂项目的纯build有30% ~ 70%性能提升，而且对于上述人工调优后的项目，build性能仍然有不小的提升。这佐证了前面的人工调优方式不光费时费力，而且达不到最大收益，当然这是后话了。
5
结 语
BF (广度优先遍历) + Skipper算法在eBay已经得到广泛应用，我们第一时间决定将上述算法贡献回Apache Maven社区。这个过程也非易事，我们和社区紧密协作，反复重构，不断完善各种测试用例，最终社区欣然接受。
该算法起源于eBay Build Velocity的大量调优实践，我们通过打造Zeus系统收集数据，识别Maven Build的性能痛点，不断探索去解决用户问题，再到改造算法，不断测试，最后应用到eBay几千个项目并贡献回社区。其中艰辛，唯有自知，所幸天道酬勤，终有收获，也不枉我们这一路的跋山涉水。回首整个历程，我们可以自豪的说，这种实践完美诠释了eBay人取之于社区，再回馈于社区的开源精神。
与此同时，我们正在开源回去的还有同样源于eBay Build Velocity实践的feature: Maven 元描述文件（Descriptors，包括pom, metadata.xml等）预判式并发下载，目前社区正在review我们的PR。eBay在大量开发实践中诞生了很多优秀产品，这些产品需要解决的问题不仅仅是eBay需要面对的问题，期待有更多的产品加以提炼，拥抱开源，共勉之！
谨以此文由衷感谢团队成员 (Simon Wang, Eric Cai,Caddie Song, Rocky Shang, Gary Zhang, Rick Leng) 在Build Velocity项目中的辛勤付出。也特别感谢eBay平台，大量积极开发中的eBay项目为我们提供了丰富多样的Maven依赖使用场景，可以让我们放心去探索、实践、改变与贡献！
