cache

package
v1.0.5 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 16, 2024 License: Apache-2.0 Imports: 8 Imported by: 0

Documentation

Overview

Package cache implements a LRU cache.

The implementation borrows heavily from SmallLRUCache (originally by Nathan Schrenk). The object maintains a doubly-linked list of elements. When an element is accessed, it is promoted to the head of the list. When space is needed, the element at the tail of the list (the least recently used element) is evicted.

Index

Constants

This section is empty.

Variables

View Source 
var FIFOClosedError error = errors.New("DeltaFIFO: manipulating with closed queue")

Functions

func Pop 

func Pop(queue Queue) interface{}

Helper function for popping from Queue. WARNING: Do NOT use this function in non-test code to avoid races unless you really really really really know what you are doing.

Types

type ErrRequeue 

type ErrRequeue struct {
	// Err is returned by the Pop function
	Err error
}

ErrRequeue may be returned by a PopProcessFunc to safely requeue the current item. The value of Err will be returned from Pop.

func (ErrRequeue) Error 

func (e ErrRequeue) Error() string

type ExpirationCache 

type ExpirationCache struct {
	// contains filtered or unexported fields
}

ExpirationCache implements the store interface

  1. All entries are automatically time stamped on insert a. The key is computed based off the original item/keyFunc b. The value inserted under that key is the timestamped item
  2. Expiration happens lazily on read based on the expiration policy a. No item can be inserted into the store while we're expiring *any* item in the cache.
  3. Time-stamps are stripped off unexpired entries before return

Note that the ExpirationCache is inherently slower than a normal threadSafeStore because it takes a write lock every time it checks if an item has expired.

func (*ExpirationCache) Add 

func (c *ExpirationCache) Add(obj interface{}) error

Add timestamps an item and inserts it into the cache, overwriting entries that might exist under the same key.

func (*ExpirationCache) Delete 

func (c *ExpirationCache) Delete(obj interface{}) error

Delete removes an item from the cache.

func (*ExpirationCache) Get 

func (c *ExpirationCache) Get(obj interface{}) (interface{}, bool, error)

Get returns unexpired items. It purges the cache of expired items in the process.

func (*ExpirationCache) GetByKey 

func (c *ExpirationCache) GetByKey(key string) (interface{}, bool, error)

GetByKey returns the item stored under the key, or sets exists=false.

func (*ExpirationCache) List 

func (c *ExpirationCache) List() []interface{}

List retrieves a list of unexpired items. It purges the cache of expired items in the process.

func (*ExpirationCache) ListKeys 

func (c *ExpirationCache) ListKeys() []string

ListKeys returns a list of all keys in the expiration cache.

func (*ExpirationCache) Replace 

func (c *ExpirationCache) Replace(list []interface{}, resourceVersion string) error

Replace will convert all items in the given list to TimestampedEntries before attempting the replace operation. The replace operation will delete the contents of the ExpirationCache `c`.

func (*ExpirationCache) Resync 

func (c *ExpirationCache) Resync() error

Resync will touch all objects to put them into the processing queue

func (*ExpirationCache) Update 

func (c *ExpirationCache) Update(obj interface{}) error

Update has not been implemented yet for lack of a use case, so this method simply calls `Add`. This effectively refreshes the timestamp.

type ExpirationPolicy 

type ExpirationPolicy interface {
	IsExpired(obj *timestampedEntry) bool
}

ExpirationPolicy dictates when an object expires. Currently only abstracted out so unittests don't rely on the system clock.

type FIFO 

type FIFO struct {
	// contains filtered or unexported fields
}

FIFO receives adds and updates from a Reflector, and puts them in a queue for FIFO order processing. If multiple adds/updates of a single item happen while an item is in the queue before it has been processed, it will only be processed once, and when it is processed, the most recent version will be processed. This can't be done with a channel.

FIFO solves this use case:

  • You want to process every object (exactly) once.
  • You want to process the most recent version of the object when you process it.
  • You do not want to process deleted objects, they should be removed from the queue.
  • You do not want to periodically reprocess objects.

Compare with DeltaFIFO for other use cases.

func NewFIFO 

