What could possibly be difficult about developing something you use every day, like app stores or package managers?

What is Package Management

Package management: a concept that is widely recognized, yet deeply misunderstood.

I recall when I first started using Linux, I only knew from my classmates that on this operating system, you installed software by typing commands, rather than the Windows way of visiting various mysterious software download sites, downloading odd installer packages, and clicking "Next." At the time, I was amazed by Linux’s design. Of course, later I realized there was nothing surprising about it: what I was using was simply a package manager.

Later, I remember buying a Nexus 6P. At that time, many Android phones in China still required distributing APK files to get software. Many students even had to install update assistants on their phones, which required extensive manual intervention just to update applications. But after getting my Nexus 6P, I discovered that I only needed to search for apps in the Google Play Store, click install, and then I didn’t have to worry about anything else.

Each app is like a box. Clicking "Install" in the store is like bringing it home. Opening it is like opening the box. Updating is like replacing the contents inside with new ones. Uninstalling is like throwing the box away. The app store is like a big supermarket.

Installing software, or as a developer, distributing the software you’ve developed, should sound like a very mature and elegant process. Imagine an Apple developer who only needs to write code in Xcode, press publish, and then a large number of users can install and enjoy their software in the App Store. Each app is like a small box that can be easily and uniformly downloaded, opened, updated, uninstalled, and tracked...

If the world were as elegant as I’ve described, that would be great.

Directed Acyclic Graph

Let's take a look at the popular package managers in the industry today: winget, npm, nuget, apt, yum, dnf, pip, nix, homebrew, cargo, composer, gem, maven, gradle, snap, conda, pacman…… Their usage is all the same: users tell them which packages they need, and they help users set up an environment with those packages, after which the packages can be used or development can begin.

The content we will discuss next is general knowledge about package management and does not involve any specific package manager.

As developers, we face a fundamental question every day: why does it work on my computer, but not on the user's computer?

The answer is simple. The user's computer environment is different from the developer's environment. The differences may lie in: the user's computer might be missing certain components, libraries, environment variables, configuration files, have a different operating system version, or a different chip instruction set…… Developers have not tested all those possible scenarios.

We can abstract the differences mentioned above—that is: components, libraries, configurations, chips, etc.—into a single concept: dependencies. Every package has dependencies. These dependencies might be a binary, the internet, a configuration file, an Nvidia graphics card, or a specific operating system.

Therefore, different packages will have vastly different dependencies. Dependencies themselves may recursively introduce more dependencies. If each package is a node and each dependency relationship is an edge, then the entire dependency structure is a graph. This graph is directed and must be acyclic. In data structures, a directed acyclic graph is called a DAG.

So, installing a package is not as simple as: carrying a box home and opening it. What we carry home might be an entire tree.

Basic Requirements

The most typical issue is this: If two packages, A and B, both depend on C, then when a user installs A, we obviously need to install C. If the user wants to install both A and B, it is clearly unnecessary to install C twice. Installing it once can effectively save disk space and bandwidth.

Similarly, there are more issues to consider. The introduction of one package should obviously not break another. Packages should be isolated from one another.

From the user's perspective, they may want to upgrade a specific package or downgrade a specific one. Both upgrading and downgrading should be allowed and should not cause any damage to the system.

From the administrator's perspective, there is a need to query the current context, for example: How was a specific package introduced? Which packages consume the most disk space and which consume the least? Who are the publishers of these packages? Are they the latest versions?

From the developer's perspective, the distinction between compile-time and runtime dependencies is important. Although we generally consider runtime dependencies to be a subset of compile-time dependencies, and this assumption usually does not cause major problems, there is another aspect: In our own development process, suppose I am a package author. It is likely that software packages with the same name and version are actually compiled from different source code. How can I correctly include these packages during my own compilation phase?

<!-- 但是，不同版本的包，很可能其依赖树都是不一样的。 -->

Global Package Management apt

Next, our focus shifts to discussing solutions within the industry. Let's first look at the most popular package management system in the Debian world: APT.

Some of you may not have experience developing large-scale C or C++ projects and might mistakenly believe that apt is simply used for installing software. While apt can indeed install software, it is fundamentally a package manager. The essence of package management is the deployment of software packages.

For example: In Linux, if your C++ program needs to include a header file for a library like libcurl, that file must exist in the /usr/include/ directory. Or, if you have developed a video format converter that needs to call ffmpeg, then ffmpeg must exist in the /usr/bin/ directory. These files are what we call software packages.

At this point, there is a very simple and clear relationship: this is a dependency. Your program depends on libcurl or ffmpeg. Therefore, apt can correctly understand this situation; it will first help you install libcurl or ffmpeg, and then install your program.

It sounds simple, but comparing this with our requirements makes the picture clearer. While we can handle cases where both A and B have dependencies on C, if other software also wants to install ffmpeg, they will quickly realize that ffmpeg has already been installed by your application. Your system will only have one copy of ffmpeg. This effectively reduces disk usage.

Of course, apt is smart enough to handle this as well. If two pieces of software both depend on ffmpeg, ffmpeg will only be uninstalled after both pieces of software have been completely removed. This is because apt maintains a reference count. A software package is only uninstalled when its reference count reaches 0.

