Package Managers and Dependency Hell

Abstract

A modern program is installed with one command, apt install, pip install or npm install, which fetches the program and every library it needs, and the libraries those need, at compatible versions. The tools that do this, package managers, grew out of a decade of manual work: in the early 1990s installing Unix software meant downloading a tarball, finding its libraries by hand and compiling. The FreeBSD ports collection (1993), Debian’s dpkg (1994) and Red Hat’s RPM (1995) recorded dependencies; Debian’s APT (1999) resolved them automatically; Perl’s CPAN (1995) carried the idea from operating systems to programming languages, and npm, pip and Cargo followed. The problem they solve has a name, dependency hell, and a proof attached: in 2005 European researchers showed that deciding whether a package can be installed at all is NP-complete.

Before Package Managers

On early Unix systems, new software arrived as source code in a compressed archive. The user unpacked it, read the README, ran a configuration script, discovered that a library was missing, went to find that library, discovered that it in turn needed another, and eventually ran make install, which copied files into system directories with no record of what had been put where. Removing the program meant remembering which files it had installed. Upgrading a library could break every program that had been compiled against the old one.

Windows users met the same problem in binary form. Programs shipped shared libraries, DLLs, and their installers copied them into the common system directory, sometimes overwriting a newer version with an older one that the installer happened to carry. The next program that needed the newer version stopped working. Users called it DLL hell (see The Linker and Loader Story). Microsoft’s answers came with Windows 2000, whose Windows File Protection stopped installers from replacing system DLLs, and with side-by-side assemblies, which let each application load its own version; an MSDN article by Rick Anderson in January 2000 was titled “The End of DLL Hell.”

Recording Dependencies

The first step was bookkeeping. On 26 August 1993 Jordan Hubbard committed the Makefile for FreeBSD’s package install suite, and in August 1994 the “port make macros” that became the ports collection: for each program, a directory with a Makefile that knew where to fetch the source, which patches to apply, how to build it and which other ports it depended on. NetBSD’s pkgsrc (1997) and Gentoo’s Portage were built on the same idea.

Linux distributions shipped binaries instead. Ian Murdock wrote the first version of dpkg for Debian as a shell script in January 1994; it was rewritten in Perl and then, by Ian Jackson, in C. Each .deb file carried metadata naming the packages it depended on, the packages it conflicted with and the versions it needed. At Red Hat, Erik Troan and Marc Ewing wrote the RPM package manager in 1995, and RPM became the second major Linux package format (see The Linux Distributions).

These tools could check dependencies but not satisfy them. If a package needed a library that was not installed, rpm refused and printed the missing name, and the user went looking for it, often finding that the library needed something else. Red Hat users called the result “RPM hell.”

Resolving Them

APT, the Advanced Package Tool, arrived with Debian 2.1 on 9 March 1999. It worked above dpkg and against repositories of packages on the network: apt-get install computed the set of packages needed, downloaded them and installed them in order. Red Hat’s world got the equivalent with yum, and Fedora replaced yum with DNF, the default from Fedora 22. Users rarely saw how hard the computation was, because distribution maintainers kept their repositories consistent.

It was hard. The European EDOS project, which studied the quality of open-source distributions, proved in a 2005 report that deciding whether a single package can be installed from a repository of Debian or Red Hat packages is NP-complete, and Fabio Mancinelli, Roberto Di Cosmo and their colleagues published the analysis at the Automated Software Engineering conference in September 2006. The encoding is direct: each package becomes a Boolean variable, a dependency becomes an implication and a conflict a clause forbidding two packages together. In the other direction, any instance of the satisfiability problem can be written as a repository. From 2007, when Chris Tucker and colleagues presented OPIUM at the International Conference on Software Engineering, package managers increasingly handed the problem to SAT solvers: openSUSE’s libsolv, Eclipse’s plugin installer and the Conda package manager among them.

The Language Repositories

