Introduction
Maven is widely used as a Java project build tool at eBay. As an essential component of Maven, maven-resolver resolves declared dependencies, calculates dependency graphs, mediates conflicts and forms the classpaths for compilation and deployment. This is the so-called dependency resolution process.
One of the main impediments to fast iterations of software development was long build times. As part of eBay’s commitment to velocity and building improvements, we developed a Maven extension called Zeus, which was designed to collect and visualize the Maven build data in Kibana reports. We were surprised to find out that the Maven resolver has serious performance bottlenecks when it comes to resolving complex dependencies. In such circumstances, Maven dependencies resolution can be responsible for most of those build times, therefore slowing down the development efficiency.
To speed up those times, we implemented a new algorithm: BF (breadth first traversal) and Skipper (skip unnecessary dependency resolution), which helped reduce the pure build time for heavy Java applications at eBay by a whopping 30 to 70 percent! With this algorithm, Maven can break through the bottleneck and complete the dependency resolution in the shortest time with the least computation, regardless of how complex the dependency graph is.
Problem Analysis
Note: the test data mentioned in this article is based on pure build, which equals to Maven build (mvn clean install -DskipTests) that runs when the local repository is fully populated. It does not involve downloading any Maven artifacts nor test execution.
A Maven build is composed of 4 parts: dependency download, dependency resolution, plugin execution and tests execution. The dependency resolution time is similar to the total time of running mvn dependency:tree.
From the build data collected by Zeus, we knew some projects at eBay were experiencing severe slowness (between five and ten minutes) in the dependency resolution step. Particularly brutal examples could take over 30 minutes and 20GB of memory merely to print out the dependency tree. This delay is clearly unacceptable, but to fix it, we first needed to know how Maven resolves dependencies.
Maven Dependency Resolution
A Maven dependency defaults to compile scope, which propagates all child dependencies recursively.
The figure above shows the X dependency and its transitive dependencies. Maven will resolve the dependencies as follows:
-
To support transitive dependency propagation, Maven uses a DF (depth first search) algorithm to traverse all paths in the following order:
-
X -> Y -> Z 2.0
-
X -> G -> J -> Z 1.0
-
X -> H -> Z2.0
-
X -> Z 2.0
-
X -> D -> Z 2.0
-
To mediate the conflicts, Maven takes the approach of the nearest transitive dependency in the tree depth and the first in resolution. The final winner is purple Z 2.0 as it is nearest to the root; the yellow Z 2.0 nodes are duplicate conflict losers and brown Z 1.0 is a version conflict loser.
By running mvn dependency:tree -dverbose, Maven indicates for each transitive dependency why it was omitted, choosing from one of the following conflicts:
-
Duplicate conflict (omitted for duplicate)
-
Version conflict (omitted for conflict)
As eBay’s business grows, more and more dependencies will be used to implement various features, and transitive dependencies will also grow geometrically. The final dependency graph can be very complex and brings a significant quantity of conflicts. There are two ways to resolve conflicts:
-
Version management: Leverage Maven’s dependency management or BOM import to manage transitive dependency versions.
-
Exclusions: Exclude unwanted dependency versions.
Maven recommends the former, but in fact, the latter is easier for users to understand and is more widely used. Using exclusions so widely may lead to the following performance problems.
75 Million Memory Nodes vs 1500+ Final Dependencies
Take the slowest project in the below graphic as an example. About 75 million nodes were created in memory when Maven tried to build the dependency tree of the project.
75 million nodes demonstrated the dependency graph could be very complex in an enterprise level project. Be that as it may, only 1500 or so dependencies are retained in the dependency tree output.
Therefore, we can conclude most of these nodes are conflicting nodes that will be truncated after conflict mediation, and won't show up in the dependency tree. However, the calculation of these nodes is inevitable, which leads to serious performance issues.
To find out the root cause, we ran mvnDebug dependency:tree and imported Maven source code into the IDE for remote debugging. During debugging, we learned that 75 million nodes were created due to the following behaviors:
-
Certain low-level libraries rely on several heavy dependencies (which brings hundreds of transitive dependencies), and which are referenced by many other business-related libraries.
-
Certain libraries are built on outdated technology stacks, and their transitive dependencies are no longer managed by the parent POM of the current technology stack.
-
Circular dependencies (the same cycle pattern will be skipped until it appears 10 times).
If full path traversal of all nodes is inevitable, we wondered, is there a cache that saves the resolution result by a key like GAV so that Maven can reuse and speed up the resolution?
The answer, happily, is yes. But by checking the code of maven-resolver, we knew the cache key Maven uses is very complicated, and exclusions (DependencySelector below) are also part of the key.
In the Maven world, exclusions can be inherited. Maven needs to trace up the exclusions defined by all parent nodes; this means when the exclusions up the tree differ, the cached resolution result for the same artifact won't be reused, and needs to be recalculated repeatedly. This is, we think, the Achilles heel of Maven dependency resolution.
Exclusions Matters - The Achilles Heel of Maven Resolver Cache
In the above illustration:
-
On the left, both B and C depend on D, and D and its children will be resolved only once as cache hits.
-
On the right, B does not define any exclusions while C excludes F. D and its child node E will be resolved twice as the exclusions differ. Imagine if D is a heavy dependency that could introduce many transitive dependencies. In that case, all of D’s children need to be recalculated!
Exclusions here play a decisive role in cache hit rate. Many conflicting nodes may require recalculation as exclusions inherited from all parent nodes usually differ. This leads to:
-
Severe slowness in dependency resolution
-
Recalculated nodes taking up huge amounts of memory, triggering GC frequently and resulting in out of memory.
Back to the above project! As the dependency graph is too complex to understand, developers have to use exclusions widely to eliminate conflicts in order to solve all kinds of runtime exceptions. But this results in continual cache misses. Maven has to waste much of the build time resolving those unnecessary nodes.
Algorithm Implementation: BF + Skipper
To solve the resolution slowness, the key is to avoid unnecessary calculation. We can manage the transitive dependency versions and the exclusions in the parent POM to ensure that the same dependency always has the same exclusions. Such changes do improve the build performance significantly, but usually include quite a few dependency changes which are error-prone and require unwanted testing.
eBay has been committed to open-source contributions for decades. It was in that spirit we decided to modify the maven-resolver, as the dependency resolution slowness we are facing today is not unique to eBay, but a common issue for all Maven users developing enterprise applications.
As mentioned, maven-resolver is responsible for calculating the final dependencies required for project compilation and deployment. Any incorrect modifications to this component will lead to the compilation or deployment failure of any projects using Maven.
Thus when considering a “new algorithm,” the primary considerations must be performance, of course, but also 100 percent compatibility. As Rome wasn’t built in a day, the implementation of such an algorithm requires many attempts and much verification. This article will showcase the final implementation: BF + Skipper.
In the below illustration:
-
To achieve 100 percent compatibility, the new algorithm does not touch Maven's conflict mediation part.
-
To achieve better performance, the full path traversal is transformed into a selective traversal to avoid unnecessary calculations of massive conflicting nodes. The dependency graph can thus be greatly simplified and yet yield the consistent dependency tree output.
The main flow is as follows:
-
Convert the Maven dependency resolution strategy from DF to BF.
-
Skip the resolution of certain nodes by predicting if the current node being resolved belongs to one of the following conflicts:
-
If the node belongs to a version conflict, skip resolution directly.
-
If the node belongs to a duplicate conflict, determine whether the conflict path needs to be preserved to be compatible with the conflict mediation algorithm. Force resolution if yes and skip resolution otherwise.
To understand this easily, let‘s compare the two approaches:
BF: Predict Conflicts
Maven traverses all dependency nodes based on the DF algorithm and then mediates the conflicts according to the order and depth away from the root node. The BF algorithm traverses the nodes from top to bottom and from left to right, which is exactly the same order as when Maven mediates conflicts.
In other words, in the BF algorithm, for any nodes with the same GA (groupId + artifactId), the first one resolved is always the winner, and the latter ones to resolve must be conflict losers.
By changing the traversal strategy from DF to BF, we can predict whether the current node is either a duplicate conflict or a version conflict and skip selectively by checking if a node with the same GA has been resolved.
Skipper: Avoid Unnecessary Resolution of Conflicting Nodes
To avoid unnecessary resolution of conflicting nodes, we created a skipper. Skipper can match in the present resolved nodes according to the following principles to determine whether the current node can be skipped:
-
If a node with the same GAV (GroupId + ArtifactId + Version) has already been resolved, the current node must be a duplicate and may be skipped.
-
If a node with the same GA has already been resolved and the version of the current node differs, then the current node must be a version conflict, which can be safely ignored.
Skip Resolution of Version Conflicting Nodes
In the above illustration:
-
The purple D:1 (D with version: 1, #4) is in depth 2 of the tree, D:1 is already the winner.
-
When resolving D:2 (D with version 2, #5), D:2 has a different version than D:1 and must be the conflict loser, D:2 and all its children can be safely skipped.
Skip Resolution of Duplicate Nodes
To compare the depth and sequence of tree nodes, we need to calculate the coordinate of the current node before resolution. The coordinates 2,2 in the illustration represent the 2nd depth in the tree and the 2nd node in given depth.
In the above illustration:
-
Purple R#3 is resolved at the depth 2 in the tree, which is already the winner.
-
Blue R#5 is a duplicate of R#3. R#5 locates at (3,1) which is on the left side of R#3 (2,2); this means the parent node of R#5 (B#2 in depth 2) is declared before R#3 in the POM of root node A. In such case, we must force resolve R#5.
-
Since R#3 is already the winner, brown R#8 and R#11 are conflict losers, and both of them are on the right side of the blue R#5 which was force-resolved recently. In this case, R#8, R#11 and its children (brown dotted S node) can be skipped.
Force Resolution of Specific Duplicate Nodes
The initial implementation of this algorithm did not involve the mentioned force-resolution logic. The accuracy rate of testing with over 500 eBay applications reached 99 percent, a very successful result for a first attempt.
The last one percent of failure cases are diverse, and can include the incorrect dependency scope (compile, runtime, provided and more) selection. Solving one-percent incompatibility is the biggest obstacle to achieve a zero failure rate and requires an in-depth understanding of Maven's conflict mediation algorithm. The choices before us are:
Method I: Deal with each failure case separately.
Method II: Adapt the differences of conflict mediation between the two algorithms.
We choose the latter, as the former method may complicate the code logic and let slip cases that are unrevealed during our test.
After digging into Maven’s conflict mediation algorithm, we finally located the problem: The number of duplicate nodes’ conflicting paths — used for conflict mediation in the original DF implementation — are bigger than in our BF solution. This is because we have skipped a large number of node calculations and thus miss some auxiliary conflict paths that are also referenced for conflict mediation.
Maven’s DF Strategy
On the left, Maven resolves the nodes in a depth-first strategy following the sequence of 1 - 12. The resolution order of all R nodes is:
In this process, the winner has been elected 3 times: R#4 -> R#5 -> R#8. Although the R#8 is the final winner, Maven still counts in the path of all temporary winners (R#4, R#5) as auxiliary paths for conflict mediation. Here are the conflict paths that eventually participate in mediation：
-
A -> B -> D -> R
-
A -> B -> R
-
A -> R
Our Strategy: BF + Skipper
On the right, Maven resolves the nodes in a breadth-first strategy following the sequence of 1 - 12.
Without force-resolution,the first R node resolved is R#3, which is already the final winner. All subsequent R nodes are skipped, which means there is only one path: A - > R, used to mediate conflicts.
With force-resolution, the flow is as follows:
-
Firstly resolve R#3, which is already the winner.
-
Then R#6, R#6 is on the left side of R#3, which needs to be force-resolved.
-
Then R#8, R#8 is on right side comparing to the last force-resolved R#6 but conflicts with R#3, thus skipped.
-
Likewise, R#10 needs to be force resolved as it locates on the left side of last force-resolved R#6.
-
R#11 and R#12 locates on the right side of last force-resolved R#10 and can be skipped
In this way, the conflict paths are as follows:
-
A -> R
-
A -> B -> R
-
A -> B -> D -> R
Here all conflicting paths are preserved, albeit with a reversed sequence, and the last 1% of incompatibilities are solved with this method.
Conclusion
This algorithm was shipped as a feature of Zeus and had already been enabled for most of the Java applications at eBay months ago. As the change is made on the Maven core, which is very critical to the result of a Maven build, we certified the solution before the release by testing 2,000 to 3,000 Java applications, comparing the dependency tree between the two algorithms with an automated method. Those large numbers of applications provide a great diversity of Maven dependency usage scenarios and help us guarantee the accuracy and effectiveness of this algorithm.
Now that this algorithm has been widely adopted at eBay, we decided to contribute it back to the Apache Maven community. We worked closely with the community, refactored the code and improved test cases continuously, and ultimately the PRs were officially accepted in May 2022 and incorporated into maven-resolver (v1.8.0).
Soon after the release, engineers from Ali Group tried it and reported very positive feedback. Below is the comment they shared:
This algorithm mainly solves the slowness in dependency resolution but the dependency downloading part. Maven was born to be downloading POMs in sequence which causes long build times when the dependencies are not available in local cache. To solve such download slowness, we continued to work on the 2nd contribution: parallelized dependency collector on top of the BF algorithm which would download all dependencies’ POM in parallel. The community has accepted our changes and released it into maven-resolver (v1.9.x) .
The combination of a parallelized Maven dependency collector with the BF and Skipper now makes the BF algorithm the most appropriate option to achieve a fast yet consistent Maven build. Maven 3.9.0 that released in Feb 2023 has already shipped the two contributions, you may find the brief introduction from the official product page:
This algorithm is derived from the massive Maven build tuning practices at eBay. We collected and visualized data, identified the bottlenecks, implemented and verified the algorithm, applied our fixes to thousands of eBay applications, then contributed back. Although the road to open-source was paved with obstacles, the result is rewarding and promising. Kudos to the eBay Application Framework Team who dedicated a great deal of time to the birth of this approach! Such practices demonstrated the open-source spirit of eBayers: We take from the community and give back to the community.