Besides apt, there are others such as yum and pacman. They are all global package managers. The characteristic of a global package manager is that it installs software packages into the system's global directories. This means all users can use this software package.

The benefit of this is that all users can use the software package. The drawback is also that all users can use the software package.

Unresolvable Upgrade Issues

Why is this a downside? Naturally, its first problem is this: if A and B have different requirements for C—for example, one requires version 2.0 and the other requires version 3.0—this issue cannot be resolved by a global package manager. A global package manager can only check the historical versions of A and B, find the first solution that resolves the conflict, and then install that version.

The process described above sounds easy. All you need to do is find a conflict-free solution. However, this is an NP-complete problem. This means the problem cannot be solved in polynomial time. The complexity of this problem is the same as that of the Traveling Salesman Problem. Currently, global package managers use pseudo-solvers to address this issue.

In fact, an optimal solution may not even exist for this problem. For instance, a newer version of A might require an older version of C, while a newer version of B might require a newer version of C. In this case, you must either upgrade A or upgrade B. There is simply no such thing as an optimal solution. A pseudo-solver merely helps you obtain a feasible solution.

Destructive Upgrade and Downgrade

The problems with global package management go beyond dependency conflicts. Another significant issue is destructive upgrades and downgrades.

In the real world, it is highly likely that two different components will provide the same file. For example, both Docker and Docker Desktop provide Docker, but one is based on containerd while the other is based on virtualization. Even worse, they might write to the same file during installation and both attempt to delete this file during uninstallation.

In such cases, every installation, upgrade, downgrade, or uninstallation is essentially destructive, non-reversible, and non-atomic. Files are very likely to be overwritten.

For example, if you use Ubuntu's do-release-upgrade command, say to upgrade from 22.04 to 24.04, you will be faced with a 50-minute exam consisting of about 100 questions. The content of the exam is the package manager constantly asking you: a package has been upgraded, but its configuration file has been modified. What should be done now? Every Linux user should have experienced this pain.

Divide and Conquer

The core problem with global package management lies in the fact that package conflicts, once they occur, become extremely troublesome. A computer is typically used for a wide variety of tasks: frontend development, backend development, operations, gaming, office work, and learning... These activities can easily lead to a large number of packages being installed, resulting in conflicts.

Many people might think: if using a single global environment leads to conflicts, why not adopt a divide-and-conquer approach? For example, break a massive project down into a dozen smaller projects, and run each small project in an isolated environment—such as a separate folder, a container, or even a virtual machine—so that its packages cannot interfere with others. Wouldn't that solve the problem?

This idea is correct. The concept of divide and conquer is to break a large problem into smaller problems and solve them individually. In practice, this is exactly the mainstream approach in the industry: transforming monolithic applications into microservices. Each microservice runs in an isolated environment, ensuring that its dependencies do not affect others.

In Python, venv and conda; in Node.js, nvm; in Java, maven—all of these embody this approach. They isolate the dependency environments to avoid conflicts.

The Biggest Drawback of Divide and Conquer

For macOS users, the solution above will certainly be very familiar. macOS has a well-known folder: Applications. This folder stores all apps. Each app is an independent folder containing all the files for that app. This way, each app operates in an isolated environment and does not affect other apps. The approach here follows the same logic.

The benefit of this solution is that each app is independent and does not interfere with others. While using this divide-and-conquer approach can effectively reduce the likelihood of conflicts, the cost is also significant: if both A and B depend on C, then C must exist in at least two copies. As a result, disk space usage can become very large.

You might not feel the impact yet. Some statistics show that a typical Windows system for an ordinary user may contain over 30 copies of Electron. This is because whenever you install a software application developed with Electron, it requires an additional installation of Electron for you. Although Electron is not large and typical users can tolerate it, this becomes unacceptable for high-density computing scenarios.

Imagine a microservices-based data center where each service runs in a complete, isolated Linux environment. This means that for as many services as you have, you may need to maintain that many Linux images. Although container technology can deduplicate repeatedly used images, the problem still exists. Deduplication itself carries a significant cost, which we will discuss in more detail later when we get to file systems.

Monolithic

The concept above, which involves bundling all dependencies together, can mitigate this problem to some extent. We can refer to this approach as: Monolithic.

Although completely resolving dependency conflicts is difficult, bundling all dependencies together ensures that the dependencies are correct. This is also the mainstream practice for Windows and macOS.

Currently, the mainstream approach in data centers is to split applications into microservices, treat each part as a monolith, and use the simplest dependency management between these parts.

For example, each monolith explicitly declares its dependencies on other monoliths, including the allowed version ranges.

Therefore, Monolithic and microservices may sound like two entirely different design philosophies, but in reality, they apply a divide-and-conquer strategy to a complex problem, solving two distinct issues. If you wish, you can even split the architecture into more than two layers: three, four, or more.

Nix

In addition to the two approaches mentioned above, there is another approach: Nix.

Nix is a package manager. Its key characteristic is that it is a functional package manager. This means that packages in Nix are immutable. Once a package is installed, it cannot be changed. As a result, Nix ensures that installing one package does not affect other packages.

