User talk:Prabuanand

Why apk-tools is different than other package managers

apk add and apk del manipulate the desired state

In traditional package managers like dnf and apt, requesting the installation or removal of packages causes those packages to be directly installed or removed, after a consistency check.

In apk, when you do apk add foo or apk del bar, it adds foo or bar as a dependency constraint in /etc/apk/world which describes the desired system state. Package installation or removal is done as a side effect of modifying this system state. It is also possible to edit /etc/apk/world with the text editor of your choice and then use apk fix to synchronize the installed packages with the desired system state. Because of this design, you can also add conflicts to the desired system state. For example, we recently had a bug in Alpine where pipewire-pulse was preferred over pulseaudio due to having a simpler dependency graph. This was not a problem though, because users could simply add a conflict against pipewire-pulse by doing apk add !pipewire-pulse.

Another result of this design is that apk will never commit a change to the system that leaves it unbootable. If it cannot verify the correctness of the requested change, it will back out adding the constraint before attempting to change what packages are actually installed on the system. This allows our dependency solver to be rigid: there is no way to override or defeat the solver other than providing a scenario that results in a valid solution. Verification and unpacking is done in parallel to package fetching

Unlike other package managers, when installing or upgrading packages, apk is completely driven by the package fetching I/O. When the package data is fetched, it is verified and unpacked on the fly. This allows package installations and upgrades to be extremely fast.

To make this safe, package contents are initially unpacked to temporary files and then atomically renamed once the verification steps are complete and the package is ready to be committed to disk. apk does not use a particularly advanced solver

Lately, traditional package managers have bragged about having advanced SAT solvers for resolving complicated constraint issues automatically. For example, aptitude is capable of solving sudoku puzzles. apk is definitely not capable of that, and I consider that a feature.

While it is true that apk does have a deductive dependency solver, it does not perform backtracking. The solver is also constrained: it is not allowed to make changes to the /etc/apk/world file. This ensures that the solver cannot propose a solution that will leave your system in an inconsistent state.

Personally, I think that trying to make a smart solver instead of appropriately constraining the problem is a poor design choice. I believe the fact that apt, aptitude and dnf have all written code to constrain their SAT solvers in various ways proves this point.

To conclude, package managers can be made to go fast, and be safe while doing it, but require a careful design that is well-constrained. apk makes its own tradeoffs: a less powerful but easy to audit solver, trickier parallel execution instead of phase-based execution. These were the right decisions for us, but may not be the right decisions for other distributions.

Source: https://ariadne.space/2021/04/25/why-apk-tools-is-different-than-other-package-managers/

A high level view of the moving parts

Our adventure begins at the /etc/apk/world file. This file contains the basic set of constraints imposed on the system: every constraint listed here must be solvable in order for the system to be considered correct, and no transaction may be committed that is incorrect. In other words, the package management system can be proven to be in a correct state every time a constraint is added or removed with the apk add/del commands.

Note I used the word transaction there: at its core, apk is a transactional package manager, though we have not fully exploited the transactional capabilities yet. A transaction is created by copying the current constraint list (db->world), manipulating it with apk_deps_add and then committing it with apk_solver_commit. The commitment phase does pre-flight checks directly and returns an error if the transaction fails to pass.

This means that removing packages works the same way: you copy the current constraint set, remove the desired constraint, and then commit the result, which either errors out or updates the installed constraint set after the transaction is committed. A deeper look into the solver itself

As noted above, the primary entry point into the solver is to call the apk_solver_commit function, which at the time that I am writing this, is located in the apk-tools source code at src/commit.c:679. This function does a few pre-flight checks and then calls into the solver itself, using apk_solver_solve, which generates the actual transaction to be committed. If there are errors, the generated transaction is discarded and a report is printed instead, otherwise the generated transaction is committed using apk_solver_commit_changeset.

In essence, the code in src/commit.c can be thought of as the middle layer between the applets and the core solver. The core solver itself lives in src/solver.c and as previously noted, the main entry point is apk_solver_solve, which generates a proposed transaction to satisfy the requested constraints. This function lives at src/solver.c:1021, and is the only entry point into the solver itself.

The first thing the solver does is alphabetically sort the constraint set. If you’ve noticed that /etc/apk/world is always in alphabetical order, this is a side effect of that sorting.

Once the world constraints (the ones in /etc/apk/world) are alphabetically ordered, the next step is to figure out what package, if any, presently satisfies the constraint. This is handled by the discover_name function, which is called recursively on every constraint applicable to the system, starting with the world constraint.

The next step is to generate a fuzzy solution. This is done by walking the dependency graph again, calling the apply_constraint function. This step does basic dependency resolution, removing possible solutions which explicitly conflict. Reverse dependencies (install_if) are partially evaluated in this phase, but complex constraints (such as those involving a version constraint or multiple solutions) are not evaluated yet.

Once basic constraints are applied to the proposed updated world, the next step is to walk the dependency graph again, reconsidering the fuzzy solution generated in the step above. This step is done by the reconsider_name function, which walks over parts of the dependency graph that are still ambiguous. Finally, packages are selected to resolve these ambiguities using the select_package function. Afterwards, the final changeset is emitted by the generate_changeset function. A deep dive into reconsider_name and select_package

As should hopefully be obvious by now, the really complicated cases are handled by the reconsider_name function. These cases include scenarios such as virtual providers, situations where more than one package satisfies the constraint set, and so on. For these scenarios, it is the responsibility of the reconsider_name function to select the most optimal package. Similarly, it is the responsibility of the select_package function to check the work done by reconsider_name and finalize the package selection if appropriate by removing the constraint from the ambiguous list.

The primary purpose of the reconsider_name function is to use discover_name and apply_constraint to move more specific constraints upwards and downwards through the dependency graph, narrowing the possible set of packages which can satisfy a given restraint, ideally to one package or less. These simplified dependency nodes are then fed into select_package to deduce the best package selection to make.

The select_package function checks each constraint, and the list of remaining candidate packages, and then picks the best package for each constraint. This is done by calling compare_providers for each possible package and until the best one is found. The heuristics checked by compare_providers are, in order:

   The packages are checked to see if they are NULL or not. The one that isn’t NULL wins. This is mostly as a safety check.
   We check to see if the user is using --latest or not. If they are, then the behavior changes a little bit. The details aren’t so important, you can read the source if you really want to know. Basically, in this step, we determine how fresh a package is, in alignment with what the user’s likely opinion on freshness would be.
   The provider versions are compared, if applicable. Highest version wins.
   The package versions themselves are compared. Highest version wins.
   The already installed package is preferred if the version is the same (this is helpful in upgrade transactions to make them less noisy).
   The provider_priority field is compared. Highest priority wins. This means that provider_priority is only checked for unversioned providers.
   Finally, the earliest repository in /etc/apk/repositories is preferred if all else is the same.

Hopefully, this demystifies some of the common misconceptions around how the solver works, especially how provider_priority works. Personally, I think in retrospect, despite working on the spec and implementing it in apk-tools, that provider_priority was a mistake, and the preferred solution should be to always use versioned providers (e.g. provides="foo=100") instead. The fact that we have moved to versioning cmd: providers in this way demonstrates that provider_priority isn’t really a good design. Source: https://ariadne.space/2021/10/31/spelunking-through-the-apk-tools-dependency-solver/

https://git.alpinelinux.org/aports/tree/scripts