func NewFIFO(keyFunc KeyFunc) *FIFO

NewFIFO returns a Store which can be used to queue up items to process.

func (*FIFO) Add 

func (f *FIFO) Add(obj interface{}) error

Add inserts an item, and puts it in the queue. The item is only enqueued if it doesn't already exist in the set.

func (*FIFO) AddIfNotPresent 

func (f *FIFO) AddIfNotPresent(obj interface{}) error

AddIfNotPresent inserts an item, and puts it in the queue. If the item is already present in the set, it is neither enqueued nor added to the set.

This is useful in a single producer/consumer scenario so that the consumer can safely retry items without contending with the producer and potentially enqueueing stale items.

func (*FIFO) Close 

func (f *FIFO) Close()

Close the queue.

func (*FIFO) Delete 

func (f *FIFO) Delete(obj interface{}) error

Delete removes an item. It doesn't add it to the queue, because this implementation assumes the consumer only cares about the objects, not the order in which they were created/added.

func (*FIFO) Get 

func (f *FIFO) Get(obj interface{}) (item interface{}, exists bool, err error)

Get returns the requested item, or sets exists=false.

func (*FIFO) GetByKey 

func (f *FIFO) GetByKey(key string) (item interface{}, exists bool, err error)

GetByKey returns the requested item, or sets exists=false.

func (*FIFO) HasSynced 

func (f *FIFO) HasSynced() bool

Return true if an Add/Update/Delete/AddIfNotPresent are called first, or an Update called first but the first batch of items inserted by Replace() has been popped

func (*FIFO) IsClosed 

func (f *FIFO) IsClosed() bool

Checks if the queue is closed

func (*FIFO) List 

func (f *FIFO) List() []interface{}

List returns a list of all the items.

func (*FIFO) ListKeys 

func (f *FIFO) ListKeys() []string

ListKeys returns a list of all the keys of the objects currently in the FIFO.

func (*FIFO) Pop 

func (f *FIFO) Pop(process PopProcessFunc) (interface{}, error)

Pop waits until an item is ready and processes it. If multiple items are ready, they are returned in the order in which they were added/updated. The item is removed from the queue (and the store) before it is processed, so if you don't successfully process it, it should be added back with AddIfNotPresent(). process function is called under lock, so it is safe update data structures in it that need to be in sync with the queue.

func (*FIFO) Replace 

func (f *FIFO) Replace(list []interface{}, resourceVersion string) error

Replace will delete the contents of 'f', using instead the given map. 'f' takes ownership of the map, you should not reference the map again after calling this function. f's queue is reset, too; upon return, it will contain the items in the map, in no particular order.

func (*FIFO) Resync 

func (f *FIFO) Resync() error

Resync will touch all objects to put them into the processing queue

func (*FIFO) Update 

func (f *FIFO) Update(obj interface{}) error

Update is the same as Add in this implementation.

type FakeExpirationPolicy 

type FakeExpirationPolicy struct {
	NeverExpire     sets.String
	RetrieveKeyFunc KeyFunc
}

func (*FakeExpirationPolicy) IsExpired 

func (p *FakeExpirationPolicy) IsExpired(obj *timestampedEntry) bool

type Index 

type Index map[string]sets.String

Index maps the indexed value to a set of keys in the store that match on that value

type IndexFunc 

type IndexFunc func(obj interface{}) ([]string, error)

IndexFunc knows how to provide an indexed value for an object.

type Indexer 

type Indexer interface {
	Store
	// Retrieve list of objects that match on the named indexing function
	Index(indexName string, obj interface{}) ([]interface{}, error)
	// IndexKeys returns the set of keys that match on the named indexing function.
	IndexKeys(indexName, indexKey string) ([]string, error)
	// ListIndexFuncValues returns the list of generated values of an Index func
	ListIndexFuncValues(indexName string) []string
	// ByIndex lists object that match on the named indexing function with the exact key
	ByIndex(indexName, indexKey string) ([]interface{}, error)
	// GetIndexer return the indexers
	GetIndexers() Indexers

	// AddIndexers adds more indexers to this store.  If you call this after you already have data
	// in the store, the results are undefined.
	AddIndexers(newIndexers Indexers) error
}

