Debian Codegraph @

pkg/util/flowcontrol/conc_alloc.go

raw
1 /*
2 Copyright 2022 The Kubernetes Authors.
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 */
16
17 package flowcontrol
18
19 import (
20 "errors"
21 "fmt"
22 "math"
23 "sort"
24 )
25
26 // allocProblemItem is one of the classes to which computeConcurrencyAllocation should make an allocation
27 type allocProblemItem struct {
28 target float64
29 lowerBound float64
30 upperBound float64
31 }
32
33 // relativeAllocItem is like allocProblemItem but with target avoiding zero and the bounds divided by the target
34 type relativeAllocItem struct {
35 target float64
36 relativeLowerBound float64
37 relativeUpperBound float64
38 }
39
40 // relativeAllocProblem collects together all the classes and holds the result of sorting by increasing bounds.
41 // For J <= K, ascendingIndices[J] identifies a bound that is <= the one of ascendingIndices[K].
42 // When ascendingIndices[J] = 2*N + 0, this identifies the lower bound of items[N].
43 // When ascendingIndices[J] = 2*N + 1, this identifies the upper bound of items[N].
44 type relativeAllocProblem struct {
45 items []relativeAllocItem
46 ascendingIndices []int
47 }
48
49 // initIndices fills in ascendingIndices and sorts them
50 func (rap *relativeAllocProblem) initIndices() *relativeAllocProblem {
51 rap.ascendingIndices = make([]int, len(rap.items)*2)
52 for idx := 0; idx < len(rap.ascendingIndices); idx++ {
53 rap.ascendingIndices[idx] = idx
54 }
55 sort.Sort(rap)
56 return rap
57 }
58
59 func (rap *relativeAllocProblem) getItemIndex(idx int) (int, bool) {
60 packedIndex := rap.ascendingIndices[idx]
61 itemIndex := packedIndex / 2
62 return itemIndex, packedIndex == itemIndex*2
63 }
64
65 // decode(J) returns the bound associated with ascendingIndices[J], the associated items index,
66 // and a bool indicating whether the bound is the item's lower bound.
67 func (rap *relativeAllocProblem) decode(idx int) (float64, int, bool) {
68 itemIdx, lower := rap.getItemIndex(idx)
69 if lower {
70 return rap.items[itemIdx].relativeLowerBound, itemIdx, lower
71 }
72 return rap.items[itemIdx].relativeUpperBound, itemIdx, lower
73 }
74
75 func (rap *relativeAllocProblem) getProportion(idx int) float64 {
76 prop, _, _ := rap.decode(idx)
77 return prop
78 }
79
80 func (rap *relativeAllocProblem) Len() int { return len(rap.items) * 2 }
81
82 func (rap *relativeAllocProblem) Less(i, j int) bool {
83 return rap.getProportion(i) < rap.getProportion(j)
84 }
85
86 func (rap *relativeAllocProblem) Swap(i, j int) {
87 rap.ascendingIndices[i], rap.ascendingIndices[j] = rap.ascendingIndices[j], rap.ascendingIndices[i]
88 }
89
90 // minMax records the minimum and maximum value seen while scanning a set of numbers
91 type minMax struct {
92 min float64
93 max float64
94 }
95
96 // note scans one more number
97 func (mm *minMax) note(x float64) {
98 mm.min = math.Min(mm.min, x)
99 mm.max = math.Max(mm.max, x)
100 }
101
102 const MinTarget = 0.001
103 const epsilon = 0.0000001
104
105 // computeConcurrencyAllocation returns the unique `allocs []float64`, and
106 // an associated `fairProp float64`, that jointly have
107 // all of the following properties (to the degree that floating point calculations allow)
108 // if possible otherwise returns an error saying why it is impossible.
109 // `allocs` sums to `requiredSum`.
110 // For each J in [0, len(classes)):
111 // 1. `classes[J].lowerBound <= allocs[J] <= classes[J].upperBound` and
112 // 2. exactly one of the following is true:
113 // 2a. `allocs[J] == fairProp * classes[J].target`,
114 // 2b. `allocs[J] == classes[J].lowerBound && classes[J].lowerBound > fairProp * classes[J].target`, or
115 // 2c. `allocs[J] == classes[J].upperBound && classes[J].upperBound < fairProp * classes[J].target`.
116 //
117 // Each allocProblemItem is required to have `target >= lowerBound >= 0` and `upperBound >= lowerBound`.
118 // A target smaller than MinTarget is treated as if it were MinTarget.
119 func computeConcurrencyAllocation(requiredSum int, classes []allocProblemItem) ([]float64, float64, error) {
120 if requiredSum < 0 {
121 return nil, 0, errors.New("negative sums are not supported")
122 }
123 requiredSumF := float64(requiredSum)
124 var lowSum, highSum, targetSum float64
125 ubRange := minMax{min: float64(math.MaxFloat32)}
126 lbRange := minMax{min: float64(math.MaxFloat32)}
127 relativeItems := make([]relativeAllocItem, len(classes))
128 for idx, item := range classes {
129 target := item.target
130 if item.lowerBound < 0 {
131 return nil, 0, fmt.Errorf("lower bound %d is %v but negative lower bounds are not allowed", idx, item.lowerBound)
132 }
133 if target < item.lowerBound {
134 return nil, 0, fmt.Errorf("target %d is %v, which is below its lower bound of %v", idx, target, item.lowerBound)
135 }
136 if item.upperBound < item.lowerBound {
137 return nil, 0, fmt.Errorf("upper bound %d is %v but should not be less than the lower bound %v", idx, item.upperBound, item.lowerBound)
138 }
139 if target < MinTarget {
140 // tweak this to a non-zero value so avoid dividing by zero
141 target = MinTarget
142 }
143 lowSum += item.lowerBound
144 highSum += item.upperBound
145 targetSum += target
146 relativeItem := relativeAllocItem{
147 target: target,
148 relativeLowerBound: item.lowerBound / target,
149 relativeUpperBound: item.upperBound / target,
150 }
151 ubRange.note(relativeItem.relativeUpperBound)
152 lbRange.note(relativeItem.relativeLowerBound)
153 relativeItems[idx] = relativeItem
154 }
155 if lbRange.max > 1 {
156 return nil, 0, fmt.Errorf("lbRange.max-1=%v, which is impossible because lbRange.max can not be greater than 1", lbRange.max-1)
157 }
158 if lowSum-requiredSumF > epsilon {
159 return nil, 0, fmt.Errorf("lower bounds sum to %v, which is higher than the required sum of %v", lowSum, requiredSum)
160 }
161 if requiredSumF-highSum > epsilon {
162 return nil, 0, fmt.Errorf("upper bounds sum to %v, which is lower than the required sum of %v", highSum, requiredSum)
163 }
164 ans := make([]float64, len(classes))
165 if requiredSum == 0 {
166 return ans, 0, nil
167 }
168 if lowSum-requiredSumF > -epsilon { // no wiggle room, constrained from below
169 for idx, item := range classes {
170 ans[idx] = item.lowerBound
171 }
172 return ans, lbRange.min, nil
173 }
174 if requiredSumF-highSum > -epsilon { // no wiggle room, constrained from above
175 for idx, item := range classes {
176 ans[idx] = item.upperBound
177 }
178 return ans, ubRange.max, nil
179 }
180 // Now we know the solution is a unique fairProp in [lbRange.min, ubRange.max].
181 // See if the solution does not run into any bounds.
182 fairProp := requiredSumF / targetSum
183 if lbRange.max <= fairProp && fairProp <= ubRange.min { // no bounds matter
184 for idx := range classes {
185 ans[idx] = relativeItems[idx].target * fairProp
186 }
187 return ans, fairProp, nil
188 }
189 // Sadly, some bounds matter.
190 // We find the solution by sorting the bounds and considering progressively
191 // higher values of fairProp, starting from lbRange.min.
192 rap := (&relativeAllocProblem{items: relativeItems}).initIndices()
193 sumSoFar := lowSum
194 fairProp = lbRange.min
195 var sensitiveTargetSum, deltaSensitiveTargetSum float64
196 var numSensitiveClasses, deltaSensitiveClasses int
197 var nextIdx int
198 // `nextIdx` is the next `rap` index to consider.
199 // `sumSoFar` is what the allocs would sum to if the current
200 // value of `fairProp` solves the problem.
201 // If the current value of fairProp were the answer then
202 // `sumSoFar == requiredSum`.
203 // Otherwise the next increment in fairProp involves changing the allocations
204 // of `numSensitiveClasses` classes whose targets sum to `sensitiveTargetSum`;
205 // for the other classes, an upper or lower bound has applied and will continue to apply.
206 // The last increment of nextIdx calls for adding `deltaSensitiveClasses`
207 // to `numSensitiveClasses` and adding `deltaSensitiveTargetSum` to `sensitiveTargetSum`.
208 for sumSoFar < requiredSumF {
209 // There might be more than one bound that is equal to the current value
210 // of fairProp; find all of them because they will all be relevant to
211 // the next change in fairProp.
212 // Set nextBound to the next bound that is NOT equal to fairProp,
213 // and advance nextIdx to the index of that bound.
214 var nextBound float64
215 for {
216 sensitiveTargetSum += deltaSensitiveTargetSum
217 numSensitiveClasses += deltaSensitiveClasses
218 if nextIdx >= rap.Len() {
219 return nil, 0, fmt.Errorf("impossible: ran out of bounds to consider in bound-constrained problem")
220 }
221 var itemIdx int
222 var lower bool
223 nextBound, itemIdx, lower = rap.decode(nextIdx)
224 if lower {
225 deltaSensitiveClasses = 1
226 deltaSensitiveTargetSum = rap.items[itemIdx].target
227 } else {
228 deltaSensitiveClasses = -1
229 deltaSensitiveTargetSum = -rap.items[itemIdx].target
230 }
231 nextIdx++
232 if nextBound > fairProp {
233 break
234 }
235 }
236 // fairProp can increase to nextBound without passing any intermediate bounds.
237 if numSensitiveClasses == 0 {
238 // No classes are affected by the next range of fairProp; skip right past it
239 fairProp = nextBound
240 continue
241 }
242 // See whether fairProp can increase to the solution before passing the next bound.
243 deltaFairProp := (requiredSumF - sumSoFar) / sensitiveTargetSum
244 nextProp := fairProp + deltaFairProp
245 if nextProp <= nextBound {
246 fairProp = nextProp
247 break
248 }
249 // No, fairProp has to increase above nextBound
250 sumSoFar += (nextBound - fairProp) * sensitiveTargetSum
251 fairProp = nextBound
252 }
253 for idx, item := range classes {
254 ans[idx] = math.Max(item.lowerBound, math.Min(item.upperBound, fairProp*relativeItems[idx].target))
255 }
256 return ans, fairProp, nil
257 }