/
modeling.go
328 lines (300 loc) · 9.2 KB
/
modeling.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
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
package modeling
import (
"container/list"
"errors"
"math"
"sync"
rbt "github.com/emirpasic/gods/trees/redblacktree"
corev1 "k8s.io/api/core/v1"
"k8s.io/apimachinery/pkg/api/resource"
"k8s.io/klog/v2"
clusterapis "github.com/karmada-io/karmada/pkg/apis/cluster/v1alpha1"
)
var (
mu sync.Mutex
modelSortings [][]resource.Quantity
defaultModelSorting []clusterapis.ResourceName
)
// ResourceSummary records the list of resourceModels
type ResourceSummary []resourceModels
// resourceModels records the number of each allocatable resource models.
type resourceModels struct {
// quantity is the total number of each allocatable resource models
// +required
Quantity int
// when the number of node is less than or equal to six, it will be sorted by linkedlist,
// when the number of node is more than six, it will be sorted by red-black tree.
// when the data structure is linkedlist,
// each item will store clusterResourceNode.
// +required
linkedlist *list.List
// when the data structure is redblack tree,
// each item will store a key-value pair,
// key is ResourceList, the value is quantity of this ResourceList
// +optional
redblackTree *rbt.Tree
}
// ClusterResourceNode represents the each raw resource entity without modeling.
type ClusterResourceNode struct {
// quantity is the the number of this node
// Only when the resourceLists are exactly the same can they be counted as the same node.
// +required
quantity int
// resourceList records the resource list of this node.
// It maybe contain cpu, mrmory, gpu...
// User can specify which parameters need to be included before the cluster starts
// +required
resourceList ResourceList
}
// ResourceList is a set of (resource name, quantity) pairs.
type ResourceList map[clusterapis.ResourceName]resource.Quantity
// InitSummary is the init function of modeling data structure
func InitSummary(resourceModels []clusterapis.ResourceModel) (ResourceSummary, error) {
var rsName []clusterapis.ResourceName
var rsList []ResourceList
for _, rm := range resourceModels {
tmp := map[clusterapis.ResourceName]resource.Quantity{}
for _, rmItem := range rm.Ranges {
if len(rsName) != len(rm.Ranges) {
rsName = append(rsName, rmItem.Name)
}
tmp[rmItem.Name] = rmItem.Min
}
rsList = append(rsList, tmp)
}
if len(rsName) != 0 && len(rsList) != 0 && (len(rsName) != len(rsList[0])) {
return nil, errors.New("the number of resourceName is not equal the number of resourceList")
}
var rs ResourceSummary
if len(rsName) != 0 {
defaultModelSorting = rsName
}
rs = make(ResourceSummary, len(rsList))
// generate a sorted array by first priority of ResourceName
modelSortings = make([][]resource.Quantity, len(rsName))
for index := 0; index < len(rsList); index++ {
for i, name := range rsName {
modelSortings[i] = append(modelSortings[i], rsList[index][name])
}
}
return rs, nil
}
// NewClusterResourceNode create new cluster resource node
func NewClusterResourceNode(resourceList corev1.ResourceList) ClusterResourceNode {
return ClusterResourceNode{
quantity: 1,
resourceList: ConvertToResourceList(resourceList),
}
}
func (rs *ResourceSummary) getIndex(crn ClusterResourceNode) int {
index := math.MaxInt
for i, m := range defaultModelSorting {
tmpIndex := searchLastLessElement(modelSortings[i], crn.resourceList[m])
if tmpIndex < index {
index = tmpIndex
}
}
return index
}
func searchLastLessElement(nums []resource.Quantity, target resource.Quantity) int {
low, high := 0, len(nums)-1
for low <= high {
mid := low + ((high - low) >> 1)
diff1 := nums[mid].Cmp(target)
var diff2 int
if mid != len(nums)-1 {
diff2 = nums[mid+1].Cmp(target)
}
// diff < 1 means nums[mid] <= target
// diff == 1 means nums[mid+1] > target
if diff1 < 1 {
if (mid == len(nums)-1) || (diff2 == 1) {
// find the last less element that equal to target element
return mid
}
low = mid + 1
} else {
high = mid - 1
}
}
return -1
}
// clusterResourceNodeComparator provides a fast comparison on clusterResourceNodes
func clusterResourceNodeComparator(a, b interface{}) int {
s1 := a.(ClusterResourceNode)
s2 := b.(ClusterResourceNode)
for index := 0; index < len(defaultModelSorting); index++ {
tmp1, tmp2 := s1.resourceList[defaultModelSorting[index]], s2.resourceList[defaultModelSorting[index]]
diff := tmp1.Cmp(tmp2)
if diff != 0 {
return diff
}
}
return 0
}
func safeChangeNum(num *int, change int) {
mu.Lock()
defer mu.Unlock()
*num += change
}
// AddToResourceSummary add resource node into modeling summary
func (rs *ResourceSummary) AddToResourceSummary(crn ClusterResourceNode) {
index := rs.getIndex(crn)
modeling := &(*rs)[index]
if rs.GetNodeNumFromModel(modeling) <= 5 {
root := modeling.linkedlist
if root == nil {
root = list.New()
}
found := false
// traverse linkedlist to add quantity of recourse modeling
for element := root.Front(); element != nil; element = element.Next() {
switch clusterResourceNodeComparator(element.Value, crn) {
case 0:
{
tmpCrn := element.Value.(ClusterResourceNode)
safeChangeNum(&tmpCrn.quantity, crn.quantity)
element.Value = tmpCrn
found = true
break
}
case 1:
{
root.InsertBefore(crn, element)
found = true
break
}
case -1:
{
continue
}
}
if found {
break
}
}
if !found {
root.PushBack(crn)
}
modeling.linkedlist = root
} else {
root := modeling.redblackTree
if root == nil {
root = llConvertToRbt(modeling.linkedlist)
modeling.linkedlist = nil
}
tmpNode := root.GetNode(crn)
if tmpNode != nil {
node := tmpNode.Key.(ClusterResourceNode)
safeChangeNum(&node.quantity, crn.quantity)
tmpNode.Key = node
} else {
root.Put(crn, crn.quantity)
}
modeling.redblackTree = root
}
safeChangeNum(&modeling.Quantity, crn.quantity)
}
func llConvertToRbt(list *list.List) *rbt.Tree {
root := rbt.NewWith(clusterResourceNodeComparator)
for element := list.Front(); element != nil; element = element.Next() {
tmpCrn := element.Value.(ClusterResourceNode)
root.Put(tmpCrn, tmpCrn.quantity)
}
return root
}
func rbtConvertToLl(rbt *rbt.Tree) *list.List {
root := list.New()
for _, v := range rbt.Keys() {
root.PushBack(v)
}
return root
}
// ConvertToResourceList is convert from corev1.ResourceList to ResourceList
func ConvertToResourceList(rslist corev1.ResourceList) ResourceList {
resourceList := ResourceList{}
for name, quantity := range rslist {
if name == corev1.ResourceCPU {
resourceList[clusterapis.ResourceCPU] = quantity
} else if name == corev1.ResourceMemory {
resourceList[clusterapis.ResourceMemory] = quantity
} else if name == corev1.ResourceStorage {
resourceList[clusterapis.ResourceStorage] = quantity
} else if name == corev1.ResourceEphemeralStorage {
resourceList[clusterapis.ResourceEphemeralStorage] = quantity
}
}
return resourceList
}
// GetNodeNumFromModel is for getting node number from the modeling
func (rs *ResourceSummary) GetNodeNumFromModel(model *resourceModels) int {
if model.linkedlist != nil && model.redblackTree == nil {
return model.linkedlist.Len()
} else if model.linkedlist == nil && model.redblackTree != nil {
return model.redblackTree.Size()
} else if model.linkedlist == nil && model.redblackTree == nil {
return 0
} else if model.linkedlist != nil && model.redblackTree != nil {
klog.Info("GetNodeNum: unknow error")
}
return 0
}
// DeleteFromResourceSummary dalete resource node into modeling summary
func (rs *ResourceSummary) DeleteFromResourceSummary(crn ClusterResourceNode) error {
index := rs.getIndex(crn)
modeling := &(*rs)[index]
if rs.GetNodeNumFromModel(modeling) >= 6 {
root := modeling.redblackTree
tmpNode := root.GetNode(crn)
if tmpNode != nil {
node := tmpNode.Key.(ClusterResourceNode)
safeChangeNum(&node.quantity, -crn.quantity)
tmpNode.Key = node
if node.quantity == 0 {
root.Remove(tmpNode)
}
} else {
return errors.New("delete fail: node no found in redblack tree")
}
modeling.redblackTree = root
} else {
root, tree := modeling.linkedlist, modeling.redblackTree
if root == nil && tree != nil {
root = rbtConvertToLl(tree)
}
if root == nil && tree == nil {
return errors.New("delete fail: node no found in linked list")
}
found := false
// traverse linkedlist to remove quantity of recourse modeling
for element := root.Front(); element != nil; element = element.Next() {
if clusterResourceNodeComparator(element.Value, crn) == 0 {
tmpCrn := element.Value.(ClusterResourceNode)
safeChangeNum(&tmpCrn.quantity, -crn.quantity)
element.Value = tmpCrn
if tmpCrn.quantity == 0 {
root.Remove(element)
}
found = true
}
if found {
break
}
}
if !found {
return errors.New("delete fail: node no found in linkedlist")
}
modeling.linkedlist = root
}
safeChangeNum(&modeling.Quantity, -crn.quantity)
return nil
}
// UpdateInResourceSummary update resource node into modeling summary
func (rs *ResourceSummary) UpdateInResourceSummary(oldNode, newNode ClusterResourceNode) error {
rs.AddToResourceSummary(newNode)
err := rs.DeleteFromResourceSummary(oldNode)
if err != nil {
return errors.New("delete fail: node no found in linked list")
}
return nil
}