about summary refs log tree commit diff
path: root/tools/nixery/server/layers/grouping.go
blob: 07a9e0e230a511fc524f4cf137d96ccbfe15646a (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
// 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:
//
// 1. 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 }
package layers

import (
	"crypto/sha1"
	"fmt"
	"log"
	"regexp"
	"sort"
	"strings"

	"gonum.org/v1/gonum/graph/flow"
	"gonum.org/v1/gonum/graph/simple"
)

// RuntimeGraph represents structured information from Nix about the runtime
// dependencies of a derivation.
//
// This is generated in Nix by using the exportReferencesGraph feature.
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"`
}

// 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 Popularity = map[string]int

// Layer represents the data returned for each layer that Nix should
// build for the container image.
type Layer struct {
	Contents    []string `json:"contents"`
	mergeRating uint64
}

// Hash the contents of a layer to create a deterministic identifier that can be
// used for caching.
func (l *Layer) Hash() string {
	sum := sha1.Sum([]byte(strings.Join(l.Contents, ":")))
	return fmt.Sprintf("%x", sum)
}

func (a Layer) merge(b Layer) Layer {
	a.Contents = append(a.Contents, b.Contents...)
	a.mergeRating += b.mergeRating
	return a
}

// closure as pointed to by the graph nodes.
type closure struct {
	GraphID    int64
	Path       string
	Size       uint64
	Refs       []string
	Popularity int
}

func (c *closure) ID() int64 {
	return c.GraphID
}

var nixRegexp = regexp.MustCompile(`^/nix/store/[a-z0-9]+-`)

func (c *closure) DOTID() string {
	return nixRegexp.ReplaceAllString(c.Path, "")
}

// bigOrPopular checks whether this closure should be considered for
// separation into its own layer, even if it would otherwise only
// appear in a subtree of the dominator tree.
func (c *closure) bigOrPopular() bool {
	const sizeThreshold = 100 * 1000000 // 100MB

	if c.Size > sizeThreshold {
		return true
	}

	// The threshold value used here is currently roughly the
	// minimum number of references that only 1% of packages in
	// the entire package set have.
	//
	// TODO(tazjin): Do this more elegantly by calculating
	// percentiles for each package and using those instead.
	if c.Popularity >= 1000 {
		return true
	}

	return false
}

func insertEdges(graph *simple.DirectedGraph, cmap *map[string]*closure, node *closure) {
	// Big or popular nodes get a separate edge from the top to
	// flag them for their own layer.
	if node.bigOrPopular() && !graph.HasEdgeFromTo(0, node.ID()) {
		edge := graph.NewEdge(graph.Node(0), node)
		graph.SetEdge(edge)
	}

	for _, c := range node.Refs {
		// Nix adds a self reference to each node, which
		// should not be inserted.
		if c != node.Path {
			edge := graph.NewEdge(node, (*cmap)[c])
			graph.SetEdge(edge)
		}
	}
}

// Create a graph structure from the references supplied by Nix.
func buildGraph(refs *RuntimeGraph, pop *Popularity) *simple.DirectedGraph {
	cmap := make(map[string]*closure)
	graph := simple.NewDirectedGraph()

	// Insert all closures into the graph, as well as a fake root
	// closure which serves as the top of the tree.
	//
	// A map from store paths to IDs is kept to actually insert
	// edges below.
	root := &closure{
		GraphID: 0,
		Path:    "image_root",
	}
	graph.AddNode(root)

	for idx, c := range refs.Graph {
		node := &closure{
			GraphID: int64(idx + 1), // inc because of root node
			Path:    c.Path,
			Size:    c.Size,
			Refs:    c.Refs,
		}

		if p, ok := (*pop)[node.DOTID()]; ok {
			node.Popularity = p
		} else {
			node.Popularity = 1
		}

		graph.AddNode(node)
		cmap[c.Path] = node
	}

	// Insert the top-level closures with edges from the root
	// node, then insert all edges for each closure.
	for _, p := range refs.References.Graph {
		edge := graph.NewEdge(root, cmap[p])
		graph.SetEdge(edge)
	}

	for _, c := range cmap {
		insertEdges(graph, &cmap, c)
	}

	return graph
}

// Extracts a subgraph starting at the specified root from the
// dominator tree. The subgraph is converted into a flat list of
// layers, each containing the store paths and merge rating.
func groupLayer(dt *flow.DominatorTree, root *closure) Layer {
	size := root.Size
	contents := []string{root.Path}
	children := dt.DominatedBy(root.ID())

	// This iteration does not use 'range' because the list being
	// iterated is modified during the iteration (yes, I'm sorry).
	for i := 0; i < len(children); i++ {
		child := children[i].(*closure)
		size += child.Size
		contents = append(contents, child.Path)
		children = append(children, dt.DominatedBy(child.ID())...)
	}

	// Contents are sorted to ensure that hashing is consistent
	sort.Strings(contents)

	return Layer{
		Contents: contents,
		// TODO(tazjin): The point of this is to factor in
		// both the size and the popularity when making merge
		// decisions, but there might be a smarter way to do
		// it than a plain multiplication.
		mergeRating: uint64(root.Popularity) * size,
	}
}

// Calculate the dominator tree of the entire package set and group
// each top-level subtree into a layer.
//
// Layers are merged together until they fit into the layer budget,
// based on their merge rating.
func dominate(budget int, graph *simple.DirectedGraph) []Layer {
	dt := flow.Dominators(graph.Node(0), graph)

	var layers []Layer
	for _, n := range dt.DominatedBy(dt.Root().ID()) {
		layers = append(layers, groupLayer(&dt, n.(*closure)))
	}

	sort.Slice(layers, func(i, j int) bool {
		return layers[i].mergeRating < layers[j].mergeRating
	})

	if len(layers) > budget {
		log.Printf("Ideal image has %v layers, but budget is %v\n", len(layers), budget)
	}

	for len(layers) > budget {
		merged := layers[0].merge(layers[1])
		layers[1] = merged
		layers = layers[1:]
	}

	return layers
}

// 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.
func Group(refs *RuntimeGraph, pop *Popularity, budget int) []Layer {
	graph := buildGraph(refs, pop)
	return dominate(budget, graph)
}