Debian Codegraph @

pkg/util/flowcontrol/watch_tracker.go

raw
1 /*
2 Copyright 2021 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 "net/http"
21 "sync"
22
23 metainternalversion "k8s.io/apimachinery/pkg/apis/meta/internalversion"
24 "k8s.io/apimachinery/pkg/apis/meta/internalversion/scheme"
25 metav1 "k8s.io/apimachinery/pkg/apis/meta/v1"
26 "k8s.io/apimachinery/pkg/util/sets"
27 "k8s.io/apiserver/pkg/endpoints/request"
28
29 "k8s.io/klog/v2"
30 )
31
32 // readOnlyVerbs contains verbs for read-only requests.
33 var readOnlyVerbs = sets.NewString("get", "list", "watch", "proxy")
34
35 // watchIdentifier identifies group of watches that are similar.
36 // As described in the "Priority and Fairness" KEP, we consider
37 // watches similar if they have the same resourceType, namespace
38 // and name. We ignore selectors as they have to be evaluated
39 // when processing an even anyway.
40 //
41 // TODO: For now we only track the number of watches registered
42 // in our kube-apiserver. Eventually we should consider sharing
43 // this information with other kube-apiserver as described in the
44 // KEP, but this isn't part of the first version.
45 type watchIdentifier struct {
46 apiGroup string
47 resource string
48 namespace string
49 name string
50 }
51
52 // ForgetWatchFunc is a function that should be called to forget
53 // the previously registered watch from the watch tracker.
54 type ForgetWatchFunc func()
55
56 // WatchTracker is an interface that allows tracking the number
57 // of watches in the system for the purpose of estimating the
58 // cost of incoming mutating requests.
59 type WatchTracker interface {
60 // RegisterWatch reqisters a watch based on the provided http.Request
61 // in the tracker. It returns the function that should be called
62 // to forget the watcher once it is finished.
63 RegisterWatch(r *http.Request) ForgetWatchFunc
64
65 // GetInterestedWatchCount returns the number of watches that are
66 // potentially interested in a request with a given RequestInfo
67 // for the purpose of estimating cost of that request.
68 GetInterestedWatchCount(requestInfo *request.RequestInfo) int
69 }
70
71 // builtinIndexes represents of set of indexes registered in
72 // watchcache that are indexing watches and increase speed of
73 // their processing.
74 // We define the indexes as a map from a resource to the path
75 // to the field in the object on which the index is built.
76 type builtinIndexes map[string]string
77
78 func getBuiltinIndexes() builtinIndexes {
79 // The only existing indexes as of now are:
80 // - spec.nodeName for pods
81 // - metadata.Name for nodes, secrets and configmaps
82 // However, we can ignore the latter, because the requestInfo.Name
83 // is set for them (i.e. we already catch them correctly).
84 return map[string]string{
85 "pods": "spec.nodeName",
86 }
87 }
88
89 // watchTracker tracks the number of watches in the system for
90 // the purpose of estimating the cost of incoming mutating requests.
91 type watchTracker struct {
92 // indexes represents a set of registered indexes.
93 // It can't change after creation.
94 indexes builtinIndexes
95
96 lock sync.Mutex
97 watchCount map[watchIdentifier]int
98 }
99
100 func NewWatchTracker() WatchTracker {
101 return &watchTracker{
102 indexes: getBuiltinIndexes(),
103 watchCount: make(map[watchIdentifier]int),
104 }
105 }
106
107 const (
108 unsetValue = "<unset>"
109 )
110
111 func getIndexValue(r *http.Request, field string) string {
112 opts := metainternalversion.ListOptions{}
113 if err := scheme.ParameterCodec.DecodeParameters(r.URL.Query(), metav1.SchemeGroupVersion, &opts); err != nil {
114 klog.Warningf("Couldn't parse list options for %v: %v", r.URL.Query(), err)
115 return unsetValue
116 }
117 if opts.FieldSelector == nil {
118 return unsetValue
119 }
120 if value, ok := opts.FieldSelector.RequiresExactMatch(field); ok {
121 return value
122 }
123 return unsetValue
124 }
125
126 type indexValue struct {
127 resource string
128 value string
129 }
130
131 // RegisterWatch implements WatchTracker interface.
132 func (w *watchTracker) RegisterWatch(r *http.Request) ForgetWatchFunc {
133 requestInfo, ok := request.RequestInfoFrom(r.Context())
134 if !ok || requestInfo == nil || requestInfo.Verb != "watch" {
135 return nil
136 }
137
138 var index *indexValue
139 if indexField, ok := w.indexes[requestInfo.Resource]; ok {
140 index = &indexValue{
141 resource: requestInfo.Resource,
142 value: getIndexValue(r, indexField),
143 }
144 }
145
146 identifier := &watchIdentifier{
147 apiGroup: requestInfo.APIGroup,
148 resource: requestInfo.Resource,
149 namespace: requestInfo.Namespace,
150 name: requestInfo.Name,
151 }
152
153 w.lock.Lock()
154 defer w.lock.Unlock()
155 w.updateIndexLocked(identifier, index, 1)
156 return w.forgetWatch(identifier, index)
157 }
158
159 func (w *watchTracker) updateIndexLocked(identifier *watchIdentifier, index *indexValue, incr int) {
160 if index == nil {
161 w.watchCount[*identifier] += incr
162 } else {
163 // For resources with defined index, for a given watch event we are
164 // only processing the watchers that:
165 // (a) do not specify field selector for an index field
166 // (b) do specify field selector with the value equal to the value
167 // coming from the processed object
168 //
169 // TODO(wojtek-t): For the sake of making progress and initially
170 // simplifying the implementation, we approximate (b) for all values
171 // as the value for an empty string. The assumption we're making here
172 // is that the difference between the actual number of watchers that
173 // will be processed, i.e. (a)+(b) above and the one from our
174 // approximation i.e. (a)+[(b) for field value of ""] will be small.
175 // This seem to be true in almost all production clusters, which makes
176 // it a reasonable first step simplification to unblock progres on it.
177 if index.value == unsetValue || index.value == "" {
178 w.watchCount[*identifier] += incr
179 }
180 }
181 }
182
183 func (w *watchTracker) forgetWatch(identifier *watchIdentifier, index *indexValue) ForgetWatchFunc {
184 return func() {
185 w.lock.Lock()
186 defer w.lock.Unlock()
187
188 w.updateIndexLocked(identifier, index, -1)
189 if w.watchCount[*identifier] == 0 {
190 delete(w.watchCount, *identifier)
191 }
192 }
193 }
194
195 // GetInterestedWatchCount implements WatchTracker interface.
196 //
197 // TODO(wojtek-t): As of now, requestInfo for object creation (POST) doesn't
198 // contain the Name field set. Figure out if we can somehow get it for the
199 // more accurate cost estimation.
200 //
201 // TODO(wojtek-t): Figure out how to approach DELETECOLLECTION calls.
202 func (w *watchTracker) GetInterestedWatchCount(requestInfo *request.RequestInfo) int {
203 if requestInfo == nil || readOnlyVerbs.Has(requestInfo.Verb) {
204 return 0
205 }
206
207 result := 0
208 // The watches that we're interested in include:
209 // - watches for all objects of a resource type (no namespace and name specified)
210 // - watches for all objects of a resource type in the same namespace (no name specified)
211 // - watched interested in this particular object
212 identifier := &watchIdentifier{
213 apiGroup: requestInfo.APIGroup,
214 resource: requestInfo.Resource,
215 }
216
217 w.lock.Lock()
218 defer w.lock.Unlock()
219
220 result += w.watchCount[*identifier]
221
222 if requestInfo.Namespace != "" {
223 identifier.namespace = requestInfo.Namespace
224 result += w.watchCount[*identifier]
225 }
226
227 if requestInfo.Name != "" {
228 identifier.name = requestInfo.Name
229 result += w.watchCount[*identifier]
230 }
231
232 return result
233 }