3 ms·

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

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.

PhilipRoman 3y ago
The Arch Way of doing things involves only ever providing a single version of each package.
- chriswarbo 3y ago
  But which version should they provide? The dependency resolution still needs to happen somewhere ;)
  - PhilipRoman 3y ago
    The latest one obviously; any issues are left to the user as an exercise
    - menaerus 3y ago
      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?
      - rcxdude 3y ago
        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.
        menaerus 3y ago
        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?
        rcxdude 3y ago
        "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_upgrades_are_unsupported https://wiki.archlinux.org/title/System_maintenance#Partial_...
      - assbuttbuttass 3y ago
        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-2.2 https://packages.debian.org/bookworm/guile-3.0 https://packages.debian.org/bookworm/guile-3.0
        menaerus 3y ago
        From https://fedoraproject.org/wiki/Features/DNF#Including_libsolv_in_Fedora 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 > ...
    - skummetmaelk 3y ago
      Interesting though that Arch users on the whole seem to experience less system problems than for example Ubuntu users.
      - rcxdude 3y ago
        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).
davexunit 3y ago
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.
- di4na 3y ago
  Which is a complex way to say that humans do it by hand.
  - chriswarbo 3y ago
    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).
  - rcxdude 3y ago
    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.
  - davexunit 3y ago
papercrane 3y ago
RPM based distributions typically use dnf, which uses the SAT solver library libsolv https://github.com/openSUSE/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/external-dependency-solver-protocol.md https://salsa.debian.org/apt-team/apt/-/blob/main/doc/extern...
j16sdiz 3y ago
Debian use a SAT solver for that.

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.

PhilipRoman 3y ago

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

chriswarbo 3y ago
But which version should they provide? The dependency resolution still needs to happen somewhere ;)
- PhilipRoman 3y ago
  The latest one obviously; any issues are left to the user as an exercise
  - menaerus 3y ago
    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?
    - rcxdude 3y ago
      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.
      - menaerus 3y ago
        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?
        rcxdude 3y ago
        "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_upgrades_are_unsupported https://wiki.archlinux.org/title/System_maintenance#Partial_...
    - assbuttbuttass 3y ago
      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-2.2 https://packages.debian.org/bookworm/guile-3.0 https://packages.debian.org/bookworm/guile-3.0
      - menaerus 3y ago
        From https://fedoraproject.org/wiki/Features/DNF#Including_libsolv_in_Fedora 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 > ...
  - skummetmaelk 3y ago
    Interesting though that Arch users on the whole seem to experience less system problems than for example Ubuntu users.
    - rcxdude 3y ago
      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).

davexunit 3y ago

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.

di4na 3y ago
Which is a complex way to say that humans do it by hand.
- chriswarbo 3y ago
  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).
- rcxdude 3y ago
  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.
- davexunit 3y ago

papercrane 3y ago

RPM based distributions typically use dnf, which uses the SAT solver library libsolv https://github.com/openSUSE/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/external-dependency-solver-protocol.md https://salsa.debian.org/apt-team/apt/-/blob/main/doc/extern...

j16sdiz 3y ago

Debian use a SAT solver for that.