Debian Codegraph @

pkg/util/flowcontrol/apf_controller.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 flowcontrol
18
19 import (
20 "context"
21 "crypto/sha256"
22 "encoding/binary"
23 "errors"
24 "fmt"
25 "math"
26 "math/rand"
27 "sort"
28 "sync"
29 "time"
30
31 "github.com/google/go-cmp/cmp" //nolint:depguard
32 apiequality "k8s.io/apimachinery/pkg/api/equality"
33 apierrors "k8s.io/apimachinery/pkg/api/errors"
34 metav1 "k8s.io/apimachinery/pkg/apis/meta/v1"
35 "k8s.io/apimachinery/pkg/labels"
36 utilerrors "k8s.io/apimachinery/pkg/util/errors"
37 utilruntime "k8s.io/apimachinery/pkg/util/runtime"
38 "k8s.io/apimachinery/pkg/util/sets"
39 "k8s.io/apimachinery/pkg/util/wait"
40 fcboot "k8s.io/apiserver/pkg/apis/flowcontrol/bootstrap"
41 "k8s.io/apiserver/pkg/authentication/user"
42 "k8s.io/apiserver/pkg/endpoints/request"
43 "k8s.io/apiserver/pkg/util/apihelpers"
44 fq "k8s.io/apiserver/pkg/util/flowcontrol/fairqueuing"
45 fcfmt "k8s.io/apiserver/pkg/util/flowcontrol/format"
46 "k8s.io/apiserver/pkg/util/flowcontrol/metrics"
47 fcrequest "k8s.io/apiserver/pkg/util/flowcontrol/request"
48 "k8s.io/client-go/tools/cache"
49 "k8s.io/client-go/util/workqueue"
50 "k8s.io/klog/v2"
51 "k8s.io/utils/clock"
52
53 flowcontrol "k8s.io/api/flowcontrol/v1"
54 flowcontrolapplyconfiguration "k8s.io/client-go/applyconfigurations/flowcontrol/v1"
55 flowcontrolclient "k8s.io/client-go/kubernetes/typed/flowcontrol/v1"
56 flowcontrollister "k8s.io/client-go/listers/flowcontrol/v1"
57 )
58
59 const timeFmt = "2006-01-02T15:04:05.999"
60
61 const (
62 // priorityLevelMaxSeatsPercent is the percentage of the nominalCL used as max seats allocatable from work estimator
63 priorityLevelMaxSeatsPercent = float64(0.15)
64 )
65
66 // This file contains a simple local (to the apiserver) controller
67 // that digests API Priority and Fairness config objects (FlowSchema
68 // and PriorityLevelConfiguration) into the data structure that the
69 // filter uses. At this first level of development this controller
70 // takes the simplest possible approach: whenever notified of any
71 // change to any config object, or when any priority level that is
72 // undesired becomes completely unused, all the config objects are
73 // read and processed as a whole.
74
75 const (
76 // Borrowing among priority levels will be accomplished by periodically
77 // adjusting the current concurrency limits (CurrentCLs);
78 // borrowingAdjustmentPeriod is that period.
79 borrowingAdjustmentPeriod = 10 * time.Second
80
81 // The input to the seat borrowing is smoothed seat demand figures.
82 // This constant controls the decay rate of that smoothing,
83 // as described in the comment on the `seatDemandStats` field of `priorityLevelState`.
84 // The particular number appearing here has the property that half-life
85 // of that decay is 5 minutes.
86 // This is a very preliminary guess at a good value and is likely to be tweaked
87 // once we get some experience with borrowing.
88 seatDemandSmoothingCoefficient = 0.977
89 )
90
91 // The funcs in this package follow the naming convention that the suffix
92 // "Locked" means the relevant mutex must be locked at the start of each
93 // call and will be locked upon return. For a configController, the
94 // suffix "ReadLocked" stipulates a read lock while just "Locked"
95 // stipulates a full lock. Absence of either suffix means that either
96 // (a) the lock must NOT be held at call time and will not be held
97 // upon return or (b) locking is irrelevant.
98
99 // StartFunction begins the process of handling a request. If the
100 // request gets queued then this function uses the given hashValue as
101 // the source of entropy as it shuffle-shards the request into a
102 // queue. The descr1 and descr2 values play no role in the logic but
103 // appear in log messages. This method does not return until the
104 // queuing, if any, for this request is done. If `execute` is false
105 // then `afterExecution` is irrelevant and the request should be
106 // rejected. Otherwise the request should be executed and
107 // `afterExecution` must be called exactly once.
108 type StartFunction func(ctx context.Context, hashValue uint64) (execute bool, afterExecution func())
109
110 // RequestDigest holds necessary info from request for flow-control
111 type RequestDigest struct {
112 RequestInfo *request.RequestInfo
113 User user.Info
114 }
115
116 // `*configController` maintains eventual consistency with the API
117 // objects that configure API Priority and Fairness, and provides a
118 // procedural interface to the configured behavior. The methods of
119 // this type and cfgMeal follow the convention that the suffix
120 // "Locked" means that the caller must hold the configController lock.
121 type configController struct {
122 name string // varies in tests of fighting controllers
123 clock clock.PassiveClock
124 queueSetFactory fq.QueueSetFactory
125 reqsGaugeVec metrics.RatioedGaugeVec
126 execSeatsGaugeVec metrics.RatioedGaugeVec
127
128 // How this controller appears in an ObjectMeta ManagedFieldsEntry.Manager
129 asFieldManager string
130
131 // Given a boolean indicating whether a FlowSchema's referenced
132 // PriorityLevelConfig exists, return a boolean indicating whether
133 // the reference is dangling
134 foundToDangling func(bool) bool
135
136 // configQueue holds `(interface{})(0)` when the configuration
137 // objects need to be reprocessed.
138 configQueue workqueue.TypedRateLimitingInterface[int]
139
140 plLister flowcontrollister.PriorityLevelConfigurationLister
141 plInformerSynced cache.InformerSynced
142
143 fsLister flowcontrollister.FlowSchemaLister
144 fsInformerSynced cache.InformerSynced
145
146 flowcontrolClient flowcontrolclient.FlowcontrolV1Interface
147
148 // serverConcurrencyLimit is the limit on the server's total
149 // number of non-exempt requests being served at once. This comes
150 // from server configuration.
151 serverConcurrencyLimit int
152
153 // watchTracker implements the necessary WatchTracker interface.
154 WatchTracker
155
156 // MaxSeatsTracker tracks the maximum seats that should be allocatable from the
157 // work estimator for a given priority level. This controller does not enforce
158 // any limits on max seats stored in this tracker, it is up to the work estimator
159 // to set lower/upper limits on max seats (currently min=1, max=10).
160 MaxSeatsTracker
161
162 // the most recent update attempts, ordered by increasing age.
163 // Consumer trims to keep only the last minute's worth of entries.
164 // The controller uses this to limit itself to at most six updates
165 // to a given FlowSchema in any minute.
166 // This may only be accessed from the one and only worker goroutine.
167 mostRecentUpdates []updateAttempt
168
169 // This must be locked while accessing the later fields.
170 // A lock for writing is needed
171 // for writing to any of the following:
172 // - the flowSchemas field
173 // - the slice held in the flowSchemas field
174 // - the priorityLevelStates field
175 // - the map held in the priorityLevelStates field
176 // - any field of a priorityLevelState held in that map
177 lock sync.RWMutex
178
179 // flowSchemas holds the flow schema objects, sorted by increasing
180 // numerical (decreasing logical) matching precedence. Every
181 // FlowSchema in this slice is immutable.
182 flowSchemas apihelpers.FlowSchemaSequence
183
184 // priorityLevelStates maps the PriorityLevelConfiguration object
185 // name to the state for that level. Every name referenced from a
186 // member of `flowSchemas` has an entry here.
187 priorityLevelStates map[string]*priorityLevelState
188
189 // nominalCLSum is the sum of the nominalCL fields in the priorityLevelState records.
190 // This can exceed serverConcurrencyLimit because of the deliberate rounding up
191 // in the computation of the nominalCL values.
192 // This is tracked because it is an input to the allocation adjustment algorithm.
193 nominalCLSum int
194 }
195
196 type updateAttempt struct {
197 timeUpdated time.Time
198 updatedItems sets.String // FlowSchema names
199 }
200
201 // priorityLevelState holds the state specific to a priority level.
202 type priorityLevelState struct {
203 // the API object or prototype prescribing this level. Nothing
204 // reached through this pointer is mutable.
205 pl *flowcontrol.PriorityLevelConfiguration
206
207 // qsCompleter holds the QueueSetCompleter derived from `pl`
208 // and `queues`.
209 qsCompleter fq.QueueSetCompleter
210
211 // The QueueSet for this priority level.
212 // Never nil.
213 queues fq.QueueSet
214
215 // quiescing==true indicates that this priority level should be
216 // removed when its queues have all drained.
217 quiescing bool
218
219 // number of goroutines between Controller::Match and calling the
220 // returned StartFunction
221 numPending int
222
223 // Observers tracking number of requests waiting, executing
224 reqsGaugePair metrics.RatioedGaugePair
225
226 // Observer of number of seats occupied throughout execution
227 execSeatsObs metrics.RatioedGauge
228
229 // Integrator of seat demand, reset every CurrentCL adjustment period
230 seatDemandIntegrator fq.Integrator
231
232 // Gauge of seat demand / nominalCL
233 seatDemandRatioedGauge metrics.RatioedGauge
234
235 // seatDemandStats is derived from periodically examining the seatDemandIntegrator.
236 // The average, standard deviation, and high watermark come directly from the integrator.
237 // envelope = avg + stdDev.
238 // Periodically smoothed gets replaced with `max(envelope, A*smoothed + (1-A)*envelope)`,
239 // where A is seatDemandSmoothingCoefficient.
240 seatDemandStats seatDemandStats
241
242 // nominalCL is the nominal concurrency limit configured in the PriorityLevelConfiguration
243 nominalCL int
244
245 // minCL is the nominal limit less the lendable amount
246 minCL int
247
248 //maxCL is the nominal limit plus the amount that may be borrowed
249 maxCL int
250
251 // currentCL is the dynamically derived concurrency limit to impose for now
252 currentCL int
253 }
254
255 type seatDemandStats struct {
256 avg float64
257 stdDev float64
258 highWatermark int
259 smoothed float64
260 }
261
262 func (stats *seatDemandStats) update(obs fq.IntegratorResults) {
263 stats.highWatermark = int(math.Round(obs.Max))
264 if obs.Duration <= 0 {
265 return
266 }
267 if math.IsNaN(obs.Deviation) {
268 obs.Deviation = 0
269 }
270 stats.avg = obs.Average
271 stats.stdDev = obs.Deviation
272 envelope := obs.Average + obs.Deviation
273 stats.smoothed = math.Max(envelope, seatDemandSmoothingCoefficient*stats.smoothed+(1-seatDemandSmoothingCoefficient)*envelope)
274 }
275
276 // NewTestableController is extra flexible to facilitate testing
277 func newTestableController(config TestableConfig) *configController {
278 cfgCtlr := &configController{
279 name: config.Name,
280 clock: config.Clock,
281 queueSetFactory: config.QueueSetFactory,
282 reqsGaugeVec: config.ReqsGaugeVec,
283 execSeatsGaugeVec: config.ExecSeatsGaugeVec,
284 asFieldManager: config.AsFieldManager,
285 foundToDangling: config.FoundToDangling,
286 serverConcurrencyLimit: config.ServerConcurrencyLimit,
287 flowcontrolClient: config.FlowcontrolClient,
288 priorityLevelStates: make(map[string]*priorityLevelState),
289 WatchTracker: NewWatchTracker(),
290 MaxSeatsTracker: NewMaxSeatsTracker(),
291 }
292 klog.V(2).Infof("NewTestableController %q with serverConcurrencyLimit=%d, name=%s, asFieldManager=%q", cfgCtlr.name, cfgCtlr.serverConcurrencyLimit, cfgCtlr.name, cfgCtlr.asFieldManager)
293 // Start with longish delay because conflicts will be between
294 // different processes, so take some time to go away.
295 cfgCtlr.configQueue = workqueue.NewTypedRateLimitingQueueWithConfig(
296 workqueue.NewTypedItemExponentialFailureRateLimiter[int](200*time.Millisecond, 8*time.Hour),
297 workqueue.TypedRateLimitingQueueConfig[int]{Name: "priority_and_fairness_config_queue"},
298 )
299 // ensure the data structure reflects the mandatory config
300 cfgCtlr.lockAndDigestConfigObjects(nil, nil)
301 fci := config.InformerFactory.Flowcontrol().V1()
302 pli := fci.PriorityLevelConfigurations()
303 fsi := fci.FlowSchemas()
304 cfgCtlr.plLister = pli.Lister()
305 cfgCtlr.plInformerSynced = pli.Informer().HasSynced
306 cfgCtlr.fsLister = fsi.Lister()
307 cfgCtlr.fsInformerSynced = fsi.Informer().HasSynced
308 pli.Informer().AddEventHandler(cache.ResourceEventHandlerFuncs{
309 AddFunc: func(obj interface{}) {
310 pl := obj.(*flowcontrol.PriorityLevelConfiguration)
311 klog.V(7).Infof("Triggered API priority and fairness config reloading in %s due to creation of PLC %s", cfgCtlr.name, pl.Name)
312 cfgCtlr.configQueue.Add(0)
313 },
314 UpdateFunc: func(oldObj, newObj interface{}) {
315 newPL := newObj.(*flowcontrol.PriorityLevelConfiguration)
316 oldPL := oldObj.(*flowcontrol.PriorityLevelConfiguration)
317 if !apiequality.Semantic.DeepEqual(oldPL.Spec, newPL.Spec) {
318 klog.V(7).Infof("Triggered API priority and fairness config reloading in %s due to spec update of PLC %s", cfgCtlr.name, newPL.Name)
319 cfgCtlr.configQueue.Add(0)
320 } else {
321 klog.V(7).Infof("No trigger API priority and fairness config reloading in %s due to spec non-change of PLC %s", cfgCtlr.name, newPL.Name)
322 }
323 },
324 DeleteFunc: func(obj interface{}) {
325 name, _ := cache.DeletionHandlingMetaNamespaceKeyFunc(obj)
326 klog.V(7).Infof("Triggered API priority and fairness config reloading in %s due to deletion of PLC %s", cfgCtlr.name, name)
327 cfgCtlr.configQueue.Add(0)
328
329 }})
330 fsi.Informer().AddEventHandler(cache.ResourceEventHandlerFuncs{
331 AddFunc: func(obj interface{}) {
332 fs := obj.(*flowcontrol.FlowSchema)
333 klog.V(7).Infof("Triggered API priority and fairness config reloading in %s due to creation of FS %s", cfgCtlr.name, fs.Name)
334 cfgCtlr.configQueue.Add(0)
335 },
336 UpdateFunc: func(oldObj, newObj interface{}) {
337 newFS := newObj.(*flowcontrol.FlowSchema)
338 oldFS := oldObj.(*flowcontrol.FlowSchema)
339 // Changes to either Spec or Status are relevant. The
340 // concern is that we might, in some future release, want
341 // different behavior than is implemented now. One of the
342 // hardest questions is how does an operator roll out the
343 // new release in a cluster with multiple kube-apiservers
344 // --- in a way that works no matter what servers crash
345 // and restart when. If this handler reacts only to
346 // changes in Spec then we have a scenario in which the
347 // rollout leaves the old Status in place. The scenario
348 // ends with this subsequence: deploy the last new server
349 // before deleting the last old server, and in between
350 // those two operations the last old server crashes and
351 // recovers. The chosen solution is making this controller
352 // insist on maintaining the particular state that it
353 // establishes.
354 if !(apiequality.Semantic.DeepEqual(oldFS.Spec, newFS.Spec) &&
355 apiequality.Semantic.DeepEqual(oldFS.Status, newFS.Status)) {
356 klog.V(7).Infof("Triggered API priority and fairness config reloading in %s due to spec and/or status update of FS %s", cfgCtlr.name, newFS.Name)
357 cfgCtlr.configQueue.Add(0)
358 } else {
359 klog.V(7).Infof("No trigger of API priority and fairness config reloading in %s due to spec and status non-change of FS %s", cfgCtlr.name, newFS.Name)
360 }
361 },
362 DeleteFunc: func(obj interface{}) {
363 name, _ := cache.DeletionHandlingMetaNamespaceKeyFunc(obj)
364 klog.V(7).Infof("Triggered API priority and fairness config reloading in %s due to deletion of FS %s", cfgCtlr.name, name)
365 cfgCtlr.configQueue.Add(0)
366
367 }})
368 return cfgCtlr
369 }
370
371 func (cfgCtlr *configController) Run(stopCh <-chan struct{}) error {
372 defer utilruntime.HandleCrash()
373
374 // Let the config worker stop when we are done
375 defer cfgCtlr.configQueue.ShutDown()
376
377 klog.Info("Starting API Priority and Fairness config controller")
378 if ok := cache.WaitForCacheSync(stopCh, cfgCtlr.plInformerSynced, cfgCtlr.fsInformerSynced); !ok {
379 return fmt.Errorf("Never achieved initial sync")
380 }
381
382 klog.Info("Running API Priority and Fairness config worker")
383 go wait.Until(cfgCtlr.runWorker, time.Second, stopCh)
384
385 klog.Info("Running API Priority and Fairness periodic rebalancing process")
386 go wait.Until(cfgCtlr.updateBorrowing, borrowingAdjustmentPeriod, stopCh)
387
388 <-stopCh
389 klog.Info("Shutting down API Priority and Fairness config worker")
390 return nil
391 }
392
393 func (cfgCtlr *configController) updateBorrowing() {
394 cfgCtlr.lock.Lock()
395 defer cfgCtlr.lock.Unlock()
396 cfgCtlr.updateBorrowingLocked(true, cfgCtlr.priorityLevelStates)
397 }
398
399 func (cfgCtlr *configController) updateBorrowingLocked(setCompleters bool, plStates map[string]*priorityLevelState) {
400 items := make([]allocProblemItem, 0, len(plStates))
401 nonExemptPLNames := make([]string, 0, len(plStates))
402 idxOfNonExempt := map[string]int{} // items index of non-exempt classes
403 cclOfExempt := map[string]int{} // minCurrentCL of exempt classes
404 var minCLSum, minCurrentCLSum int // sums over non-exempt classes
405 remainingServerCL := cfgCtlr.nominalCLSum
406 for plName, plState := range plStates {
407 obs := plState.seatDemandIntegrator.Reset()
408 plState.seatDemandStats.update(obs)
409 var minCurrentCL int
410 if plState.pl.Spec.Type == flowcontrol.PriorityLevelEnablementExempt {
411 minCurrentCL = max(plState.minCL, plState.seatDemandStats.highWatermark)
412 cclOfExempt[plName] = minCurrentCL
413 remainingServerCL -= minCurrentCL
414 } else {
415 // Lower bound on this priority level's adjusted concurreny limit is the lesser of:
416 // - its seat demamd high watermark over the last adjustment period, and
417 // - its configured concurrency limit.
418 // BUT: we do not want this to be lower than the lower bound from configuration.
419 // See KEP-1040 for a more detailed explanation.
420 minCurrentCL = max(plState.minCL, min(plState.nominalCL, plState.seatDemandStats.highWatermark))
421 idxOfNonExempt[plName] = len(items)
422 nonExemptPLNames = append(nonExemptPLNames, plName)
423 items = append(items, allocProblemItem{
424 lowerBound: float64(minCurrentCL),
425 upperBound: float64(plState.maxCL),
426 target: math.Max(float64(minCurrentCL), plState.seatDemandStats.smoothed),
427 })
428 minCLSum += plState.minCL
429 minCurrentCLSum += minCurrentCL
430 }
431 }
432 if len(items) == 0 && cfgCtlr.nominalCLSum > 0 {
433 klog.ErrorS(nil, "Impossible: no priority levels", "plStates", cfgCtlr.priorityLevelStates)
434 return
435 }
436 var allocs []float64
437 var shareFrac, fairFrac float64
438 var err error
439 if remainingServerCL <= minCLSum {
440 metrics.SetFairFrac(0)
441 } else if remainingServerCL <= minCurrentCLSum {
442 shareFrac = float64(remainingServerCL-minCLSum) / float64(minCurrentCLSum-minCLSum)
443 metrics.SetFairFrac(0)
444 } else {
445 allocs, fairFrac, err = computeConcurrencyAllocation(cfgCtlr.nominalCLSum, items)
446 if err != nil {
447 klog.ErrorS(err, "Unable to derive new concurrency limits", "plNames", nonExemptPLNames, "items", items)
448 allocs = make([]float64, len(items))
449 for idx, plName := range nonExemptPLNames {
450 plState := plStates[plName]
451 allocs[idx] = float64(plState.currentCL)
452 }
453 }
454 metrics.SetFairFrac(float64(fairFrac))
455 }
456 for plName, plState := range plStates {
457 idx, isNonExempt := idxOfNonExempt[plName]
458 if setCompleters {
459 qsCompleter, err := queueSetCompleterForPL(cfgCtlr.queueSetFactory, plState.queues,
460 plState.pl, plState.reqsGaugePair, plState.execSeatsObs,
461 metrics.NewUnionGauge(plState.seatDemandIntegrator, plState.seatDemandRatioedGauge))
462 if err != nil {
463 klog.ErrorS(err, "Inconceivable! Configuration error in existing priority level", "pl", plState.pl)
464 continue
465 }
466 plState.qsCompleter = qsCompleter
467 }
468 var currentCL int
469 if !isNonExempt {
470 currentCL = cclOfExempt[plName]
471 } else if remainingServerCL <= minCLSum {
472 currentCL = plState.minCL
473 } else if remainingServerCL <= minCurrentCLSum {
474 minCurrentCL := max(plState.minCL, min(plState.nominalCL, plState.seatDemandStats.highWatermark))
475 currentCL = plState.minCL + int(math.Round(float64(minCurrentCL-plState.minCL)*shareFrac))
476 } else {
477 currentCL = int(math.Round(float64(allocs[idx])))
478 }
479 relChange := relDiff(float64(currentCL), float64(plState.currentCL))
480 plState.currentCL = currentCL
481 metrics.NotePriorityLevelConcurrencyAdjustment(plState.pl.Name, float64(plState.seatDemandStats.highWatermark), plState.seatDemandStats.avg, plState.seatDemandStats.stdDev, plState.seatDemandStats.smoothed, float64(items[idx].target), currentCL)
482 logLevel := klog.Level(4)
483 if relChange >= 0.05 {
484 logLevel = 2
485 }
486 var concurrencyDenominator int
487 if currentCL > 0 {
488 concurrencyDenominator = currentCL
489 } else {
490 concurrencyDenominator = int(math.Max(1, math.Round(float64(cfgCtlr.serverConcurrencyLimit)/10)))
491 }
492 plState.seatDemandRatioedGauge.SetDenominator(float64(concurrencyDenominator))
493 klog.V(logLevel).InfoS("Update CurrentCL", "plName", plName, "seatDemandHighWatermark", plState.seatDemandStats.highWatermark, "seatDemandAvg", plState.seatDemandStats.avg, "seatDemandStdev", plState.seatDemandStats.stdDev, "seatDemandSmoothed", plState.seatDemandStats.smoothed, "fairFrac", fairFrac, "currentCL", currentCL, "concurrencyDenominator", concurrencyDenominator, "backstop", err != nil)
494 plState.queues = plState.qsCompleter.Complete(fq.DispatchingConfig{ConcurrencyLimit: currentCL, ConcurrencyDenominator: concurrencyDenominator})
495 }
496 }
497
498 // runWorker is the logic of the one and only worker goroutine. We
499 // limit the number to one in order to obviate explicit
500 // synchronization around access to `cfgCtlr.mostRecentUpdates`.
501 func (cfgCtlr *configController) runWorker() {
502 for cfgCtlr.processNextWorkItem() {
503 }
504 }
505
506 // processNextWorkItem works on one entry from the work queue.
507 // Only invoke this in the one and only worker goroutine.
508 func (cfgCtlr *configController) processNextWorkItem() bool {
509 obj, shutdown := cfgCtlr.configQueue.Get()
510 if shutdown {
511 return false
512 }
513
514 func(obj int) {
515 defer cfgCtlr.configQueue.Done(obj)
516 specificDelay, err := cfgCtlr.syncOne()
517 switch {
518 case err != nil:
519 klog.Error(err)
520 cfgCtlr.configQueue.AddRateLimited(obj)
521 case specificDelay > 0:
522 cfgCtlr.configQueue.AddAfter(obj, specificDelay)
523 default:
524 cfgCtlr.configQueue.Forget(obj)
525 }
526 }(obj)
527
528 return true
529 }
530
531 // syncOne does one full synchronization. It reads all the API
532 // objects that configure API Priority and Fairness and updates the
533 // local configController accordingly.
534 // Only invoke this in the one and only worker goroutine
535 func (cfgCtlr *configController) syncOne() (specificDelay time.Duration, err error) {
536 klog.V(5).Infof("%s syncOne at %s", cfgCtlr.name, cfgCtlr.clock.Now().Format(timeFmt))
537 all := labels.Everything()
538 newPLs, err := cfgCtlr.plLister.List(all)
539 if err != nil {
540 return 0, fmt.Errorf("unable to list PriorityLevelConfiguration objects: %w", err)
541 }
542 newFSs, err := cfgCtlr.fsLister.List(all)
543 if err != nil {
544 return 0, fmt.Errorf("unable to list FlowSchema objects: %w", err)
545 }
546 return cfgCtlr.digestConfigObjects(newPLs, newFSs)
547 }
548
549 // cfgMeal is the data involved in the process of digesting the API
550 // objects that configure API Priority and Fairness. All the config
551 // objects are digested together, because this is the simplest way to
552 // cope with the various dependencies between objects. The process of
553 // digestion is done in four passes over config objects --- three
554 // passes over PriorityLevelConfigurations and one pass over the
555 // FlowSchemas --- with the work dvided among the passes according to
556 // those dependencies.
557 type cfgMeal struct {
558 cfgCtlr *configController
559
560 newPLStates map[string]*priorityLevelState
561
562 // The sum of the concurrency shares of the priority levels in the
563 // new configuration
564 shareSum float64
565
566 // These keep track of which mandatory priority level config
567 // objects have been digested
568 haveExemptPL, haveCatchAllPL bool
569
570 // Buffered FlowSchema status updates to do. Do them when the
571 // lock is not held, to avoid a deadlock due to such a request
572 // provoking a call into this controller while the lock held
573 // waiting on that request to complete.
574 fsStatusUpdates []fsStatusUpdate
575
576 maxWaitingRequests, maxExecutingRequests int
577 }
578
579 // A buffered set of status updates for FlowSchemas
580 type fsStatusUpdate struct {
581 flowSchema *flowcontrol.FlowSchema
582 condition flowcontrol.FlowSchemaCondition
583 oldValue flowcontrol.FlowSchemaCondition
584 }
585
586 // digestConfigObjects is given all the API objects that configure
587 // cfgCtlr and writes its consequent new configState.
588 // Only invoke this in the one and only worker goroutine
589 func (cfgCtlr *configController) digestConfigObjects(newPLs []*flowcontrol.PriorityLevelConfiguration, newFSs []*flowcontrol.FlowSchema) (time.Duration, error) {
590 fsStatusUpdates := cfgCtlr.lockAndDigestConfigObjects(newPLs, newFSs)
591 var errs []error
592 currResult := updateAttempt{
593 timeUpdated: cfgCtlr.clock.Now(),
594 updatedItems: sets.String{},
595 }
596 var suggestedDelay time.Duration
597 for _, fsu := range fsStatusUpdates {
598 // if we should skip this name, indicate we will need a delay, but continue with other entries
599 if cfgCtlr.shouldDelayUpdate(fsu.flowSchema.Name) {
600 if suggestedDelay == 0 {
601 suggestedDelay = time.Duration(30+rand.Intn(45)) * time.Second
602 }
603 continue
604 }
605
606 // if we are going to issue an update, be sure we track every name we update so we know if we update it too often.
607 currResult.updatedItems.Insert(fsu.flowSchema.Name)
608 if klogV := klog.V(4); klogV.Enabled() {
609 klogV.Infof("%s writing Condition %s to FlowSchema %s, which had ResourceVersion=%s, because its previous value was %s, diff: %s",
610 cfgCtlr.name, fsu.condition, fsu.flowSchema.Name, fsu.flowSchema.ResourceVersion, fcfmt.Fmt(fsu.oldValue), cmp.Diff(fsu.oldValue, fsu.condition))
611 }
612
613 if err := apply(cfgCtlr.flowcontrolClient.FlowSchemas(), fsu, cfgCtlr.asFieldManager); err != nil {
614 if apierrors.IsNotFound(err) {
615 // This object has been deleted. A notification is coming
616 // and nothing more needs to be done here.
617 klog.V(5).Infof("%s at %s: attempted update of concurrently deleted FlowSchema %s; nothing more needs to be done", cfgCtlr.name, cfgCtlr.clock.Now().Format(timeFmt), fsu.flowSchema.Name)
618 } else {
619 errs = append(errs, fmt.Errorf("failed to set a status.condition for FlowSchema %s: %w", fsu.flowSchema.Name, err))
620 }
621 }
622 }
623 cfgCtlr.addUpdateResult(currResult)
624
625 return suggestedDelay, utilerrors.NewAggregate(errs)
626 }
627
628 func apply(client flowcontrolclient.FlowSchemaInterface, fsu fsStatusUpdate, asFieldManager string) error {
629 applyOptions := metav1.ApplyOptions{FieldManager: asFieldManager, Force: true}
630
631 // the condition field in fsStatusUpdate holds the new condition we want to update.
632 // TODO: this will break when we have multiple conditions for a flowschema
633 _, err := client.ApplyStatus(context.TODO(), toFlowSchemaApplyConfiguration(fsu), applyOptions)
634 return err
635 }
636
637 func toFlowSchemaApplyConfiguration(fsUpdate fsStatusUpdate) *flowcontrolapplyconfiguration.FlowSchemaApplyConfiguration {
638 condition := flowcontrolapplyconfiguration.FlowSchemaCondition().
639 WithType(fsUpdate.condition.Type).
640 WithStatus(fsUpdate.condition.Status).
641 WithReason(fsUpdate.condition.Reason).
642 WithLastTransitionTime(fsUpdate.condition.LastTransitionTime).
643 WithMessage(fsUpdate.condition.Message)
644
645 return flowcontrolapplyconfiguration.FlowSchema(fsUpdate.flowSchema.Name).
646 WithStatus(flowcontrolapplyconfiguration.FlowSchemaStatus().
647 WithConditions(condition),
648 )
649 }
650
651 // shouldDelayUpdate checks to see if a flowschema has been updated too often and returns true if a delay is needed.
652 // Only invoke this in the one and only worker goroutine
653 func (cfgCtlr *configController) shouldDelayUpdate(flowSchemaName string) bool {
654 numUpdatesInPastMinute := 0
655 oneMinuteAgo := cfgCtlr.clock.Now().Add(-1 * time.Minute)
656 for idx, update := range cfgCtlr.mostRecentUpdates {
657 if oneMinuteAgo.After(update.timeUpdated) {
658 // this and the remaining items are no longer relevant
659 cfgCtlr.mostRecentUpdates = cfgCtlr.mostRecentUpdates[:idx]
660 return false
661 }
662 if update.updatedItems.Has(flowSchemaName) {
663 numUpdatesInPastMinute++
664 if numUpdatesInPastMinute > 5 {
665 return true
666 }
667 }
668 }
669 return false
670 }
671
672 // addUpdateResult adds the result. It isn't a ring buffer because
673 // this is small and rate limited.
674 // Only invoke this in the one and only worker goroutine
675 func (cfgCtlr *configController) addUpdateResult(result updateAttempt) {
676 cfgCtlr.mostRecentUpdates = append([]updateAttempt{result}, cfgCtlr.mostRecentUpdates...)
677 }
678
679 func (cfgCtlr *configController) lockAndDigestConfigObjects(newPLs []*flowcontrol.PriorityLevelConfiguration, newFSs []*flowcontrol.FlowSchema) []fsStatusUpdate {
680 cfgCtlr.lock.Lock()
681 defer cfgCtlr.lock.Unlock()
682 meal := cfgMeal{
683 cfgCtlr: cfgCtlr,
684 newPLStates: make(map[string]*priorityLevelState),
685 }
686
687 meal.digestNewPLsLocked(newPLs)
688 meal.digestFlowSchemasLocked(newFSs)
689 meal.processOldPLsLocked()
690
691 // Supply missing mandatory PriorityLevelConfiguration objects
692 if !meal.haveExemptPL {
693 meal.imaginePL(fcboot.MandatoryPriorityLevelConfigurationExempt)
694 }
695 if !meal.haveCatchAllPL {
696 meal.imaginePL(fcboot.MandatoryPriorityLevelConfigurationCatchAll)
697 }
698
699 meal.finishQueueSetReconfigsLocked()
700
701 // The new config has been constructed
702 cfgCtlr.priorityLevelStates = meal.newPLStates
703 klog.V(5).InfoS("Switched to new API Priority and Fairness configuration", "maxWaitingRequests", meal.maxWaitingRequests, "maxExecutinRequests", meal.maxExecutingRequests)
704
705 metrics.GetWaitingReadonlyConcurrency().SetDenominator(float64(meal.maxWaitingRequests))
706 metrics.GetWaitingMutatingConcurrency().SetDenominator(float64(meal.maxWaitingRequests))
707 metrics.GetExecutingReadonlyConcurrency().SetDenominator(float64(meal.maxExecutingRequests))
708 metrics.GetExecutingMutatingConcurrency().SetDenominator(float64(meal.maxExecutingRequests))
709
710 return meal.fsStatusUpdates
711 }
712
713 // Digest the new set of PriorityLevelConfiguration objects.
714 // Pretend broken ones do not exist.
715 func (meal *cfgMeal) digestNewPLsLocked(newPLs []*flowcontrol.PriorityLevelConfiguration) {
716 for _, pl := range newPLs {
717 state := meal.cfgCtlr.priorityLevelStates[pl.Name]
718 if state == nil {
719 labelValues := []string{pl.Name}
720 state = &priorityLevelState{
721 reqsGaugePair: metrics.RatioedGaugeVecPhasedElementPair(meal.cfgCtlr.reqsGaugeVec, 1, 1, labelValues),
722 execSeatsObs: meal.cfgCtlr.execSeatsGaugeVec.NewForLabelValuesSafe(0, 1, labelValues),
723 seatDemandIntegrator: fq.NewNamedIntegrator(meal.cfgCtlr.clock, pl.Name),
724 seatDemandRatioedGauge: metrics.ApiserverSeatDemands.NewForLabelValuesSafe(0, 1, []string{pl.Name}),
725 }
726 }
727 qsCompleter, err := queueSetCompleterForPL(meal.cfgCtlr.queueSetFactory, state.queues,
728 pl, state.reqsGaugePair, state.execSeatsObs,
729 metrics.NewUnionGauge(state.seatDemandIntegrator, state.seatDemandRatioedGauge))
730 if err != nil {
731 klog.Warningf("Ignoring PriorityLevelConfiguration object %s because its spec (%s) is broken: %s", pl.Name, fcfmt.Fmt(pl.Spec), err)
732 continue
733 }
734 meal.newPLStates[pl.Name] = state
735 state.pl = pl
736 state.qsCompleter = qsCompleter
737 if state.quiescing { // it was undesired, but no longer
738 klog.V(3).Infof("Priority level %q was undesired and has become desired again", pl.Name)
739 state.quiescing = false
740 }
741 nominalConcurrencyShares, _, _ := plSpecCommons(state.pl)
742 meal.shareSum += float64(*nominalConcurrencyShares)
743 meal.haveExemptPL = meal.haveExemptPL || pl.Name == flowcontrol.PriorityLevelConfigurationNameExempt
744 meal.haveCatchAllPL = meal.haveCatchAllPL || pl.Name == flowcontrol.PriorityLevelConfigurationNameCatchAll
745 }
746 }
747
748 // Digest the given FlowSchema objects. Ones that reference a missing
749 // or broken priority level are not to be passed on to the filter for
750 // use. We do this before holding over old priority levels so that
751 // requests stop going to those levels and FlowSchemaStatus values
752 // reflect this. This function also adds any missing mandatory
753 // FlowSchema objects. The given objects must all have distinct
754 // names.
755 func (meal *cfgMeal) digestFlowSchemasLocked(newFSs []*flowcontrol.FlowSchema) {
756 fsSeq := make(apihelpers.FlowSchemaSequence, 0, len(newFSs))
757 fsMap := make(map[string]*flowcontrol.FlowSchema, len(newFSs))
758 var haveExemptFS, haveCatchAllFS bool
759 for i, fs := range newFSs {
760 otherFS := fsMap[fs.Name]
761 if otherFS != nil {
762 // This client is forbidden to do this.
763 panic(fmt.Sprintf("Given two FlowSchema objects with the same name: %s and %s", fcfmt.Fmt(otherFS), fcfmt.Fmt(fs)))
764 }
765 fsMap[fs.Name] = fs
766 _, goodPriorityRef := meal.newPLStates[fs.Spec.PriorityLevelConfiguration.Name]
767
768 // Ensure the object's status reflects whether its priority
769 // level reference is broken.
770 //
771 // TODO: consider not even trying if server is not handling
772 // requests yet.
773 meal.presyncFlowSchemaStatus(fs, meal.cfgCtlr.foundToDangling(goodPriorityRef), fs.Spec.PriorityLevelConfiguration.Name)
774
775 if !goodPriorityRef {
776 klog.V(6).Infof("Ignoring FlowSchema %s because of bad priority level reference %q", fs.Name, fs.Spec.PriorityLevelConfiguration.Name)
777 continue
778 }
779 fsSeq = append(fsSeq, newFSs[i])
780 haveExemptFS = haveExemptFS || fs.Name == flowcontrol.FlowSchemaNameExempt
781 haveCatchAllFS = haveCatchAllFS || fs.Name == flowcontrol.FlowSchemaNameCatchAll
782 }
783 // sort into the order to be used for matching
784 sort.Sort(fsSeq)
785
786 // Supply missing mandatory FlowSchemas, in correct position
787 if !haveExemptFS {
788 fsSeq = append(apihelpers.FlowSchemaSequence{fcboot.MandatoryFlowSchemaExempt}, fsSeq...)
789 }
790 if !haveCatchAllFS {
791 fsSeq = append(fsSeq, fcboot.MandatoryFlowSchemaCatchAll)
792 }
793
794 meal.cfgCtlr.flowSchemas = fsSeq
795 klogV := klog.V(5)
796 if klogV.Enabled() {
797 for _, fs := range fsSeq {
798 klogV.Infof("Using FlowSchema %s", fcfmt.Fmt(fs))
799 }
800 }
801 }
802
803 // Consider all the priority levels in the previous configuration.
804 // Keep the ones that are in the new config, supply mandatory
805 // behavior, or are still busy; for the rest: drop it if it has no
806 // queues, otherwise start the quiescing process if that has not
807 // already been started.
808 func (meal *cfgMeal) processOldPLsLocked() {
809 for plName, plState := range meal.cfgCtlr.priorityLevelStates {
810 if meal.newPLStates[plName] != nil {
811 // Still desired and already updated
812 continue
813 }
814 if plName == flowcontrol.PriorityLevelConfigurationNameExempt && !meal.haveExemptPL || plName == flowcontrol.PriorityLevelConfigurationNameCatchAll && !meal.haveCatchAllPL {
815 // BTW, we know the Spec has not changed what is says about queuing because the
816 // mandatory objects have immutable Specs as far as queuing is concerned.
817 klog.V(3).Infof("Retaining mandatory priority level %q despite lack of API object", plName)
818 } else {
819 if plState.numPending == 0 && plState.queues.IsIdle() {
820 // The QueueSet is done
821 // draining and no use is coming from another
822 // goroutine
823 klog.V(3).Infof("Removing undesired priority level %q, Type=%v", plName, plState.pl.Spec.Type)
824 meal.cfgCtlr.MaxSeatsTracker.ForgetPriorityLevel(plName)
825 continue
826 }
827 if !plState.quiescing {
828 klog.V(3).Infof("Priority level %q became undesired", plName)
829 plState.quiescing = true
830 }
831 }
832 var err error
833 plState.qsCompleter, err = queueSetCompleterForPL(meal.cfgCtlr.queueSetFactory, plState.queues,
834 plState.pl, plState.reqsGaugePair, plState.execSeatsObs,
835 metrics.NewUnionGauge(plState.seatDemandIntegrator, plState.seatDemandRatioedGauge))
836 if err != nil {
837 // This can not happen because queueSetCompleterForPL already approved this config
838 panic(fmt.Sprintf("%s from name=%q spec=%s", err, plName, fcfmt.Fmt(plState.pl.Spec)))
839 }
840 // We deliberately include the lingering priority levels
841 // here so that their queues get some concurrency and they
842 // continue to drain. During this interim a lingering
843 // priority level continues to get a concurrency
844 // allocation determined by all the share values in the
845 // regular way.
846 nominalConcurrencyShares, _, _ := plSpecCommons(plState.pl)
847 meal.shareSum += float64(*nominalConcurrencyShares)
848 meal.haveExemptPL = meal.haveExemptPL || plName == flowcontrol.PriorityLevelConfigurationNameExempt
849 meal.haveCatchAllPL = meal.haveCatchAllPL || plName == flowcontrol.PriorityLevelConfigurationNameCatchAll
850 meal.newPLStates[plName] = plState
851 }
852 }
853
854 // For all the priority levels of the new config, divide up the
855 // server's total concurrency limit among them and create/update their
856 // QueueSets.
857 func (meal *cfgMeal) finishQueueSetReconfigsLocked() {
858 for plName, plState := range meal.newPLStates {
859 nominalConcurrencyShares, lendablePercent, borrowingLimitPercent := plSpecCommons(plState.pl)
860 // The use of math.Ceil here means that the results might sum
861 // to a little more than serverConcurrencyLimit but the
862 // difference will be negligible.
863 concurrencyLimit := int(math.Ceil(float64(meal.cfgCtlr.serverConcurrencyLimit) * float64(*nominalConcurrencyShares) / meal.shareSum))
864 var lendableCL, borrowingCL int
865 if lendablePercent != nil {
866 lendableCL = int(math.Round(float64(concurrencyLimit) * float64(*lendablePercent) / 100))
867 }
868 if borrowingLimitPercent != nil {
869 borrowingCL = int(math.Round(float64(concurrencyLimit) * float64(*borrowingLimitPercent) / 100))
870 } else {
871 borrowingCL = meal.cfgCtlr.serverConcurrencyLimit
872 }
873
874 metrics.SetPriorityLevelConfiguration(plName, concurrencyLimit, concurrencyLimit-lendableCL, concurrencyLimit+borrowingCL)
875 cfgChanged := plState.nominalCL != concurrencyLimit || plState.minCL != concurrencyLimit-lendableCL || plState.maxCL != concurrencyLimit+borrowingCL
876 plState.nominalCL = concurrencyLimit
877 plState.minCL = concurrencyLimit - lendableCL
878 plState.maxCL = concurrencyLimit + borrowingCL
879 meal.maxExecutingRequests += concurrencyLimit
880 if limited := plState.pl.Spec.Limited; limited != nil {
881 if qCfg := limited.LimitResponse.Queuing; qCfg != nil {
882 meal.maxWaitingRequests += int(qCfg.Queues * qCfg.QueueLengthLimit)
883
884 // Max seats allocatable from work estimator is calculated as MAX(1, MIN(0.15 * nominalCL, nominalCL/handSize)).
885 // This is to keep max seats relative to total available concurrency with a minimum value of 1.
886 // 15% of nominal concurrency was chosen since it preserved the previous max seats of 10 for default priority levels
887 // when using apiserver's default total server concurrency of 600 (--max-requests-inflight=400, --max-mutating-requests-inflight=200).
888 // This ensures that clusters with relatively high inflight requests will continue to use a max seats of 10
889 // while clusters with lower inflight requests will use max seats no greater than nominalCL/handSize.
890 // Calculated max seats can return arbitrarily high values but work estimator currently limits max seats at 10.
891 handSize := plState.pl.Spec.Limited.LimitResponse.Queuing.HandSize
892 maxSeats := uint64(math.Max(1, math.Min(math.Ceil(float64(concurrencyLimit)*priorityLevelMaxSeatsPercent), float64(int32(concurrencyLimit)/handSize))))
893 meal.cfgCtlr.MaxSeatsTracker.SetMaxSeats(plName, maxSeats)
894 }
895 }
896 if plState.queues == nil {
897 initialCL := concurrencyLimit - lendableCL/2
898 klog.V(2).Infof("Introducing queues for priority level %q: config=%s, nominalCL=%d, lendableCL=%d, borrowingCL=%d, currentCL=%d, quiescing=%v (shares=%v, shareSum=%v)", plName, fcfmt.Fmt(plState.pl.Spec), concurrencyLimit, lendableCL, borrowingCL, initialCL, plState.quiescing, nominalConcurrencyShares, meal.shareSum)
899 plState.seatDemandStats = seatDemandStats{}
900 plState.currentCL = initialCL
901 } else {
902 logLevel := klog.Level(5)
903 if cfgChanged {
904 logLevel = 2
905 }
906 klog.V(logLevel).Infof("Retaining queues for priority level %q: config=%s, nominalCL=%d, lendableCL=%d, borrowingCL=%d, currentCL=%d, quiescing=%v, numPending=%d (shares=%v, shareSum=%v)", plName, fcfmt.Fmt(plState.pl.Spec), concurrencyLimit, lendableCL, borrowingCL, plState.currentCL, plState.quiescing, plState.numPending, nominalConcurrencyShares, meal.shareSum)
907 }
908 }
909 meal.cfgCtlr.nominalCLSum = meal.maxExecutingRequests
910 meal.cfgCtlr.updateBorrowingLocked(false, meal.newPLStates)
911 }
912
913 // queueSetCompleterForPL returns an appropriate QueueSetCompleter for the
914 // given priority level configuration. Returns nil and an error if the given
915 // object is malformed in a way that is a problem for this package.
916 func queueSetCompleterForPL(qsf fq.QueueSetFactory, queues fq.QueueSet, pl *flowcontrol.PriorityLevelConfiguration, reqsIntPair metrics.RatioedGaugePair, execSeatsObs metrics.RatioedGauge, seatDemandGauge metrics.Gauge) (fq.QueueSetCompleter, error) {
917 if (pl.Spec.Type == flowcontrol.PriorityLevelEnablementLimited) != (pl.Spec.Limited != nil) {
918 return nil, errors.New("broken union structure at the top, for Limited")
919 }
920 if (pl.Spec.Type == flowcontrol.PriorityLevelEnablementExempt) != (pl.Spec.Exempt != nil) {
921 return nil, errors.New("broken union structure at the top, for Exempt")
922 }
923 if (pl.Spec.Type == flowcontrol.PriorityLevelEnablementExempt) != (pl.Name == flowcontrol.PriorityLevelConfigurationNameExempt) {
924 // This package does not attempt to cope with a priority level dynamically switching between exempt and not.
925 return nil, errors.New("non-alignment between name and type")
926 }
927 qcQS := fq.QueuingConfig{Name: pl.Name}
928 if pl.Spec.Limited != nil {
929 if (pl.Spec.Limited.LimitResponse.Type == flowcontrol.LimitResponseTypeReject) != (pl.Spec.Limited.LimitResponse.Queuing == nil) {
930 return nil, errors.New("broken union structure for limit response")
931 }
932 qcAPI := pl.Spec.Limited.LimitResponse.Queuing
933 if qcAPI != nil {
934 qcQS = fq.QueuingConfig{Name: pl.Name,
935 DesiredNumQueues: int(qcAPI.Queues),
936 QueueLengthLimit: int(qcAPI.QueueLengthLimit),
937 HandSize: int(qcAPI.HandSize),
938 }
939 }
940 } else {
941 qcQS = fq.QueuingConfig{Name: pl.Name, DesiredNumQueues: -1}
942 }
943 var qsc fq.QueueSetCompleter
944 var err error
945 if queues != nil {
946 qsc, err = queues.BeginConfigChange(qcQS)
947 } else {
948 qsc, err = qsf.BeginConstruction(qcQS, reqsIntPair, execSeatsObs, seatDemandGauge)
949 }
950 if err != nil {
951 err = fmt.Errorf("priority level %q has QueuingConfiguration %#+v, which is invalid: %w", pl.Name, qcQS, err)
952 }
953 return qsc, err
954 }
955
956 func (meal *cfgMeal) presyncFlowSchemaStatus(fs *flowcontrol.FlowSchema, isDangling bool, plName string) {
957 danglingCondition := apihelpers.GetFlowSchemaConditionByType(fs, flowcontrol.FlowSchemaConditionDangling)
958 if danglingCondition == nil {
959 danglingCondition = &flowcontrol.FlowSchemaCondition{
960 Type: flowcontrol.FlowSchemaConditionDangling,
961 }
962 }
963 desiredStatus := flowcontrol.ConditionFalse
964 var desiredReason, desiredMessage string
965 if isDangling {
966 desiredStatus = flowcontrol.ConditionTrue
967 desiredReason = "NotFound"
968 desiredMessage = fmt.Sprintf("This FlowSchema references the PriorityLevelConfiguration object named %q but there is no such object", plName)
969 } else {
970 desiredReason = "Found"
971 desiredMessage = fmt.Sprintf("This FlowSchema references the PriorityLevelConfiguration object named %q and it exists", plName)
972 }
973 if danglingCondition.Status == desiredStatus && danglingCondition.Reason == desiredReason && danglingCondition.Message == desiredMessage {
974 return
975 }
976 now := meal.cfgCtlr.clock.Now()
977 meal.fsStatusUpdates = append(meal.fsStatusUpdates, fsStatusUpdate{
978 flowSchema: fs,
979 condition: flowcontrol.FlowSchemaCondition{
980 Type: flowcontrol.FlowSchemaConditionDangling,
981 Status: desiredStatus,
982 LastTransitionTime: metav1.NewTime(now),
983 Reason: desiredReason,
984 Message: desiredMessage,
985 },
986 oldValue: *danglingCondition})
987 }
988
989 // imaginePL adds a priority level based on one of the mandatory ones
990 // that does not actually exist (right now) as a real API object.
991 func (meal *cfgMeal) imaginePL(proto *flowcontrol.PriorityLevelConfiguration) {
992 klog.V(3).Infof("No %s PriorityLevelConfiguration found, imagining one", proto.Name)
993 labelValues := []string{proto.Name}
994 reqsGaugePair := metrics.RatioedGaugeVecPhasedElementPair(meal.cfgCtlr.reqsGaugeVec, 1, 1, labelValues)
995 execSeatsObs := meal.cfgCtlr.execSeatsGaugeVec.NewForLabelValuesSafe(0, 1, labelValues)
996 seatDemandIntegrator := fq.NewNamedIntegrator(meal.cfgCtlr.clock, proto.Name)
997 seatDemandRatioedGauge := metrics.ApiserverSeatDemands.NewForLabelValuesSafe(0, 1, []string{proto.Name})
998 qsCompleter, err := queueSetCompleterForPL(meal.cfgCtlr.queueSetFactory, nil, proto, reqsGaugePair,
999 execSeatsObs, metrics.NewUnionGauge(seatDemandIntegrator, seatDemandRatioedGauge))
1000 if err != nil {
1001 // This can not happen because proto is one of the mandatory
1002 // objects and these are not erroneous
1003 panic(err)
1004 }
1005 meal.newPLStates[proto.Name] = &priorityLevelState{
1006 pl: proto,
1007 qsCompleter: qsCompleter,
1008 reqsGaugePair: reqsGaugePair,
1009 execSeatsObs: execSeatsObs,
1010 seatDemandIntegrator: seatDemandIntegrator,
1011 seatDemandRatioedGauge: seatDemandRatioedGauge,
1012 }
1013 nominalConcurrencyShares, _, _ := plSpecCommons(proto)
1014 meal.shareSum += float64(*nominalConcurrencyShares)
1015 }
1016
1017 // startRequest classifies and, if appropriate, enqueues the request.
1018 // Returns a nil Request if and only if the request is to be rejected.
1019 // The returned bool indicates whether the request is exempt from
1020 // limitation. The startWaitingTime is when the request started
1021 // waiting in its queue, or `Time{}` if this did not happen.
1022 func (cfgCtlr *configController) startRequest(ctx context.Context, rd RequestDigest,
1023 noteFn func(fs *flowcontrol.FlowSchema, pl *flowcontrol.PriorityLevelConfiguration, flowDistinguisher string),
1024 workEstimator func() fcrequest.WorkEstimate,
1025 queueNoteFn fq.QueueNoteFn) (fs *flowcontrol.FlowSchema, pl *flowcontrol.PriorityLevelConfiguration, isExempt bool, req fq.Request, startWaitingTime time.Time) {
1026 klog.V(7).Infof("startRequest(%#+v)", rd)
1027 cfgCtlr.lock.RLock()
1028 defer cfgCtlr.lock.RUnlock()
1029 var selectedFlowSchema, catchAllFlowSchema *flowcontrol.FlowSchema
1030 for _, fs := range cfgCtlr.flowSchemas {
1031 if matchesFlowSchema(rd, fs) {
1032 selectedFlowSchema = fs
1033 break
1034 }
1035 if fs.Name == flowcontrol.FlowSchemaNameCatchAll {
1036 catchAllFlowSchema = fs
1037 }
1038 }
1039 if selectedFlowSchema == nil {
1040 // This should never happen. If the requestDigest's User is a part of
1041 // system:authenticated or system:unauthenticated, the catch-all flow
1042 // schema should match it. However, if that invariant somehow fails,
1043 // fallback to the catch-all flow schema anyway.
1044 if catchAllFlowSchema == nil {
1045 // This should absolutely never, ever happen! APF guarantees two
1046 // undeletable flow schemas at all times: an exempt flow schema and a
1047 // catch-all flow schema.
1048 panic(fmt.Sprintf("no fallback catch-all flow schema found for request %#+v and user %#+v", rd.RequestInfo, rd.User))
1049 }
1050 selectedFlowSchema = catchAllFlowSchema
1051 klog.Warningf("no match found for request %#+v and user %#+v; selecting catchAll=%s as fallback flow schema", rd.RequestInfo, rd.User, fcfmt.Fmt(selectedFlowSchema))
1052 }
1053 plName := selectedFlowSchema.Spec.PriorityLevelConfiguration.Name
1054 plState := cfgCtlr.priorityLevelStates[plName]
1055 var numQueues int32
1056 var hashValue uint64
1057 var flowDistinguisher string
1058 if plState.pl.Spec.Type != flowcontrol.PriorityLevelEnablementExempt {
1059 if plState.pl.Spec.Limited.LimitResponse.Type == flowcontrol.LimitResponseTypeQueue {
1060 numQueues = plState.pl.Spec.Limited.LimitResponse.Queuing.Queues
1061 }
1062 if numQueues > 1 {
1063 flowDistinguisher = computeFlowDistinguisher(rd, selectedFlowSchema.Spec.DistinguisherMethod)
1064 hashValue = hashFlowID(selectedFlowSchema.Name, flowDistinguisher)
1065 }
1066 }
1067
1068 noteFn(selectedFlowSchema, plState.pl, flowDistinguisher)
1069 workEstimate := workEstimator()
1070
1071 if plState.pl.Spec.Type != flowcontrol.PriorityLevelEnablementExempt {
1072 startWaitingTime = cfgCtlr.clock.Now()
1073 }
1074 klog.V(7).Infof("startRequest(%#+v) => fsName=%q, distMethod=%#+v, plName=%q, numQueues=%d", rd, selectedFlowSchema.Name, selectedFlowSchema.Spec.DistinguisherMethod, plName, numQueues)
1075 req, idle := plState.queues.StartRequest(ctx, &workEstimate, hashValue, flowDistinguisher, selectedFlowSchema.Name, rd.RequestInfo, rd.User, queueNoteFn)
1076 if idle {
1077 cfgCtlr.maybeReapReadLocked(plName, plState)
1078 }
1079 return selectedFlowSchema, plState.pl, plState.pl.Spec.Type == flowcontrol.PriorityLevelEnablementExempt, req, startWaitingTime
1080 }
1081
1082 // maybeReap will remove the last internal traces of the named
1083 // priority level if it has no more use. Call this after getting a
1084 // clue that the given priority level is undesired and idle.
1085 func (cfgCtlr *configController) maybeReap(plName string) {
1086 cfgCtlr.lock.RLock()
1087 defer cfgCtlr.lock.RUnlock()
1088 plState := cfgCtlr.priorityLevelStates[plName]
1089 if plState == nil {
1090 klog.V(7).Infof("plName=%s, plState==nil", plName)
1091 return
1092 }
1093 useless := plState.quiescing && plState.numPending == 0 && plState.queues.IsIdle()
1094 klog.V(7).Infof("plState.quiescing=%v, plState.numPending=%d, useless=%v", plState.quiescing, plState.numPending, useless)
1095 if !useless {
1096 return
1097 }
1098 klog.V(3).Infof("Triggered API priority and fairness config reloading because priority level %s is undesired and idle", plName)
1099 cfgCtlr.configQueue.Add(0)
1100 }
1101
1102 // maybeReapLocked requires the cfgCtlr's lock to already be held and
1103 // will remove the last internal traces of the named priority level if
1104 // it has no more use. Call this if both (1) plState.queues is
1105 // non-nil and reported being idle, and (2) cfgCtlr's lock has not
1106 // been released since then.
1107 func (cfgCtlr *configController) maybeReapReadLocked(plName string, plState *priorityLevelState) {
1108 if !(plState.quiescing && plState.numPending == 0) {
1109 return
1110 }
1111 klog.V(3).Infof("Triggered API priority and fairness config reloading because priority level %s is undesired and idle", plName)
1112 cfgCtlr.configQueue.Add(0)
1113 }
1114
1115 // computeFlowDistinguisher extracts the flow distinguisher according to the given method
1116 func computeFlowDistinguisher(rd RequestDigest, method *flowcontrol.FlowDistinguisherMethod) string {
1117 if method == nil {
1118 return ""
1119 }
1120 switch method.Type {
1121 case flowcontrol.FlowDistinguisherMethodByUserType:
1122 return rd.User.GetName()
1123 case flowcontrol.FlowDistinguisherMethodByNamespaceType:
1124 return rd.RequestInfo.Namespace
1125 default:
1126 // this line shall never reach
1127 panic("invalid flow-distinguisher method")
1128 }
1129 }
1130
1131 func hashFlowID(fsName, fDistinguisher string) uint64 {
1132 hash := sha256.New()
1133 var sep = [1]byte{0}
1134 hash.Write([]byte(fsName))
1135 hash.Write(sep[:])
1136 hash.Write([]byte(fDistinguisher))
1137 var sum [32]byte
1138 hash.Sum(sum[:0])
1139 return binary.LittleEndian.Uint64(sum[:8])
1140 }
1141
1142 func relDiff(x, y float64) float64 {
1143 diff := math.Abs(x - y)
1144 den := math.Max(math.Abs(x), math.Abs(y))
1145 if den == 0 {
1146 return 0
1147 }
1148 return diff / den
1149 }
1150
1151 // plSpecCommons returns the (NominalConcurrencyShares, LendablePercent, BorrowingLimitPercent) of the given priority level config
1152 func plSpecCommons(pl *flowcontrol.PriorityLevelConfiguration) (*int32, *int32, *int32) {
1153 if limiter := pl.Spec.Limited; limiter != nil {
1154 return limiter.NominalConcurrencyShares, limiter.LendablePercent, limiter.BorrowingLimitPercent
1155 }
1156 limiter := pl.Spec.Exempt
1157 var nominalConcurrencyShares int32
1158 if limiter.NominalConcurrencyShares != nil {
1159 nominalConcurrencyShares = *limiter.NominalConcurrencyShares
1160 }
1161 return &nominalConcurrencyShares, limiter.LendablePercent, nil
1162 }