Building an extremely fast Python package manager, in Rust - Charlie Marsh | EuroRust 2024

Thank you. My name's Ben. Awesome. Hi, my name's Charlie. I work at Astral.

We build developer tools for the Python ecosystem in Rust. So, we're best known for two tools, the first of which is called Ruff. Ruff is a Python linter and formatter. In the Rust ecosystem, the analogous tools would be Rustfmt and Clippy. Additionally, we also build a tool called UV, which is what I’m going to be talking about today.

Uv is a fast all-in-one Python package manager. You can use Uv to install Python, create virtual environments, resolve dependencies, install packages, build packages, and publish packages to the registry. If you've worked in the Python ecosystem at all, you might be familiar with tools like Pip, Pipx, Pym, Virtualenv, and Poetry. Uv is designed to be an alternative to all of those tools, rather than any one of them. A framing that I sometimes use is that we want Uv to be this single binary that provides you with everything you need to be productive with Python.

So you curl, install UV, and it just drops you into this pit of success in terms of not having to worry about how to install Python, what's Python versus Python 3, what's pip versus pip3, and how to manage all the things that are installed on your machine. UV does a lot while being significantly faster than many of the other tools in the Python ecosystem. When we started working on a package manager specifically for Python, I anticipated some of this. There are so many different tools that have tried to tackle Python packaging. What makes you think that what the ecosystem needs is just one more tool? I am naive enough to genuinely believe that what the ecosystem needs is just one more tool.

And I am naive enough to actually believe that what we are doing is quite different from many of the efforts that have been made before, particularly in Python, for at least two reasons that tie back to why I'm here speaking at a Rust conference. The first reason is the scope of what we're trying to build. Python tooling is very fragmented, so for any workflow you want to execute in Python, you typically need to chain together a variety of different tools, and for each step in that workflow, you have numerous options for which tool to use. With UV, we're aiming to create this unified stack.

So UV is not built on top of anything else; it is pure Rust. We have developed everything ourselves, including the resolver, dependency installer, and virtual environment manager. We have re-implemented all these Python standards and specifications from scratch in Rust. So, ICUV is this new take on Python where we're trying to create a very unified set of tools, and it's heavily inspired by the experience we have in Rust.

Rust tooling is, like, this very high-confidence endeavor that we have in Rust, right? Rust tooling is like this very high-confidence endeavor where, if you clone a project, you're pretty confident that you can figure out how to run and build it successfully. And that's sort of what we're trying to achieve with UV. The second aspect is performance. I enjoy building very fast software.

I think it's extremely fun, but it's also very impactful for users. One thing that we observed in the tools we built is that when you have tools that are significantly faster than other tools, it really changes the user's relationship with the tool and the way they work. For example, in Ruff, we've spoken to companies where their entire linting pipeline used to run on CI, and it was something that everyone hated because it always blocked their pull requests. Now, we provide them with a tool that's fast enough to run as a pre-commit hook or even on typing.

And so suddenly, it's this tool that's actually helping you write much better code and stuff much faster. So, like I said, everything we build is powered by Rust. In my opinion, there's at least some evidence that this different vision for Python tooling is working. We have UV—this is just UV, not including Rough—we have a lot of GitHub stars and a couple of hundred contributors.

But we're also closing in on almost 30 million downloads a month. This is a tool that we released in February, so it's been about six to eight months. I think the most shocking statistic I've seen is that over the past 30 days, 13% of requests to the Python Package Index came from people using UE. The Package Index serves around 2 billion downloads a day, which means that's like a quarter of a billion downloads coming from people using UV.

And I include this information because this is not a science experiment, right? This is something that's making a really big impact—this is like a major Rust project that we shipped, which is having a significant influence on a completely different programming community that a lot of people are using. While considering how to frame some of the challenges we've faced in building UV, an interesting question arose: if you're such a big fan of Cargo and Rust tooling, why not simply frame this as rebuilding Cargo? Even more superficially, why not just fork Cargo and swap out the index to hit PyPI instead of crates.io or whatever? Of course, that won't work, right?

Because Python is not Rust, I don't think I need to convince people here of that. However, I want to discuss a few aspects of Python, particularly Python packaging, that are different from how things work in the Rust ecosystem, as well as some of the problems that have arisen in attempts to build a package manager. The first point is that Python does not support multiple versions. This means you cannot have two versions of the same package installed simultaneously.

