A pip resolve command to convert to transitive == requirements very fast by scanning wheels for static dependency info (WORKING PROTOTYPE!)

[cosmicexplorer]

Please let me know if it would be more convenient to provide this issue in another form such as a google doc or something!

What's the problem this feature will solve?

At Twitter, we are trying to enable the creation of self-bootstrapping "ipex" files, executable zip files of Python code which can resolve 3rdparty requirements when first run. This approach greatly reduces the time to build, upload, and deploy compared to a typical PEX file, which contains all of its dependencies in a single monolithic zip archive created at pex build time. The implementation of "ipex" in pantsbuild/pants#8793 (more background at that link) will invoke pex at runtime, which will itself invoke a pip subprocess (since pex version 2) to resolve these 3rdparty dependencies. #7729 is a separate performance fix to enable this runtime resolve approach.

Because ipex files do not contain their 3rdparty requirements at build time, it's not necessary to run the entirety of pip download or pip install. Instead, in pantsbuild/pants#8793, pants will take all of the requirements provided by the user (which may include requirements with inequalities, or no version constraints at all), then convert to a list of transitive == requirements. This ensures that the ipex file will resolve the same requirements at build time and run time, even if the index changes in between.

Describe the solution you'd like

A pip resolve command with similar syntax to pip download, which instead writes a list of == requirement strings, each with a single download URL, to stdout, corresponding to the transitive dependencies of the input requirements. These download URLs correspond to every file that would have been downloaded by pip download.

pants would be able to invoke pip resolve as a distinct phase of generating an ipex file. pex would likely not be needed to intermediate this resolve command -- we could just execute pip resolve directly as a subprocess from within pants. The pants v2 engine makes process executions individually cacheable, and transparently executable on a remote cluster via the Bazel Remote Execution API, so pants users would then be able to generate these "dehydrated" ipex files at extremely low latency if the pip resolve command can be made performant enough.

Alternative Solutions / Prototype Implementation

As described above, pantsbuild/pants#8793 is able to create ipex files already, by simply using pip download via pex to extract the transitive == requirements. The utility of a separate pip resolve command, if any, would lie in whether it can achieve the same end goal of extracting transitive == requirements, but with significantly greater performance.

In a pip branch I have implemented a prototype pip resolve command which is able to achieve an immediate ~2x speedup vs pip download on the first run, before almost immediately levelling out to 800ms on every run afterwards.

This performance is achieved with two techniques:

1. Extracting the contents of the METADATA file from a url for a wheel without actually downloading the wheel at all.

