cache

type Cacheable ¶ added in v1.15.0

type Cacheable[T any] interface {
	// Index generates an index for the hash table.
	Index() string
	// Equal is used to detect modifications of the data.
	Equal(other *T) bool
}

Cacheable defines a cacheable type.

type CacheablePointer ¶ added in v1.15.0

type CacheablePointer[T any] interface {
	*T
	Cacheable[T]
}

CacheablePointer defines a pointer to a type that implements the Cacheable interface.

type Epoch ¶ added in v1.15.0

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

Epoch represents a revision of the cache data.

func (e Epoch) Valid(previous Epoch) bool

type GetSnapshot ¶ added in v1.15.0

type GetSnapshot[T any] struct {
	// Epoch is the revision of the cache data.  The client can memoize any
	// transformations applied to the items and reuse those until a time
	// when the epoch becomes invalid.
	Epoch Epoch
	// Item is the individual cache item.
	Item *T
}

GetSnapshot is a user view of cache data.

type IndexFunc ¶ added in v1.15.0

type IndexFunc[T any, TP CacheablePointer[T]] func(t TP) string

IndexFunc provides the client a way to define how indexes are generated from cache resources. The index must be unique across all resources.

type LRUExpireCache ¶ added in v1.0.0

type LRUExpireCache[K comparable, T any] struct {
	// contains filtered or unexported fields
}

LRUExpireCache is a drop in replacement for the apimachinery version that makes it typed with generics, and also data immutable via deep copies.

func NewLRUExpireCache[K comparable, T any](maxSize int) *LRUExpireCache[K, T]

func (c *LRUExpireCache[K, T]) Add(key K, value T, ttl time.Duration)

func (c *LRUExpireCache[K, T]) Get(key K) (T, bool)

func (c *LRUExpireCache[K, T]) ZeroCopy()

type ListSnapshot ¶ added in v1.15.0

type ListSnapshot[T any] struct {
	// Epoch is the revision of the cache data.  The client can memoize any
	// transformations applied to the items and reuse those until a time
	// when the epoch becomes invalid.
	Epoch Epoch
	// Items are the individual cache items.  No ordering constraints are placed
	// on the snapshot items as this is likely to be more efficient downstream
	// after any potential filtering operations.
	Items []*T
}

ListSnapshot is a user view of cache data.

type RefreshAheadCache ¶ added in v1.15.0

type RefreshAheadCache[T any, TP CacheablePointer[T]] struct {
	// contains filtered or unexported fields
}

RefreshAheadCache is a hightly efficient high performance cache implementation for sets of resources.

Synchronization ¶

One of the key observations with a timeout cache that is lazily loaded on a cache miss is that someone needs to pay a performance penalty. This implementation focuses on background synchronization of data either periodically or explicitly through a synchronization operation.

Explicit synchronization is deliberately blocking so that when control is returned back to the client, the expected data is guaranteed to be in the cache ready for subsequent use.

Either the entire cache can be refreshed, which facilitates addition of resources out-of-band, or synchronization of individual resources for example on creation or update to avoid having to perform a potentially costly rebuild.

Local writes are applied through a write-through overlay. A local mutation is immediately visible in the effective cache view. If a refresh is already in flight when that mutation happens, the overlay survives that refresh so the stale backend snapshot cannot erase the new value.

Correctness depends on two usage constraints:

• This is a single-instance cache. If callers write through one process and read through another cache instance, read-your-writes is not guaranteed.
• InsertIfAbsent and Upsert must only be called after the corresponding backend write has synchronously and atomically committed. A refresh that starts after such a write is assumed to observe that committed state.

Once a later refresh starts after the mutation, the backend snapshot is treated as authoritative again and the overlay entry is discarded. In other words, the overlay only bridges writes that land during an in-flight refresh; it is not a long-lived reconciliation layer.

This model has primarily been designed and tested for singleton-style writes, for example creates keyed by a unique primary key where only one object can exist for that key.

For a single cache instance, concurrent calls to InsertIfAbsent and Upsert are serialized by the cache lock. However, if multiple writers concurrently commit different values for the same key in the backend, the cache does not try to apply any extra heuristic to pick a local winner beyond that serialization order. In that case the visible value will still converge back to the backend on the next authoritative refresh.

Read Performance ¶

Background synchronization ensures every client read will perform equally well. To facilitate efficient lookups of individual resources in the cache each resource will be indexed via some form of hashing function that uniquely identfies that resource.

The cache features pre-population so it will be ready to use, and this synchronization status can be fed directly into Kubernetes readiness probes to facilitate a seemless rolling upgrade experience.

Read Safety ¶

If we naively passed a slice up to the client, then that could be accidentally mutated through filtering operations such as slices.Delete. The easy fix is to perform a deep copy of the data, but this is costly due to the use of runtime reflection.

We implement a halfway policy that is both performant and also less likely to fall foul of accidental mutation. Cache resources are only ever referred by pointer, facilitating zero copy for individual resources. When a client wishes to list all resources we return a new array that can be mutated pointing to each of the resources, doing only the minimal amount of work as is necessary.

Downstream Performance Optimization ¶

Synchronization events are epochs. When a client lists resources, not only does it return an array of resource pointers, it also returns the epoch for which it is valid for.

This allows clients to memoize any transformations made against the cached resurces and further improve performance. An example of this is JSON encoding which uses runtime type reflection and is relatively costly.

func NewRefreshAheadCache[T any, TP CacheablePointer[T]](refresh RefreshFunc[T, TP], options *RefreshAheadCacheOptions) *RefreshAheadCache[T, TP]

func (c *RefreshAheadCache[T, TP]) Get(index string) (*GetSnapshot[T], error)

func (c *RefreshAheadCache[T, TP]) InsertIfAbsent(item TP) error

func (c *RefreshAheadCache[T, TP]) Invalidate() error

func (c *RefreshAheadCache[T, TP]) List() (*ListSnapshot[T], error)

func (c *RefreshAheadCache[T, TP]) Run(ctx context.Context) error

func (c *RefreshAheadCache[T, TP]) Upsert(item TP) error

type RefreshAheadCacheOptions ¶ added in v1.15.0

type RefreshAheadCacheOptions struct {
	// RefreshPeriod controls how often to refresh data.
	RefreshPeriod time.Duration
}

RefreshAheadCacheOptions allows the cache to be configured in various ways.

type RefreshFunc ¶ added in v1.15.0

type RefreshFunc[T any, TP CacheablePointer[T]] func(ctx context.Context) ([]TP, error)

RefreshFunc provides the client a way to define how to load the cache data. It is recommended that any post processing that happens on raw data also occurs during a refresh to hide the cost.

type TimeoutCache ¶

type TimeoutCache[V any] struct {
	// contains filtered or unexported fields
}

TimeoutCache provides a cache with timeout.

func New[V any](refresh time.Duration) *TimeoutCache[V]

func NewWithClock[V any](refresh time.Duration, c clock) *TimeoutCache[V]

func (m *TimeoutCache[V]) Get() (value V, ok bool)

func (m *TimeoutCache[V]) Invalidate()

func (m *TimeoutCache[V]) Set(value V)