Variable pipelines

[awgreene]

Task

Write an RFC for resolution pipelines as a possible (extensible/observable) architecture for generating Variables for resolution.

Introduction

The deppy solver takes as input a slice of Variables. A Variable contains an unique ID and a slice of Constraint that models its relationships to other Variables. The solver unwraps this set of Variables into a boolean statement that is given as input to the internal SAT solver. With this mechanism, the deppy solver tries to determine the smallest set of Variables such that all constraints are met.

Variables are derived by VariableSources from domain specific objects (e.g. user intents, packages, bundles, the cluster, etc.) whose properties drive the conversion between domain object and Variable including all of the Variable's constraints. Here's an example:

Required Package
A required package Variable represents the user's intent to install a package, optionally within a semver range and/or specific channel. It could be defined in code as follows:

v := NewSimpleVariable("required-package/foo", Dependency(getBundleVariableIDs(packageName, semverRange, channel)))

Where required-package/foo is the ID of the variable, and the dependency constraint references all bundles within the channel/semver range. The dependency constraint would look roughly like:

~ required-package/foo ∨ bundle_1 ∨ bundle_2 ∨ ... ∨ bundle_n_,

in other words, either at least one of the bundle variables is true OR required-package/foo is false.

Variable Generation Process
The current variable generation process is as follows:

• for each Operator create a required package variable with the filtered set of bundles
• for each of the bundles, create a variable for the bundle including all constraints (e.g. dependencies, conflicts, etc.)
• recursively explore the dependency chain for each bundle, creating variables for the dependencies
• add global constraint variables to ensure solutions only take one bundle / package and one bundle / gvk

This set of variables will be passed to the resolver for evaluation.

Problem

We need a way to produce the Variables and their Constraints, from a variety of sources (e.g. resources, cluster(s), catalog source(s), etc.). It needs to be easy to observe the Variable creation process. This is important for debugging and making it easier to understand why the resolver is behaving in a particular way. It should also be extensible. We want to avoid going deep into the code in order to add a new VariableSource.

Requirements

• Must Observability: it should be relatively easy to debug and understand which variables are being produced and how
• Must Extensibility: the process by which we observe the environment and produce variables should be easily extensible: adding new types of variables and constraints to affect resolution (e.g. no installations on Friday's)
• Should Configurability: it should be possible to define the variable production process externally to deppy (e.g. via configuration file or kubernetes resource)

Acceptance Criteria

• RFC for pipelines written up and socialized
• Consensus is reached
• If green, break down the RFC into issues

[github-actions]

This issue has become stale because it has been open 60 days with no activity. The maintainers of this repo will remove this label during issue triage or it will be removed automatically after an update. Adding the lifecycle/frozen label will cause this issue to ignore lifecycle events.

[github-actions]

This issue has become stale because it has been open 60 days with no activity. The maintainers of this repo will remove this label during issue triage or it will be removed automatically after an update. Adding the lifecycle/frozen label will cause this issue to ignore lifecycle events.

[perdasilva]

closed as obsolete