| 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 |
"context" |
| 21 |
|
| 22 |
"k8s.io/apiserver/pkg/util/flowcontrol/debug" |
| 23 |
"k8s.io/apiserver/pkg/util/flowcontrol/metrics" |
| 24 |
"k8s.io/apiserver/pkg/util/flowcontrol/request" |
| 25 |
) |
| 26 |
|
| 27 |
// QueueSetFactory is used to create QueueSet objects. Creation, like |
| 28 |
// config update, is done in two phases: the first phase consumes the |
| 29 |
// QueuingConfig and the second consumes the DispatchingConfig. They |
| 30 |
// are separated so that errors from the first phase can be found |
| 31 |
// before committing to a concurrency allotment for the second. |
| 32 |
type QueueSetFactory interface { |
| 33 |
// BeginConstruction does the first phase of creating a QueueSet. |
| 34 |
// The RatioedGaugePair observes number of requests, |
| 35 |
// execution covering just the regular phase. |
| 36 |
// The denominator for the waiting phase is |
| 37 |
// max(1, QueuingConfig.QueueLengthLimit) X max(1, QueuingConfig.DesiredNumQueues). |
| 38 |
// The RatioedGauge observes number of seats occupied through all phases of execution. |
| 39 |
// The denominator for all the ratioed concurrency gauges is supplied later in the DispatchingConfig. |
| 40 |
// The Gauge observes the seat demand (executing + queued seats). |
| 41 |
BeginConstruction(QueuingConfig, metrics.RatioedGaugePair, metrics.RatioedGauge, metrics.Gauge) (QueueSetCompleter, error) |
| 42 |
} |
| 43 |
|
| 44 |
// QueueSetCompleter finishes the two-step process of creating or |
| 45 |
// reconfiguring a QueueSet |
| 46 |
type QueueSetCompleter interface { |
| 47 |
// Complete returns a QueueSet configured by the given |
| 48 |
// dispatching configuration. |
| 49 |
Complete(DispatchingConfig) QueueSet |
| 50 |
} |
| 51 |
|
| 52 |
// QueueSet is the abstraction for the queuing and dispatching |
| 53 |
// functionality of one non-exempt priority level. It covers the |
| 54 |
// functionality described in the "Assignment to a Queue", "Queuing", |
| 55 |
// and "Dispatching" sections of |
| 56 |
// https://github.com/kubernetes/enhancements/blob/master/keps/sig-api-machinery/1040-priority-and-fairness/README.md |
| 57 |
// . Some day we may have connections between priority levels, but |
| 58 |
// today is not that day. |
| 59 |
type QueueSet interface { |
| 60 |
// BeginConfigChange starts the two-step process of updating the |
| 61 |
// configuration. No change is made until Complete is called. If |
| 62 |
// `C := X.BeginConstruction(q)` then `C.Complete(d)` returns the |
| 63 |
// same value `X`. If the QueuingConfig's DesiredNumQueues field |
| 64 |
// is zero then the other queuing-specific config parameters are |
| 65 |
// not changed, so that the queues continue draining as before. |
| 66 |
// In any case, reconfiguration does not discard any queue unless |
| 67 |
// and until it is undesired and empty. |
| 68 |
BeginConfigChange(QueuingConfig) (QueueSetCompleter, error) |
| 69 |
|
| 70 |
// IsIdle returns a bool indicating whether the QueueSet was idle |
| 71 |
// at the moment of the return. Idle means the QueueSet has zero |
| 72 |
// requests queued and zero executing. This bit can change only |
| 73 |
// (1) during a call to StartRequest and (2) during a call to |
| 74 |
// Request::Finish. In the latter case idleness can only change |
| 75 |
// from false to true. |
| 76 |
IsIdle() bool |
| 77 |
|
| 78 |
// StartRequest begins the process of handling a request. If the |
| 79 |
// request gets queued and the number of queues is greater than 1 |
| 80 |
// then StartRequest uses the given hashValue as the source of |
| 81 |
// entropy as it shuffle-shards the request into a queue. The |
| 82 |
// descr1 and descr2 values play no role in the logic but appear |
| 83 |
// in log messages. This method always returns quickly (without |
| 84 |
// waiting for the request to be dequeued). If this method |
| 85 |
// returns a nil Request value then caller should reject the |
| 86 |
// request and the returned bool indicates whether the QueueSet |
| 87 |
// was idle at the moment of the return. Otherwise idle==false |
| 88 |
// and the client must call the Finish method of the Request |
| 89 |
// exactly once. |
| 90 |
StartRequest(ctx context.Context, width *request.WorkEstimate, hashValue uint64, flowDistinguisher, fsName string, descr1, descr2 interface{}, queueNoteFn QueueNoteFn) (req Request, idle bool) |
| 91 |
|
| 92 |
// Dump saves and returns the instant internal state of the queue-set. |
| 93 |
// Note that dumping process will stop the queue-set from proceeding |
| 94 |
// any requests. |
| 95 |
// For debugging only. |
| 96 |
Dump(includeRequestDetails bool) debug.QueueSetDump |
| 97 |
} |
| 98 |
|
| 99 |
// QueueNoteFn is called when a request enters and leaves a queue |
| 100 |
type QueueNoteFn func(inQueue bool) |
| 101 |
|
| 102 |
// Request represents the remainder of the handling of one request |
| 103 |
type Request interface { |
| 104 |
// Finish determines whether to execute or reject the request and |
| 105 |
// invokes `execute` if the decision is to execute the request. |
| 106 |
// The returned `idle bool` value indicates whether the QueueSet |
| 107 |
// was idle when the value was calculated, but might no longer be |
| 108 |
// accurate by the time the client examines that value. |
| 109 |
Finish(execute func()) (idle bool) |
| 110 |
} |
| 111 |
|
| 112 |
// QueuingConfig defines the configuration of the queuing aspect of a QueueSet. |
| 113 |
type QueuingConfig struct { |
| 114 |
// Name is used to identify a queue set, allowing for descriptive information about its intended use |
| 115 |
Name string |
| 116 |
|
| 117 |
// DesiredNumQueues is the number of queues that the API says |
| 118 |
// should exist now. This may be non-positive, in which case |
| 119 |
// QueueLengthLimit, and HandSize are ignored. |
| 120 |
// A value of zero means to respect the ConcurrencyLimit of the DispatchingConfig. |
| 121 |
// A negative value means to always dispatch immediately upon arrival |
| 122 |
// (i.e., the requests are "exempt" from limitation). |
| 123 |
DesiredNumQueues int |
| 124 |
|
| 125 |
// QueueLengthLimit is the maximum number of requests that may be waiting in a given queue at a time |
| 126 |
QueueLengthLimit int |
| 127 |
|
| 128 |
// HandSize is a parameter of shuffle sharding. Upon arrival of a request, a queue is chosen by randomly |
| 129 |
// dealing a "hand" of this many queues and then picking one of minimum length. |
| 130 |
HandSize int |
| 131 |
} |
| 132 |
|
| 133 |
// DispatchingConfig defines the configuration of the dispatching aspect of a QueueSet. |
| 134 |
type DispatchingConfig struct { |
| 135 |
// ConcurrencyLimit is the maximum number of requests of this QueueSet that may be executing at a time |
| 136 |
ConcurrencyLimit int |
| 137 |
|
| 138 |
// ConcurrencyDenominator is used in relative metrics of concurrency. |
| 139 |
// It equals ConcurrencyLimit except when that is zero. |
| 140 |
ConcurrencyDenominator int |
| 141 |
} |