Debian Codegraph @

pkg/storage/cacher/store.go

raw
1 /*
2 Copyright 2024 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
22 "k8s.io/apimachinery/pkg/fields"
23 "k8s.io/apimachinery/pkg/labels"
24 "k8s.io/apimachinery/pkg/runtime"
25 "k8s.io/apiserver/pkg/features"
26 utilfeature "k8s.io/apiserver/pkg/util/feature"
27 "k8s.io/client-go/tools/cache"
28 )
29
30 const (
31 // btreeDegree defines the degree of btree storage.
32 // Decided based on the benchmark results (below).
33 // Selected the lowest degree from three options with best runtime (16,32,128).
34 // │ 2 │ 4 │ 8 │ 16 │ 32 │ 64 │ 128 │
35 // │ sec/op │ sec/op vs base │ sec/op vs base │ sec/op vs base │ sec/op vs base │ sec/op vs base │ sec/op vs base │
36 // StoreCreateList/RV=NotOlderThan-24 473.0µ ± 11% 430.1µ ± 9% -9.08% (p=0.005 n=10) 427.9µ ± 6% -9.54% (p=0.002 n=10) 403.9µ ± 8% -14.62% (p=0.000 n=10) 401.0µ ± 4% -15.22% (p=0.000 n=10) 408.0µ ± 4% -13.75% (p=0.000 n=10) 385.9µ ± 4% -18.42% (p=0.000 n=10)
37 // StoreCreateList/RV=ExactMatch-24 604.7µ ± 4% 596.7µ ± 8% ~ (p=0.529 n=10) 604.6µ ± 4% ~ (p=0.971 n=10) 601.1µ ± 4% ~ (p=0.853 n=10) 611.0µ ± 6% ~ (p=0.105 n=10) 598.2µ ± 5% ~ (p=0.579 n=10) 608.2µ ± 3% ~ (p=0.796 n=10)
38 // StoreList/List=All/Paginate=False/RV=Empty-24 729.1µ ± 5% 692.9µ ± 3% -4.96% (p=0.002 n=10) 693.7µ ± 3% -4.86% (p=0.000 n=10) 688.3µ ± 1% -5.59% (p=0.000 n=10) 690.4µ ± 5% -5.31% (p=0.002 n=10) 689.7µ ± 2% -5.40% (p=0.000 n=10) 687.8µ ± 3% -5.67% (p=0.000 n=10)
39 // StoreList/List=All/Paginate=True/RV=Empty-24 19.51m ± 2% 19.84m ± 2% ~ (p=0.105 n=10) 19.89m ± 3% ~ (p=0.190 n=10) 19.64m ± 4% ~ (p=0.853 n=10) 19.34m ± 4% ~ (p=0.481 n=10) 20.22m ± 4% +3.66% (p=0.007 n=10) 19.58m ± 4% ~ (p=0.912 n=10)
40 // StoreList/List=Namespace/Paginate=False/RV=Empty-24 1.672m ± 4% 1.635m ± 2% ~ (p=0.247 n=10) 1.673m ± 5% ~ (p=0.631 n=10) 1.657m ± 2% ~ (p=0.971 n=10) 1.656m ± 4% ~ (p=0.739 n=10) 1.678m ± 2% ~ (p=0.631 n=10) 1.718m ± 8% ~ (p=0.105 n=10)
41 // geomean 1.467m 1.420m -3.24% 1.430m -2.58% 1.403m -4.38% 1.402m -4.46% 1.417m -3.44% 1.403m -4.41%
42 //
43 // │ 2 │ 4 │ 8 │ 16 │ 32 │ 64 │ 128 │
44 // │ B/op │ B/op vs base │ B/op vs base │ B/op vs base │ B/op vs base │ B/op vs base │ B/op vs base │
45 // StoreCreateList/RV=NotOlderThan-24 98.58Ki ± 11% 101.33Ki ± 13% ~ (p=0.280 n=10) 99.80Ki ± 26% ~ (p=0.353 n=10) 109.63Ki ± 9% ~ (p=0.075 n=10) 112.56Ki ± 6% +14.18% (p=0.007 n=10) 114.41Ki ± 10% +16.05% (p=0.003 n=10) 115.06Ki ± 12% +16.72% (p=0.011 n=10)
46 // StoreCreateList/RV=ExactMatch-24 117.1Ki ± 0% 117.5Ki ± 0% ~ (p=0.218 n=10) 116.9Ki ± 0% ~ (p=0.052 n=10) 117.3Ki ± 0% ~ (p=0.353 n=10) 116.9Ki ± 0% ~ (p=0.075 n=10) 117.0Ki ± 0% ~ (p=0.436 n=10) 117.0Ki ± 0% ~ (p=0.280 n=10)
47 // StoreList/List=All/Paginate=False/RV=Empty-24 6.023Mi ± 0% 6.024Mi ± 0% +0.01% (p=0.037 n=10) 6.024Mi ± 0% ~ (p=0.493 n=10) 6.024Mi ± 0% +0.01% (p=0.035 n=10) 6.024Mi ± 0% ~ (p=0.247 n=10) 6.024Mi ± 0% ~ (p=0.247 n=10) 6.024Mi ± 0% ~ (p=0.315 n=10)
48 // StoreList/List=All/Paginate=True/RV=Empty-24 64.22Mi ± 0% 64.21Mi ± 0% ~ (p=0.075 n=10) 64.23Mi ± 0% ~ (p=0.280 n=10) 64.21Mi ± 0% -0.02% (p=0.002 n=10) 64.22Mi ± 0% ~ (p=0.579 n=10) 64.22Mi ± 0% ~ (p=0.971 n=10) 64.22Mi ± 0% ~ (p=1.000 n=10)
49 // StoreList/List=Namespace/Paginate=False/RV=Empty-24 8.177Mi ± 0% 8.178Mi ± 0% ~ (p=0.579 n=10) 8.177Mi ± 0% ~ (p=0.971 n=10) 8.179Mi ± 0% ~ (p=0.579 n=10) 8.178Mi ± 0% ~ (p=0.739 n=10) 8.179Mi ± 0% ~ (p=0.315 n=10) 8.176Mi ± 0% ~ (p=0.247 n=10)
50 // geomean 2.034Mi 2.047Mi +0.61% 2.039Mi +0.22% 2.079Mi +2.19% 2.088Mi +2.66% 2.095Mi +3.01% 2.098Mi +3.12%
51 //
52 // │ 2 │ 4 │ 8 │ 16 │ 32 │ 64 │ 128 │
53 // │ allocs/op │ allocs/op vs base │ allocs/op vs base │ allocs/op vs base │ allocs/op vs base │ allocs/op vs base │ allocs/op vs base │
54 // StoreCreateList/RV=NotOlderThan-24 560.0 ± 0% 558.0 ± 0% -0.36% (p=0.000 n=10) 557.0 ± 0% -0.54% (p=0.000 n=10) 558.0 ± 0% -0.36% (p=0.000 n=10) 557.0 ± 0% -0.54% (p=0.000 n=10) 557.0 ± 0% -0.54% (p=0.000 n=10) 557.0 ± 0% -0.54% (p=0.000 n=10)
55 // StoreCreateList/RV=ExactMatch-24 871.0 ± 0% 870.0 ± 0% -0.11% (p=0.038 n=10) 870.0 ± 0% -0.11% (p=0.004 n=10) 870.0 ± 0% -0.11% (p=0.005 n=10) 869.0 ± 0% -0.23% (p=0.000 n=10) 870.0 ± 0% -0.11% (p=0.001 n=10) 870.0 ± 0% -0.11% (p=0.000 n=10)
56 // StoreList/List=All/Paginate=False/RV=Empty-24 351.0 ± 3% 358.0 ± 1% +1.99% (p=0.034 n=10) 352.5 ± 3% ~ (p=0.589 n=10) 358.5 ± 1% +2.14% (p=0.022 n=10) 356.5 ± 3% ~ (p=0.208 n=10) 355.0 ± 3% ~ (p=0.224 n=10) 355.0 ± 3% ~ (p=0.183 n=10)
57 // StoreList/List=All/Paginate=True/RV=Empty-24 494.4k ± 0% 494.4k ± 0% ~ (p=0.424 n=10) 494.6k ± 0% +0.06% (p=0.000 n=10) 492.7k ± 0% -0.34% (p=0.000 n=10) 494.5k ± 0% +0.02% (p=0.009 n=10) 493.0k ± 0% -0.28% (p=0.000 n=10) 494.4k ± 0% ~ (p=0.424 n=10)
58 // StoreList/List=Namespace/Paginate=False/RV=Empty-24 32.43k ± 0% 32.44k ± 0% ~ (p=0.579 n=10) 32.43k ± 0% ~ (p=0.971 n=10) 32.45k ± 0% ~ (p=0.517 n=10) 32.44k ± 0% ~ (p=0.670 n=10) 32.46k ± 0% ~ (p=0.256 n=10) 32.41k ± 0% ~ (p=0.247 n=10)
59 // geomean 4.872k 4.887k +0.31% 4.870k -0.03% 4.885k +0.28% 4.880k +0.17% 4.875k +0.06% 4.876k +0.08%
60 btreeDegree = 16
61 )
62
63 type storeIndexer interface {
64 Add(obj interface{}) error
65 Update(obj interface{}) error
66 Delete(obj interface{}) error
67 List() []interface{}
68 ListKeys() []string
69 Get(obj interface{}) (item interface{}, exists bool, err error)
70 GetByKey(key string) (item interface{}, exists bool, err error)
71 Replace([]interface{}, string) error
72 ByIndex(indexName, indexedValue string) ([]interface{}, error)
73 }
74
75 type orderedLister interface {
76 ListPrefix(prefix, continueKey string) []interface{}
77 Count(prefix, continueKey string) (count int)
78 Clone() orderedLister
79 }
80
81 func newStoreIndexer(indexers *cache.Indexers) storeIndexer {
82 if utilfeature.DefaultFeatureGate.Enabled(features.BtreeWatchCache) {
83 return newThreadedBtreeStoreIndexer(storeElementIndexers(indexers), btreeDegree)
84 }
85 return cache.NewIndexer(storeElementKey, storeElementIndexers(indexers))
86 }
87
88 // Computing a key of an object is generally non-trivial (it performs
89 // e.g. validation underneath). Similarly computing object fields and
90 // labels. To avoid computing them multiple times (to serve the event
91 // in different List/Watch requests), in the underlying store we are
92 // keeping structs (key, object, labels, fields).
93 type storeElement struct {
94 Key string
95 Object runtime.Object
96 Labels labels.Set
97 Fields fields.Set
98 }
99
100 func storeElementKey(obj interface{}) (string, error) {
101 elem, ok := obj.(*storeElement)
102 if !ok {
103 return "", fmt.Errorf("not a storeElement: %v", obj)
104 }
105 return elem.Key, nil
106 }
107
108 func storeElementObject(obj interface{}) (runtime.Object, error) {
109 elem, ok := obj.(*storeElement)
110 if !ok {
111 return nil, fmt.Errorf("not a storeElement: %v", obj)
112 }
113 return elem.Object, nil
114 }
115
116 func storeElementIndexFunc(objIndexFunc cache.IndexFunc) cache.IndexFunc {
117 return func(obj interface{}) (strings []string, e error) {
118 seo, err := storeElementObject(obj)
119 if err != nil {
120 return nil, err
121 }
122 return objIndexFunc(seo)
123 }
124 }
125
126 func storeElementIndexers(indexers *cache.Indexers) cache.Indexers {
127 if indexers == nil {
128 return cache.Indexers{}
129 }
130 ret := cache.Indexers{}
131 for indexName, indexFunc := range *indexers {
132 ret[indexName] = storeElementIndexFunc(indexFunc)
133 }
134 return ret
135 }