2 Copyright 2014 The Kubernetes Authors.
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
8 http://www.apache.org/licenses/LICENSE-2.0
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.
23 "k8s.io/apimachinery/pkg/util/clock"
27 // ExpirationCache implements the store interface
28 // 1. All entries are automatically time stamped on insert
29 // a. The key is computed based off the original item/keyFunc
30 // b. The value inserted under that key is the timestamped item
31 // 2. Expiration happens lazily on read based on the expiration policy
32 // a. No item can be inserted into the store while we're expiring
33 // *any* item in the cache.
34 // 3. Time-stamps are stripped off unexpired entries before return
35 // Note that the ExpirationCache is inherently slower than a normal
36 // threadSafeStore because it takes a write lock every time it checks if
37 // an item has expired.
38 type ExpirationCache struct {
39 cacheStorage ThreadSafeStore
42 expirationPolicy ExpirationPolicy
43 // expirationLock is a write lock used to guarantee that we don't clobber
44 // newly inserted objects because of a stale expiration timestamp comparison
45 expirationLock sync.Mutex
48 // ExpirationPolicy dictates when an object expires. Currently only abstracted out
49 // so unittests don't rely on the system clock.
50 type ExpirationPolicy interface {
51 IsExpired(obj *timestampedEntry) bool
54 // TTLPolicy implements a ttl based ExpirationPolicy.
55 type TTLPolicy struct {
56 // >0: Expire entries with an age > ttl
57 // <=0: Don't expire any entry
60 // Clock used to calculate ttl expiration
64 // IsExpired returns true if the given object is older than the ttl, or it can't
66 func (p *TTLPolicy) IsExpired(obj *timestampedEntry) bool {
67 return p.Ttl > 0 && p.Clock.Since(obj.timestamp) > p.Ttl
70 // timestampedEntry is the only type allowed in a ExpirationCache.
71 type timestampedEntry struct {
76 // getTimestampedEntry returns the timestampedEntry stored under the given key.
77 func (c *ExpirationCache) getTimestampedEntry(key string) (*timestampedEntry, bool) {
78 item, _ := c.cacheStorage.Get(key)
79 if tsEntry, ok := item.(*timestampedEntry); ok {
85 // getOrExpire retrieves the object from the timestampedEntry if and only if it hasn't
86 // already expired. It holds a write lock across deletion.
87 func (c *ExpirationCache) getOrExpire(key string) (interface{}, bool) {
88 // Prevent all inserts from the time we deem an item as "expired" to when we
89 // delete it, so an un-expired item doesn't sneak in under the same key, just
91 c.expirationLock.Lock()
92 defer c.expirationLock.Unlock()
93 timestampedItem, exists := c.getTimestampedEntry(key)
97 if c.expirationPolicy.IsExpired(timestampedItem) {
98 klog.V(4).Infof("Entry %v: %+v has expired", key, timestampedItem.obj)
99 c.cacheStorage.Delete(key)
102 return timestampedItem.obj, true
105 // GetByKey returns the item stored under the key, or sets exists=false.
106 func (c *ExpirationCache) GetByKey(key string) (interface{}, bool, error) {
107 obj, exists := c.getOrExpire(key)
108 return obj, exists, nil
111 // Get returns unexpired items. It purges the cache of expired items in the
113 func (c *ExpirationCache) Get(obj interface{}) (interface{}, bool, error) {
114 key, err := c.keyFunc(obj)
116 return nil, false, KeyError{obj, err}
118 obj, exists := c.getOrExpire(key)
119 return obj, exists, nil
122 // List retrieves a list of unexpired items. It purges the cache of expired
123 // items in the process.
124 func (c *ExpirationCache) List() []interface{} {
125 items := c.cacheStorage.List()
127 list := make([]interface{}, 0, len(items))
128 for _, item := range items {
129 obj := item.(*timestampedEntry).obj
130 if key, err := c.keyFunc(obj); err != nil {
131 list = append(list, obj)
132 } else if obj, exists := c.getOrExpire(key); exists {
133 list = append(list, obj)
139 // ListKeys returns a list of all keys in the expiration cache.
140 func (c *ExpirationCache) ListKeys() []string {
141 return c.cacheStorage.ListKeys()
144 // Add timestamps an item and inserts it into the cache, overwriting entries
145 // that might exist under the same key.
146 func (c *ExpirationCache) Add(obj interface{}) error {
147 c.expirationLock.Lock()
148 defer c.expirationLock.Unlock()
150 key, err := c.keyFunc(obj)
152 return KeyError{obj, err}
154 c.cacheStorage.Add(key, ×tampedEntry{obj, c.clock.Now()})
158 // Update has not been implemented yet for lack of a use case, so this method
159 // simply calls `Add`. This effectively refreshes the timestamp.
160 func (c *ExpirationCache) Update(obj interface{}) error {
164 // Delete removes an item from the cache.
165 func (c *ExpirationCache) Delete(obj interface{}) error {
166 c.expirationLock.Lock()
167 defer c.expirationLock.Unlock()
168 key, err := c.keyFunc(obj)
170 return KeyError{obj, err}
172 c.cacheStorage.Delete(key)
176 // Replace will convert all items in the given list to TimestampedEntries
177 // before attempting the replace operation. The replace operation will
178 // delete the contents of the ExpirationCache `c`.
179 func (c *ExpirationCache) Replace(list []interface{}, resourceVersion string) error {
180 c.expirationLock.Lock()
181 defer c.expirationLock.Unlock()
182 items := make(map[string]interface{}, len(list))
184 for _, item := range list {
185 key, err := c.keyFunc(item)
187 return KeyError{item, err}
189 items[key] = ×tampedEntry{item, ts}
191 c.cacheStorage.Replace(items, resourceVersion)
195 // Resync will touch all objects to put them into the processing queue
196 func (c *ExpirationCache) Resync() error {
197 return c.cacheStorage.Resync()
200 // NewTTLStore creates and returns a ExpirationCache with a TTLPolicy
201 func NewTTLStore(keyFunc KeyFunc, ttl time.Duration) Store {
202 return &ExpirationCache{
203 cacheStorage: NewThreadSafeStore(Indexers{}, Indices{}),
205 clock: clock.RealClock{},
206 expirationPolicy: &TTLPolicy{ttl, clock.RealClock{}},