Another feature of Nix is that its package storage is flat. The system has a directory called /nix/store, and all packages are installed under this directory. Each package can only appear in one directory. This allows Nix to ensure that installing one package does not affect other packages.

However, this is different from Apple's Application model. Nix is not monolithic. A package in nix/store does not contain its dependencies!

Nix's build process is deterministic (Slide 12 of the PPT). This means that given the same inputs, Nix always produces the same outputs. This is achieved by building packages in a sandbox, ensuring that only explicitly specified dependencies are visible during the build process, rather than the system's global state (Slide 15 of the PPT). This method avoids inconsistencies in build results caused by different environments.

In Nix, the smallest build unit is called a derivation (Slide 13 of the PPT). Each derivation is a function describing how to build a package. All inputs must be explicitly specified, and the build takes place in a sandbox. This allows Nix to ensure that the output of each derivation is deterministic and that its results are predictable.

The Nix Store is a read-only storage area that can only be modified via Nix commands (Slide 14 of the PPT). The output path of each derivation includes a hash value based on its contents. This ensures that any changes to inputs or the build process are reflected in the hash value, thereby preventing package conflicts.

Nix also supports binary caches (PPT page 19). Because Nix can compute the output hash before building, it can easily cache build results and serve these caches via a file server. This significantly speeds up package installation, as users can retrieve pre-built packages directly from the cache without having to rebuild them every time. In other words, the package download process in Nix is quite interesting: compiling and downloading will always yield the same result. Therefore, your local machine effectively becomes a Nix cache.

The installation and uninstallation process in Nix is atomic. When installing a package, if its dependencies already exist in the Nix Store, they are used directly; otherwise, they are built and stored in the Nix Store. When uninstalling a package, unneeded packages are removed via the garbage collection mechanism.

NixOS is an operating system based on Nix that integrates package management with system configuration (PPT page 26). In NixOS, system configuration is also managed using Nix. This means that users can declaratively describe the system configuration, and NixOS will automatically build and deploy the system based on these configurations (PPT page 28).

In summary, Nix solves many problems associated with traditional package management through its unique functional package management model. Its deterministic builds, package isolation and sharing, atomic installation and uninstallation, and robust binary caching make it a very powerful package management tool.

Nuget

NuGet is a package manager designed by Microsoft for .NET development. As a package manager, it shares the same issues as other package managers. However, NuGet's approach to resolving these issues is quite clever. It leans more towards a Nix-like philosophy. Although NuGet does not guarantee package immutability, it also uses dynamic linking to resolve package conflicts. Within a single project, NuGet acts as a Monolithic package manager.

For example, when a .NET application needs to reference a package, it requests it from NuGet. NuGet downloads it from the official servers to a global path, such as ~/.nuget/packages/. The final storage path includes the package name and version, ensuring that multiple versions of the same package do not conflict.

When the project actually uses the package, NuGet provides the specific version required. This avoids redundant downloads and resolves dependency conflicts. The approach is similar to Nix in that it stores all packages in a centralized location for shared use, yet also resembles a Monolithic model by bundling packages together to prevent conflicts.

Of course, for a single .NET project, it is impossible to depend on both A and B if A and B depend on different versions of C. This would cause serious errors during the final packaging stage. We sometimes use Binding Redirect to mitigate this issue, allowing the runtime to tolerate the different versions of the package. However, this problem cannot be fundamentally resolved.

Other Package Managers

Above, we discussed apt, dnf, pip, npm, maven, nix, nuget, and others. Each has its own pros and cons, but they share the same core idea: installing dependency packages to a specific location and then allowing users to use them.

There are also tools that look like package managers but are not, because they do not solve dependency issues. For example: winget. To publish a package on winget, you only need to provide a download URL. At best, winget is just a downloader that indexes a large number of package download URLs, after which you are responsible for downloading and installing them yourself. It is completely unable to resolve dependency issues. As for uninstalling, upgrading, or downgrading, these are all handled by the installation programs of the packages themselves.

snap and flatpak are also methods for resolving dependency conflicts. They use the squashfs file system to bundle all dependencies into a single file. This means a snap package constitutes a complete environment. The benefit of this approach is that snap packages are immutable and will not affect other packages. The drawbacks are, of course, very clear: wasted disk space, duplicate downloads of packages, and potential conflicts in configuration files.

Summary

Having gotten this far, we are left facing a fact that is not entirely pleasant: package management is, in reality, something for which we have yet to find a universal solution. Although Nix is a fairly robust approach, its counterintuitive nature has prevented it from achieving widespread adoption. In the industry, more often than not, we still build monolithic package management systems, combined with Docker and virtual machines, using a divide-and-conquer strategy to resolve dependency conflicts.

What appears to be a simple act of downloading something from an app store conceals a great deal of underlying complexity. Every day, as we swipe through our phones and browse the list of installed applications, we are presented only with a beautifully polished façade crafted by modern software engineering: a world where we can mindlessly browse the store, trusting the system to handle everything for us. But the day we decide to distribute software ourselves, we will quickly realize that the world is far from so simple.