Debian Codegraph @

pkg/util/flowcontrol/fairqueuing/integrator.go

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