forked from hashicorp/nomad
-
Notifications
You must be signed in to change notification settings - Fork 1
/
funcs.go
139 lines (120 loc) · 3.67 KB
/
funcs.go
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
package structs
import (
crand "crypto/rand"
"fmt"
"math"
)
// RemoveAllocs is used to remove any allocs with the given IDs
// from the list of allocations
func RemoveAllocs(alloc []*Allocation, remove []*Allocation) []*Allocation {
// Convert remove into a set
removeSet := make(map[string]struct{})
for _, remove := range remove {
removeSet[remove.ID] = struct{}{}
}
n := len(alloc)
for i := 0; i < n; i++ {
if _, ok := removeSet[alloc[i].ID]; ok {
alloc[i], alloc[n-1] = alloc[n-1], nil
i--
n--
}
}
alloc = alloc[:n]
return alloc
}
// FilterTerminalAllocs filters out all allocations in a terminal state
func FilterTerminalAllocs(allocs []*Allocation) []*Allocation {
n := len(allocs)
for i := 0; i < n; i++ {
if allocs[i].TerminalStatus() {
allocs[i], allocs[n-1] = allocs[n-1], nil
i--
n--
}
}
return allocs[:n]
}
// AllocsFit checks if a given set of allocations will fit on a node.
// The netIdx can optionally be provided if its already been computed.
// If the netIdx is provided, it is assumed that the client has already
// ensured there are no collisions.
func AllocsFit(node *Node, allocs []*Allocation, netIdx *NetworkIndex) (bool, string, *Resources, error) {
// Compute the utilization from zero
used := new(Resources)
// Add the reserved resources of the node
if node.Reserved != nil {
if err := used.Add(node.Reserved); err != nil {
return false, "", nil, err
}
}
// For each alloc, add the resources
for _, alloc := range allocs {
if err := used.Add(alloc.Resources); err != nil {
return false, "", nil, err
}
}
// Check that the node resources are a super set of those
// that are being allocated
if superset, dimension := node.Resources.Superset(used); !superset {
return false, dimension, used, nil
}
// Create the network index if missing
if netIdx == nil {
netIdx = NewNetworkIndex()
if netIdx.SetNode(node) || netIdx.AddAllocs(allocs) {
return false, "reserved port collision", used, nil
}
}
// Check if the network is overcommitted
if netIdx.Overcommitted() {
return false, "bandwidth exceeded", used, nil
}
// Allocations fit!
return true, "", used, nil
}
// ScoreFit is used to score the fit based on the Google work published here:
// http://www.columbia.edu/~cs2035/courses/ieor4405.S13/datacenter_scheduling.ppt
// This is equivalent to their BestFit v3
func ScoreFit(node *Node, util *Resources) float64 {
// Determine the node availability
nodeCpu := float64(node.Resources.CPU)
if node.Reserved != nil {
nodeCpu -= float64(node.Reserved.CPU)
}
nodeMem := float64(node.Resources.MemoryMB)
if node.Reserved != nil {
nodeMem -= float64(node.Reserved.MemoryMB)
}
// Compute the free percentage
freePctCpu := 1 - (float64(util.CPU) / nodeCpu)
freePctRam := 1 - (float64(util.MemoryMB) / nodeMem)
// Total will be "maximized" the smaller the value is.
// At 100% utilization, the total is 2, while at 0% util it is 20.
total := math.Pow(10, freePctCpu) + math.Pow(10, freePctRam)
// Invert so that the "maximized" total represents a high-value
// score. Because the floor is 20, we simply use that as an anchor.
// This means at a perfect fit, we return 18 as the score.
score := 20.0 - total
// Bound the score, just in case
// If the score is over 18, that means we've overfit the node.
if score > 18.0 {
score = 18.0
} else if score < 0 {
score = 0
}
return score
}
// GenerateUUID is used to generate a random UUID
func GenerateUUID() string {
buf := make([]byte, 16)
if _, err := crand.Read(buf); err != nil {
panic(fmt.Errorf("failed to read random bytes: %v", err))
}
return fmt.Sprintf("%08x-%04x-%04x-%04x-%12x",
buf[0:4],
buf[4:6],
buf[6:8],
buf[8:10],
buf[10:16])
}