| 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 |
} |