Documentation
¶
Overview ¶
This package reads an export reference graph (i.e. a graph representing the runtime dependencies of a set of derivations) created by Nix and groups it in a way that is likely to match the grouping for other derivation sets with overlapping dependencies.
This is used to determine which derivations to include in which layers of a container image.
Inputs ¶
- a graph of Nix runtime dependencies, generated via exportReferenceGraph
- popularity values of each package in the Nix package set (in the form of a direct reference count)
- a maximum number of layers to allocate for the image (the "layer budget")
Algorithm ¶
It works by first creating a (directed) dependency tree:
img (root node) │ ├───> A ─────┐ │ v ├───> B ───> E │ ^ ├───> C ─────┘ │ │ │ v └───> D ───> F
│ └────> G
Each node (i.e. package) is then visited to determine how important it is to separate this node into its own layer, specifically:
- Is the node within a certain threshold percentile of absolute popularity within all of nixpkgs? (e.g. `glibc`, `openssl`)
2. Is the node's runtime closure above a threshold size? (e.g. 100MB)
In either case, a bit is flipped for this node representing each condition and an edge to it is inserted directly from the image root, if it does not already exist.
For the rest of the example we assume 'G' is above the threshold size and 'E' is popular.
This tree is then transformed into a dominator tree:
img │ ├───> A ├───> B ├───> C ├───> E ├───> D ───> F └───> G
Specifically this means that the paths to A, B, C, E, G, and D always pass through the root (i.e. are dominated by it), whilst F is dominated by D (all paths go through it).
The top-level subtrees are considered as the initially selected layers.
If the list of layers fits within the layer budget, it is returned.
Otherwise, a merge rating is calculated for each layer. This is the product of the layer's total size and its root node's popularity.
Layers are then merged in ascending order of merge ratings until they fit into the layer budget.
Threshold values ¶
Threshold values for the partitioning conditions mentioned above have not yet been determined, but we will make a good first guess based on gut feeling and proceed to measure their impact on cache hits/misses.
Example ¶
Using the logic described above as well as the example presented in the introduction, this program would create the following layer groupings (assuming no additional partitioning):
Layer budget: 1 Layers: { A, B, C, D, E, F, G }
Layer budget: 2 Layers: { G }, { A, B, C, D, E, F }
Layer budget: 3 Layers: { G }, { E }, { A, B, C, D, F }
Layer budget: 4 Layers: { G }, { E }, { D, F }, { A, B, C }
...
Layer budget: 10 Layers: { E }, { D, F }, { A }, { B }, { C }
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func PackageFromPath ¶
PackageFromPath returns the name of a Nix package based on its output store path.
Types ¶
type Layer ¶
Layer represents the data returned for each layer that Nix should build for the container image.
func GroupLayers ¶
func GroupLayers(refs *RuntimeGraph, pop *Popularity, budget int) []Layer
groupLayers applies the algorithm described above the its input and returns a list of layers, each consisting of a list of Nix store paths that it should contain.
type Popularity ¶
Popularity data for each Nix package that was calculated in advance.
Popularity is a number from 1-100 that represents the popularity percentile in which this package resides inside of the nixpkgs tree.
type RuntimeGraph ¶
type RuntimeGraph struct {
References struct {
Graph []string `json:"graph"`
} `json:"exportReferencesGraph"`
Graph []struct {
Size uint64 `json:"closureSize"`
Path string `json:"path"`
Refs []string `json:"references"`
} `json:"graph"`
}
runtimeGraph represents structured information from Nix about the runtime dependencies of a derivation.
This is generated in Nix by using the exportReferencesGraph feature.
Source Files