Debian Codegraph @

pkg/server/filters/priority-and-fairness.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 filters
18
19 import (
20 "context"
21 "fmt"
22 "net/http"
23 "runtime"
24 "strconv"
25 "sync"
26 "sync/atomic"
27 "time"
28
29 flowcontrol "k8s.io/api/flowcontrol/v1"
30 apitypes "k8s.io/apimachinery/pkg/types"
31 epmetrics "k8s.io/apiserver/pkg/endpoints/metrics"
32 apirequest "k8s.io/apiserver/pkg/endpoints/request"
33 "k8s.io/apiserver/pkg/server/httplog"
34 utilflowcontrol "k8s.io/apiserver/pkg/util/flowcontrol"
35 fcmetrics "k8s.io/apiserver/pkg/util/flowcontrol/metrics"
36 flowcontrolrequest "k8s.io/apiserver/pkg/util/flowcontrol/request"
37 "k8s.io/klog/v2"
38 utilsclock "k8s.io/utils/clock"
39 )
40
41 // PriorityAndFairnessClassification identifies the results of
42 // classification for API Priority and Fairness
43 type PriorityAndFairnessClassification struct {
44 FlowSchemaName string
45 FlowSchemaUID apitypes.UID
46 PriorityLevelName string
47 PriorityLevelUID apitypes.UID
48 }
49
50 // waitingMark tracks requests waiting rather than being executed
51 var waitingMark = &requestWatermark{
52 phase: epmetrics.WaitingPhase,
53 }
54
55 var atomicMutatingExecuting, atomicReadOnlyExecuting atomic.Int32
56 var atomicMutatingWaiting, atomicReadOnlyWaiting atomic.Int32
57
58 // newInitializationSignal is defined for testing purposes.
59 var newInitializationSignal = utilflowcontrol.NewInitializationSignal
60
61 func truncateLogField(s string) string {
62 const maxFieldLogLength = 64
63
64 if len(s) > maxFieldLogLength {
65 s = s[0:maxFieldLogLength]
66 }
67 return s
68 }
69
70 var initAPFOnce sync.Once
71
72 type priorityAndFairnessHandler struct {
73 handler http.Handler
74 longRunningRequestCheck apirequest.LongRunningRequestCheck
75 fcIfc utilflowcontrol.Interface
76 workEstimator flowcontrolrequest.WorkEstimatorFunc
77
78 // droppedRequests tracks the history of dropped requests for
79 // the purpose of computing RetryAfter header to avoid system
80 // overload.
81 droppedRequests utilflowcontrol.DroppedRequestsTracker
82
83 // newReqWaitCtxFn creates a derived context with a deadline
84 // of how long a given request can wait in its queue.
85 newReqWaitCtxFn func(context.Context) (context.Context, context.CancelFunc)
86 }
87
88 func (h *priorityAndFairnessHandler) Handle(w http.ResponseWriter, r *http.Request) {
89 ctx := r.Context()
90 requestInfo, ok := apirequest.RequestInfoFrom(ctx)
91 if !ok {
92 handleError(w, r, fmt.Errorf("no RequestInfo found in context"))
93 return
94 }
95 user, ok := apirequest.UserFrom(ctx)
96 if !ok {
97 handleError(w, r, fmt.Errorf("no User found in context"))
98 return
99 }
100
101 isWatchRequest := watchVerbs.Has(requestInfo.Verb)
102
103 // Skip tracking long running non-watch requests.
104 if h.longRunningRequestCheck != nil && h.longRunningRequestCheck(r, requestInfo) && !isWatchRequest {
105 klog.V(6).Infof("Serving RequestInfo=%#+v, user.Info=%#+v as longrunning\n", requestInfo, user)
106 h.handler.ServeHTTP(w, r)
107 return
108 }
109
110 var classification *PriorityAndFairnessClassification
111 noteFn := func(fs *flowcontrol.FlowSchema, pl *flowcontrol.PriorityLevelConfiguration, flowDistinguisher string) {
112 classification = &PriorityAndFairnessClassification{
113 FlowSchemaName: fs.Name,
114 FlowSchemaUID: fs.UID,
115 PriorityLevelName: pl.Name,
116 PriorityLevelUID: pl.UID,
117 }
118
119 httplog.AddKeyValue(ctx, "apf_pl", truncateLogField(pl.Name))
120 httplog.AddKeyValue(ctx, "apf_fs", truncateLogField(fs.Name))
121 }
122 // estimateWork is called, if at all, after noteFn
123 estimateWork := func() flowcontrolrequest.WorkEstimate {
124 if classification == nil {
125 // workEstimator is being invoked before classification of
126 // the request has completed, we should never be here though.
127 klog.ErrorS(fmt.Errorf("workEstimator is being invoked before classification of the request has completed"),
128 "Using empty FlowSchema and PriorityLevelConfiguration name", "verb", r.Method, "URI", r.RequestURI)
129 return h.workEstimator(r, "", "")
130 }
131
132 workEstimate := h.workEstimator(r, classification.FlowSchemaName, classification.PriorityLevelName)
133
134 fcmetrics.ObserveWorkEstimatedSeats(classification.PriorityLevelName, classification.FlowSchemaName, workEstimate.MaxSeats())
135 httplog.AddKeyValue(ctx, "apf_iseats", workEstimate.InitialSeats)
136 httplog.AddKeyValue(ctx, "apf_fseats", workEstimate.FinalSeats)
137 httplog.AddKeyValue(ctx, "apf_additionalLatency", workEstimate.AdditionalLatency)
138
139 return workEstimate
140 }
141
142 var served bool
143 isMutatingRequest := !nonMutatingRequestVerbs.Has(requestInfo.Verb)
144 noteExecutingDelta := func(delta int32) {
145 if isMutatingRequest {
146 watermark.recordMutating(int(atomicMutatingExecuting.Add(delta)))
147 } else {
148 watermark.recordReadOnly(int(atomicReadOnlyExecuting.Add(delta)))
149 }
150 }
151 noteWaitingDelta := func(delta int32) {
152 if isMutatingRequest {
153 waitingMark.recordMutating(int(atomicMutatingWaiting.Add(delta)))
154 } else {
155 waitingMark.recordReadOnly(int(atomicReadOnlyWaiting.Add(delta)))
156 }
157 }
158 queueNote := func(inQueue bool) {
159 if inQueue {
160 noteWaitingDelta(1)
161 } else {
162 noteWaitingDelta(-1)
163 }
164 }
165
166 digest := utilflowcontrol.RequestDigest{
167 RequestInfo: requestInfo,
168 User: user,
169 }
170
171 if isWatchRequest {
172 // This channel blocks calling handler.ServeHTTP() until closed, and is closed inside execute().
173 // If APF rejects the request, it is never closed.
174 shouldStartWatchCh := make(chan struct{})
175
176 watchInitializationSignal := newInitializationSignal()
177 // This wraps the request passed to handler.ServeHTTP(),
178 // setting a context that plumbs watchInitializationSignal to storage
179 var watchReq *http.Request
180 // This is set inside execute(), prior to closing shouldStartWatchCh.
181 // If the request is rejected by APF it is left nil.
182 var forgetWatch utilflowcontrol.ForgetWatchFunc
183
184 defer func() {
185 // Protect from the situation when request will not reach storage layer
186 // and the initialization signal will not be send.
187 if watchInitializationSignal != nil {
188 watchInitializationSignal.Signal()
189 }
190 // Forget the watcher if it was registered.
191 //
192 // This is race-free because by this point, one of the following occurred:
193 // case <-shouldStartWatchCh: execute() completed the assignment to forgetWatch
194 // case <-resultCh: Handle() completed, and Handle() does not return
195 // while execute() is running
196 if forgetWatch != nil {
197 forgetWatch()
198 }
199 }()
200
201 execute := func() {
202 startedAt := time.Now()
203 defer func() {
204 httplog.AddKeyValue(ctx, "apf_init_latency", time.Since(startedAt))
205 }()
206 noteExecutingDelta(1)
207 defer noteExecutingDelta(-1)
208 served = true
209 setResponseHeaders(classification, w)
210
211 forgetWatch = h.fcIfc.RegisterWatch(r)
212
213 // Notify the main thread that we're ready to start the watch.
214 close(shouldStartWatchCh)
215
216 // Wait until the request is finished from the APF point of view
217 // (which is when its initialization is done).
218 watchInitializationSignal.Wait()
219 }
220
221 // Ensure that an item can be put to resultCh asynchronously.
222 resultCh := make(chan interface{}, 1)
223
224 // Call Handle in a separate goroutine.
225 // The reason for it is that from APF point of view, the request processing
226 // finishes as soon as watch is initialized (which is generally orders of
227 // magnitude faster then the watch request itself). This means that Handle()
228 // call finishes much faster and for performance reasons we want to reduce
229 // the number of running goroutines - so we run the shorter thing in a
230 // dedicated goroutine and the actual watch handler in the main one.
231 go func() {
232 defer func() {
233 err := recover()
234 // do not wrap the sentinel ErrAbortHandler panic value
235 if err != nil && err != http.ErrAbortHandler {
236 // Same as stdlib http server code. Manually allocate stack
237 // trace buffer size to prevent excessively large logs
238 const size = 64 << 10
239 buf := make([]byte, size)
240 buf = buf[:runtime.Stack(buf, false)]
241 err = fmt.Sprintf("%v\n%s", err, buf)
242 }
243
244 // Ensure that the result is put into resultCh independently of the panic.
245 resultCh <- err
246 }()
247
248 // We create handleCtx with an adjusted deadline, for two reasons.
249 // One is to limit the time the request waits before its execution starts.
250 // The other reason for it is that Handle() underneath may start additional goroutine
251 // that is blocked on context cancellation. However, from APF point of view,
252 // we don't want to wait until the whole watch request is processed (which is
253 // when it context is actually cancelled) - we want to unblock the goroutine as
254 // soon as the request is processed from the APF point of view.
255 //
256 // Note that we explicitly do NOT call the actuall handler using that context
257 // to avoid cancelling request too early.
258 handleCtx, handleCtxCancel := h.newReqWaitCtxFn(ctx)
259 defer handleCtxCancel()
260
261 // Note that Handle will return irrespective of whether the request
262 // executes or is rejected. In the latter case, the function will return
263 // without calling the passed `execute` function.
264 h.fcIfc.Handle(handleCtx, digest, noteFn, estimateWork, queueNote, execute)
265 }()
266
267 select {
268 case <-shouldStartWatchCh:
269 func() {
270 // TODO: if both goroutines panic, propagate the stack traces from both
271 // goroutines so they are logged properly:
272 defer func() {
273 // Protect from the situation when request will not reach storage layer
274 // and the initialization signal will not be send.
275 // It has to happen before waiting on the resultCh below.
276 watchInitializationSignal.Signal()
277 // TODO: Consider finishing the request as soon as Handle call panics.
278 if err := <-resultCh; err != nil {
279 panic(err)
280 }
281 }()
282 watchCtx := utilflowcontrol.WithInitializationSignal(ctx, watchInitializationSignal)
283 watchReq = r.WithContext(watchCtx)
284 h.handler.ServeHTTP(w, watchReq)
285 }()
286 case err := <-resultCh:
287 if err != nil {
288 panic(err)
289 }
290 }
291 } else {
292 execute := func() {
293 noteExecutingDelta(1)
294 defer noteExecutingDelta(-1)
295 served = true
296 setResponseHeaders(classification, w)
297
298 h.handler.ServeHTTP(w, r)
299 }
300
301 func() {
302 handleCtx, cancelFn := h.newReqWaitCtxFn(ctx)
303 defer cancelFn()
304 h.fcIfc.Handle(handleCtx, digest, noteFn, estimateWork, queueNote, execute)
305 }()
306 }
307
308 if !served {
309 setResponseHeaders(classification, w)
310
311 epmetrics.RecordDroppedRequest(r, requestInfo, epmetrics.APIServerComponent, isMutatingRequest)
312 epmetrics.RecordRequestTermination(r, requestInfo, epmetrics.APIServerComponent, http.StatusTooManyRequests)
313 h.droppedRequests.RecordDroppedRequest(classification.PriorityLevelName)
314
315 // TODO(wojtek-t): Idea from deads2k: we can consider some jittering and in case of non-int
316 // number, just return the truncated result and sleep the remainder server-side.
317 tooManyRequests(r, w, strconv.Itoa(int(h.droppedRequests.GetRetryAfter(classification.PriorityLevelName))))
318 }
319 }
320
321 // WithPriorityAndFairness limits the number of in-flight
322 // requests in a fine-grained way.
323 func WithPriorityAndFairness(
324 handler http.Handler,
325 longRunningRequestCheck apirequest.LongRunningRequestCheck,
326 fcIfc utilflowcontrol.Interface,
327 workEstimator flowcontrolrequest.WorkEstimatorFunc,
328 defaultRequestWaitLimit time.Duration,
329 ) http.Handler {
330 if fcIfc == nil {
331 klog.Warningf("priority and fairness support not found, skipping")
332 return handler
333 }
334 initAPFOnce.Do(func() {
335 initMaxInFlight(0, 0)
336 // Fetching these gauges is delayed until after their underlying metric has been registered
337 // so that this latches onto the efficient implementation.
338 waitingMark.readOnlyObserver = fcmetrics.GetWaitingReadonlyConcurrency()
339 waitingMark.mutatingObserver = fcmetrics.GetWaitingMutatingConcurrency()
340 })
341
342 clock := &utilsclock.RealClock{}
343 newReqWaitCtxFn := func(ctx context.Context) (context.Context, context.CancelFunc) {
344 return getRequestWaitContext(ctx, defaultRequestWaitLimit, clock)
345 }
346
347 priorityAndFairnessHandler := &priorityAndFairnessHandler{
348 handler: handler,
349 longRunningRequestCheck: longRunningRequestCheck,
350 fcIfc: fcIfc,
351 workEstimator: workEstimator,
352 droppedRequests: utilflowcontrol.NewDroppedRequestsTracker(),
353 newReqWaitCtxFn: newReqWaitCtxFn,
354 }
355 return http.HandlerFunc(priorityAndFairnessHandler.Handle)
356 }
357
358 // StartPriorityAndFairnessWatermarkMaintenance starts the goroutines to observe and maintain watermarks for
359 // priority-and-fairness requests.
360 func StartPriorityAndFairnessWatermarkMaintenance(stopCh <-chan struct{}) {
361 startWatermarkMaintenance(watermark, stopCh)
362 startWatermarkMaintenance(waitingMark, stopCh)
363 }
364
365 func setResponseHeaders(classification *PriorityAndFairnessClassification, w http.ResponseWriter) {
366 if classification == nil {
367 return
368 }
369
370 // We intentionally set the UID of the flow-schema and priority-level instead of name. This is so that
371 // the names that cluster-admins choose for categorization and priority levels are not exposed, also
372 // the names might make it obvious to the users that they are rejected due to classification with low priority.
373 w.Header().Set(flowcontrol.ResponseHeaderMatchedPriorityLevelConfigurationUID, string(classification.PriorityLevelUID))
374 w.Header().Set(flowcontrol.ResponseHeaderMatchedFlowSchemaUID, string(classification.FlowSchemaUID))
375 }
376
377 func tooManyRequests(req *http.Request, w http.ResponseWriter, retryAfter string) {
378 // Return a 429 status indicating "Too Many Requests"
379 w.Header().Set("Retry-After", retryAfter)
380 http.Error(w, "Too many requests, please try again later.", http.StatusTooManyRequests)
381 }
382
383 // getRequestWaitContext returns a new context with a deadline of how
384 // long the request is allowed to wait before it is removed from its
385 // queue and rejected.
386 // The context.CancelFunc returned must never be nil and the caller is
387 // responsible for calling the CancelFunc function for cleanup.
388 // - ctx: the context associated with the request (it may or may
389 // not have a deadline).
390 // - defaultRequestWaitLimit: the default wait duration that is used
391 // if the request context does not have any deadline.
392 // (a) initialization of a watch or
393 // (b) a request whose context has no deadline
394 //
395 // clock comes in handy for testing the function
396 func getRequestWaitContext(ctx context.Context, defaultRequestWaitLimit time.Duration, clock utilsclock.PassiveClock) (context.Context, context.CancelFunc) {
397 if ctx.Err() != nil {
398 return ctx, func() {}
399 }
400
401 reqArrivedAt := clock.Now()
402 if reqReceivedTimestamp, ok := apirequest.ReceivedTimestampFrom(ctx); ok {
403 reqArrivedAt = reqReceivedTimestamp
404 }
405
406 // a) we will allow the request to wait in the queue for one
407 // fourth of the time of its allotted deadline.
408 // b) if the request context does not have any deadline
409 // then we default to 'defaultRequestWaitLimit'
410 // in any case, the wait limit for any request must not
411 // exceed the hard limit of 1m
412 //
413 // request has deadline:
414 // wait-limit = min(remaining deadline / 4, 1m)
415 // request has no deadline:
416 // wait-limit = min(defaultRequestWaitLimit, 1m)
417 thisReqWaitLimit := defaultRequestWaitLimit
418 if deadline, ok := ctx.Deadline(); ok {
419 thisReqWaitLimit = deadline.Sub(reqArrivedAt) / 4
420 }
421 if thisReqWaitLimit > time.Minute {
422 thisReqWaitLimit = time.Minute
423 }
424
425 return context.WithDeadline(ctx, reqArrivedAt.Add(thisReqWaitLimit))
426 }