Indexer is a storage interface that lets you list objects using multiple indexing functions

func NewIndexer 

func NewIndexer(keyFunc KeyFunc, indexers Indexers) Indexer

NewIndexer returns an Indexer implemented simply with a map and a lock.

type Indexers 

type Indexers map[string]IndexFunc

Indexers maps a name to a IndexFunc

type Indices 

type Indices map[string]Index

Indices maps a name to an Index

type Item 

type Item struct {
	Key   string
	Value Value
}

Item is what is stored in the cache

type KeyError 

type KeyError struct {
	Obj interface{}
	Err error
}

KeyError will be returned any time a KeyFunc gives an error; it includes the object at fault.

func (KeyError) Error 

func (k KeyError) Error() string

Error gives a human-readable description of the error.

type KeyFunc 

type KeyFunc func(obj interface{}) (string, error)

KeyFunc knows how to make a key from an object. Implementations should be deterministic.

func IndexFuncToKeyFuncAdapter 

func IndexFuncToKeyFuncAdapter(indexFunc IndexFunc) KeyFunc

IndexFuncToKeyFuncAdapter adapts an indexFunc to a keyFunc. This is only useful if your index function returns unique values for every object. This is conversion can create errors when more than one key is found. You should prefer to make proper key and index functions.

type LRUCache 

type LRUCache struct {
	// contains filtered or unexported fields
}

LRUCache is a typical LRU cache implementation. If the cache reaches the capacity, the least recently used item is deleted from the cache. Note the capacity is not the number of items, but the total sum of the Size() of each item.

func NewLRUCache 

func NewLRUCache(capacity int64) *LRUCache

NewLRUCache creates a new empty cache with the given capacity.

func (*LRUCache) Capacity 

func (lru *LRUCache) Capacity() int64

Capacity returns the cache maximum capacity.

func (*LRUCache) Clear 

func (lru *LRUCache) Clear()

Clear will clear the entire cache.

func (*LRUCache) Delete 

func (lru *LRUCache) Delete(key string) bool

Delete removes an entry from the cache, and returns if the entry existed.

func (*LRUCache) Get 

func (lru *LRUCache) Get(key string) (v Value, ok bool)

Get returns a value from the cache, and marks the entry as most recently used.

func (*LRUCache) Items 

func (lru *LRUCache) Items() []Item

Items returns all the values for the cache, ordered from most recently used to last recently used.

func (*LRUCache) Keys 

func (lru *LRUCache) Keys() []string

Keys returns all the keys for the cache, ordered from most recently used to last recently used.

func (*LRUCache) Length 

func (lru *LRUCache) Length() int64

Length returns how many elements are in the cache

func (*LRUCache) Oldest 

func (lru *LRUCache) Oldest() (oldest time.Time)

Oldest returns the insertion time of the oldest element in the cache, or a IsZero() time if cache is empty.

func (*LRUCache) Set 

func (lru *LRUCache) Set(key string, value Value)

Set sets a value in the cache.

func (*LRUCache) SetCapacity 

func (lru *LRUCache) SetCapacity(capacity int64)

SetCapacity will set the capacity of the cache. If the capacity is smaller, and the current cache size exceed that capacity, the cache will be shrank.

func (*LRUCache) SetIfAbsent 

func (lru *LRUCache) SetIfAbsent(key string, value Value)

SetIfAbsent will set the value in the cache if not present. If the value exists in the cache, we don't set it.

func (*LRUCache) Size 

func (lru *LRUCache) Size() int64

Size returns the sum of the objects' Size() method.

func (*LRUCache) Stats 

func (lru *LRUCache) Stats() (length, size, capacity int64, oldest time.Time)

Stats returns a few stats on the cache.

func (*LRUCache) StatsJSON 

func (lru *LRUCache) StatsJSON() string

StatsJSON returns stats as a JSON object in a string.

type PopProcessFunc 

type PopProcessFunc func(interface{}) error

PopProcessFunc is passed to Pop() method of Queue interface. It is supposed to process the element popped from the queue.

type Queue 

