Never thought of dependencies as a SAT issue before... Makes sense once I think about it.
I always imagined dependencies as a tree.
If I have dependency x which uses foo 1.0 and dependency y which uses foo 2.0, isn't it possible to get an unsatisfiable rule?
Why do we need a universal version of foo? Cant we just use both foo 1.0 and 2.0? When being used by x, we use foo1.0 and when being used by y, use foo 2.0
NPM actually works like this afaik (you can have multiple versions of a given package in tree).
Vendoring is another way to work around the single-version per name requirement. It's mainly problematic with shared types and when they "escape" over the API boundary (ie. are exposed somehow).
> Why do we need a universal version of foo? Cant we just use both foo 1.0 and 2.0? When being used by x, we use foo1.0 and when being used by y, use foo 2.0
You need language-level support for your packaging for this, so that the compiler or runtime can bind a call to foo.bar() to foo 1.0 when the call happens in x, and foo 2.0 when it happens in y.
Dependencies are a graph, not a tree. Say z depends on x and y, which version of foo do you use?
Requiring a single version makes certain things a lot easier to deal with, because not all dependencies are actually inherited by another. If foo is an executable then sure, you can have multiple versions and it's no issue. If foo is a library then you might need to fail because there is no solution that works. Or you might not, it depends.
Author here. As others have commented, some package managers allow multiple versions of the same dependency. Conda doesn't, and I wanted to stick to the Conda rules in the article ;)
"Dependency resolution is something programmers usually take for granted. Be it cargo, npm, or whatever package manager you use, no one is actually surprised when this black-box figures out, all by itself, the specific set of packages that should be installed."
I am personally still surprised npm/node etc. both work and are used unsarcastically.
I think the need for a Magic Solver suggests weaknesses in how we package and load dependencies. Every piece of running code should have its own space for dependencies. If most of them happen to coincide, then good: we can save a lot of RAM. But if not, also good.
That’s what containers do - package the dependencies with a piece of running code. That’s also one of the main reasons for their quick, wide adoption, even by conservative enterprises.
But this gets more challenging as the granularity of what’s being packaged reduces. You can see this even in the container case: consider a container that depends on a particular version range of another container. For any possible solution to this, there are disadvantages which make it untenable in some situations.
There’s no good general solution to this other than being explicit about the version dependencies and solving the dependency issues when deploying, whether manually or automatically. A automated solver helps with that.
Btw, you can see something like what you described in Java programs built with Maven (for example). Run Maven’s dependency:tree function on any non-trivial program and you’ll see different versions of the same package appearing over and over, because each package does have its own (logical) space for dependencies.
But Maven still has a version solver built in, and even with your proposed solution plus a solver, you can find plenty of articles on the web saying things like “Maven dependency conflicts can be really hard to solve.” The reason for that is when it fails, it’s because it’s encountered a difficult or impossible situation that (currently) requires human intervention.
Not at all. They do exactly what you were suggesting. If you think they’re a bandaid, then you’d need to explain why your own suggestion isn’t a bandaid.
How many container systems can share dependencies in both RAM and disk, and do all the same kinds of IPC, while also sharing system daemons and all that?
The way Android and more recent Windows do things is my favorite solution so far.
All dependencies included in static packages, not actually containerized, and with all the heavy lifting done by things built right into the OS, always there, and specifically designed to be used that way, without much emphasis on lots of separate daemons, at least not on desktop.
Even just saying "The OS always has this daemon" isn't enough, because so many services are designed to be configured specifically for a deployment and there isn't any one size fits all solution.
Even something as simple as MQTT has a ton of ways to configure it, and there's no way for a client to even query what permissions it has and what other clients are on what available servers, it all has to be manually set up.
Containers aren't perfect, of course. But they do exactly what the other commenter was asking for: "Every piece of running code should have its own space for dependencies."
Could it be done better? Sure. But there are tradeoffs. You mentioned Android, where the obvious tradeoff is that the entire ecosystem revolves around the Dalvik VM. That approach isn't really practical right now for more general OSes like Linux and Windows.
I'm not so sure the whole OS revolving around Dalvik is really a problem. You can still run C++ native code to accelerate specific things.
Obviously it's a problem because of all the millions of man hours of existing stuff for other OSes, but in theory, I don't see why a managed code only ecosystem wouldn't work.
I could even see it being faster than current OSes, in some future imaginary world where Android had a MakeHardwareAcceleratedCDNServer(folder, port, config).
So many applications(Obviously not all, but a fair number) out there are fairly boring, probably shouldn't even be written at all, and probably could be covered with a small set of high level primitives.
If we had kept on thinking the way we did in the early days of Windows, we'd probably have more things like Excel, abstractions that cover insane numbers of use cases without plugins or anything.
The problem is when you are dealing with dependencies that are "vocabulary terms". These are required to be common. In Rust, one example would be serde and I'm assuming pydantic would similary apply.
For Rust, these can also impact build times so people actively work to keep down what dependencies can be duplicated which are semver incompatible versions.
I don't understand the purpose of package managers in general during the development where you have the total ownership of your code, 3rd party dependencies and whole build process.
I had a privilege to use conan on semi-large codebase - what a clusterfuck that is. I can't imagine a single scenarios why I would be using it.
Indeed but this comes back to opting to write spaghetti apps by default.
For example we're talking in English right here, and it's a rich language we can express a whole lot in. It has no version although it's slowly updated over time. But it's mostly the same version around the world, with some local differences. We still understand each other. Despite our minds may be vastly different, we can express each other in this language. Same goes even for language models now.
Imagine we had something as common as JSON, but more in-depth so it can be used as direct representation in memory, and this was the lingua franca not only between servers, but between libraries, apps, and even objects within an app.
Then our dependency entanglement issue would also not exist.
What we did was a choice. It was a lazy choice, ignorant choice. A choice that introduces instant tech debt. And dependency conflicts are one of the results of this choice.
> What we did was a choice. It was a lazy choice, ignorant choice.
This is utter nonsense. If you think you know how to do this better, there are billions or trillions of dollars waiting to reward you.
Intelligent creatures like humans can fairly easily compensate for communication mismatches. That's enormously more difficult for us to program computers to do.
We've only just stumbled on technology that might help with that - the latest generation of language models - but it'll probably take decades of work by everyone involved, on the entire planet, to be able to get to a point that resembles what you're imagining as the non-lazy, non-ignorant choice. Which proves that laziness and ignorance are not the issue.
It doesn't matter what the common language is, if library developers enjoy breaking changes like they seem to, they'll make them. They'll just remove features, change the way stuff works, or make trivial changes like renaming stuff...
Android has API levels where they don't do that, but that's because Google can afford to provide almost everything themselves.... random npm and pypi contributors don't seem interested in keeping compatibility.
So some kind of smart version system or container or something seems to be needed.
Although, I think in a perfect world our standard libraries would be rich enough that we would not need many libraries, and the ones we did need would mostly only be a few hundred lines at most, and we'd basically never have libraries depending on other libraries or any tangled webs like that.
Maybe I'm just spoiled in Python, but library devs in the Python ecosystem seem highly disciplined in this respect. Packages tend to be forward-compatible for years, even with very active development cycles, and breaking changes tend to be treated carefully and announced with plenty of advance warning.
That said, I don't understand this mentality that libraries can never change. Eventually things need to change. It's impossible to predict all future requirements.
> Imagine we had something as common as JSON, but more in-depth so it can be used as direct representation in memory, and this was the lingua franca not only between servers, but between libraries, apps, and even objects within an app.
There are and have been several attempts to do things like this. One of them is the Arrow library for "arrays" as used in scientific computing, machine learning, etc. It's a huge amount of work.
Ideally, one would also prefer higher versions of each package. How much longer would it take to find a solution with the guarantee that there's no other solution with all packages at least as good?
Unfortunately, it is sometimes not even possible to say which solution should be preferred because different branches lead to different sets of packages having higher versions. There is not really an "ultimate" heuristic to determine which of the two sets is better.
However, users are always encouraged to add more constraints to shape the solution, and packagers encouraged to take good care of the metadata.
At prefix we are quite interested in figuring out how we can help packagers to determine e.g. compatibility ranges more correctly by doing static analysis and such things.
Author here. I glossed over this in the article, but the solver is actually privileging higher versions as you suggest. In the "set" step, when we arbitrarily set a variable to true, we have a heuristic that picks the highest possible version of the package.
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.
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.
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).
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.
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.
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.
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).
I think, this is going to be the third go at the problem? The first two were hands-down awful leading to creation of Mamba. But speeding things up is only part of the solution here.
Conda package ecosystem has a bunch of issues that are related to the format and the repositories providing packages as well as on the policy for accepting packages into those repositories. They tried to solve too many problems at once, probably, w/o even realizing what kind of problem they are attacking.
Here's a major problem with Conda ecosystem, the way I see it: package developers are encouraged to produce very "precise" dependency requirements because this makes installation process go faster and ensures less wiggle room for untested dependency combination. This, in turn, results in proliferation of package versions, all of which declare themselves as incompatible and non-interchangeable with many others.
On top of this, beside providing just the Python packages, Conda, ambitiously, wants to also provide shared libraries, which blows up the minimum installation to an enormous size, including the number of packages that need installing.
So, being a Conda package maintainer, you will face a dilemma: do you want your users to be able to install the package in acceptable time (at least under 10 minutes...) or work towards compatibility with multiple different versions of other packages the users might need for other reasons in the same environment (and your installation times start shooting through the roof). In my experience, the longest successful Conda install took about a day (i.e. close to 24 hours). It may take few days for Conda to fail to install (due to imaginary or real conflict).
Now, add to this the existence of multiple sources for different packages (i.e. "channels"). Different channels may, and actually quite often do provide different unrelated other packages in their channel, but the users cannot specify the channel when requesting to install a package on per-package basis. So, the solver needs to guess somehow which channel to prefer as a source of any given package. The problem is that while the package version found in that channel might be the same, the requirements for that package might differ between channels.
So, while aiming at providing a lot of possibly useful features, Conda programmers programmed themselves into a corner with no good way out.
Several things might help, but none will ultimately solve the situation.
* Package bundles (or meta-packages, like they are called in some Linux distributions) will cut significantly on the work a solver needs to do. A lot of the basic (shared libraries) packages are, essentially, always the same in each install.
* LTS curated channel snapshots. I.e. provide a very large collection of packages that are verified to all work together, but unlike the meta-packages need not be installed together.
* Incorporate channel into version specification, especially when specifying package dependencies so that maintainers were required to specify the source of their dependencies when submitting their package.
* There are a bunch of (very) infrequently used options in the current solver that can be safely removed, but they add to the complexity and the time the solver spends in various "impossible" scenarios.
Let me try to reply to you (as one of the authors of mamba and as a conda-forge core dev):
Mamba has solved (seemingly successfuly) many problems of conda being slow. It's used by default in conda-forge, the largest conda repository out there.
Asking packagers to add upper bounds is less of a speed-hack vs. just the correct thing to do. What's interesting about conda-forge is that upper bounds can also be added later on via a "repodata patch". They really just serve to get users packages that are actually compatible.
The kind of "freak solves" are not a thing anymore with mamba.
I agree with you that multiple channels present problems. Channels that explicitly inherit from each other work quite well together (e.g. bioconda and robostack channels extend conda-forge), but the Anaconda main (defaults) channel and conda-forge do not work well together – on the metadata and ABI level. For this reason we encourage users to never mix those two.
At prefix.dev we do want to make it easy to build "on top of" conda-forge in the future.
I think most issues on your list that follows at the end are non-issues once you start to use mamba. And I would encourage you wholeheartedly to give micromamba a try (for a really fast, single-binary experience with no base env and slim installation) or pixi (again, no base env, just a Rust binary).
Asking packagers to add upper bounds is less of a speed-hack vs. just the correct thing to do. What's interesting about conda-forge is that upper bounds can also be added later on via a "repodata patch".
I'm glad upper bounds can be updated, that definitely seems like the right approach. As a challenge on "just the correct thing to do", how should someone releasing a package using pandas specify an upper bound? Many basic dataframe uses will work just fine with pandas 3, whenever that happens. Some dataframe uses will break even in future minor releases. It's not clear to me that packagers can reliably predict that future.
Another example of upper bounds causing pain: I mostly use poetry which unfortunately makes overrides extremely hard. A bunch of small Django packages work fine in Django 4 but haven't been updated in years and specify they only work for Django 3.x releases. The poetry folks say it's a packager problem, the packagers never respond to a PR, and off I go to make an internal fork of yet another library.
I don't really use conda or mamba for my own things. My interaction with these is in supporting others who need to use a package that I help develop. So, even if mamba works better (as in faster), it doesn't help me, as my goal is to make sure the package installs with what the users will have.
Knowing my audience, it's hard to get them to install anything, no matter how beneficial to them. Also, to their defense, any additional step they need to make when installing is an extra failure point, or at least adds more labor and confusion to the process most users see as tedious and uninteresting -- setting their environment.
So, unless mamba replaces conda, I still need to support conda.
Anyways. The biggest problem isn't even the speed. It's the conceptual problem. Both mamba and conda are pushing package maintainers towards very (unnecessarily) precise dependency version specification. This creates a lot of interoperability problems. Software goes "stale" very quickly. Since this is often used in scientific setting, the research reproducibility suffers a lot from this.
The blame is only partially with mamba / conda. The other bad thing that is happening in this environment is the lack of standards. Even if dependency on anything below minor version was prohibited, it would slow down the software rot, but not by much. Minor Python versions go stale after about four iterations, which is something like four years. Meaning that software that was written five years ago, if it wasn't maintained during that time is in most likelihood unusable today.
Yet another problem is the lack of organization in this environment. Enterprise Linux distributions are trying to ensure relative stability of the system they provide to the customer by testing third-party packages provided with the system together with the system. Nobody does anything comparable to it in Python world. This results in situations where installation performed from the same requirements days apart installs different packages (and of course you notice it when things start to break as a result). Even worse, when things don't immediately break, but the results of the research start to differ day on day.
In my view, Python is a bad choice for research due to how its environment is organized (mostly not organized). But, I guess, that the current policy is to sacrifice any desirable engineering qualities one might want from an environment to popularity because that allows to onboard more researches who would otherwise be stuck with MS Excel and / or Matlab. It's sad though that there needs to be a compromise at all...
Unpopular opinion: code should have no dependencies.
Thus, tools that ease the proliferation of dependencies encourage bad practices and must be avoided.
If you want to use somebody's else code, copy it verbatim into your project. Avoid unstable third-party code that needs to be updated every year (or worse, every week).
I kind of agree with you. This is why I’m trying to move my team to Go for new development rather than TypeScript. I end up having to spend about one day per month fixing dependencies. Our versions are pinned but upstream someone just said, “use latest”. Then everything breaks and I have to upgrade our project from TypeScript 3 to 4 or 5. Then I have to figure out interdependencies. It’s a mess.
Alas, sometimes that unstable third-party code is from some guy two desks down, and you need to use it. And it's unstable because it's not-quite-done yet.
Dependencies are life. Sure, eliminate the ones you don't need, but on most larger(ish) projects, you're going to have dependencies, be them internal or external.
> If you want to use somebody's else code, copy it verbatim into your project.
Copy/paste is a code smell ;)
A nice middle ground is referencing the code you want via its hash; rather than some ambiguous, made up identifier. That way:
- We retain the structure of separation, rather accumulating a big ball of mud.
- There's nothing ambiguous that needs "resolving": a hash corresponds to precisely one (known) file; assuming the algo's not been broken ;)
- Anyone using our project, anywhere in the world, at any time in the future, will get the exact same code.
- References to the same hash can be shared across projects directly (no need for e.g. deduplicating filesystems)
- We can reference multiple different copies/versions without conflict, since they'll have different hashes.
- Referenced files can be cached for as long as we like (since they won't change, there's no invalidation; although we may want to "garbage collect" to save space)
- No need for central "locations" (such as HTTP URLs): we can grab files from mirrors, P2P, other people's caches, etc. and it makes no difference to the file's hash.
- No need to trust third-parties, e.g. using HTTPS, PGP, etc. since we can verify whether the file we receive has the hash we want.
One way to do this is git submodules, although they rely on specific locations so we might want something like a magnet link for robustness and longevity.
Another is IPFS, whose addresses are content hashes.
Yet another is a tool like Nix, which has the advantage that we can calculate the contents of files; e.g. specifying our desired hashes in one place, and having them propagated/spliced/etc. as needed through the project (making it easier to update/replace in the future). We can also specify patches and arbitrary other pre-processing, to ensure we're getting precisely, and only, the code we want.
Note that these aren't mutually-exclusive: Nix and Git work very well together, for example.
If your dependency has a security update, how are you going to get that if you copy-paste the code? The thing these dependency managers do well is that they notify you about these types of issues.
.. That said, people need to be very careful about what they add as dependency. Having 1000+ transitive dependencies is just asking for security issues.
We effectively do the copy-paste. Dependencies are manually committed as a subdirectory to a "deps" directory, and the build scripts updated to search for it in that subdirectory.
To update, we simply download the new version we want, replace the code in the subdirectory, do a build, make some tweaks if needed to build scripts and code, and run tests. Once it builds and tests are fine, we commit both the updated dependency and the other changes in one go.
To get notified we use email (ie subscribe to updates) or just manually keep track.
A nice side-effect of this is that it's trivial to study the changes between the old and the new version before committing. While subtle subterfuge would be hard to spot, blatant stuff like including a bitcoin miner or whatever is trivial to catch.
I definitely think you should minimize 3rd party dependencies. That is where things turn nasty fast. You want 1 chef in the kitchen wherever possible. This "open source" movement has sapped so much life force from many developers by forcing them to chase ideological rabbits around all day. I think it's intentional at this point too.
I'm enjoying the magic of letting my framework/language vendor manage much of this circus for me. I am perfectly content being a filthy capitalist pig of a developer and paying money for my tools. Every time I can pay to outsource complexity, I am going to do it.
If you are actually focused on problem solving, working with certain vendors that include most batteries can make for a significantly more productive and happy dev experience. Forcing yourself into dep management hell just so you can brag on twitter about avoiding that one evil vendor is accomplishing what, exactly?
If you spend more than an hour a week worrying about dependencies, and you are trying to ship business functionality, why? Why suffer like this? Presumably the business to be implemented is already shitty enough. Why do we want to make it 10x harder with broken technology designs?