So, if we have a package that depends on a specific version of the LLM and a specific version of LangChain, these are just two popular packages for working with language models. Maybe the version of VLLM requires Pydantic 2, but that version of LangChain does not support Pydantic 2. In Rust, this is actually a solvable graph because Rust allows pulling in multiple versions of a single crate in its resolution in the graph. However, in Python, it's not.

This is not a graph that can be solved. You cannot satisfy this set of dependencies when you're trying to resolve a Python project. Instead, you might go to the user and say, "Actually, you need to lift the restriction on vllm." Maybe they will respond, "Okay, I'll accept any version." Then, we are responsible for going through and testing all the different vllm versions. Eventually, we may find an older version that works with Pydantic 1. This resolution is acceptable.

We can actually satisfy this. However, going through and solving this set of constraints and testing all those versions can be very slow and quite expensive. It's important to realize that this is not the complete graph. If you only depend on these two packages, VLLM and LangChain, you end up with something that is just a subset of the entire graph that you need to solve. Cargo has to handle a similar situation.

Cargo does need to figure out a set of dependencies that satisfy the constraints you give it. However, Cargo does not have the exact same formulation of this problem. Cargo is not required to find exactly one version of each package that helps you satisfy the graph. While Cargo still has to solve a problem, it is tackling a much less constrained one. The version of the problem where you need to satisfy all the dependencies and can only have exactly one version of each package is NP-hard, which is quite challenging.

So the first problem that we run into, which is quite different from how things work in Rust, is that we don’t have this multi-version support. This gives us an NP-hard constraint satisfaction problem that we have to try and solve as efficiently as we can. The second issue is that Python has this very rich mechanism for filtering your requirements by platform. In Python, you might see a set of requirements that looks like this: it’s just a bunch of packages at the versions that you’re allowed to include. Then, at the end, we have this identifier on the right, which specifies that `importlib` should only be installed if the user is running a version of Python prior to 3.10.

And if we look at some of the transitive dependencies, we might see that we also need to include the Colorama package, but only if the user is on Windows. These markers have a whole grammar around them, so you can use "and" and "or" within them. This concept, by itself, is not very different from what we have in Rust, where you can specify conditional dependencies based on the platform. However, it is important to keep in mind that when dealing with this grammar and all these conditions, we must consider them alongside that single version constraint.

So, if the user provides us with dependencies that look like this, they're requesting Pydantic 2 on Windows and Pydantic 1 everywhere else. It's a bit complicated because this actually forms a satisfiable graph, even though they're asking for two completely distinct versions of Pydantic. We know that a machine is either Windows or not Windows, right? Those conditions on the right cannot both be true at the same time. Therefore, we need to consider how these markers work in relation to one another.

As a counterexample, we cannot solve this issue because, in Python 3.12 or 3.13, the user would be asking us to install both Pydantic 2 and Pydantic 1. Therefore, we need to reject this request. If you consider what is happening here, we have two requirements for the same package, and we are looking at these markers—these environments on which the user wants us to install them. If we think of these as Marker A and Marker B, the question we are trying to answer is: Do A and B overlap? Do those marker expressions overlap?

Which could also be formulated as, can they both be true at the same time? This can also be framed in terms of whether they are disjoint. Additionally, it can be expressed in terms of a Boolean satisfiability problem. So, is the expression "A and B" satisfiable? Is it possible to satisfy that expression?

And when you hear the term "satisfiable," you should be very worried because this is also NP-hard. Deciding whether two marker expressions are disjoint is actually an NP-hard problem. It may seem straightforward here because it involves just windows and non-windows. One might think, "Of course those are disjoint." However, in practice, when we solve complex graphs, we often end up with numerous very large markers.

This is from "Solving Transformers," which is a really popular Python project. These are real marker expressions that end up in the lock file through the process of solving the dependencies. These expressions are fully simplified and normalized. Please do not apply extremely rigorous simplification to these; they can be tens or hundreds of kilobytes in size in terms of the expressions you start creating.

So we don't have multiversion support, which makes solving much harder. We also have to perform all sorts of algebra on the environment markers, the support, and the logical operators, which creates a completely separate set of NP-hard problems. I want to briefly discuss a few more issues that, thankfully, are not NP-hard, but still cause some trouble. One issue is that in Python, when you're working with third-party packages, a lot of the time you're not actually interfacing with Python code. For example, when you're using NumPy or SciPy, those libraries are all written in C or C++.

They're written in native code and then compiled and exposed through Python. So, there are a lot of standards in Python and in the ecosystem around enabling people to pre-build those distributions. When they publish a new version of NumPy, they don't just publish the source code; they also provide builds for Windows and for Linux, likely targeting a variety of different glibc versions.