type Queue interface {
	Store

	// Pop blocks until it has something to process.
	// It returns the object that was process and the result of processing.
	// The PopProcessFunc may return an ErrRequeue{...} to indicate the item
	// should be requeued before releasing the lock on the queue.
	Pop(PopProcessFunc) (interface{}, error)

	// AddIfNotPresent adds a value previously
	// returned by Pop back into the queue as long
	// as nothing else (presumably more recent)
	// has since been added.
	AddIfNotPresent(interface{}) error

	// HasSynced returns true if the first batch of items has been popped
	HasSynced() bool

	// Close queue
	Close()
}

Queue is exactly like a Store, but has a Pop() method too.

type Store 

type Store interface {
	Add(obj interface{}) error
	Update(obj interface{}) error
	Delete(obj interface{}) error
	List() []interface{}
	ListKeys() []string
	Get(obj interface{}) (item interface{}, exists bool, err error)
	GetByKey(key string) (item interface{}, exists bool, err error)

	// Replace will delete the contents of the store, using instead the
	// given list. Store takes ownership of the list, you should not reference
	// it after calling this function.
	Replace([]interface{}, string) error
	Resync() error
}

Store is a generic object storage interface. Reflector knows how to watch a server and update a store. A generic store is provided, which allows Reflector to be used as a local caching system, and an LRU store, which allows Reflector to work like a queue of items yet to be processed.

Store makes no assumptions about stored object identity; it is the responsibility of a Store implementation to provide a mechanism to correctly key objects and to define the contract for obtaining objects by some arbitrary key type.

func NewFakeExpirationStore 

func NewFakeExpirationStore(keyFunc KeyFunc, deletedKeys chan<- string, expirationPolicy ExpirationPolicy, cacheClock clock.Clock) Store

func NewStore 

func NewStore(keyFunc KeyFunc) Store

NewStore returns a Store implemented simply with a map and a lock.

func NewTTLStore 

func NewTTLStore(keyFunc KeyFunc, ttl time.Duration) Store

NewTTLStore creates and returns a ExpirationCache with a TTLPolicy

type TTLPolicy 

type TTLPolicy struct {
	//	 >0: Expire entries with an age > ttl
	//	<=0: Don't expire any entry
	Ttl time.Duration

	// Clock used to calculate ttl expiration
	Clock clock.Clock
}

TTLPolicy implements a ttl based ExpirationPolicy.

func (*TTLPolicy) IsExpired 

func (p *TTLPolicy) IsExpired(obj *timestampedEntry) bool

IsExpired returns true if the given object is older than the ttl, or it can't determine its age.

type ThreadSafeStore 

type ThreadSafeStore interface {
	Add(key string, obj interface{})
	Update(key string, obj interface{})
	Delete(key string)
	Get(key string) (item interface{}, exists bool)
	List() []interface{}
	ListKeys() []string
	Replace(map[string]interface{}, string)
	Index(indexName string, obj interface{}) ([]interface{}, error)
	IndexKeys(indexName, indexKey string) ([]string, error)
	ListIndexFuncValues(name string) []string
	ByIndex(indexName, indexKey string) ([]interface{}, error)
	GetIndexers() Indexers

	// AddIndexers adds more indexers to this store.  If you call this after you already have data
	// in the store, the results are undefined.
	AddIndexers(newIndexers Indexers) error
	Resync() error
}

ThreadSafeStore is an interface that allows concurrent access to a storage backend. TL;DR caveats: you must not modify anything returned by Get or List as it will break the indexing feature in addition to not being thread safe.

The guarantees of thread safety provided by List/Get are only valid if the caller treats returned items as read-only. For example, a pointer inserted in the store through `Add` will be returned as is by `Get`. Multiple clients might invoke `Get` on the same key and modify the pointer in a non-thread-safe way. Also note that modifying objects stored by the indexers (if any) will *not* automatically lead to a re-index. So it's not a good idea to directly modify the objects returned by Get/List, in general.

func NewThreadSafeStore 

func NewThreadSafeStore(indexers Indexers, indices Indices) ThreadSafeStore

type Value 

type Value interface {
	// Size returns how big this value is.
	Size() int
}

Value is the interface values that go into LRUCache need to satisfy

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.