Debian Codegraph @

pkg/storage/cacher/watch_cache.go

raw
1 /*
2 Copyright 2015 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 cacher
18
19 import (
20 "context"
21 "fmt"
22 "math"
23 "sort"
24 "sync"
25 "time"
26
27 "k8s.io/apimachinery/pkg/api/errors"
28 metav1 "k8s.io/apimachinery/pkg/apis/meta/v1"
29 "k8s.io/apimachinery/pkg/fields"
30 "k8s.io/apimachinery/pkg/labels"
31 "k8s.io/apimachinery/pkg/runtime"
32 "k8s.io/apimachinery/pkg/runtime/schema"
33 "k8s.io/apimachinery/pkg/watch"
34 "k8s.io/apiserver/pkg/features"
35 "k8s.io/apiserver/pkg/storage"
36 "k8s.io/apiserver/pkg/storage/cacher/delegator"
37 "k8s.io/apiserver/pkg/storage/cacher/metrics"
38 "k8s.io/apiserver/pkg/storage/cacher/progress"
39 utilfeature "k8s.io/apiserver/pkg/util/feature"
40 "k8s.io/client-go/tools/cache"
41 "k8s.io/component-base/tracing"
42 "k8s.io/klog/v2"
43 "k8s.io/utils/clock"
44 )
45
46 const (
47 // blockTimeout determines how long we're willing to block the request
48 // to wait for a given resource version to be propagated to cache,
49 // before terminating request and returning Timeout error with retry
50 // after suggestion.
51 blockTimeout = 3 * time.Second
52
53 // resourceVersionTooHighRetrySeconds is the seconds before a operation should be retried by the client
54 // after receiving a 'too high resource version' error.
55 resourceVersionTooHighRetrySeconds = 1
56
57 // defaultLowerBoundCapacity is a default value for event cache capacity's lower bound.
58 // TODO: Figure out, to what value we can decreased it.
59 defaultLowerBoundCapacity = 100
60
61 // defaultUpperBoundCapacity should be able to keep the required history.
62 defaultUpperBoundCapacity = 100 * 1024
63 )
64
65 // watchCacheEvent is a single "watch event" that is send to users of
66 // watchCache. Additionally to a typical "watch.Event" it contains
67 // the previous value of the object to enable proper filtering in the
68 // upper layers.
69 type watchCacheEvent struct {
70 Type watch.EventType
71 Object runtime.Object
72 ObjLabels labels.Set
73 ObjFields fields.Set
74 PrevObject runtime.Object
75 PrevObjLabels labels.Set
76 PrevObjFields fields.Set
77 Key string
78 ResourceVersion uint64
79 RecordTime time.Time
80 }
81
82 // watchCache implements a Store interface.
83 // However, it depends on the elements implementing runtime.Object interface.
84 //
85 // watchCache is a "sliding window" (with a limited capacity) of objects
86 // observed from a watch.
87 type watchCache struct {
88 sync.RWMutex
89
90 // Condition on which lists are waiting for the fresh enough
91 // resource version.
92 cond *sync.Cond
93
94 // Maximum size of history window.
95 capacity int
96
97 // upper bound of capacity since event cache has a dynamic size.
98 upperBoundCapacity int
99
100 // lower bound of capacity since event cache has a dynamic size.
101 lowerBoundCapacity int
102
103 // keyFunc is used to get a key in the underlying storage for a given object.
104 keyFunc func(runtime.Object) (string, error)
105
106 // getAttrsFunc is used to get labels and fields of an object.
107 getAttrsFunc func(runtime.Object) (labels.Set, fields.Set, error)
108
109 // cache is used a cyclic buffer - the "current" contents of it are
110 // stored in [start_index%capacity, end_index%capacity) - so the
111 // "current" contents have exactly end_index-start_index items.
112 cache []*watchCacheEvent
113 startIndex int
114 endIndex int
115 // removedEventSinceRelist holds the information whether any of the events
116 // were already removed from the `cache` cyclic buffer since the last relist
117 removedEventSinceRelist bool
118
119 // store will effectively support LIST operation from the "end of cache
120 // history" i.e. from the moment just after the newest cached watched event.
121 // It is necessary to effectively allow clients to start watching at now.
122 // NOTE: We assume that <store> is thread-safe.
123 store storeIndexer
124
125 // ResourceVersion up to which the watchCache is propagated.
126 resourceVersion uint64
127
128 // ResourceVersion of the last list result (populated via Replace() method).
129 listResourceVersion uint64
130
131 // This handler is run at the end of every successful Replace() method.
132 onReplace func()
133
134 // This handler is run at the end of every Add/Update/Delete method
135 // and additionally gets the previous value of the object.
136 eventHandler func(*watchCacheEvent)
137
138 // for testing timeouts.
139 clock clock.Clock
140
141 // eventFreshDuration defines the minimum watch history watchcache will store.
142 eventFreshDuration time.Duration
143
144 // An underlying storage.Versioner.
145 versioner storage.Versioner
146
147 // cacher's group resource
148 groupResource schema.GroupResource
149
150 // For testing cache interval invalidation.
151 indexValidator indexValidator
152
153 // Requests progress notification if there are requests waiting for watch
154 // to be fresh
155 waitingUntilFresh *progress.ConditionalProgressRequester
156
157 // Stores previous snapshots of orderedLister to allow serving requests from previous revisions.
158 snapshots Snapshotter
159 }
160
161 func newWatchCache(
162 keyFunc func(runtime.Object) (string, error),
163 eventHandler func(*watchCacheEvent),
164 getAttrsFunc func(runtime.Object) (labels.Set, fields.Set, error),
165 versioner storage.Versioner,
166 indexers *cache.Indexers,
167 clock clock.WithTicker,
168 eventFreshDuration time.Duration,
169 groupResource schema.GroupResource,
170 progressRequester *progress.ConditionalProgressRequester) *watchCache {
171 wc := &watchCache{
172 capacity: defaultLowerBoundCapacity,
173 keyFunc: keyFunc,
174 getAttrsFunc: getAttrsFunc,
175 cache: make([]*watchCacheEvent, defaultLowerBoundCapacity),
176 lowerBoundCapacity: defaultLowerBoundCapacity,
177 upperBoundCapacity: capacityUpperBound(eventFreshDuration),
178 startIndex: 0,
179 endIndex: 0,
180 store: newStoreIndexer(indexers),
181 resourceVersion: 0,
182 listResourceVersion: 0,
183 eventHandler: eventHandler,
184 clock: clock,
185 eventFreshDuration: eventFreshDuration,
186 versioner: versioner,
187 groupResource: groupResource,
188 waitingUntilFresh: progressRequester,
189 }
190 if utilfeature.DefaultFeatureGate.Enabled(features.ListFromCacheSnapshot) {
191 wc.snapshots = newStoreSnapshotter()
192 }
193 metrics.WatchCacheCapacity.WithLabelValues(groupResource.String()).Set(float64(wc.capacity))
194 wc.cond = sync.NewCond(wc.RLocker())
195 wc.indexValidator = wc.isIndexValidLocked
196
197 return wc
198 }
199
200 // capacityUpperBound denotes the maximum possible capacity of the watch cache
201 // to which it can resize.
202 func capacityUpperBound(eventFreshDuration time.Duration) int {
203 if eventFreshDuration <= DefaultEventFreshDuration {
204 return defaultUpperBoundCapacity
205 }
206 // eventFreshDuration determines how long the watch events are supposed
207 // to be stored in the watch cache.
208 // In very high churn situations, there is a need to store more events
209 // in the watch cache, hence it would have to be upsized accordingly.
210 // Because of that, for larger values of eventFreshDuration, we set the
211 // upper bound of the watch cache's capacity proportionally to the ratio
212 // between eventFreshDuration and DefaultEventFreshDuration.
213 // Given that the watch cache size can only double, we round up that
214 // proportion to the next power of two.
215 exponent := int(math.Ceil((math.Log2(eventFreshDuration.Seconds() / DefaultEventFreshDuration.Seconds()))))
216 if maxExponent := int(math.Floor((math.Log2(math.MaxInt32 / defaultUpperBoundCapacity)))); exponent > maxExponent {
217 // Making sure that the capacity's upper bound fits in a 32-bit integer.
218 exponent = maxExponent
219 klog.Warningf("Capping watch cache capacity upper bound to %v", defaultUpperBoundCapacity<<exponent)
220 }
221 return defaultUpperBoundCapacity << exponent
222 }
223
224 // Add takes runtime.Object as an argument.
225 func (w *watchCache) Add(obj interface{}) error {
226 object, resourceVersion, err := w.objectToVersionedRuntimeObject(obj)
227 if err != nil {
228 return err
229 }
230 event := watch.Event{Type: watch.Added, Object: object}
231
232 f := func(elem *storeElement) error { return w.store.Add(elem) }
233 return w.processEvent(event, resourceVersion, f)
234 }
235
236 // Update takes runtime.Object as an argument.
237 func (w *watchCache) Update(obj interface{}) error {
238 object, resourceVersion, err := w.objectToVersionedRuntimeObject(obj)
239 if err != nil {
240 return err
241 }
242 event := watch.Event{Type: watch.Modified, Object: object}
243
244 f := func(elem *storeElement) error { return w.store.Update(elem) }
245 return w.processEvent(event, resourceVersion, f)
246 }
247
248 // Delete takes runtime.Object as an argument.
249 func (w *watchCache) Delete(obj interface{}) error {
250 object, resourceVersion, err := w.objectToVersionedRuntimeObject(obj)
251 if err != nil {
252 return err
253 }
254 event := watch.Event{Type: watch.Deleted, Object: object}
255
256 f := func(elem *storeElement) error { return w.store.Delete(elem) }
257 return w.processEvent(event, resourceVersion, f)
258 }
259
260 func (w *watchCache) objectToVersionedRuntimeObject(obj interface{}) (runtime.Object, uint64, error) {
261 object, ok := obj.(runtime.Object)
262 if !ok {
263 return nil, 0, fmt.Errorf("obj does not implement runtime.Object interface: %v", obj)
264 }
265 resourceVersion, err := w.versioner.ObjectResourceVersion(object)
266 if err != nil {
267 return nil, 0, err
268 }
269 return object, resourceVersion, nil
270 }
271
272 // processEvent is safe as long as there is at most one call to it in flight
273 // at any point in time.
274 func (w *watchCache) processEvent(event watch.Event, resourceVersion uint64, updateFunc func(*storeElement) error) error {
275 metrics.EventsReceivedCounter.WithLabelValues(w.groupResource.String()).Inc()
276
277 key, err := w.keyFunc(event.Object)
278 if err != nil {
279 return fmt.Errorf("couldn't compute key: %v", err)
280 }
281 elem := &storeElement{Key: key, Object: event.Object}
282 elem.Labels, elem.Fields, err = w.getAttrsFunc(event.Object)
283 if err != nil {
284 return err
285 }
286
287 wcEvent := &watchCacheEvent{
288 Type: event.Type,
289 Object: elem.Object,
290 ObjLabels: elem.Labels,
291 ObjFields: elem.Fields,
292 Key: key,
293 ResourceVersion: resourceVersion,
294 RecordTime: w.clock.Now(),
295 }
296
297 // We can call w.store.Get() outside of a critical section,
298 // because the w.store itself is thread-safe and the only
299 // place where w.store is modified is below (via updateFunc)
300 // and these calls are serialized because reflector is processing
301 // events one-by-one.
302 previous, exists, err := w.store.Get(elem)
303 if err != nil {
304 return err
305 }
306 if exists {
307 previousElem := previous.(*storeElement)
308 wcEvent.PrevObject = previousElem.Object
309 wcEvent.PrevObjLabels = previousElem.Labels
310 wcEvent.PrevObjFields = previousElem.Fields
311 }
312
313 if err := func() error {
314 w.Lock()
315 defer w.Unlock()
316
317 w.updateCache(wcEvent)
318 w.resourceVersion = resourceVersion
319 defer w.cond.Broadcast()
320
321 err := updateFunc(elem)
322 if err != nil {
323 return err
324 }
325 if w.snapshots != nil {
326 if orderedLister, ordered := w.store.(orderedLister); ordered {
327 if w.isCacheFullLocked() {
328 oldestRV := w.cache[w.startIndex%w.capacity].ResourceVersion
329 w.snapshots.RemoveLess(oldestRV)
330 }
331 w.snapshots.Add(w.resourceVersion, orderedLister)
332 }
333 }
334 return err
335 }(); err != nil {
336 return err
337 }
338
339 // Avoid calling event handler under lock.
340 // This is safe as long as there is at most one call to Add/Update/Delete and
341 // UpdateResourceVersion in flight at any point in time, which is true now,
342 // because reflector calls them synchronously from its main thread.
343 if w.eventHandler != nil {
344 w.eventHandler(wcEvent)
345 }
346 metrics.RecordResourceVersion(w.groupResource.String(), resourceVersion)
347 return nil
348 }
349
350 // Assumes that lock is already held for write.
351 func (w *watchCache) updateCache(event *watchCacheEvent) {
352 w.resizeCacheLocked(event.RecordTime)
353 if w.isCacheFullLocked() {
354 // Cache is full - remove the oldest element.
355 w.startIndex++
356 w.removedEventSinceRelist = true
357 }
358 w.cache[w.endIndex%w.capacity] = event
359 w.endIndex++
360 }
361
362 // resizeCacheLocked resizes the cache if necessary:
363 // - increases capacity by 2x if cache is full and all cached events occurred within last eventFreshDuration.
364 // - decreases capacity by 2x when recent quarter of events occurred outside of eventFreshDuration(protect watchCache from flapping).
365 func (w *watchCache) resizeCacheLocked(eventTime time.Time) {
366 if w.isCacheFullLocked() && eventTime.Sub(w.cache[w.startIndex%w.capacity].RecordTime) < w.eventFreshDuration {
367 capacity := min(w.capacity*2, w.upperBoundCapacity)
368 if capacity > w.capacity {
369 w.doCacheResizeLocked(capacity)
370 }
371 return
372 }
373 if w.isCacheFullLocked() && eventTime.Sub(w.cache[(w.endIndex-w.capacity/4)%w.capacity].RecordTime) > w.eventFreshDuration {
374 capacity := max(w.capacity/2, w.lowerBoundCapacity)
375 if capacity < w.capacity {
376 w.doCacheResizeLocked(capacity)
377 }
378 return
379 }
380 }
381
382 // isCacheFullLocked used to judge whether watchCacheEvent is full.
383 // Assumes that lock is already held for write.
384 func (w *watchCache) isCacheFullLocked() bool {
385 return w.endIndex == w.startIndex+w.capacity
386 }
387
388 // doCacheResizeLocked resize watchCache's event array with different capacity.
389 // Assumes that lock is already held for write.
390 func (w *watchCache) doCacheResizeLocked(capacity int) {
391 newCache := make([]*watchCacheEvent, capacity)
392 if capacity < w.capacity {
393 // adjust startIndex if cache capacity shrink.
394 w.startIndex = w.endIndex - capacity
395 }
396 for i := w.startIndex; i < w.endIndex; i++ {
397 newCache[i%capacity] = w.cache[i%w.capacity]
398 }
399 w.cache = newCache
400 metrics.RecordsWatchCacheCapacityChange(w.groupResource.String(), w.capacity, capacity)
401 w.capacity = capacity
402 }
403
404 func (w *watchCache) UpdateResourceVersion(resourceVersion string) {
405 rv, err := w.versioner.ParseResourceVersion(resourceVersion)
406 if err != nil {
407 klog.Errorf("Couldn't parse resourceVersion: %v", err)
408 return
409 }
410
411 func() {
412 w.Lock()
413 defer w.Unlock()
414 w.resourceVersion = rv
415 w.cond.Broadcast()
416 }()
417
418 // Avoid calling event handler under lock.
419 // This is safe as long as there is at most one call to Add/Update/Delete and
420 // UpdateResourceVersion in flight at any point in time, which is true now,
421 // because reflector calls them synchronously from its main thread.
422 if w.eventHandler != nil {
423 wcEvent := &watchCacheEvent{
424 Type: watch.Bookmark,
425 ResourceVersion: rv,
426 }
427 w.eventHandler(wcEvent)
428 }
429 metrics.RecordResourceVersion(w.groupResource.String(), rv)
430 }
431
432 // List returns list of pointers to <storeElement> objects.
433 func (w *watchCache) List() []interface{} {
434 return w.store.List()
435 }
436
437 // waitUntilFreshAndBlock waits until cache is at least as fresh as given <resourceVersion>.
438 // NOTE: This function acquired lock and doesn't release it.
439 // You HAVE TO explicitly call w.RUnlock() after this function.
440 func (w *watchCache) waitUntilFreshAndBlock(ctx context.Context, resourceVersion uint64) error {
441 startTime := w.clock.Now()
442 defer func() {
443 if resourceVersion > 0 {
444 metrics.WatchCacheReadWait.WithContext(ctx).WithLabelValues(w.groupResource.String()).Observe(w.clock.Since(startTime).Seconds())
445 }
446 }()
447
448 // In case resourceVersion is 0, we accept arbitrarily stale result.
449 // As a result, the condition in the below for loop will never be
450 // satisfied (w.resourceVersion is never negative), this call will
451 // never hit the w.cond.Wait().
452 // As a result - we can optimize the code by not firing the wakeup
453 // function (and avoid starting a gorotuine), especially given that
454 // resourceVersion=0 is the most common case.
455 if resourceVersion > 0 {
456 go func() {
457 // Wake us up when the time limit has expired. The docs
458 // promise that time.After (well, NewTimer, which it calls)
459 // will wait *at least* the duration given. Since this go
460 // routine starts sometime after we record the start time, and
461 // it will wake up the loop below sometime after the broadcast,
462 // we don't need to worry about waking it up before the time
463 // has expired accidentally.
464 <-w.clock.After(blockTimeout)
465 w.cond.Broadcast()
466 }()
467 }
468
469 w.RLock()
470 span := tracing.SpanFromContext(ctx)
471 span.AddEvent("watchCache locked acquired")
472 for w.resourceVersion < resourceVersion {
473 if w.clock.Since(startTime) >= blockTimeout {
474 // Request that the client retry after 'resourceVersionTooHighRetrySeconds' seconds.
475 return storage.NewTooLargeResourceVersionError(resourceVersion, w.resourceVersion, resourceVersionTooHighRetrySeconds)
476 }
477 w.cond.Wait()
478 }
479 span.AddEvent("watchCache fresh enough")
480 return nil
481 }
482
483 type sortableStoreElements []interface{}
484
485 func (s sortableStoreElements) Len() int {
486 return len(s)
487 }
488
489 func (s sortableStoreElements) Less(i, j int) bool {
490 return s[i].(*storeElement).Key < s[j].(*storeElement).Key
491 }
492
493 func (s sortableStoreElements) Swap(i, j int) {
494 s[i], s[j] = s[j], s[i]
495 }
496
497 // WaitUntilFreshAndList returns list of pointers to `storeElement` objects along
498 // with their ResourceVersion and the name of the index, if any, that was used.
499 func (w *watchCache) WaitUntilFreshAndList(ctx context.Context, resourceVersion uint64, key string, opts storage.ListOptions) (resp listResp, index string, err error) {
500 if delegator.ConsistentReadSupported() && w.notFresh(resourceVersion) {
501 w.waitingUntilFresh.Add()
502 err = w.waitUntilFreshAndBlock(ctx, resourceVersion)
503 w.waitingUntilFresh.Remove()
504 } else {
505 err = w.waitUntilFreshAndBlock(ctx, resourceVersion)
506 }
507
508 defer w.RUnlock()
509 if err != nil {
510 return listResp{}, "", err
511 }
512 return w.list(ctx, resourceVersion, key, opts)
513 }
514
515 // NOTICE: Structure follows the shouldDelegateList function in
516 // staging/src/k8s.io/apiserver/pkg/storage/cacher/delegator.go
517 func (w *watchCache) list(ctx context.Context, resourceVersion uint64, key string, opts storage.ListOptions) (resp listResp, index string, err error) {
518 switch opts.ResourceVersionMatch {
519 case metav1.ResourceVersionMatchExact:
520 return w.listExactRV(key, "", resourceVersion)
521 case metav1.ResourceVersionMatchNotOlderThan:
522 case "":
523 // Continue
524 if len(opts.Predicate.Continue) > 0 {
525 continueKey, continueRV, err := storage.DecodeContinue(opts.Predicate.Continue, key)
526 if err != nil {
527 return listResp{}, "", errors.NewBadRequest(fmt.Sprintf("invalid continue token: %v", err))
528 }
529 if continueRV > 0 {
530 return w.listExactRV(key, continueKey, uint64(continueRV))
531 } else {
532 // Continue with negative RV is a consistent read - already handled via waitUntilFreshAndBlock.
533 // Don't pass matchValues as they don't support continueKey
534 return w.listLatestRV(key, continueKey, nil)
535 }
536 }
537 // Legacy exact match
538 if opts.Predicate.Limit > 0 && len(opts.ResourceVersion) > 0 && opts.ResourceVersion != "0" {
539 return w.listExactRV(key, "", resourceVersion)
540 }
541 // Consistent Read - already handled via waitUntilFreshAndBlock
542 }
543 return w.listLatestRV(key, "", opts.Predicate.MatcherIndex(ctx))
544 }
545
546 func (w *watchCache) listExactRV(key, continueKey string, resourceVersion uint64) (resp listResp, index string, err error) {
547 if w.snapshots == nil {
548 return listResp{}, "", errors.NewResourceExpired(fmt.Sprintf("too old resource version: %d", resourceVersion))
549 }
550 store, ok := w.snapshots.GetLessOrEqual(resourceVersion)
551 if !ok {
552 return listResp{}, "", errors.NewResourceExpired(fmt.Sprintf("too old resource version: %d", resourceVersion))
553 }
554 items := store.ListPrefix(key, continueKey)
555 return listResp{
556 Items: items,
557 ResourceVersion: resourceVersion,
558 }, "", nil
559 }
560
561 func (w *watchCache) listLatestRV(key, continueKey string, matchValues []storage.MatchValue) (resp listResp, index string, err error) {
562 // This isn't the place where we do "final filtering" - only some "prefiltering" is happening here. So the only
563 // requirement here is to NOT miss anything that should be returned. We can return as many non-matching items as we
564 // want - they will be filtered out later. The fact that we return less things is only further performance improvement.
565 // TODO: if multiple indexes match, return the one with the fewest items, so as to do as much filtering as possible.
566 for _, matchValue := range matchValues {
567 if result, err := w.store.ByIndex(matchValue.IndexName, matchValue.Value); err == nil {
568 result, err = filterPrefixAndOrder(key, result)
569 return listResp{
570 Items: result,
571 ResourceVersion: w.resourceVersion,
572 }, matchValue.IndexName, err
573 }
574 }
575 if store, ok := w.store.(orderedLister); ok {
576 result := store.ListPrefix(key, continueKey)
577 return listResp{
578 Items: result,
579 ResourceVersion: w.resourceVersion,
580 }, "", nil
581 }
582 result := w.store.List()
583 result, err = filterPrefixAndOrder(key, result)
584 return listResp{
585 Items: result,
586 ResourceVersion: w.resourceVersion,
587 }, "", err
588 }
589
590 func filterPrefixAndOrder(prefix string, items []interface{}) ([]interface{}, error) {
591 var result []interface{}
592 for _, item := range items {
593 elem, ok := item.(*storeElement)
594 if !ok {
595 return nil, fmt.Errorf("non *storeElement returned from storage: %v", item)
596 }
597 if !hasPathPrefix(elem.Key, prefix) {
598 continue
599 }
600 result = append(result, item)
601 }
602 sort.Sort(sortableStoreElements(result))
603 return result, nil
604 }
605
606 func (w *watchCache) notFresh(resourceVersion uint64) bool {
607 w.RLock()
608 defer w.RUnlock()
609 return resourceVersion > w.resourceVersion
610 }
611
612 // WaitUntilFreshAndGet returns a pointers to <storeElement> object.
613 func (w *watchCache) WaitUntilFreshAndGet(ctx context.Context, resourceVersion uint64, key string) (interface{}, bool, uint64, error) {
614 var err error
615 if delegator.ConsistentReadSupported() && w.notFresh(resourceVersion) {
616 w.waitingUntilFresh.Add()
617 err = w.waitUntilFreshAndBlock(ctx, resourceVersion)
618 w.waitingUntilFresh.Remove()
619 } else {
620 err = w.waitUntilFreshAndBlock(ctx, resourceVersion)
621 }
622 defer w.RUnlock()
623 if err != nil {
624 return nil, false, 0, err
625 }
626 value, exists, err := w.store.GetByKey(key)
627 return value, exists, w.resourceVersion, err
628 }
629
630 func (w *watchCache) ListKeys() []string {
631 return w.store.ListKeys()
632 }
633
634 // Get takes runtime.Object as a parameter. However, it returns
635 // pointer to <storeElement>.
636 func (w *watchCache) Get(obj interface{}) (interface{}, bool, error) {
637 object, ok := obj.(runtime.Object)
638 if !ok {
639 return nil, false, fmt.Errorf("obj does not implement runtime.Object interface: %v", obj)
640 }
641 key, err := w.keyFunc(object)
642 if err != nil {
643 return nil, false, fmt.Errorf("couldn't compute key: %v", err)
644 }
645
646 return w.store.Get(&storeElement{Key: key, Object: object})
647 }
648
649 // GetByKey returns pointer to <storeElement>.
650 func (w *watchCache) GetByKey(key string) (interface{}, bool, error) {
651 return w.store.GetByKey(key)
652 }
653
654 // Replace takes slice of runtime.Object as a parameter.
655 func (w *watchCache) Replace(objs []interface{}, resourceVersion string) error {
656 version, err := w.versioner.ParseResourceVersion(resourceVersion)
657 if err != nil {
658 return err
659 }
660
661 toReplace := make([]interface{}, 0, len(objs))
662 for _, obj := range objs {
663 object, ok := obj.(runtime.Object)
664 if !ok {
665 return fmt.Errorf("didn't get runtime.Object for replace: %#v", obj)
666 }
667 key, err := w.keyFunc(object)
668 if err != nil {
669 return fmt.Errorf("couldn't compute key: %v", err)
670 }
671 objLabels, objFields, err := w.getAttrsFunc(object)
672 if err != nil {
673 return err
674 }
675 toReplace = append(toReplace, &storeElement{
676 Key: key,
677 Object: object,
678 Labels: objLabels,
679 Fields: objFields,
680 })
681 }
682
683 w.Lock()
684 defer w.Unlock()
685
686 // Ensure startIndex never decreases, so that existing watchCacheInterval
687 // instances get "invalid" errors if the try to download from the buffer
688 // using their own start/end indexes calculated from previous buffer
689 // content.
690
691 // Empty the cyclic buffer, ensuring startIndex doesn't decrease.
692 w.startIndex = w.endIndex
693 w.removedEventSinceRelist = false
694
695 if err := w.store.Replace(toReplace, resourceVersion); err != nil {
696 return err
697 }
698 if w.snapshots != nil {
699 w.snapshots.Reset()
700 if orderedLister, ordered := w.store.(orderedLister); ordered {
701 w.snapshots.Add(version, orderedLister)
702 }
703 }
704 w.listResourceVersion = version
705 w.resourceVersion = version
706 if w.onReplace != nil {
707 w.onReplace()
708 }
709 w.cond.Broadcast()
710
711 metrics.RecordResourceVersion(w.groupResource.String(), version)
712 klog.V(3).Infof("Replaced watchCache (rev: %v) ", resourceVersion)
713 return nil
714 }
715
716 func (w *watchCache) SetOnReplace(onReplace func()) {
717 w.Lock()
718 defer w.Unlock()
719 w.onReplace = onReplace
720 }
721
722 func (w *watchCache) Resync() error {
723 // Nothing to do
724 return nil
725 }
726
727 func (w *watchCache) getListResourceVersion() uint64 {
728 w.RLock()
729 defer w.RUnlock()
730 return w.listResourceVersion
731 }
732
733 func (w *watchCache) currentCapacity() int {
734 w.RLock()
735 defer w.RUnlock()
736 return w.capacity
737 }
738
739 const (
740 // minWatchChanSize is the min size of channels used by the watch.
741 // We keep that set to 10 for "backward compatibility" until we
742 // convince ourselves based on some metrics that decreasing is safe.
743 minWatchChanSize = 10
744 // maxWatchChanSizeWithIndexAndTriger is the max size of the channel
745 // used by the watch using the index and trigger selector.
746 maxWatchChanSizeWithIndexAndTrigger = 10
747 // maxWatchChanSizeWithIndexWithoutTrigger is the max size of the channel
748 // used by the watch using the index but without triggering selector.
749 // We keep that set to 1000 for "backward compatibility", until we
750 // convinced ourselves based on some metrics that decreasing is safe.
751 maxWatchChanSizeWithIndexWithoutTrigger = 1000
752 // maxWatchChanSizeWithoutIndex is the max size of the channel
753 // used by the watch not using the index.
754 // TODO(wojtek-t): Figure out if the value shouldn't be higher.
755 maxWatchChanSizeWithoutIndex = 100
756 )
757
758 func (w *watchCache) suggestedWatchChannelSize(indexExists, triggerUsed bool) int {
759 // To estimate the channel size we use a heuristic that a channel
760 // should roughly be able to keep one second of history.
761 // We don't have an exact data, but given we store updates from
762 // the last <eventFreshDuration>, we approach it by dividing the
763 // capacity by the length of the history window.
764 chanSize := int(math.Ceil(float64(w.currentCapacity()) / w.eventFreshDuration.Seconds()))
765
766 // Finally we adjust the size to avoid ending with too low or
767 // to large values.
768 if chanSize < minWatchChanSize {
769 chanSize = minWatchChanSize
770 }
771 var maxChanSize int
772 switch {
773 case indexExists && triggerUsed:
774 maxChanSize = maxWatchChanSizeWithIndexAndTrigger
775 case indexExists && !triggerUsed:
776 maxChanSize = maxWatchChanSizeWithIndexWithoutTrigger
777 case !indexExists:
778 maxChanSize = maxWatchChanSizeWithoutIndex
779 }
780 if chanSize > maxChanSize {
781 chanSize = maxChanSize
782 }
783 return chanSize
784 }
785
786 // isIndexValidLocked checks if a given index is still valid.
787 // This assumes that the lock is held.
788 func (w *watchCache) isIndexValidLocked(index int) bool {
789 return index >= w.startIndex
790 }
791
792 // getAllEventsSinceLocked returns a watchCacheInterval that can be used to
793 // retrieve events since a certain resourceVersion. This function assumes to
794 // be called under the watchCache lock.
795 func (w *watchCache) getAllEventsSinceLocked(resourceVersion uint64, key string, opts storage.ListOptions) (*watchCacheInterval, error) {
796 _, matchesSingle := opts.Predicate.MatchesSingle()
797 matchesSingle = matchesSingle && !opts.Recursive
798 if opts.SendInitialEvents != nil && *opts.SendInitialEvents {
799 return w.getIntervalFromStoreLocked(key, matchesSingle)
800 }
801
802 size := w.endIndex - w.startIndex
803 var oldest uint64
804 switch {
805 case w.listResourceVersion > 0 && !w.removedEventSinceRelist:
806 // If no event was removed from the buffer since last relist, the oldest watch
807 // event we can deliver is one greater than the resource version of the list.
808 oldest = w.listResourceVersion + 1
809 case size > 0:
810 // If the previous condition is not satisfied: either some event was already
811 // removed from the buffer or we've never completed a list (the latter can
812 // only happen in unit tests that populate the buffer without performing
813 // list/replace operations), the oldest watch event we can deliver is the first
814 // one in the buffer.
815 oldest = w.cache[w.startIndex%w.capacity].ResourceVersion
816 default:
817 return nil, fmt.Errorf("watch cache isn't correctly initialized")
818 }
819
820 if resourceVersion == 0 {
821 if opts.SendInitialEvents == nil {
822 // resourceVersion = 0 means that we don't require any specific starting point
823 // and we would like to start watching from ~now.
824 // However, to keep backward compatibility, we additionally need to return the
825 // current state and only then start watching from that point.
826 //
827 // TODO: In v2 api, we should stop returning the current state - #13969.
828 return w.getIntervalFromStoreLocked(key, matchesSingle)
829 }
830 // SendInitialEvents = false and resourceVersion = 0
831 // means that the request would like to start watching
832 // from Any resourceVersion
833 resourceVersion = w.resourceVersion
834 }
835 if resourceVersion < oldest-1 {
836 return nil, errors.NewResourceExpired(fmt.Sprintf("too old resource version: %d (%d)", resourceVersion, oldest-1))
837 }
838
839 // Binary search the smallest index at which resourceVersion is greater than the given one.
840 f := func(i int) bool {
841 return w.cache[(w.startIndex+i)%w.capacity].ResourceVersion > resourceVersion
842 }
843 first := sort.Search(size, f)
844 indexerFunc := func(i int) *watchCacheEvent {
845 return w.cache[i%w.capacity]
846 }
847 ci := newCacheInterval(w.startIndex+first, w.endIndex, indexerFunc, w.indexValidator, resourceVersion, w.RWMutex.RLocker())
848 return ci, nil
849 }
850
851 // getIntervalFromStoreLocked returns a watchCacheInterval
852 // that covers the entire storage state.
853 // This function assumes to be called under the watchCache lock.
854 func (w *watchCache) getIntervalFromStoreLocked(key string, matchesSingle bool) (*watchCacheInterval, error) {
855 ci, err := newCacheIntervalFromStore(w.resourceVersion, w.store, key, matchesSingle)
856 if err != nil {
857 return nil, err
858 }
859 return ci, nil
860 }