They might also have to multiply that by the number of Python minor versions they support. Some packages might have 70, 100, or more artifacts for a single release. Another issue that this causes is that sometimes these distributions are really, really large. For example, PyTorch is about 500 megabytes. Therefore, whenever we're interfacing with these artifacts, we have to be very careful about how much work we do and how we do it, because they can be quite substantial.

I think the thing that causes me the most frustration is that in Python, packages are not guaranteed to have statically defined metadata. Knowing their metadata is extremely important because you need to understand their dependencies. Most of the time, a package will include its dependencies in a statically defined way, but this is not a requirement. In the worst case, you may have to clone the Python project, run some arbitrary Python code, and interrogate the dependencies to extract them. As a result, during the resolution process, you occasionally have to execute Python source code for dependency projects that users rely on.

Another one, which is a little bit more superficial, is that when projects do have metadata, it's serialized as email headers. I include this because what we see here is an ecosystem that has evolved, often organically, over decades. It's easy to sit here and laugh, and it is kind of funny, right? Like, why would they do it that way? Why would they use email headers?

But at the time that behavior was specified, JSON did not exist. For me, when I see the set of problems, the right response is really to be curious about what we, as a Rust ecosystem, can learn from what worked in Python and what has been challenging. I sort of straddle the border here. So, what can we, as a Python ecosystem, learn from Rust? What can we take from Rust and bring back to try to make Python better?

This is like one of, if not the most popular programming ecosystems on Earth, right? Building for this ecosystem has a very high impact. Our approach is to take these problems seriously and then try to solve them in new and different ways, often inspired and powered by the experience we have with Rust. I mention Rust a lot; UV is written in pure Rust.

And when I think about why Rust is important or helpful for the project, there are really four things that stand out to me. The first is safety. This is perhaps an obvious one, but when I started learning Rust, I actually didn't care at all about memory safety. I did not understand why it was important or even really what it was. My programming background contributed to this.

I now think that memory safety is actually very underrated because I suspect there are a lot of people who think like I did when I started learning Rust. We have now shipped two very large projects to millions and millions of people, including millions of Python users. To the best of my recollection, I don't think we've ever had a user-reported issue that was caused by a memory problem, which is kind of crazy. The sheer lower bound on the quality of software that we can ship with Rust, assuming we stay within the guidelines, is super high. For me, that's important because when we're building tooling, I'm not going to call it mission-critical, but it's something people are using all day throughout their day.

Building reliable software is incredibly useful. The second point is portability, and I'm going to sort of misuse the term because I want to describe something fairly specific, which may sound very obvious to people who work with Rust. With Rust, we can build binaries that users can download and run on all sorts of different platforms with no external dependencies, right? That's actually a super useful property because it means we can tell users to download and install UV, and we can then install Python for them. We're not building a tool that depends on them having some other toolchain or some other set of dependencies installed. This has really been pretty game-changing for people in Python.

They no longer have to worry about how to brew install Python or how to do X, Y, or Z. They can just install UV, and we can take it from there. There's no additional setup or bootstrapping necessary. I also think a lot about the accessibility of the language and the ecosystem.

We have, across Rust and UV, over 700 contributors. Many of these individuals claim to be writing Rust for the first time. A significant number of them come from the Python ecosystem and are looking for a reason or an entry point into Rust. When I first started the project, a common critique was that it would never work because we would struggle to build a community around it, as many of our users couldn't contribute or work on the project. I believe this critique has been very much disproven by the way our community has developed.

I think Rust is a hard language to learn. I do not think it's the right fit for every project. I don't know if that's controversial or not, but the tooling, resources, and ecosystem have made it into a very accessible systems programming language. Like I said, I had no systems programming experience prior to learning Rust two years ago. Part of the reason I started working with Rust was because I wanted to learn and get better at it.

And now, you know, we ship these things that a lot of people are using. So for me, I think I really admire the way that Rust has made building this kind of software accessible to software engineers. And then the last point is performance. There's a lot to say about performance, and I will talk about it, but I think the way that I've come to think about Rust and performance is that Rust gives you a high baseline for how fast your programs will be. Additionally, it provides you with all the tools you need to build really fast programs and encourages you to care about many of the details that matter when you're trying to write truly performant code.

