lru

Documentation

Overview

Package lru implements a specialised least recently used cache.

Index

• type Cache
  • func NewCache(capacity uint, onEvict EvictionFunc) *Cache
  • func (c *Cache) Get(key string) ([]byte, lifetime.Lifetime, bool)
  • func (c *Cache) PruneExpired() uint
  • func (c *Cache) Put(key string, data []byte, lt lifetime.Lifetime) bool
• type EvictionFunc

Types

type Cache

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

Cache implements an LRU cache that evicts its oldest entry as necessary. It is safe for concurrent access. The key is always a string; the value can be any type. Instances are regarded as a low-level primitive, so there is no built-in monitoring. This should be provided around the site of exported methods.

func NewCache

func NewCache(capacity uint, onEvict EvictionFunc) *Cache

NewCache creates a new LRU cache with a maximum number of entries, and function to call when elements are evicted. The capacity can be 0, however a function must be provided.

We generally care about bytes rather than the number of entries, as that's the underlying constraint, however we do not know how much memory is taken up by our internal data structures, and value may be owned elsewhere (so us storing a pointer to 24 bytes does not mean 24 bytes would've been saved if it wasn't in our cache). As a result, we delegate to the implementer, and use a metric that is perhaps less directly useful, but at least correct.

func (*Cache) Get

func (c *Cache) Get(key string) ([]byte, lifetime.Lifetime, bool)

Get retrieves the value stored under a key. If the key does not exist, the bool will be false, in which case other return values should be ignored. A key may contain nil data. The returned values must not be modified.

func (*Cache) PruneExpired

func (c *Cache) PruneExpired() uint

PruneExpired scans the cache and removes elements whose lifetime has expired. Note EvictionFunc is not called.

This function incurs a latency hit on other access. On the surface we want a larger number of smaller caches to mitigate the effect, however this leads to more network requests between peers, which are orders of magnitude slower.

func (*Cache) Put

func (c *Cache) Put(key string, data []byte, lt lifetime.Lifetime) bool

Put adds, or updates the value stored under, a key. It returns whether the key already existed in the cache. Data may be nil.

type EvictionFunc

type EvictionFunc func(lifetime.Lifetime)

EvictionFunc is a function called with a cache entry's lifetime when it is removed due to the cache being at capacity, a new entry needing to be added, and this one being the one referenced longest ago. The lifetime must not be modified.