| 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 queueset |
| 18 |
|
| 19 |
import ( |
| 20 |
"context" |
| 21 |
"time" |
| 22 |
|
| 23 |
"k8s.io/apimachinery/pkg/util/sets" |
| 24 |
genericrequest "k8s.io/apiserver/pkg/endpoints/request" |
| 25 |
"k8s.io/apiserver/pkg/util/flowcontrol/debug" |
| 26 |
fq "k8s.io/apiserver/pkg/util/flowcontrol/fairqueuing" |
| 27 |
"k8s.io/apiserver/pkg/util/flowcontrol/fairqueuing/promise" |
| 28 |
fcrequest "k8s.io/apiserver/pkg/util/flowcontrol/request" |
| 29 |
) |
| 30 |
|
| 31 |
// request is a temporary container for "requests" with additional |
| 32 |
// tracking fields required for QueueSet functionality. |
| 33 |
type request struct { |
| 34 |
ctx context.Context |
| 35 |
|
| 36 |
qs *queueSet |
| 37 |
|
| 38 |
flowDistinguisher string |
| 39 |
fsName string |
| 40 |
|
| 41 |
// The relevant queue. Is nil if this request did not go through |
| 42 |
// a queue. |
| 43 |
queue *queue |
| 44 |
|
| 45 |
// estimated amount of work of the request |
| 46 |
workEstimate completedWorkEstimate |
| 47 |
|
| 48 |
// decision gets set to a `requestDecision` indicating what to do |
| 49 |
// with this request. It gets set exactly once, when the request |
| 50 |
// is removed from its queue. The value will be decisionReject, |
| 51 |
// decisionCancel, or decisionExecute. |
| 52 |
// |
| 53 |
// decision.Set is called with the queueSet locked. |
| 54 |
// decision.Get is called without the queueSet locked. |
| 55 |
decision promise.WriteOnce |
| 56 |
|
| 57 |
// arrivalTime is the real time when the request entered this system |
| 58 |
arrivalTime time.Time |
| 59 |
|
| 60 |
// descr1 and descr2 are not used in any logic but they appear in |
| 61 |
// log messages |
| 62 |
descr1, descr2 interface{} |
| 63 |
|
| 64 |
queueNoteFn fq.QueueNoteFn |
| 65 |
|
| 66 |
// The preceding fields are filled in at creation and not modified since; |
| 67 |
// the following fields may be modified later and must only be accessed while |
| 68 |
// holding the queueSet's lock. |
| 69 |
|
| 70 |
// Removes this request from its queue. If the request is not put into a |
| 71 |
// a queue it will be nil. |
| 72 |
removeFromQueueLocked removeFromFIFOFunc |
| 73 |
|
| 74 |
// arrivalR is R(arrivalTime). R is, confusingly, also called "virtual time". |
| 75 |
// This field is meaningful only while the request is waiting in the virtual world. |
| 76 |
arrivalR fcrequest.SeatSeconds |
| 77 |
|
| 78 |
// startTime is the real time when the request began executing |
| 79 |
startTime time.Time |
| 80 |
|
| 81 |
// Indicates whether client has called Request::Wait() |
| 82 |
waitStarted bool |
| 83 |
} |
| 84 |
|
| 85 |
type completedWorkEstimate struct { |
| 86 |
fcrequest.WorkEstimate |
| 87 |
totalWork fcrequest.SeatSeconds // initial plus final work |
| 88 |
finalWork fcrequest.SeatSeconds // only final work |
| 89 |
} |
| 90 |
|
| 91 |
// queue is a sequence of requests that have arrived but not yet finished |
| 92 |
// execution in both the real and virtual worlds. |
| 93 |
type queue struct { |
| 94 |
// The requestsWaiting not yet executing in the real world are stored in a FIFO list. |
| 95 |
requestsWaiting fifo |
| 96 |
|
| 97 |
// nextDispatchR is the R progress meter reading at |
| 98 |
// which the next request will be dispatched in the virtual world. |
| 99 |
nextDispatchR fcrequest.SeatSeconds |
| 100 |
|
| 101 |
// requestsExecuting is the set of requests executing in the real world. |
| 102 |
requestsExecuting sets.Set[*request] |
| 103 |
|
| 104 |
// index is the position of this queue among those in its queueSet. |
| 105 |
index int |
| 106 |
|
| 107 |
// seatsInUse is the total number of "seats" currently occupied |
| 108 |
// by all the requests that are currently executing in this queue. |
| 109 |
seatsInUse int |
| 110 |
} |
| 111 |
|
| 112 |
// queueSum tracks the sum of initial seats, max seats, and |
| 113 |
// totalWork from all requests in a given queue |
| 114 |
type queueSum struct { |
| 115 |
// InitialSeatsSum is the sum of InitialSeats |
| 116 |
// associated with all requests in a given queue. |
| 117 |
InitialSeatsSum int |
| 118 |
|
| 119 |
// MaxSeatsSum is the sum of MaxSeats |
| 120 |
// associated with all requests in a given queue. |
| 121 |
MaxSeatsSum int |
| 122 |
|
| 123 |
// TotalWorkSum is the sum of totalWork of the waiting requests |
| 124 |
TotalWorkSum fcrequest.SeatSeconds |
| 125 |
} |
| 126 |
|
| 127 |
func (req *request) totalWork() fcrequest.SeatSeconds { |
| 128 |
return req.workEstimate.totalWork |
| 129 |
} |
| 130 |
|
| 131 |
func (qs *queueSet) completeWorkEstimate(we *fcrequest.WorkEstimate) completedWorkEstimate { |
| 132 |
finalWork := qs.computeFinalWork(we) |
| 133 |
return completedWorkEstimate{ |
| 134 |
WorkEstimate: *we, |
| 135 |
totalWork: qs.computeInitialWork(we) + finalWork, |
| 136 |
finalWork: finalWork, |
| 137 |
} |
| 138 |
} |
| 139 |
|
| 140 |
func (qs *queueSet) computeInitialWork(we *fcrequest.WorkEstimate) fcrequest.SeatSeconds { |
| 141 |
return fcrequest.SeatsTimesDuration(float64(we.InitialSeats), qs.estimatedServiceDuration) |
| 142 |
} |
| 143 |
|
| 144 |
func (qs *queueSet) computeFinalWork(we *fcrequest.WorkEstimate) fcrequest.SeatSeconds { |
| 145 |
return fcrequest.SeatsTimesDuration(float64(we.FinalSeats), we.AdditionalLatency) |
| 146 |
} |
| 147 |
|
| 148 |
func (q *queue) dumpLocked(includeDetails bool) debug.QueueDump { |
| 149 |
waitingDigest := make([]debug.RequestDump, 0, q.requestsWaiting.Length()) |
| 150 |
q.requestsWaiting.Walk(func(r *request) bool { |
| 151 |
waitingDigest = append(waitingDigest, dumpRequest(includeDetails)(r)) |
| 152 |
return true |
| 153 |
}) |
| 154 |
executingDigest := SetMapReduce(dumpRequest(includeDetails), append1[debug.RequestDump])(q.requestsExecuting) |
| 155 |
|
| 156 |
sum := q.requestsWaiting.QueueSum() |
| 157 |
queueSum := debug.QueueSum{ |
| 158 |
InitialSeatsSum: sum.InitialSeatsSum, |
| 159 |
MaxSeatsSum: sum.MaxSeatsSum, |
| 160 |
TotalWorkSum: sum.TotalWorkSum.String(), |
| 161 |
} |
| 162 |
|
| 163 |
return debug.QueueDump{ |
| 164 |
NextDispatchR: q.nextDispatchR.String(), |
| 165 |
Requests: waitingDigest, |
| 166 |
RequestsExecuting: executingDigest, |
| 167 |
ExecutingRequests: q.requestsExecuting.Len(), |
| 168 |
SeatsInUse: q.seatsInUse, |
| 169 |
QueueSum: queueSum, |
| 170 |
} |
| 171 |
} |
| 172 |
|
| 173 |
func dumpRequest(includeDetails bool) func(*request) debug.RequestDump { |
| 174 |
return func(r *request) debug.RequestDump { |
| 175 |
ans := debug.RequestDump{ |
| 176 |
MatchedFlowSchema: r.fsName, |
| 177 |
FlowDistinguisher: r.flowDistinguisher, |
| 178 |
ArriveTime: r.arrivalTime, |
| 179 |
StartTime: r.startTime, |
| 180 |
WorkEstimate: r.workEstimate.WorkEstimate, |
| 181 |
} |
| 182 |
if includeDetails { |
| 183 |
userInfo, _ := genericrequest.UserFrom(r.ctx) |
| 184 |
ans.UserName = userInfo.GetName() |
| 185 |
requestInfo, ok := genericrequest.RequestInfoFrom(r.ctx) |
| 186 |
if ok { |
| 187 |
ans.RequestInfo = *requestInfo |
| 188 |
} |
| 189 |
} |
| 190 |
return ans |
| 191 |
} |
| 192 |
} |
| 193 |
|
| 194 |
// SetMapReduce is map-reduce starting from a set type in the sets package. |
| 195 |
func SetMapReduce[Elt comparable, Result, Accumulator any](mapFn func(Elt) Result, reduceFn func(Accumulator, Result) Accumulator) func(map[Elt]sets.Empty) Accumulator { |
| 196 |
return func(set map[Elt]sets.Empty) Accumulator { |
| 197 |
var ans Accumulator |
| 198 |
for elt := range set { |
| 199 |
ans = reduceFn(ans, mapFn(elt)) |
| 200 |
} |
| 201 |
return ans |
| 202 |
} |
| 203 |
} |
| 204 |
|
| 205 |
// SliceMapReduce is map-reduce starting from a slice. |
| 206 |
func SliceMapReduce[Elt, Result, Accumulator any](mapFn func(Elt) Result, reduceFn func(Accumulator, Result) Accumulator) func([]Elt) Accumulator { |
| 207 |
return func(slice []Elt) Accumulator { |
| 208 |
var ans Accumulator |
| 209 |
for _, elt := range slice { |
| 210 |
ans = reduceFn(ans, mapFn(elt)) |
| 211 |
} |
| 212 |
return ans |
| 213 |
} |
| 214 |
} |
| 215 |
|
| 216 |
func or(x, y bool) bool { return x || y } |
| 217 |
|
| 218 |
func append1[Elt any](slice []Elt, next Elt) []Elt { return append(slice, next) } |