expiration_cache.go

Documentation: k8s.io/client-go/tools/cache

     1  /*
     2  Copyright 2014 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 cache
    18  
    19  import (
    20  	"sync"
    21  	"time"
    22  
    23  	"k8s.io/utils/clock"
    24  )
    25  
    26  // ExpirationCache implements the store interface
    27  //  1. All entries are automatically time stamped on insert
    28  //     a. The key is computed based off the original item/keyFunc
    29  //     b. The value inserted under that key is the timestamped item
    30  //  2. Expiration happens lazily on read based on the expiration policy
    31  //     a. No item can be inserted into the store while we're expiring
    32  //     *any* item in the cache.
    33  //  3. Time-stamps are stripped off unexpired entries before return
    34  //
    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
    40  	keyFunc          KeyFunc
    41  	clock            clock.Clock
    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
    46  }
    47  
    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
    52  }
    53  
    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
    58  	TTL time.Duration
    59  
    60  	// Clock used to calculate ttl expiration
    61  	Clock clock.Clock
    62  }
    63  
    64  // IsExpired returns true if the given object is older than the ttl, or it can't
    65  // determine its age.
    66  func (p *TTLPolicy) IsExpired(obj *TimestampedEntry) bool {
    67  	return p.TTL > 0 && p.Clock.Since(obj.Timestamp) > p.TTL
    68  }
    69  
    70  // TimestampedEntry is the only type allowed in a ExpirationCache.
    71  // Keep in mind that it is not safe to share timestamps between computers.
    72  // Behavior may be inconsistent if you get a timestamp from the API Server and
    73  // use it on the client machine as part of your ExpirationCache.
    74  type TimestampedEntry struct {
    75  	Obj       interface{}
    76  	Timestamp time.Time
    77  	key       string
    78  }
    79  
    80  // getTimestampedEntry returns the TimestampedEntry stored under the given key.
    81  func (c *ExpirationCache) getTimestampedEntry(key string) (*TimestampedEntry, bool) {
    82  	item, _ := c.cacheStorage.Get(key)
    83  	if tsEntry, ok := item.(*TimestampedEntry); ok {
    84  		return tsEntry, true
    85  	}
    86  	return nil, false
    87  }
    88  
    89  // getOrExpire retrieves the object from the TimestampedEntry if and only if it hasn't
    90  // already expired. It holds a write lock across deletion.
    91  func (c *ExpirationCache) getOrExpire(key string) (interface{}, bool) {
    92  	// Prevent all inserts from the time we deem an item as "expired" to when we
    93  	// delete it, so an un-expired item doesn't sneak in under the same key, just
    94  	// before the Delete.
    95  	c.expirationLock.Lock()
    96  	defer c.expirationLock.Unlock()
    97  	timestampedItem, exists := c.getTimestampedEntry(key)
    98  	if !exists {
    99  		return nil, false
   100  	}
   101  	if c.expirationPolicy.IsExpired(timestampedItem) {
   102  		c.cacheStorage.Delete(key)
   103  		return nil, false
   104  	}
   105  	return timestampedItem.Obj, true
   106  }
   107  
   108  // GetByKey returns the item stored under the key, or sets exists=false.
   109  func (c *ExpirationCache) GetByKey(key string) (interface{}, bool, error) {
   110  	obj, exists := c.getOrExpire(key)
   111  	return obj, exists, nil
   112  }
   113  
   114  // Get returns unexpired items. It purges the cache of expired items in the
   115  // process.
   116  func (c *ExpirationCache) Get(obj interface{}) (interface{}, bool, error) {
   117  	key, err := c.keyFunc(obj)
   118  	if err != nil {
   119  		return nil, false, KeyError{obj, err}
   120  	}
   121  	obj, exists := c.getOrExpire(key)
   122  	return obj, exists, nil
   123  }
   124  
   125  // List retrieves a list of unexpired items. It purges the cache of expired
   126  // items in the process.
   127  func (c *ExpirationCache) List() []interface{} {
   128  	items := c.cacheStorage.List()
   129  
   130  	list := make([]interface{}, 0, len(items))
   131  	for _, item := range items {
   132  		key := item.(*TimestampedEntry).key
   133  		if obj, exists := c.getOrExpire(key); exists {
   134  			list = append(list, obj)
   135  		}
   136  	}
   137  	return list
   138  }
   139  
   140  // ListKeys returns a list of all keys in the expiration cache.
   141  func (c *ExpirationCache) ListKeys() []string {
   142  	return c.cacheStorage.ListKeys()
   143  }
   144  
   145  // Add timestamps an item and inserts it into the cache, overwriting entries
   146  // that might exist under the same key.
   147  func (c *ExpirationCache) Add(obj interface{}) error {
   148  	key, err := c.keyFunc(obj)
   149  	if err != nil {
   150  		return KeyError{obj, err}
   151  	}
   152  	c.expirationLock.Lock()
   153  	defer c.expirationLock.Unlock()
   154  
   155  	c.cacheStorage.Add(key, &TimestampedEntry{obj, c.clock.Now(), key})
   156  	return nil
   157  }
   158  
   159  // Update has not been implemented yet for lack of a use case, so this method
   160  // simply calls `Add`. This effectively refreshes the timestamp.
   161  func (c *ExpirationCache) Update(obj interface{}) error {
   162  	return c.Add(obj)
   163  }
   164  
   165  // Delete removes an item from the cache.
   166  func (c *ExpirationCache) Delete(obj interface{}) error {
   167  	key, err := c.keyFunc(obj)
   168  	if err != nil {
   169  		return KeyError{obj, err}
   170  	}
   171  	c.expirationLock.Lock()
   172  	defer c.expirationLock.Unlock()
   173  	c.cacheStorage.Delete(key)
   174  	return nil
   175  }
   176  
   177  // Replace will convert all items in the given list to TimestampedEntries
   178  // before attempting the replace operation. The replace operation will
   179  // delete the contents of the ExpirationCache `c`.
   180  func (c *ExpirationCache) Replace(list []interface{}, resourceVersion string) error {
   181  	items := make(map[string]interface{}, len(list))
   182  	ts := c.clock.Now()
   183  	for _, item := range list {
   184  		key, err := c.keyFunc(item)
   185  		if err != nil {
   186  			return KeyError{item, err}
   187  		}
   188  		items[key] = &TimestampedEntry{item, ts, key}
   189  	}
   190  	c.expirationLock.Lock()
   191  	defer c.expirationLock.Unlock()
   192  	c.cacheStorage.Replace(items, resourceVersion)
   193  	return nil
   194  }
   195  
   196  // Resync is a no-op for one of these
   197  func (c *ExpirationCache) Resync() error {
   198  	return nil
   199  }
   200  
   201  // NewTTLStore creates and returns a ExpirationCache with a TTLPolicy
   202  func NewTTLStore(keyFunc KeyFunc, ttl time.Duration) Store {
   203  	return NewExpirationStore(keyFunc, &TTLPolicy{ttl, clock.RealClock{}})
   204  }
   205  
   206  // NewExpirationStore creates and returns a ExpirationCache for a given policy
   207  func NewExpirationStore(keyFunc KeyFunc, expirationPolicy ExpirationPolicy) Store {
   208  	return &ExpirationCache{
   209  		cacheStorage:     NewThreadSafeStore(Indexers{}, Indices{}),
   210  		keyFunc:          keyFunc,
   211  		clock:            clock.RealClock{},
   212  		expirationPolicy: expirationPolicy,
   213  	}
   214  }
   215
View as plain text