• _hacky_extract_sub_reqs() (see https://github.com/cosmicexplorer/pip/blob/a60a3977e929cfaed6d64b0c9e3713d7c502e51e/src/pip/_internal/resolution/legacy/resolver.py#L550-L552) will:
  a. send a HEAD request to get the length of the zip file
  b. perform several successive GET requests to extract the relative location of the METADATA file
  c. extract the DEFLATE-compressed METADATA file and INFLATE it
  d. parse all Requires-Dist lines in METADATA for requirement strings
• This is surprisingly reliable, and extremely fast! This makes pip resolve tensorflow==1.14 take 15 seconds, compared to 24 seconds for pip download tensorflow==1.14.
• A URL to a non-wheel file is processed the normal way -- by downloading the file, then preparing it into a dist.

2. Caching the result of each self._resolve_one() call in a persistent json file.

• RequirementDependencyCache implements this (see https://github.com/cosmicexplorer/pip/blob/a60a3977e929cfaed6d64b0c9e3713d7c502e51e/src/pip/_internal/resolution/legacy/resolver.py#L240).
• This is keyed by RequirementConcreteUrl (see https://github.com/cosmicexplorer/pip/blob/a60a3977e929cfaed6d64b0c9e3713d7c502e51e/src/pip/_internal/resolution/legacy/resolver.py#L187), which is a pairing of an == Requirement with a url that it can be downloaded from.
  • Therefore the cache file's information will remain correct over time, as long as the indices only allow publishing a single version of a package exactly once.
• This causes pip resolve invocations to stay at ~800-900ms in a "no-op" case when every transitive requirement is in the cache.
• Both wheel and non-wheel requirements are cached.
• This cache is also populated by pip download and everything else calling Resolver.resolve(self, ...), but only pip resolve will actually consume the cache in the current prototype.
• If a user runs pip resolve once, then runs it again with a single input requirement string changed, most of the transitive requirements will remain cached, avoiding the need to make any network requests except to update the changed transitive requirements.

Additional context

This pip resolve command as described above (with the resolve cache) would possibly be able to resolve this long-standing TODO about separating dependency resolution from preparation, without requiring any separate infrastructure changes on PyPI's part:

pip/src/pip/_internal/resolution/legacy/resolver.py

Lines 158 to 160 in f2fbc7d

	Once PyPI has static dependency metadata available, it would be
	possible to move the preparation to become a step separated from
	dependency resolution.

I have only discussed the single "ipex" motivating use case here, but I want to make it clear that I am making this issue because I believe a pip resolve command would be generally useful to all pip users. I didn't implement it in the prototype above, but I believe that after the pip resolve command stabilizes and any inconsistencies between it and pip download are worked out, it would likely be possible to make pip download consume the output of pip resolve directly, which would allow removal of the if self.quickly_parse_sub_requirements conditionals added to resolver.py, as well as (probably) improve pip download performance by waiting to download every wheel file in parallel after resolving URLs for them with pip resolve!

For that reason, I think a pip resolve command which can quickly resolve URLs for requirements before downloading them is likely to be a useful feature for all pip users.

I am extremely open to designing/implementing whatever changes pip contributors might desire in order for this change to go in, and I would also fully understand if this use case is something pip isn't able to support right now.

[pfmoore]

I haven't read this proposal in detail yet, but are you aware that there's ongoing work to implement a new resolver in pip - #6536?

We should certainly look at the ideas here and consider how they integrate with the new resolver work (I am personally particularly interested in the idea of getting wheel metadata without downloading the whole wheel).

Ping @pradyunsg @uranusjr - we should pick this up tomorrow in our meeting and feed back to @cosmicexplorer from that.

[cosmicexplorer]

Thank you so much for the prompt reply!! I was not aware of that (or had forgotten) and will read up on #6536 now! I will see if I can refactor this issue into a comment on #6536!

(I am personally particularly interested in the idea of getting wheel metadata without downloading the whole wheel)

:D :D I didn't expect that to work out at all, it was super surprising! I would definitely love to help clarify how this part works and will look to see how to fit it into the context of #6536!

[pradyunsg]

@cosmicexplorer this is cool stuff! I'm definitely interested in taking a look at this and piggy-backing off of this work to possibly integrate it with the new resolver! @pfmoore discussing this in the syncup sounds like a great idea to me!

Also, kudos @cosmicexplorer (and anyone else who worked in this) for actually working on this, with the not-so-great abstractions that we have in pip's internals back when y'all started this work. Maybe we can discuss a bit about how it was to deal with them if we get time to chat. :)

[cosmicexplorer]

Also, kudos @cosmicexplorer (and anyone else who worked in this) for actually working on this, with the not-so-great abstractions that we have in pip's internals back when y'all started this work. Maybe we can discuss a bit about how it was to deal with them if we get time to chat. :)

Just me for now! Would love to! The thing I had to iterate several times on (off and on since last August) was just hammering out a way to make some requirements get processed without calling .prepare_linked_requirement() beforehand. I chose to mutate e.g. the new .force_eager_download field of InstallRequirement instances in this prototype to avoid having to modify too much of the control flow in legacy/resolver.py. This usage of mutation then forced me to create an "immutable" RequirementConcreteUrl cache key class so that it could be persisted, separate from any mutable InstallRequirement instance within a single pip invocation.

I feel like having download occur as part of the resolve process by itself made it specifically more difficult to modify the implementation for performance without changing the behavior of the resolution process in subtle ways. I had experimented with adding multithreading earlier, but had to comment out a very large amount of code in many separate files to avoid failing assertions (e.g. only editable requirements can have an existing source_dir, or something) before even getting it to run once on a small example.

So I think splitting out a pip resolve command, which would produce some programmatic output that pip download can then consume directly, even without any of the performance enhancements described above, might be an interesting way to structure the new resolver API alone. And having something like RequirementConcreteUrl used to represent "an == requirement from a specific URL" with a specific type, instead of having that concept only expressed indirectly via mutable state in InstallRequirement instances, seems like it might also contribute to more effectively reasoning about pip resolves in the abstract, which feels like fertile ground for further performance enhancements down the road.

EDIT: Hmm, in reading #5051 I'm realizing that the RequirementConcreteUrl I've used in this prototype should probably be something like InstallationCandidate instead.

[uranusjr]

@cosmicexplorer Would you be interested in taking a look at #7799, which is trying to add a new resolver to pip? I’m hitting problems trying to build “prepare” multiple versions of a package. The approach I’m taking now is to “clone” the InstallRequirement and prepare the cloned instance. It seems like we’re doing a lot of the same things, and I’d be super grateful if we could exchange some insights in this area.

[pradyunsg]

I've spent some time understanding understand the work done here and here are my notes / brain-dump of my understanding. @cosmicexplorer Definitely feel free to correct me in case I understood something incorrectly here. :)

(coming back up here, to flag that my tone in the rest of the comment may not come across as 100% positive but I really am super glad that someone has actually worked on this stuff!)

---

pip resolve command proposed here, is trying to solve the same problem as one of the oldest open issues in pip -- show what version would be installed by a pip install run -- #53. There have been similar requests in the past too, but no one actually showed up with an implementation -- eg. #6340, #6430 (and more that I really don't want to spend the time searching for). This specific feature has on my personal radar for a long time as a "do after the new resolver rollout" task.

@cosmicexplorer a question regarding the implementation strategy taken -- any reason you didn't add a flag to pip install and add a "do a print and exit" after

pip/src/pip/_internal/commands/install.py

Lines 380 to 382 in 60d6402

	to_install = resolver.get_installation_order(
	requirement_set
	)

Did you create a new command, to avoid "reading" from the dependency cache in pip install and friends?

As far as I can tell, this work is strictly unrelated to bringing in a new resolver and changing the resolution behavior/result (which is the work I've been chipping at since 2017 and, recently, @pfmoore, @uranusjr and I have been working on implementing as part of the donor funded work).

---

Beyond that, there has been a whole bunch of work done around speeding up the "get the metadata" step -- the most "expensive" step in our dependency resolution process -- through strategies that we have discussed in the past like (1) dependency information caching and (2) metadata from partial downloads. The fact that this stuff has actually been implemented and is working is great; since I expect we can reuse/adopt these pretty easily -- which is awesome! We should have dedicated discussions for both of them separately and I'm 100% on board for "bringing them in".

The most recent comments mentioning "we should do X" for the these:

• New Resolver: technical choices #7406 (comment) -- partial downloads
• New Resolver: technical choices #7406 (comment) -- persistent disc caching

---

There are other wider improvements that affect other tooling other pip haven't been tried as part of @cosmicexplorer's work (which is fair, but I want an excuse to list them in one place so...) such as exposing reliable dependency metadata directly from sdists, directly from package indexes and without requiring complete PEP 517 builds / wheel metadata preparation^[1].

^[1]: we'd need to a new optional "build-system" hook -- to directly get dependency information from a source tree -- it was present in initial drafts of PEP 517, but subsequently removed as YAGNI; despite my protests that it's needed by a proper resolver. 😞

---

Overall, everything implemented here is useful though we'd need to think a bit about the rollout and implications of these changes (like we would for any "broad" changes to pip) before merging them in. I think we should definitely think whether we want to bundle parts of this work (especially metadata speedups) with the new resolver rollout.

[pradyunsg]

Relabeled, since this isn't about changing dependency resolution results, but exposing the results more directly in the CLI and bringing in speedups to "get metadata".

[dholth]

I'm delighted that you are taking advantage of this wheel feature.

Did you know you can do a range request for the last n bytes of a file, without knowing its length?

I wrote this in 2012. It is a seekable file backed by http and a sparse on-disk file. You can pass it to ZipFile and download exactly the files you want to download plus the zip index. It will require some updating and removing of debug features. https://github.com/dholth/httpfile/blob/master/httpfile.py

Wheel also suggests that the metadata (the .dist-info directory) be at the end of the .zip archive. I'm not sure if everyone follows that suggestion.

[cosmicexplorer]

Did you know you can do a range request for the last n bytes of a file, without knowing its length?

I did not! Thank you!!!

I wrote this in 2012. It is a seekable file backed by http and a sparse on-disk file. You can pass it to ZipFile and download exactly the files you want to download plus the zip index. It will require some updating and removing of debug features. https://github.com/dholth/httpfile/blob/master/httpfile.py

It would be really really nice to be able to use this instead of the _hackily_extract_sub_requirements() method in the prototype branch at https://github.com/pypa/pip/compare/master...cosmicexplorer:requirement-dependencies-cache?expand=1!! I would really like to help make this process less hacky and your work here seems really relevant!! I'll check it out!!!

Wheel also suggests that the metadata (the .dist-info directory) be at the end of the .zip archive. I'm not sure if everyone follows that suggestion

Currently, this approach will resolve the last 2000 (arbitrary) bytes of a zip file, then read the central directory header from the zip file to locate the METADATA file. So this technique relies on the central directory header being at the end of the file (required by the zip format, I believe) to read where METADATA is, then it makes a range request for just those bytes. So it doesn't require that METADATA itself is at the end of the archive.

EDIT: See section 4.3 of https://pkware.cachefly.net/webdocs/casestudies/APPNOTE.TXT regarding the central directory header!

[dholth]

Try fetching the last 8k of the file to start. It will get you the central directory and METADATA more than half the time, based on looking at some of the most popular wheels.

#!/usr/bin/env python
import glob
import zipfile
import os.path

for wheel in sorted(glob.glob('*.whl'), key=lambda x: os.path.getsize(x)):
    wf = zipfile.ZipFile(wheel)
    metadata = next(info for info in reversed(wf.infolist()) if info.filename.endswith('/METADATA'))
    offset = metadata.header_offset
    size = os.path.getsize(wheel)
    print("%6d %s offset: %d cd: %d" % (size - offset, wheel, offset, size - wf.start_dir))

[cosmicexplorer]

That’s a fantastic optimization that I also hadn’t considered ^_^!!!! Hey — would you accept it if I added this functionality (adapting your code above) as a PR against your httpfile repo? It would be a first draft — I’m very good at iterating on changes in response to feedback. I could try to make a separate PR with some attempt at the updates you mentioned in your first message as well.

If I have major issues for some reason with httpfile, I’ll try to open an issue. I think it sounds like a great idea to use your existing work here, though.

[dholth]

I'd be glad to accept pull requests against httpfile to develop it as a useful package instead of just a proof of concept

[pradyunsg]

@pfmoore @uranusjr I think it'd be handy to add a card to our project board to explore this if we can. This can be a significant speedup due to less time spent hitting the network.

[pradyunsg]

#53 just got significant housekeeping done to it. That's now the appropriate tracking issue for this functionality.

[cosmicexplorer]

That's now the appropriate tracking issue for this functionality.

Awesome!! :D super glad this is being picked up!!! Can this issue be closed, then? Or are there remaining elements that might be useful to split out?

[cosmicexplorer]

(I'd also be interested in productionizing any of the above, if nobody else has planned to work on all of it yet!) I guess I can probably just look at the github project for this!

[jsar3004]

Hello, I am a beginner in open source. I want to learn and contribute to pip but I can't understand the complex code. Please guide me on how to get started and what to learn if any skills are required.

[pradyunsg]

Let me know if people aren't ready for this yet

FWIW, I hadn't communicated w/ everyone to figure out how we would be picking up the various parts of this task and implementing things.

---

@cosmicexplorer #8448 is a fairly large PR and I have a very strong bias toward keeping PRs smaller and following a change-a-single-thing per PR/commit style, to make it easier to review. IIUC, there's 2 functional changes in this PR that we should break off into separate PRs:

• partial wheel metadata download support
• parallelization of wheel downloads ("hydration" here)

Notably, there's also a logical/semnatic change in this PR -- we're no longer guaranteeing that the requirement_set returned after Resolver.resolve can be used immediately for installation (technically, we don't do that today, but that's because of sdists, not wheels).

I suggest we break that up into smaller chunks, that we tackle one-by-one:

1. partial wheel downloads for metadata (keeping "download entire file" as part of prepare)
2. move out "download entire file" out of prepare (and hence, Resolver.resolve)
3. parallelize download of multiple files

---

Related context: #8532 (comment)

Right now, @McSinyx would be updating #8532.

I think we should probably have a couple of follow up PRs to (a) refactor/move the logic for "download entire file" and then (b) "new feature" implementation to parallelize those downloads (i.e. considering user-facing behavior, output etc). After #8532 is finalized, the main blocker on that front for #53/#7819, would be moving the "download entire file" logic out of the resolver's scope. For @McSinyx's GSoC project, the parallelization of the downloads (and the corresponding UI / UX work) would be the next big-fish task for them to work on.

Here's how I suggest we move forward on the overlap of this issue and @McSinyx's GSoC project:

• @McSinyx updates Use lazy wheel to obtain dep info for new resolver #8532 to implement 1. above, according to the approach outlined in the aforementioned comment
• @cosmicexplorer (or @McSinyx, if @cosmicexplorer isn't available) refactors the logic for "download entire file" out of the resolver's scope.
  • once this is done, we can move on to other parts of A pip resolve command to convert to transitive == requirements very fast by scanning wheels for static dependency info (WORKING PROTOTYPE!) #7819, like the dependency cache or Add pip install --dry-run or similar, to get resolution result #53 even.
• @McSinyx works on figuring out how download parallelization would be presented to the user and modelled in pip's codebase.

Does that sound like a reasonable plan to going forward @cosmicexplorer @McSinyx @pypa/pip-committers? I don't want folks stepping on each other's toes. :)

[cosmicexplorer]

This planning effort above is super super welcome! Thank you!

IIUC, there's 2 functional changes in this PR that we should break off into separate PRs:

• partial wheel metadata download support
• parallelization of wheel downloads ("hydration" here)

Correct!

Notably, there's also a logical/semnatic change in this PR -- we're no longer guaranteeing that the requirement_set returned after Resolver.resolve can be used immediately for installation

Yes! You've correctly identified the main source of complexity, imho.

I suggest we break that up into smaller chunks, that we tackle one-by-one:

1. partial wheel downloads for metadata (keeping "download entire file" as part of prepare)
2. move out "download entire file" out of prepare (and hence, Resolver.resolve)
3. parallelize download of multiple files

I like this plan a lot!

• @cosmicexplorer (or @McSinyx, if @cosmicexplorer isn't available) refactors the logic for "download entire file" out of the resolver's scope.
  • once this is done, we can move on to other parts of A pip resolve command to convert to transitive == requirements very fast by scanning wheels for static dependency info (WORKING PROTOTYPE!) #7819, like the dependency cache or Add pip install --dry-run or similar, to get resolution result #53 even.

:D the dependency cache and #53 would be all the remaining parts needed for a massive performance improvement to pantsbuild/pants#8793, so this would be super exciting. I will try to dive into this refactoring step you've described this week to unblock the rest.

works on figuring out how download parallelization

Definitely agree this should be broken out! It's quite possible that the implementation here is much, much slower than it could be by manually creating threads, in addition to stomping all over download progress output and making it unreadable.

[nlhkabu]

Hello, I am a beginner in open source. I want to learn and contribute to pip but I can't understand the complex code. Please guide me on how to get started and what to learn if any skills are required.

@jsar3004 - If you're new to open source and want to contribute to Python packaging, I recommend starting with the Warehouse project. This is the codebase that powers pypi.org.
There are tickets that are marked as good for first time contributors - start there :)

[jku]

See also Warehouse issue "Expose the METADATA file of wheels in the simple API": pypi/warehouse#8254 -- I think this would solve similar issues with less clients side tricks? Of course the Warehouse feature is not implemented yet...

Also, I've started working on issue #8585 "Secure PyPI downloads with signed repository metadata": the comment I have on partial downloads is that I think those essentially cannot be verified -- there is no way to know if you are being served the metadata that was originally created. In fact there's no way to know if the metadata would even match the file hash included in the index file: a distribution mirror could serve whatever metadata it wants and it would get processed... Not sure if there's a practical attack here but the possibility seems real.

[cosmicexplorer]

Yes! And that is exactly the solution that people at Twitter including @kwlzn have proposed that we use to solve this. My interest in the client side approach is that it solves the problem for other people using tensorflow at large corporations who don’t pull from PyPI. We host an Artifactory instance, and I haven’t yet delved into how easy it would be to make the modifications to support the METADATA files as in the warehouse PR.

It seems to me that both of these approaches, when shipped to production, would likely have similar performance characteristics and produce the same result. I expect the PyPI change might end up being faster in the end, but I don’t know if, for example, some file contents get cached by the web server, and until most people are using the METADATA approach, it might end up being faster to pull tensorflow’s METADATA directly from the zip for that reason.

If this becomes outclassed by the working PyPI solution, I believe it still might not be replaceable for people who for whatever reason don’t have control of where they download their wheels from (and therefore can’t get a resolve using the metadata info). I don’t know how many of these people there are.

the comment I have on partial downloads is that I think those essentially cannot be verified -- there is no way to know if you are being served the metadata that was originally created. In fact there's no way to know if the metadata would even match the file hash included in the index file: a distribution mirror could serve whatever metadata it wants and it would get processed... Not sure if there's a practical attack here but the possibility seems real.

So this is an extremely reasonable concern, and my first thought is that if we’re thinking about adding METADATA files to PyPI that those would probably have checksummed urls too? So the more canonical warehouse approach seems like it would be beneficial for security and that would be a great reason to retire this in favor of that once it gets going.

Separately, however, I’m not entirely sure how, if you have known checksums for wheels, that you could possibly avoid eventually checking those checksums during a pip resolve. The prototype I’ve implemented (which I’ve been meaning to spend more time on recently) will use the metadata information to pull down URLs to download everything from along the way, then download all the wheels in parallel at the end, presumably checking checksums, although I need to verify that.

I am working on another approach (it works too) that modifies pip to write resolve URLs to stdout instead of actually downloading anything, and then downloads them all in one go in parallel, when the application is first started. By not downloading the wheels and checking the checksums in the same pip invocation that gets the URLs, I can definitely see a potential avenue for exploitation. However, we still have to pull down wheels in the end, and pex just uses pip to resolve now, so it should be checking checksums in the same places where pip does.

I’m vaguely familiar with where checksum validation happens in pip but not enough to answer more confidently. I think security should generally be a huge concern when proposing massive changes to pip resolves and I think that it needs a little more research on my part to be able to say more confidently that it’s not going to introduce a huge issue.

EDIT: One last possible twist on this is that along with the zipfile-searching part of this PR, it also adds a cache of dependencies, keyed by the requirement download URL, serialized in a json file, and stored across pip runs. If we wanted to methodically address the checksumming issue, it's possible we could store checksums from previous downloads there. That code is hairy and needs to be replaced anyway though, and I'm not sure how big that json file would get over time especially if we started adding longer strings to it. It would would be at best a workaround for the problem -- I believe the known attack vector of pulling a newly released version of a dependency from PyPI would reliably avoid the json cache, so it's not a solution here.

[ofek]

What is the status of this?

[uranusjr]

I think the main thing left is a format to (optionally) output the resolution result into (PEP 665, see #10636). So let’s wait for that PEP to land first.

[cosmicexplorer]

This work has largely been merged, although #12186 tracks in-flight changes to fix up metadata resolves and #12184 covers how to upstream the remaining caching of metadata lookups done in the prototype described here.