Auto-Update: Lessons learned
Last summer, we released the auto-update feature that aims to ease the update of the dependencies of your projects. Auto-update leverages the test suite you provide to determine whether or not an update is compatible with your project: it iterates through the possible updates, runs the test suite, and eventually returns the best dependency files.
So the auto-update is all about exploring a bunch of updates and picking the best one. Simple, right? Well, the task is certainly more complex than it seems. This is so true that we plan to deploy a new implementation of this feature. But before that, we'd like to share the experience we gained on this particular topic, including the traps we fell into.
The current implementation of the auto-update could be sum up in single word: optimistic. It works best if your project is already in a good shape.
Let's say your project has N outdated dependencies. At the beginning, the algorithm updates all of them and runs the test suite. In the best-case scenario, the test suite passes and the auto-update stops right away, returning the best possible update. Otherwise, it limits the update to N-1 outdated dependencies, explores each possible combination, and stops as soon as the tests pass.
This algorithm is a "brute force" update. Its design is based on a few assumptions:
Most of the Gemnasium projects are in a good shape, so there should be no more than a few outdated dependencies.
Some legacy projects have many outdated dependencies, but they will be fixed as the auto-update processes them. So this is not an issue in the long term.
The auto-update runs in the background on some kind of CI server, so it doesn't really matter if it takes a long time anyway.
But this is not true. To begin with, legacy projects do matter: they are hard and expensive to maintain, so many users are interested in fixing these projects using the auto-update feature. Actually, many of these legacy projects are web apps (Ruby On Rails or alike) and they come with a huge set of dependencies - including outdated ones. So it's very likely that we can't update all the dependencies at a time.
Time also matters. The auto-update relies on having a descent test suite for the project, but test suites tend to be slow. Actually, this is especially true when we deal with legacy web apps - the ones that would benefit the most from the auto-update feature. Updating the dependencies is problem solving. But if it takes a long time to solve the problem, we may not be interested in the result anymore.
As an example, let's consider some Ruby On Rails web app. It has about 100 dependencies: it declares 20 dependencies and has 80 nested ones. The test suite runs in 30 minutes an we can run it up to 48 times a day. They are many possibilities to be explored so we'd better optimize the search, otherwise it's too late when we get the answer:
the project has evolved and the test suite has changed
the dependencies of the project have changed
new versions have been published
The later should not be overlooked. Think about it: the project depends on 100 packages and it's very likely that one them gets a new version within a 24 hour time frame.
The current auto-update algorithm starts with the bigger updates and goes one with smaller one. It stops as soon as the test suite passes and it gives an optimal result: the best set of updates we can hope for. But there's a huge drawback though: it's silent until the very end. Let's consider that the auto-update has been running for 10 hours and is now working on a data set that's not relevant anymore (see above). So we decide to cancel the run. But then we don't anything about the dependencies that may or may not be updated. That was just a waste of CPU time. The auto-update could do a better job.
The "auto-update" name can be misleading: the current implementation attempts to upgrade everything. If a project depends on "rails" version 4.1.0 and the latest version is 4.1.7, then the requirement will be changed to something like >= 4.1.0, <= 4.1.7. Generally speaking, the new requirements make on-the-edge updates possible.
This "upgrade strategy" is fine when the project already tracks the latest versions of its dependencies: updating to the latest minor version is probably not a big deal. But what if this not the case? Let's consider that the project depends on rails 3.2.20. Even if we manage to install version 4.1.7, the test suite will probably fail. This is way too optimistic.
Reflecting on the first implementation of the auto-update feature, we eventually came up with two simple ideas and a radical perspective shift:
Finer grain. The original implementation of the auto-update searches for the best update. But finding the optimal result comes at a high price. It would be better to find a limited number of updates in a much reasonable time frame.
More feedback. So far the auto-update gives no feedback until the very end. It should give useful information to the user as it iterates through possible updates.
Don't upgrade, but downgrade instead
The auto-update used to upgrade everything. It won't do that anymore; this will be a true update. Your project depends on rails but you know it is not compatible with the 4.x branch? Set the requirement to something like ~> 3.2.20 and it will leverage your knowledge.
Now, let's consider a project that depends on the sinatra package and comes with version 1.3.0 by default (locked version as defined in Gemfile.lock). The project sets no requirement for this dependency and we don't really know what versions are compatible. Is that an issue? No, because Gemnasium will be able to figure what the requirement is! If the tests pass with version 1.3.6 (latest version of the branch) but fail with version 1.4.0, the requirements will be downgraded to '~> 1.3.0', making it impossible to install 1.4.0 or higher.
The new auto-update algorithm attempts to update one dependency at a time, no more. It relies on two nested loops:
the outer loop goes through the outdated dependencies
the inner loop explores possible updates for each one
The inner loop starts with the most optimistic update, down to no update at all:
downgrade even more & update
It stops as soon as the test suite passes. In the worst-case scenario, the requirement will be modified to lock the current version of the dependency; there will be no update at all.
This step-by-step strategy looks for possible updates on top of the ones that have already passed. The best update is the sum of all the successful updates. We can calculate this "best update" and get a partial result at any time.
This new algorithm gives feedback each time it iterates. Not only it gives you a partial result, but it also tells you about updates that fail and things that need to be fixed.
In case all the dependencies can be successfully updated, the new iterative algorithm takes a longer than the old one. But here are the facts:
this new algorithm is definitely a win for legacy projects
it won't hurt well-maintained projects because they have very few outdated dependencies anyway
To wrap it up, the new auto-update may not optimal, in theory. But it will give you something that you probably care about: feedback. One step at time, it tells about the updates that work and about those that fail. It can even fix and downgrade your requirements! Waiting for this upcoming auto-update feature? Stay tuned!
