Hacker News Reader

Comment by menaerus | Hacker News Reader

Does anyone know how Linux system package managers solve this problem, SAT or something more? It's also more difficult problem because of having to maintain ABI compatibility.

View on HN

RPM based distributions typically use dnf, which uses the SAT solver library libsolv https://github.com/openSUSE/libsolv.

I'm not 100% sure if this is current, but APT uses (or used) a heuristics search, but it is possible to configure it to use an external solver instead. See https://salsa.debian.org/apt-team/apt/-/blob/main/doc/extern...

Modern functional package managers like Guix and Nix do not use SAT solvers because they understand that package variants can differ by a lot more than just their version number. The package graph is explicit in those systems and there are no constraints to solve for.

Which is a complex way to say that humans do it by hand.

Sometimes; but there are also a bunch of "foo2nix" tools which can generate "packages" (individually, or sets of inter-dependent definitions) from other formats[0]. It's basically just generating (parameterised/overridable) "lock files". That's how Nixpkgs can contains massive collections like haskellPackages, pythonPackages, nodePackages, etc. (plus all the various copies with different compilers/interpreters/flags/etc., thanks to the overriding). It can still require some manual tweaking[1], but CI makes that easier, e.g. translate a few thousand definitions; send to CI; mark all those which fail to build as broken.

[0] Actually, they generate functions which return derivations; Nix doesn't have a concept of "package", although the term gets thrown around informally.

[1] Since those other formats are woefully inadequate at representing dependencies; not just the required compilers/interpreters themselves, but especially stuff like third-party C libraries, binaries that are assumed to be in $PATH, etc.

PS: Those "foo2nix" tools don't need to be manually invoked; they can just be another derivation, whose result gets imported (via the import-from-derivation feature). That's how I tend to manage JVM projects (using mvn2nix).

yes, but they also don't have the constraint that there can only be one version of a given dependency installed. So once you solve the dependencies for one package you have a solution for any combination of packages, unlike with traditional linux package managers.

I get the sense that you think this approach is inferior, but package managers based on version constraint solvers can't begin to approach the level of automation and reproducibility that exists in functional package managers. Lots of interesting stuff is not done by hand but through transformation with functions.

The Arch Way of doing things involves only ever providing a single version of each package.

But which version should they provide? The dependency resolution still needs to happen somewhere ;)

The latest one obviously; any issues are left to the user as an exercise

That's quite surprising but I haven't delved into this topic basically never.

Is it true that yum (dnf), apt and zypper took the approach by having SAT solvers under the hood? If so, why does arch take a different route?

Because it's easier for the developers. Arch's philosophy very much based on reducing the workload for maintainers. So they package things as close to vanilla as possible (and expect the users to make any adjustments, like enabling any services), package only one version, and have a rolling release which doesn't support older versions or even partial upgrades, so maintainers only really have to worry about making things work with the current version. They were one of the first distros to go exclusively systemd for the same reason of it allowed them to ditch their current init scripts and supporting both is a huge burden.

Interesting. If I have a program A and if I run ldd on it, it outputs dep1, dep2, dep3 and dep4. Now I do the same on program B and ldd shows that it depends on dep1 and dep2, the same ones as from program A.

If I want to update both of them, in the context of program A that would be partial update which AFAIU does not support? But in the context of program B that would be a "full" update. I'm not sure I understand what arch is going to do in this case?

"partial update" in this case means you update some packages without updating all of them (i.e. do 'pacman -Sy' followed by installing or upgrading any individual package). Usually what will happen is pacman will update those packages and any dependencies but not update any other packages will may now have been broken by that update . So if you were to pacman -Sy <program A> in this case then program B would probably be broken, and vice-versa (assuming any of the common deps have updated as well). If you were to update both then they might be fine but something else may break.

https://wiki.archlinux.org/title/System_maintenance#Partial_...

I do not think yum or apt use a SAT solver. Instead, if they need multiple versions of a package, they just give them different names

https://packages.debian.org/bookworm/guile-2.2

https://packages.debian.org/bookworm/guile-3.0

From https://fedoraproject.org/wiki/Features/DNF#Including_libsol...

> DNF is a fork of Yum 3.4 that uses libsolv via hawkey for a backend. The main goals of the project are:

> using a SAT solver for dependency resolving allowing us to eventually use the same solver in rpm too > ...

Interesting though that Arch users on the whole seem to experience less system problems than for example Ubuntu users.

a lot of that comes from the expectation that the user gets their hands dirty in actually configuring most packages in the first place. There's relatively little magic in arch. So both there's less stuff to break and when something does break the user usually can figure out the issue more easily (this is also helped by the selection pressure that is implied by the first expectation).

Debian use a SAT solver for that.

Reply on news.ycombinator.com