Debian 为 APT 重装工具以实现更优的依赖管理_AI阅读总结 — 包阅AI

“The stuff we got we don’t need, and the stuff we need we don’t got,” an old Army supply sergeant used to bitch at us back in our military days. And certainly these days, many a system administrator is echoing a similar sentiment about all the open source dependency packages on their systems.

The Debian Linux distribution is about to get a long-awaited upgrade to its Advanced Package Tool (APT), which should cut the time it takes to update needed dependencies and allow admins to make better decisions about which software packages to maintain.

The recent release of APT 2.9.3 comes with a new dependency solver, Solver3, currently as an alpha, or experimental release. A beta version should be ready for an opt-in production release for the planned February 2025 Trixie release of Debian, and, if all goes well, it will be the default solver in the following “Forky” release of Debian 14 (now scheduled for the next August).

Debian’s original solver was created over two decades ago and was state-of-the-art for its time. Indeed, APT’s sophistication was a selling point for Debian, allowing other distributions such as Ubuntu to be built on top of Debian. But can APT maintain its excellence in complex, cloud native Linux environments?

What Is a Solver?

Debian core contributor and Ubuntu engineer Julian Andres Klode has been working on the Solver3 project in his free time, on and off, since 2010, and shared some of his insights in a presentation Tuesday at the DebConf/24, being held this week in Busan, South Korea.

A solver is an algorithm for determining which packages should be added as dependencies when a new application package is added into the environment, as well as removing those dependencies no longer required by any package.

The workloads of Linux have grown considerably over the past few decades, however, and package management has grown correspondingly more complex.

Klode found that on standard Intel machines, 45% of any build time is spent rebuilding the dependency tree, thanks to APT’s insistence on checking the entire dependency tree.

“So what happens is that it actually traverses all the dependencies in the archive, and checks if everyone is satisfied or not. It’s just an enormous waste of time, which worked, I guess, 26 years ago, because there weren’t a lot of packages and even much less dependencies in the archive,” he said. “But these days, things are way too complicated to do every dependency in the archive.”

Moreover APT has revealed some quirky behaviors in this large-scale environment, Klode noted. Downgrades, for instance, do not work entirely as predicted, in terms of maintaining the proper dependencies. It can remove packages that do not need to be removed, or upgrade packages that do not need to be upgraded.

“I think most of you will have probably seen those issues,” Klode told the audience.

APT’s new solver, in contrast, only takes up 15% of the build time, which should amount to a 40% improvement in build times, Klode estimated.

The new solver comes with a number of time-saving features. For one, it is policy not to remove manually-installed packages. It will offer an explanation of why a package is being upgraded or removed, retracing the path the solver took in order to solve the package. The solver can be instructed (apt install –fix-policy) to ignore all packages that were automatically installed, maintaining the package’s overall integrity.

“And then it essentially will pick every package as if only the manually installed packages were installed,” Klode said. “Which means that when you run the command, you will essentially get the same set of installed packages as everyone else that would get with a fresh install the same set of manually installed packages.”

The Long Road to Solver3

In his talk, Klode described trying a number of different solutions before arriving at the current configuration. Each had its own mathematical underpinning — and its limitations.

First, he tried to borrow an external solver from another project. He tried picosat, then being used by FreeBSD. Essentially, the dependency problem is a sat (satisfiability) problem in logic.

He found working with an external library to be limiting, however.

“It could find solutions that are correct, but not solutions we actually want,” Klode said. It can’t generate recommendations, for instance (by default, Debian installs recommendations, but this option can be turned off).

His second path involved describing the dependency tree as a “pseudo-Boolean” optimization problem.

“Essentially, you specify global optimization criteria — such as the number of remove packages, the number of change packages, or the number of packages that will be newly installed, or the number of packages and are not up to date — then you can lexicographically combine those or use another way to combine them to get an optimal result or to get the optimization function that you want to minimize or maximize,” Klode explained.

Klode implemented Boolean optimization in multiple tries throughout the past decade: using Clasp and a Python script, using an internal class library, and as a Microsoft Research library for C. All three had issues, due to package sizes, unusual optimization choices, and over-reliance on global optimization. For instance, a search function in the Plasma desktop has multiple database options, including MySQL and SQLite but the optimization would default to SQLite.

“It was very surprising and not at all what we wanted,” Klode said.

Next up, Kode tried a graph approach.

“Each node in the graph can have one or more packages, and you can have edges between those nodes,” Klode said. Each edge would represent a set of packages.

Introducing Solver3

Although Klode never implemented a graph-based solver, the work did inform what would become the final implementation, which was called “fairly trivial.”

Here, all the dependencies are placed in a priority queue, such that the dependencies with the fewest choices come first. It is similar to but simpler than what in academia is known as a DPLL Sat Solver, an algorithm for solving propositional sat logic (often used in AI).

There is still considerable work to be done, Klode noted.

“This is going to be quite powerful, but we want to restrict it a bit to not pick solutions that actually don’t make sense,” he said. Packages for multiple architectures should be limited to only those architectures being used. Manually packages should only be removed upon explicit request, and a replacement package should designated when appropriate. Obsolete packages should also be considered only as a last choice.

More performance tests, comparing Solver3 with the traditional solver, will also need to be conducted, once Solver3 is in production.

Klode also wants to bring the Solvert3 more in line with the industry standard, MiniSat, which offers best practices around dealing with conflicts. Anotherother popular Linux package manager, RPM, used by Red Hat and others, was developed by SUSE using MiniSat as a guide.