Migrating interdependent jars

We have recently completed a build and infrastructure migration at Carfax. It involved moving around 200 jars to a new build and distribution system. We wanted to work in small steps and be able to ship applications throughout the migration. This is challenging, because our dependency graph was highly connected. We found it useful to transform the dependency graph by removing certain redundant edges and ordering nodes based on how many levels of separation they had from leaf nodes. We then migrated leaf nodes first, followed by level 1 nodes, until all levels were converted. This bottom-up breadth first approach simplifies many issues around migration.

To explain what we did, it will be helpful to look at how dependencies may be laid out for a single application:

If we were to migrate jar4, our new build system would have to understand how to pull jar2 from the old build system, and jar3 would need to understand both old and new build systems in order to retrieve all of its dependencies. If you were then to migrate jar2 next, you would end up having to rebuild jar4 in order to eliminate the old version of jar2 from its dependency tree. On the other hand, if we were to start with jar2 and then convert jar4, the new build system would not need to know anything about the old build system, and jar4 would only need to be built out once. So it should be clear, that the order in which jars get migrated makes a difference in how much work has to be done. What then is the optimal migration order?

Intuition from the above example suggests that in order to minimize work, we should assure that all of given jar's dependencies have been migrated, before the jar itself gets migrated. If we were to assign level 1 to all jars that do not have any dependencies, level 2 to all jars that depend on level 1 jars, etc., we would arrive at the following graph:

Note that jar3's level is determined by the highest level of its dependencies, jar4. If we were to leave jar3 at the same level as jar4, it would not be clear which one to migrate first. Another thing to note is that for the purposes of visualizing migration, we can safely get rid of 3 edges, because the appropriate jars are brought in transiently anyway. Now we can proceed with converting all level 1 jars, followed by level 2, etc.

The above example is very simplified. This is the problem our team was facing in reality:

Note, the levels above were assigned by the graphing software (GraphViz), and do not have any meaning in the context of the migration.

And now a graph that orders nodes by their migration level:

The bottom-up breadth-first migration approach has these important characteristics:

• Can always ship latest software.
• Number of times a jar is rebuilt is minimized.
• Build system complexity is reduced. The new build does not need to integrate with the old build. (Old build, however, still needs to integrate with the new build.)
• Throughput is maximized. Libraries of the same level can be migrated in parallell. This means less coordination is necessary on the migration team.
• No surprises. No transient dependencies using the old build will ever show up during dependency resolution.