For example, allocating and managing memory. Allocating memory is relatively slow. Rust forces you to really think about where you are allocating memory and how you are using it. So, I want to spend the rest of the talk discussing some of the things we do in UV to make it fast for two reasons. First, I think it helps demonstrate some of the strengths of Rust, but also, I just think it's kind of fun and interesting. I enjoy talking about specific examples because they're very cool.

So let's talk about version parsing. In Python, as in most ecosystems, packages have versions, right? A package could be version 1.0.0, but it could also be like 2.3.1.0. There is also the possibility of a pre-release version, such as 2.3.1-beta. This pre-release can be labeled as beta, alpha, or release candidate (rc), and the pre-release itself is considered a version.

You can have Beta One, Beta Two, and Beta Three. You can also have development releases, which are somewhat different from pre-releases; it's a totally separate tag. Additionally, you can have post-releases, which are typically used for documentation updates or other non-code updates to your project.

The specification also includes provisions for something called a local version identifier, which refers to the segment that comes after the plus sign. This has become very popular due to gaps in the standards, particularly concerning CUDA and building for specific accelerators. For instance, PyTorch utilizes this feature extensively. If you have ever worked with PyTorch, you may have encountered this, even though it was not originally intended for that purpose; however, it has become a common usage now. Additionally, the specification accommodates local documentation updates or other non-code updates to your package or project.

I think the most obscure concept is having a number followed by an exclamation point at the front. This is called the epoch. It exists, although I have never actually seen it in the wild. The epoch was largely introduced for compatibility purposes at the time the specification was created. They wanted to provide people a way to shed their old versioning schemes and declare that a new version was, in fact, the latest version.

And of course, all these things can be combined. This is actually a totally valid version. You can have an epoch and as many release segments as you want. It does not have to be just one, two, or three. And yeah, you can have... what is it?

I don't know; I don't want to be able to say it. It's like a post-release. It's a developer release of a post-release of a pre-release with a logo version segment. So anyway, if you want to represent the full spectrum of valid versions, you need a fairly complex structure. There are a lot of different fields involved.

There are two vectors in here. During the process of conducting an extensive resolution, we actually create hundreds of thousands of these. The realization—though not mine, but Burned Sushi's—is that most versions are actually very simple. The versions I'm showing here are quite straightforward, and I cannot imagine a project would actually publish something like this; most versions appear as 1.0.0. In fact, it turns out that we can represent most versions with just a single u64. While not all versions can be represented this way, most can. The way we use that representation is that, given a u64, we have eight bytes which we utilize very judiciously. Bytes six and seven represent the major version, which gets two bytes because calendar versioning is not uncommon.

So, 2023 would not be a crazy major version to see. The next three segments each get one byte. Then, at the end, the last few segments can represent either a pre-release or a post-release, right? There are many versions that we cannot represent this way. We cannot represent versions that have more than four release segments.

We couldn't represent anything with that local version identifier or anything with an epoch, but over 90% of versions fit this scheme empirically. The really cool thing is that the way this is designed means that greater versions map to larger u64 integers. Not only are we creating these all the time, but we're also comparing them constantly. For example, we often ask whether 1.0.0 is larger than 2.0.0, and so on.

And if you have two of these versions presented in that way, that comparison is just comparing two 64-bit unsigned integers. It's extremely cheap, as opposed to trying to compare that large struct we looked at before, which contains a bunch of vectors and very complicated rules regarding how they interact. So, most of the implementation of this is actually a huge comment explaining what I just walked through, but it is a real thing that we did, or that Andrew did. In this example, where we had a really complicated resolution with minimal I/O, all the data was cached locally, which sped things up by about three to four times.

We were spending a lot of time dealing with versions. Often, this is actually the best way to solve a problem. Sometimes, it's just to convince Burnt Sushi that it's really interesting and worth working on, as he tends to come out of a cave with ideas like this. A lot of what we do in a package manager involves I/O; we're downloading packages.

We're unzipping them and making network requests to get metadata. In particular, we make a lot of small, constant network requests because we do a lot of prefetching. If we know you're going to rely on these versions, we might go and ask for them from the registry, as those requests tend to be fairly small. So, UV is written entirely in async Rust and built on Tokio. Counterintuitively, we use the single-threaded runtime, and all of our I/O happens on a single Tokio thread.

And empirically, what we found is that we actually don't perform, in a relative sense, a lot of what we're doing is I/O, but it's not like we're a high-performance web server. We're actually not performing enough I/O for multiple threads to be worth it. This, for us, reduces the synchronization costs and actually ends up being faster, which is interesting. It also means that we're very careful about how we orchestrate non-I/O compute. For example, we took all the compute work that happens in the resolver that is I/O.

