| 1 |
/* |
| 2 |
Copyright 2019 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 fairqueuing |
| 18 |
|
| 19 |
import ( |
| 20 |
"math" |
| 21 |
"sync" |
| 22 |
"time" |
| 23 |
|
| 24 |
fcmetrics "k8s.io/apiserver/pkg/util/flowcontrol/metrics" |
| 25 |
|
| 26 |
"k8s.io/utils/clock" |
| 27 |
) |
| 28 |
|
| 29 |
// Integrator computes the moments of some variable X over time as |
| 30 |
// read from a particular clock. The integrals start when the |
| 31 |
// Integrator is created, and ends at the latest operation on the |
| 32 |
// Integrator. |
| 33 |
type Integrator interface { |
| 34 |
fcmetrics.Gauge |
| 35 |
|
| 36 |
GetResults() IntegratorResults |
| 37 |
|
| 38 |
// Return the results of integrating to now, and reset integration to start now |
| 39 |
Reset() IntegratorResults |
| 40 |
} |
| 41 |
|
| 42 |
// IntegratorResults holds statistical abstracts of the integration |
| 43 |
type IntegratorResults struct { |
| 44 |
Duration float64 //seconds |
| 45 |
Average float64 //time-weighted |
| 46 |
Deviation float64 //standard deviation: sqrt(avg((value-avg)^2)) |
| 47 |
Min, Max float64 |
| 48 |
} |
| 49 |
|
| 50 |
// Equal tests for semantic equality. |
| 51 |
// This considers all NaN values to be equal to each other. |
| 52 |
func (x *IntegratorResults) Equal(y *IntegratorResults) bool { |
| 53 |
return x == y || x != nil && y != nil && x.Duration == y.Duration && x.Min == y.Min && x.Max == y.Max && (x.Average == y.Average || math.IsNaN(x.Average) && math.IsNaN(y.Average)) && (x.Deviation == y.Deviation || math.IsNaN(x.Deviation) && math.IsNaN(y.Deviation)) |
| 54 |
} |
| 55 |
|
| 56 |
type integrator struct { |
| 57 |
name string |
| 58 |
clock clock.PassiveClock |
| 59 |
sync.Mutex |
| 60 |
lastTime time.Time |
| 61 |
x float64 |
| 62 |
moments Moments |
| 63 |
min, max float64 |
| 64 |
} |
| 65 |
|
| 66 |
// NewNamedIntegrator makes one that uses the given clock and name |
| 67 |
func NewNamedIntegrator(clock clock.PassiveClock, name string) Integrator { |
| 68 |
return &integrator{ |
| 69 |
name: name, |
| 70 |
clock: clock, |
| 71 |
lastTime: clock.Now(), |
| 72 |
} |
| 73 |
} |
| 74 |
|
| 75 |
func (igr *integrator) Set(x float64) { |
| 76 |
igr.Lock() |
| 77 |
igr.setLocked(x) |
| 78 |
igr.Unlock() |
| 79 |
} |
| 80 |
|
| 81 |
func (igr *integrator) Add(deltaX float64) { |
| 82 |
igr.Lock() |
| 83 |
igr.setLocked(igr.x + deltaX) |
| 84 |
igr.Unlock() |
| 85 |
} |
| 86 |
|
| 87 |
func (igr *integrator) Inc() { |
| 88 |
igr.Add(1) |
| 89 |
} |
| 90 |
|
| 91 |
func (igr *integrator) Dec() { |
| 92 |
igr.Add(-1) |
| 93 |
} |
| 94 |
|
| 95 |
func (igr *integrator) SetToCurrentTime() { |
| 96 |
igr.Set(float64(time.Now().UnixNano())) |
| 97 |
} |
| 98 |
|
| 99 |
func (igr *integrator) setLocked(x float64) { |
| 100 |
igr.updateLocked() |
| 101 |
igr.x = x |
| 102 |
if x < igr.min { |
| 103 |
igr.min = x |
| 104 |
} |
| 105 |
if x > igr.max { |
| 106 |
igr.max = x |
| 107 |
} |
| 108 |
} |
| 109 |
|
| 110 |
func (igr *integrator) updateLocked() { |
| 111 |
now := igr.clock.Now() |
| 112 |
dt := now.Sub(igr.lastTime).Seconds() |
| 113 |
igr.lastTime = now |
| 114 |
igr.moments = igr.moments.Add(ConstantMoments(dt, igr.x)) |
| 115 |
} |
| 116 |
|
| 117 |
func (igr *integrator) GetResults() IntegratorResults { |
| 118 |
igr.Lock() |
| 119 |
defer igr.Unlock() |
| 120 |
return igr.getResultsLocked() |
| 121 |
} |
| 122 |
|
| 123 |
func (igr *integrator) Reset() IntegratorResults { |
| 124 |
igr.Lock() |
| 125 |
defer igr.Unlock() |
| 126 |
results := igr.getResultsLocked() |
| 127 |
igr.moments = Moments{} |
| 128 |
igr.min = igr.x |
| 129 |
igr.max = igr.x |
| 130 |
return results |
| 131 |
} |
| 132 |
|
| 133 |
func (igr *integrator) getResultsLocked() (results IntegratorResults) { |
| 134 |
igr.updateLocked() |
| 135 |
results.Min, results.Max = igr.min, igr.max |
| 136 |
results.Duration = igr.moments.ElapsedSeconds |
| 137 |
results.Average, results.Deviation = igr.moments.AvgAndStdDev() |
| 138 |
return |
| 139 |
} |
| 140 |
|
| 141 |
// Moments are the integrals of the 0, 1, and 2 powers of some |
| 142 |
// variable X over some range of time. |
| 143 |
type Moments struct { |
| 144 |
ElapsedSeconds float64 // integral of dt |
| 145 |
IntegralX float64 // integral of x dt |
| 146 |
IntegralXX float64 // integral of x*x dt |
| 147 |
} |
| 148 |
|
| 149 |
// ConstantMoments is for a constant X |
| 150 |
func ConstantMoments(dt, x float64) Moments { |
| 151 |
return Moments{ |
| 152 |
ElapsedSeconds: dt, |
| 153 |
IntegralX: x * dt, |
| 154 |
IntegralXX: x * x * dt, |
| 155 |
} |
| 156 |
} |
| 157 |
|
| 158 |
// Add combines over two ranges of time |
| 159 |
func (igr Moments) Add(ogr Moments) Moments { |
| 160 |
return Moments{ |
| 161 |
ElapsedSeconds: igr.ElapsedSeconds + ogr.ElapsedSeconds, |
| 162 |
IntegralX: igr.IntegralX + ogr.IntegralX, |
| 163 |
IntegralXX: igr.IntegralXX + ogr.IntegralXX, |
| 164 |
} |
| 165 |
} |
| 166 |
|
| 167 |
// Sub finds the difference between a range of time and a subrange |
| 168 |
func (igr Moments) Sub(ogr Moments) Moments { |
| 169 |
return Moments{ |
| 170 |
ElapsedSeconds: igr.ElapsedSeconds - ogr.ElapsedSeconds, |
| 171 |
IntegralX: igr.IntegralX - ogr.IntegralX, |
| 172 |
IntegralXX: igr.IntegralXX - ogr.IntegralXX, |
| 173 |
} |
| 174 |
} |
| 175 |
|
| 176 |
// AvgAndStdDev returns the average and standard devation |
| 177 |
func (igr Moments) AvgAndStdDev() (float64, float64) { |
| 178 |
if igr.ElapsedSeconds <= 0 { |
| 179 |
return math.NaN(), math.NaN() |
| 180 |
} |
| 181 |
avg := igr.IntegralX / igr.ElapsedSeconds |
| 182 |
// standard deviation is sqrt( average( (x - xbar)^2 ) ) |
| 183 |
// = sqrt( Integral( x^2 + xbar^2 -2*x*xbar dt ) / Duration ) |
| 184 |
// = sqrt( ( Integral( x^2 dt ) + Duration * xbar^2 - 2*xbar*Integral(x dt) ) / Duration) |
| 185 |
// = sqrt( Integral(x^2 dt)/Duration - xbar^2 ) |
| 186 |
variance := igr.IntegralXX/igr.ElapsedSeconds - avg*avg |
| 187 |
if variance >= 0 { |
| 188 |
return avg, math.Sqrt(variance) |
| 189 |
} |
| 190 |
return avg, math.NaN() |
| 191 |
} |