The second line of development started with Perl. The Comprehensive Perl Archive Network (CPAN), conceived in 1993 and online from October 1995, was modelled on CTAN, the archive for TeX, and collected Perl modules in one mirrored archive with a client, CPAN.pm, that installed a module and its dependencies (see Larry Wall and Perl). The pattern was copied for each new language. Python’s package index, PyPI, was finalised in 2002 and 2003; Ian Bicking released pyinstall in 2008, soon renamed pip. Isaac Z. Schlueter released npm for Node.js on 12 January 2010 (see The JavaScript Revolution). On 20 November 2014 the Rust project opened crates.io for Cargo, designed by Carl Lerche and Yehuda Katz, which “follows the tradition of successes like Bundler and NPM.”

The language managers changed two assumptions. An operating system has one copy of each library, so its package manager must find one version that satisfies everyone. A program can bundle its own, so npm installed each package’s dependencies inside that package’s own directory, nested as deep as necessary, and two parts of a program could use different versions of the same library. Cargo allows several versions of a crate in one binary. The cost was size: a JavaScript project’s node_modules directory could hold thousands of packages, and from npm 3 the tool flattened the tree where it could and nested only where versions conflicted.

The second change was versioning by contract. Around 2010 Tom Preston-Werner, a co-founder of GitHub, published the Semantic Versioning specification: a version number MAJOR.MINOR.PATCH in which only a new major version may break compatibility. Package managers used it to accept any newer minor release automatically. To make builds repeatable despite this, Cargo and, from 2017, npm 5 wrote lock files that recorded the exact versions resolved, to be checked into source control with the code.

Climbing Out

On 13 December 2016 Russ Cox, one of the developers of Go, restated the NP-completeness result in a blog post that began, “Dependency hell is NP-complete. But maybe we can climb out.” The hardness came from allowing a package to declare upper bounds and conflicts, so that a solver might have to search. His proposal for Go, minimal version selection, published on 21 February 2018, allowed only minimum versions: each module states the oldest version of each dependency it works with, and the build uses the oldest version that satisfies all of them. The problem becomes a graph traversal that runs in linear time, the result is reproducible without a lock file, and a newer version of a dependency is never used unless someone asked for it. Go’s module system adopted the scheme, and the Go modules reference describes it as the algorithm Go uses to select module versions.

Python moved the other way. pip had for years installed whatever version it met first, without checking whether the combination was consistent. Its new resolver, enabled by default in pip 20.3 on 30 November 2020, backtracks: when an earlier choice leads to a conflict, it discards it and tries another version, which made installs correct and sometimes slow.

The most thorough answer was Nix, which Eelco Dolstra began in 2003 at Utrecht University and described in his PhD thesis The Purely Functional Software Deployment Model, defended on 18 January 2006. Every package is stored under a path containing a cryptographic hash of everything that went into building it: sources, compiler, libraries and build options. Two builds that differ in any input land in different directories, so any number of versions coexist, an upgrade never overwrites anything, and rolling back means pointing at the old path. GNU Guix adopted the same model.

Dead End: One System Library for Everyone

The founding idea of the distribution package managers was that one shared copy of each library, maintained by the distribution and upgraded once for everybody, was better than each program carrying its own: less disk, less memory, and one place to fix a security hole. The language repositories gave that up within a decade, and the deployment world gave it up after that. Docker, released in 2013, packaged an application with its whole user-space environment, every library included, so that it ran the same way everywhere (see The Container Revolution).

Each step moved dependency hell rather than abolishing it. Bundling made programs independent of each other’s libraries and made a vulnerable library harder to find, because it now existed in hundreds of copies. Automatic resolution from public registries made installation easy and made every program depend on strangers’ packages. In March 2016 the removal of left-pad, an eleven-line npm package, broke builds across the JavaScript world within hours (see Volunteer-Maintained Infrastructure), and attackers learned to publish malicious packages into the same registries (see Software Supply Chain Security).