Debian Codegraph @

pkg/storage/cacher/store_btree.go

raw
1 /*
2 Copyright 2022 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 "strings"
22 "sync"
23
24 "github.com/google/btree"
25 "k8s.io/client-go/tools/cache"
26 )
27
28 // newThreadedBtreeStoreIndexer returns a storage for cacher by adding locking over the two 2 data structures:
29 // * btree based storage for efficient LIST operation on prefix
30 // * map based indexer for retrieving values by index.
31 // This separation is used to allow independent snapshotting those two storages in the future.
32 // Intention is to utilize btree for its cheap snapshots that don't require locking if don't mutate data.
33 func newThreadedBtreeStoreIndexer(indexers cache.Indexers, degree int) *threadedStoreIndexer {
34 return &threadedStoreIndexer{
35 store: newBtreeStore(degree),
36 indexer: newIndexer(indexers),
37 }
38 }
39
40 type threadedStoreIndexer struct {
41 lock sync.RWMutex
42 store btreeStore
43 indexer indexer
44 }
45
46 var _ orderedLister = (*threadedStoreIndexer)(nil)
47
48 func (si *threadedStoreIndexer) Count(prefix, continueKey string) (count int) {
49 si.lock.RLock()
50 defer si.lock.RUnlock()
51 return si.store.Count(prefix, continueKey)
52 }
53
54 func (si *threadedStoreIndexer) Clone() orderedLister {
55 si.lock.RLock()
56 defer si.lock.RUnlock()
57 return si.store.Clone()
58 }
59
60 func (si *threadedStoreIndexer) Add(obj interface{}) error {
61 return si.addOrUpdate(obj)
62 }
63
64 func (si *threadedStoreIndexer) Update(obj interface{}) error {
65 return si.addOrUpdate(obj)
66 }
67
68 func (si *threadedStoreIndexer) addOrUpdate(obj interface{}) error {
69 if obj == nil {
70 return fmt.Errorf("obj cannot be nil")
71 }
72 newElem, ok := obj.(*storeElement)
73 if !ok {
74 return fmt.Errorf("obj not a storeElement: %#v", obj)
75 }
76 si.lock.Lock()
77 defer si.lock.Unlock()
78 oldElem := si.store.addOrUpdateElem(newElem)
79 return si.indexer.updateElem(newElem.Key, oldElem, newElem)
80 }
81
82 func (si *threadedStoreIndexer) Delete(obj interface{}) error {
83 storeElem, ok := obj.(*storeElement)
84 if !ok {
85 return fmt.Errorf("obj not a storeElement: %#v", obj)
86 }
87 si.lock.Lock()
88 defer si.lock.Unlock()
89 oldObj, existed := si.store.deleteElem(storeElem)
90 if !existed {
91 return nil
92 }
93 return si.indexer.updateElem(storeElem.Key, oldObj, nil)
94 }
95
96 func (si *threadedStoreIndexer) List() []interface{} {
97 si.lock.RLock()
98 defer si.lock.RUnlock()
99 return si.store.List()
100 }
101
102 func (si *threadedStoreIndexer) ListPrefix(prefix, continueKey string) []interface{} {
103 si.lock.RLock()
104 defer si.lock.RUnlock()
105 return si.store.ListPrefix(prefix, continueKey)
106 }
107
108 func (si *threadedStoreIndexer) ListKeys() []string {
109 si.lock.RLock()
110 defer si.lock.RUnlock()
111 return si.store.ListKeys()
112 }
113
114 func (si *threadedStoreIndexer) Get(obj interface{}) (item interface{}, exists bool, err error) {
115 si.lock.RLock()
116 defer si.lock.RUnlock()
117 return si.store.Get(obj)
118 }
119
120 func (si *threadedStoreIndexer) GetByKey(key string) (item interface{}, exists bool, err error) {
121 si.lock.RLock()
122 defer si.lock.RUnlock()
123 return si.store.GetByKey(key)
124 }
125
126 func (si *threadedStoreIndexer) Replace(objs []interface{}, resourceVersion string) error {
127 si.lock.Lock()
128 defer si.lock.Unlock()
129 err := si.store.Replace(objs, resourceVersion)
130 if err != nil {
131 return err
132 }
133 return si.indexer.Replace(objs, resourceVersion)
134 }
135
136 func (si *threadedStoreIndexer) ByIndex(indexName, indexValue string) ([]interface{}, error) {
137 si.lock.RLock()
138 defer si.lock.RUnlock()
139 return si.indexer.ByIndex(indexName, indexValue)
140 }
141
142 func newBtreeStore(degree int) btreeStore {
143 return btreeStore{
144 tree: btree.NewG(degree, func(a, b *storeElement) bool {
145 return a.Key < b.Key
146 }),
147 }
148 }
149
150 type btreeStore struct {
151 tree *btree.BTreeG[*storeElement]
152 }
153
154 func (s *btreeStore) Clone() orderedLister {
155 return &btreeStore{
156 tree: s.tree.Clone(),
157 }
158 }
159
160 func (s *btreeStore) Add(obj interface{}) error {
161 if obj == nil {
162 return fmt.Errorf("obj cannot be nil")
163 }
164 storeElem, ok := obj.(*storeElement)
165 if !ok {
166 return fmt.Errorf("obj not a storeElement: %#v", obj)
167 }
168 s.addOrUpdateElem(storeElem)
169 return nil
170 }
171
172 func (s *btreeStore) Update(obj interface{}) error {
173 if obj == nil {
174 return fmt.Errorf("obj cannot be nil")
175 }
176 storeElem, ok := obj.(*storeElement)
177 if !ok {
178 return fmt.Errorf("obj not a storeElement: %#v", obj)
179 }
180 s.addOrUpdateElem(storeElem)
181 return nil
182 }
183
184 func (s *btreeStore) Delete(obj interface{}) error {
185 if obj == nil {
186 return fmt.Errorf("obj cannot be nil")
187 }
188 storeElem, ok := obj.(*storeElement)
189 if !ok {
190 return fmt.Errorf("obj not a storeElement: %#v", obj)
191 }
192 s.deleteElem(storeElem)
193 return nil
194 }
195
196 func (s *btreeStore) deleteElem(storeElem *storeElement) (*storeElement, bool) {
197 return s.tree.Delete(storeElem)
198 }
199
200 func (s *btreeStore) List() []interface{} {
201 items := make([]interface{}, 0, s.tree.Len())
202 s.tree.Ascend(func(item *storeElement) bool {
203 items = append(items, item)
204 return true
205 })
206 return items
207 }
208
209 func (s *btreeStore) ListKeys() []string {
210 items := make([]string, 0, s.tree.Len())
211 s.tree.Ascend(func(item *storeElement) bool {
212 items = append(items, item.Key)
213 return true
214 })
215 return items
216 }
217
218 func (s *btreeStore) Get(obj interface{}) (item interface{}, exists bool, err error) {
219 storeElem, ok := obj.(*storeElement)
220 if !ok {
221 return nil, false, fmt.Errorf("obj is not a storeElement")
222 }
223 item, exists = s.tree.Get(storeElem)
224 return item, exists, nil
225 }
226
227 func (s *btreeStore) GetByKey(key string) (item interface{}, exists bool, err error) {
228 return s.getByKey(key)
229 }
230
231 func (s *btreeStore) Replace(objs []interface{}, _ string) error {
232 s.tree.Clear(false)
233 for _, obj := range objs {
234 storeElem, ok := obj.(*storeElement)
235 if !ok {
236 return fmt.Errorf("obj not a storeElement: %#v", obj)
237 }
238 s.addOrUpdateElem(storeElem)
239 }
240 return nil
241 }
242
243 // addOrUpdateLocked assumes a lock is held and is used for Add
244 // and Update operations.
245 func (s *btreeStore) addOrUpdateElem(storeElem *storeElement) *storeElement {
246 oldObj, _ := s.tree.ReplaceOrInsert(storeElem)
247 return oldObj
248 }
249
250 func (s *btreeStore) getByKey(key string) (item interface{}, exists bool, err error) {
251 keyElement := &storeElement{Key: key}
252 item, exists = s.tree.Get(keyElement)
253 return item, exists, nil
254 }
255
256 func (s *btreeStore) ListPrefix(prefix, continueKey string) []interface{} {
257 if continueKey == "" {
258 continueKey = prefix
259 }
260 var result []interface{}
261 s.tree.AscendGreaterOrEqual(&storeElement{Key: continueKey}, func(item *storeElement) bool {
262 if !strings.HasPrefix(item.Key, prefix) {
263 return false
264 }
265 result = append(result, item)
266 return true
267 })
268 return result
269 }
270
271 func (s *btreeStore) Count(prefix, continueKey string) (count int) {
272 if continueKey == "" {
273 continueKey = prefix
274 }
275 s.tree.AscendGreaterOrEqual(&storeElement{Key: continueKey}, func(item *storeElement) bool {
276 if !strings.HasPrefix(item.Key, prefix) {
277 return false
278 }
279 count++
280 return true
281 })
282 return count
283 }
284
285 // newIndexer returns a indexer similar to storeIndex from client-go/tools/cache.
286 // TODO: Unify the indexer code with client-go/cache package.
287 // Major differences is type of values stored and their mutability:
288 // * Indexer in client-go stores object keys, that are not mutable.
289 // * Indexer in cacher stores whole objects, which is mutable.
290 // Indexer in client-go uses keys as it is used in conjunction with map[key]value
291 // allowing for fast value retrieval, while btree used in cacher would provide additional overhead.
292 // Difference in mutability of stored values is used for optimizing some operations in client-go Indexer.
293 func newIndexer(indexers cache.Indexers) indexer {
294 return indexer{
295 indices: map[string]map[string]map[string]*storeElement{},
296 indexers: indexers,
297 }
298 }
299
300 type indexer struct {
301 indices map[string]map[string]map[string]*storeElement
302 indexers cache.Indexers
303 }
304
305 func (i *indexer) ByIndex(indexName, indexValue string) ([]interface{}, error) {
306 indexFunc := i.indexers[indexName]
307 if indexFunc == nil {
308 return nil, fmt.Errorf("index with name %s does not exist", indexName)
309 }
310 index := i.indices[indexName]
311 set := index[indexValue]
312 list := make([]interface{}, 0, len(set))
313 for _, obj := range set {
314 list = append(list, obj)
315 }
316 return list, nil
317 }
318
319 func (i *indexer) Replace(objs []interface{}, resourceVersion string) error {
320 i.indices = map[string]map[string]map[string]*storeElement{}
321 for _, obj := range objs {
322 storeElem, ok := obj.(*storeElement)
323 if !ok {
324 return fmt.Errorf("obj not a storeElement: %#v", obj)
325 }
326 err := i.updateElem(storeElem.Key, nil, storeElem)
327 if err != nil {
328 return err
329 }
330 }
331 return nil
332 }
333
334 func (i *indexer) updateElem(key string, oldObj, newObj *storeElement) (err error) {
335 var oldIndexValues, indexValues []string
336 for name, indexFunc := range i.indexers {
337 if oldObj != nil {
338 oldIndexValues, err = indexFunc(oldObj)
339 } else {
340 oldIndexValues = oldIndexValues[:0]
341 }
342 if err != nil {
343 return fmt.Errorf("unable to calculate an index entry for key %q on index %q: %w", key, name, err)
344 }
345 if newObj != nil {
346 indexValues, err = indexFunc(newObj)
347 } else {
348 indexValues = indexValues[:0]
349 }
350 if err != nil {
351 return fmt.Errorf("unable to calculate an index entry for key %q on index %q: %w", key, name, err)
352 }
353 index := i.indices[name]
354 if index == nil {
355 index = map[string]map[string]*storeElement{}
356 i.indices[name] = index
357 }
358 if len(indexValues) == 1 && len(oldIndexValues) == 1 && indexValues[0] == oldIndexValues[0] {
359 // We optimize for the most common case where indexFunc returns a single value which has not been changed
360 i.add(key, indexValues[0], newObj, index)
361 continue
362 }
363 for _, value := range oldIndexValues {
364 i.delete(key, value, index)
365 }
366 for _, value := range indexValues {
367 i.add(key, value, newObj, index)
368 }
369 }
370 return nil
371 }
372
373 func (i *indexer) add(key, value string, obj *storeElement, index map[string]map[string]*storeElement) {
374 set := index[value]
375 if set == nil {
376 set = map[string]*storeElement{}
377 index[value] = set
378 }
379 set[key] = obj
380 }
381
382 func (i *indexer) delete(key, value string, index map[string]map[string]*storeElement) {
383 set := index[value]
384 if set == nil {
385 return
386 }
387 delete(set, key)
388 // If we don's delete the set when zero, indices with high cardinality
389 // short lived resources can cause memory to increase over time from
390 // unused empty sets. See `kubernetes/kubernetes/issues/84959`.
391 if len(set) == 0 {
392 delete(index, value)
393 }
394 }
395
396 // newStoreSnapshotter returns a storeSnapshotter that stores snapshots for
397 // serving read requests with exact resource versions (RV) and pagination.
398 //
399 // Snapshots are created by calling Clone method on orderedLister, which is
400 // expected to be fast and efficient thanks to usage of B-trees.
401 // B-trees can create a lazy copy of the tree structure, minimizing overhead.
402 //
403 // Assuming the watch cache observes all events and snapshots cache after each of them,
404 // requests for a specific resource version can be served by retrieving
405 // the snapshot with the greatest RV less than or equal to the requested RV.
406 // To make snapshot retrivial efficient we need an ordered data structure, such as tree.
407 //
408 // The initial implementation uses a B-tree to achieve the following performance characteristics (n - number of snapshots stored):
409 // - `Add`: Adds a new snapshot.
410 // Complexity: O(log n).
411 // Executed for each watch event observed by the cache.
412 // - `GetLessOrEqual`: Retrieves the snapshot with the greatest RV less than or equal to the requested RV.
413 // Complexity: O(log n).
414 // Executed for each LIST request with match=Exact or continuation.
415 // - `RemoveLess`: Cleans up snapshots outside the watch history window.
416 // Complexity: O(k log n), k - number of snapshots to remove, usually only one if watch capacity was not reduced.
417 // Executed per watch event observed when the cache is full.
418 // - `Reset`: Cleans up all snapshots.
419 // Complexity: O(1).
420 // Executed when the watch cache is reinitialized.
421 //
422 // Further optimization is possible by leveraging the property that adds always
423 // increase the maximum RV and deletes only increase the minimum RV.
424 // For example, a binary search on a cyclic buffer of (RV, snapshot)
425 // should reduce number of allocations and improve removal complexity.
426 // However, this solution is more complex and is deferred for future implementation.
427 //
428 // TODO: Rewrite to use a cyclic buffer
429 func newStoreSnapshotter() *storeSnapshotter {
430 s := &storeSnapshotter{
431 snapshots: btree.NewG[rvSnapshot](btreeDegree, func(a, b rvSnapshot) bool {
432 return a.resourceVersion < b.resourceVersion
433 }),
434 }
435 return s
436 }
437
438 var _ Snapshotter = (*storeSnapshotter)(nil)
439
440 type Snapshotter interface {
441 Reset()
442 GetLessOrEqual(rv uint64) (orderedLister, bool)
443 Add(rv uint64, indexer orderedLister)
444 RemoveLess(rv uint64)
445 Len() int
446 }
447
448 type storeSnapshotter struct {
449 mux sync.RWMutex
450 snapshots *btree.BTreeG[rvSnapshot]
451 }
452
453 type rvSnapshot struct {
454 resourceVersion uint64
455 snapshot orderedLister
456 }
457
458 func (s *storeSnapshotter) Reset() {
459 s.mux.Lock()
460 defer s.mux.Unlock()
461 s.snapshots.Clear(false)
462 }
463
464 func (s *storeSnapshotter) GetLessOrEqual(rv uint64) (orderedLister, bool) {
465 s.mux.RLock()
466 defer s.mux.RUnlock()
467
468 var result *rvSnapshot
469 s.snapshots.DescendLessOrEqual(rvSnapshot{resourceVersion: rv}, func(rvs rvSnapshot) bool {
470 result = &rvs
471 return false
472 })
473 if result == nil {
474 return nil, false
475 }
476 return result.snapshot, true
477 }
478
479 func (s *storeSnapshotter) Add(rv uint64, indexer orderedLister) {
480 s.mux.Lock()
481 defer s.mux.Unlock()
482 s.snapshots.ReplaceOrInsert(rvSnapshot{resourceVersion: rv, snapshot: indexer.Clone()})
483 }
484
485 func (s *storeSnapshotter) RemoveLess(rv uint64) {
486 s.mux.Lock()
487 defer s.mux.Unlock()
488 for s.snapshots.Len() > 0 {
489 oldest, ok := s.snapshots.Min()
490 if !ok {
491 break
492 }
493 if rv <= oldest.resourceVersion {
494 break
495 }
496 s.snapshots.DeleteMin()
497 }
498 }
499
500 func (s *storeSnapshotter) Len() int {
501 s.mux.RLock()
502 defer s.mux.RUnlock()
503
504 return s.snapshots.Len()
505 }