| 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 |
} |