Debian Codegraph @

pkg/storage/cacher/watch_cache_interval.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 cacher
18
19 import (
20 "fmt"
21 "sort"
22 "sync"
23
24 "k8s.io/apimachinery/pkg/watch"
25 )
26
27 // watchCacheInterval serves as an abstraction over a source
28 // of watchCacheEvents. It maintains a window of events over
29 // an underlying source and these events can be served using
30 // the exposed Next() API. The main intent for doing things
31 // this way is to introduce an upper bound of memory usage
32 // for starting a watch and reduce the maximum possible time
33 // interval for which the lock would be held while events are
34 // copied over.
35 //
36 // The source of events for the interval is typically either
37 // the watchCache circular buffer, if events being retrieved
38 // need to be for resource versions > 0 or the underlying
39 // implementation of Store, if resource version = 0.
40 //
41 // Furthermore, an interval can be either valid or invalid at
42 // any given point of time. The notion of validity makes sense
43 // only in cases where the window of events in the underlying
44 // source can change over time - i.e. for watchCache circular
45 // buffer. When the circular buffer is full and an event needs
46 // to be popped off, watchCache::startIndex is incremented. In
47 // this case, an interval tracking that popped event is valid
48 // only if it has already been copied to its internal buffer.
49 // However, for efficiency we perform that lazily and we mark
50 // an interval as invalid iff we need to copy events from the
51 // watchCache and we end up needing events that have already
52 // been popped off. This translates to the following condition:
53 //
54 // watchCacheInterval::startIndex >= watchCache::startIndex.
55 //
56 // When this condition becomes false, the interval is no longer
57 // valid and should not be used to retrieve and serve elements
58 // from the underlying source.
59 type watchCacheInterval struct {
60 // startIndex denotes the starting point of the interval
61 // being considered. The value is the index in the actual
62 // source of watchCacheEvents. If the source of events is
63 // the watchCache, then this must be used modulo capacity.
64 startIndex int
65
66 // endIndex denotes the ending point of the interval being
67 // considered. The value is the index in the actual source
68 // of events. If the source of the events is the watchCache,
69 // then this should be used modulo capacity.
70 endIndex int
71
72 // indexer is meant to inject behaviour for how an event must
73 // be retrieved from the underlying source given an index.
74 indexer indexerFunc
75
76 // indexValidator is used to check if a given index is still
77 // valid perspective. If it is deemed that the index is not
78 // valid, then this interval can no longer be used to serve
79 // events. Use of indexValidator is warranted only in cases
80 // where the window of events in the underlying source can
81 // change over time. Furthermore, an interval is invalid if
82 // its startIndex no longer coincides with the startIndex of
83 // underlying source.
84 indexValidator indexValidator
85
86 // buffer holds watchCacheEvents that this interval returns on
87 // a call to Next(). This exists mainly to reduce acquiring the
88 // lock on each invocation of Next().
89 buffer *watchCacheIntervalBuffer
90
91 // resourceVersion is the resourceVersion from which
92 // the interval was constructed.
93 resourceVersion uint64
94
95 // lock effectively protects access to the underlying source
96 // of events through - indexer and indexValidator.
97 //
98 // Given that indexer and indexValidator only read state, if
99 // possible, Locker obtained through RLocker() is provided.
100 lock sync.Locker
101
102 // initialEventsEndBookmark will be sent after sending all events in cacheInterval
103 initialEventsEndBookmark *watchCacheEvent
104 }
105
106 type indexerFunc func(int) *watchCacheEvent
107 type indexValidator func(int) bool
108
109 func newCacheInterval(startIndex, endIndex int, indexer indexerFunc, indexValidator indexValidator, resourceVersion uint64, locker sync.Locker) *watchCacheInterval {
110 return &watchCacheInterval{
111 startIndex: startIndex,
112 endIndex: endIndex,
113 indexer: indexer,
114 indexValidator: indexValidator,
115 buffer: &watchCacheIntervalBuffer{buffer: make([]*watchCacheEvent, bufferSize)},
116 resourceVersion: resourceVersion,
117 lock: locker,
118 }
119 }
120
121 type sortableWatchCacheEvents []*watchCacheEvent
122
123 func (s sortableWatchCacheEvents) Len() int {
124 return len(s)
125 }
126
127 func (s sortableWatchCacheEvents) Less(i, j int) bool {
128 return s[i].Key < s[j].Key
129 }
130
131 func (s sortableWatchCacheEvents) Swap(i, j int) {
132 s[i], s[j] = s[j], s[i]
133 }
134
135 // newCacheIntervalFromStore is meant to handle the case of rv=0, such that the events
136 // returned by Next() need to be events from a List() done on the underlying store of
137 // the watch cache.
138 // The items returned in the interval will be sorted by Key.
139 func newCacheIntervalFromStore(resourceVersion uint64, store storeIndexer, key string, matchesSingle bool) (*watchCacheInterval, error) {
140 buffer := &watchCacheIntervalBuffer{}
141 var allItems []interface{}
142 if matchesSingle {
143 item, exists, err := store.GetByKey(key)
144 if err != nil {
145 return nil, err
146 }
147
148 if exists {
149 allItems = append(allItems, item)
150 }
151 } else {
152 allItems = store.List()
153 }
154 buffer.buffer = make([]*watchCacheEvent, len(allItems))
155 for i, item := range allItems {
156 elem, ok := item.(*storeElement)
157 if !ok {
158 return nil, fmt.Errorf("not a storeElement: %v", elem)
159 }
160 buffer.buffer[i] = &watchCacheEvent{
161 Type: watch.Added,
162 Object: elem.Object,
163 ObjLabels: elem.Labels,
164 ObjFields: elem.Fields,
165 Key: elem.Key,
166 ResourceVersion: resourceVersion,
167 }
168 buffer.endIndex++
169 }
170 sort.Sort(sortableWatchCacheEvents(buffer.buffer))
171 ci := &watchCacheInterval{
172 startIndex: 0,
173 // Simulate that we already have all the events we're looking for.
174 endIndex: 0,
175 buffer: buffer,
176 resourceVersion: resourceVersion,
177 }
178
179 return ci, nil
180 }
181
182 // Next returns the next item in the cache interval provided the cache
183 // interval is still valid. An error is returned if the interval is
184 // invalidated.
185 func (wci *watchCacheInterval) Next() (*watchCacheEvent, error) {
186 // if there are items in the buffer to return, return from
187 // the buffer.
188 if event, exists := wci.buffer.next(); exists {
189 return event, nil
190 }
191 // check if there are still other events in this interval
192 // that can be processed.
193 if wci.startIndex >= wci.endIndex {
194 return nil, nil
195 }
196 wci.lock.Lock()
197 defer wci.lock.Unlock()
198
199 if valid := wci.indexValidator(wci.startIndex); !valid {
200 return nil, fmt.Errorf("cache interval invalidated, interval startIndex: %d", wci.startIndex)
201 }
202
203 wci.fillBuffer()
204 if event, exists := wci.buffer.next(); exists {
205 return event, nil
206 }
207 return nil, nil
208 }
209
210 func (wci *watchCacheInterval) fillBuffer() {
211 wci.buffer.startIndex = 0
212 wci.buffer.endIndex = 0
213 for wci.startIndex < wci.endIndex && !wci.buffer.isFull() {
214 event := wci.indexer(wci.startIndex)
215 if event == nil {
216 break
217 }
218 wci.buffer.buffer[wci.buffer.endIndex] = event
219 wci.buffer.endIndex++
220 wci.startIndex++
221 }
222 }
223
224 const bufferSize = 100
225
226 // watchCacheIntervalBuffer is used to reduce acquiring
227 // the lock on each invocation of watchCacheInterval.Next().
228 type watchCacheIntervalBuffer struct {
229 // buffer is used to hold watchCacheEvents that
230 // the interval returns on a call to Next().
231 buffer []*watchCacheEvent
232 // The first element of buffer is defined by startIndex,
233 // its last element is defined by endIndex.
234 startIndex int
235 endIndex int
236 }
237
238 // next returns the next event present in the interval buffer provided
239 // it is not empty.
240 func (wcib *watchCacheIntervalBuffer) next() (*watchCacheEvent, bool) {
241 if wcib.isEmpty() {
242 return nil, false
243 }
244 next := wcib.buffer[wcib.startIndex]
245 wcib.startIndex++
246 return next, true
247 }
248
249 func (wcib *watchCacheIntervalBuffer) isFull() bool {
250 return wcib.endIndex >= bufferSize
251 }
252
253 func (wcib *watchCacheIntervalBuffer) isEmpty() bool {
254 return wcib.startIndex == wcib.endIndex
255 }