Support for concurrent metadata fetching

[zkat]

Fetching metadata synchronously and blocking on its resolution is bound to be extremely slow. In Orogene, our resolver is able to optimistically parallelize dependency metadata fetches before actual placement, so you can have e.g. 50 different packages looking up version information while the resolver works on the data that's already fetched.

The perf benefits of this are enormous.

Anyway just creating this issue on @Eh2406's request :)

[Eh2406]

Thank you for creating the issue, it will give us a place to remember to continue the conversation. I look forward to learning from your deep experience, and the performance issues that are of most concern to you.

If I understand correctly Orogene does not need to do any backtracking. This means that once it's decided a version is needed then it will definitely need the information about its dependencies. Furthermore it can process those dependencies in whatever order they show up.

A NP-Complete resolver also needs to handle cancellation, it may have considered foo@1.0.0 but now realizes that that version (and therefore its dependencies) are not part of the solution. In PubGrub 0.2 there is a choose_package_version which is an iterator of all things solver still considers relevant. It is perfectly reasonable for an implementation to spawn network requests for all of them, and choose one that has already been retrieved only blocking if none of them have yet returned.

Given cancellation I don't see an elegant API where the dependency provider can push work into the resolver. If some request comes in and it's still relevant everything is happy. If that request comes in and it's no longer relevant what is the resolver supposed to do? It can drop it on the floor, but that seems wasteful. It can put it in a cashe, in case the resolver needs to request it again. But in that case, this caching behavior can just as well live outside the resolver's code. Although I should make a fully worked out example to figure out what the problems are.

My fundamental question, I think, is what API would you like to see a library like PubGrub to have?

[zkat]

The backtracking is kind of irrelevant: what there needs to be an async API for is "I ran into a new-to-the-resolver dependency name, and I need to get its list of available versions", although even this might vary by package manager--this is just the kind of API that Orogene would be able to use because it works such that you get the list of versions, then you do a (synchronous) resolution based on that version list, which is now already in memory.

Once you've requested the metadata with all the versions for one package name, you don't need to repeat the process ever again--you just memoize the metadata.

So the async thing that PubGrub would need to have is something like:

trait DependencyProvider {
  type Identifier;
  type Metadata;
  async fn get_metadata(&self, id: Self::Identifier) -> Self::Metadata;
}

[Eh2406]

That makes a lot of sense. I think the existing API fits in your model as the synchronous resolution algorithm, which is called inside some wrapper that does the asynchronous data retrieval and memoize. (And we should add an example of how to make a wrapper like that.)

The place I think backtracking fits in... Let's say we have a complex package a which comes in several versions of 1.x and some 2.x. The versions of 1.x directly depend on a large number of packages, 2.x have no dependencies. If we want to optimize how quickly we can provide responses to the synchronous resolution, just when the Metadata for a comes in we would trigger a get for the Metadata for all dependencies of all versions of a. This ensures that whatever query comes next the metadata is already in flight! However if resolution decides to choose 3.x then those extra network requests will be a complete waste, and taking up bandwidth that we could be using to retrieve metadata about things that actually mattered. Even if we only prefetch for the dependencies of the versions the resolver is actually considering, backtracking means that in the future the resolver may no longer be considering those versions.

[zkat]

The way Orogene works is that it queues up multiple concurrent metadata requests based on the latest resolved version of their parent package.

So if you have just resolved v1.2 of a package, you take all of that package's dependencies and add them to a queue for concurrent lookup (which you'll wait on later), and as you get to actually resolving those other deps, you add things to the queue further: https://github.com/orogene/orogene/blob/main/crates/node-maintainer/src/resolver.rs#L109-L182

This is essentially the core of the orogene resolver (which, again, doesn't backtrack, but I don't actually think that changes the game here as much, as far as the key point of concurrent metadata fetches goes): https://github.com/orogene/orogene/blob/main/crates/node-maintainer/src/resolver.rs#L52-L276

It's a bit of a trick to make what is conceptually a sequential process parallelize the things that it can.

[Eh2406]

That is 100% possible with wrappers around PubGrub! I absolutely need to document as an example (and in the book) how to put the pieces together.