It happens on its own thread, and we are very careful about how we schedule all the work that takes place. This is the kind of thing that I think sounds very hard to do. In truth, I'm probably not smart enough to figure it out, although Ibrahim is. However, Rust as an ecosystem makes it relatively easy for us to manage the coordination of resources and the workflows within the project, which I think is pretty amazing.

I mentioned before that we use a SAT solver. Sorry, I mentioned that, but we have to solve this NP-hard problem of trying to satisfy versions. For that, we use a piece of technology called a SAT solver. The SAT solver that we use is called Pubgrub. It was originally created by Natalie Weisenbaum for the Dart ecosystem, and it's known in particular for having very good error messages.

There's a big focus on trying to create well-structured error messages. The crate we use in particular is called `pubgrubrs`, which was written by Jacob Finkelman, who is a Cargo maintainer, and Matthew Pizer. There are many classic and interesting performance optimizations in the `pubgrub` codebase. This is the component that performs the actual constraint solving beneath the resolver. For example, and I won't walk through these in detail, there's "smallvec," which involves storing small vectors inline on the stack rather than allocating memory.

There's an arena allocator for package names. There's a lot of like ARC and RCE for cheap cloning. But the cool thing, I think, in our experience with PubGrub, is that there's also a lot of domain-specific optimization that needs to happen. So PubGrub is all built around range operations. Often, you're doing unions, intersections, and complements.

We found that optimizing those and running them against a really big, heavy UV workflow sped things up by about 4 times. The cool thing is that Pubgrab was originally written with the intention of adopting it in Cargo. Although that hasn't happened yet, we adopted it and built something that many people are now using. As a result, we have a very battle-tested SAT solver and resolver in the Rust ecosystem because it has been thoroughly tested here.

And what we've been able to do, as a team, is actually profile a lot of interesting potential resolver performance optimizations for the real problems that we face in the Python ecosystem. The last thing we’ve been able to do is profile a lot of intriguing potential resolver performance optimizations related to these real problems. The last piece I want to mention here is that I just want to talk about the cache design for a second. A significant factor in making a package manager fast is, in fact, caching. In UV, we tend to optimize for what I would call "warm operations."

So often, when you're installing a package on your machine, it's a package that you've previously installed at some point in the past. It might be installed in another project. The cache was specifically designed to take advantage of that property. For example, you might have several projects on your machine that use PyTorch, so what we store is this global cache of unpacked archives.

In Python, distributions are shipped as ZIP files, but we actually don't store the ZIP files on your machine at all. Instead, when we download, we stream and unzip directly into the cache. The cache contains just a collection of unzipped ZIP files, effectively. Then, when we install, we use either reflinks, which is like copy-on-write, or hard links to link all those files.

Files are placed into the user's environment, and the cache serves as a global store for unzipped packages. When the user needs to install a package, most installations involve hard linking a collection of files into the user's project. It appears like this on disk. This is the cache from my computer.

It's just a bunch of unzipped directories that contain lots of Python files and maybe some native code. Like this cache design—none of this actually requires you to use a specific language; you could do this in any language. However, I was thinking about it as I put together this slide, and it does require a couple of things that I really didn't know how to do a few years ago. So it requires asynchronous programming, an understanding of the ZIP format and how to operate on it at a byte level. It also requires an understanding of reference links versus hard links, as well as how to implement those abstractions across different platforms.

There's a lot of implicit and accrued knowledge involved in actually building this piece of software. The crazy thing for me is that I designed and implemented most of this part, at least. I learned Rust about two years ago, with no prior systems programming experience. So, Rust actually empowered me to build this, which I find kind of mind-blowing. I'm obviously not here to sell you on Rust.

I think you like Rust, but I am here to convince you that how we are using Rust, at least, is a big success story for the language ecosystem. I spent most of my career, prior to about two years ago, writing Python and TypeScript. I came to Rust with very little idea of what I was doing, and we have now built software that has grown to hundreds of millions of downloads.

And beyond Rust and UV itself, there's this whole ecosystem of hybrid Rust-Python tools. Pydantic, which I use as an example here, is downloaded around 300 million times a month, I think. It now uses a Rust backend with a Python frontend. This Rust-backend, Python relationship means that one of the largest programming ecosystems in the world is gaining access to safer, more reliable, high-performance software. I only see that trend accelerating, and I hope it will if I have anything to say about it.

Thank you. You.