cache

README

cache

Purpose

Memory caching with the following focus:

• High concurrent throughput
• Size bounding using individual item sizes
• High hit ratio with varying concurrent access patterns
• Reference tracking for shared resource cleanup

Usage

Cache

Simple usage is a Get and Set:

a := cache.NewCache(cache.CacheOptions[string, int]{Capacity: 100})

v, ok := a.Get("hello")
if !ok {
    v = makeExpensiveValue()
    a.Set("hello", v)
}

// use v

Counting

counting.Cache tracks Release calls until all Get callers are done with their fetched value. Useful for reused buffers or data that needs cleanup:

type value struct {
  data []byte
}

func (v value) Release() {
  dataPool.Put(v.data)
}

a := counting.NewCache(counting.CacheOptions[string, int]{})

v, ok := a.Get("key1")
if !ok {
    // load data in reused buffer
    d := dataPool.Get()
    d = append(d[:0], ...key1 data...)

    v = a.Set("key1", value{data: d})
}
defer v.Release()

// use v.Value().data

Usages that require another structure outside the cache (perhaps ordered lists) could use Promote and CacheOptions.Evict.

SetS is available when individual value sizes are known.

SetLargerCapacity is available for cases when the cache is representing a value outside memory (such as the filesystem).

Design

Cache

For both Get and Set calls, the map / policy split combined with the atomic guarantee on map add allows separation of their operations for less blocking and lower contention. For Get we skip the policy promotion on contention, however on Set the policy add is never skipped to avoid trashing the ARC policy's tuning.

Counting

counting.Cache uses atomic counters and booleans with optimistic compare-and-swap loops to track Releases of returned Handles.

Improvements

• Remaining contention within policy add.
  • Any minor optimizations within the ARC policy would reduce time and thus improve contention.
  • Ability to peek a slice of evictions in the policy could allow the cache to use a single lock for the eviction loop.
• Tests and benchmarks are light in a few places.
• counting.Node.Handle() is a significant source of garbage.

Documentation

Index

• type Cache
  • func NewCache[K comparable, V any](o CacheOptions[K, V]) *Cache[K, V]
  • func (a *Cache[K, V]) All() iter.Seq2[K, V]
  • func (a *Cache[K, V]) Capacity() int64
  • func (a *Cache[K, V]) Clear()
  • func (a *Cache[K, V]) Get(k K) (_ V, ok bool)
  • func (a *Cache[K, V]) Len() int
  • func (a *Cache[K, V]) Peek(k K) (V, bool)
  • func (a *Cache[K, V]) Promote(k K)
  • func (a *Cache[K, V]) Set(k K, v V)
  • func (a *Cache[K, V]) SetAvailableCapacity(available, max int64)
  • func (a *Cache[K, V]) SetCapacity(c int64)
  • func (a *Cache[K, V]) SetLargerCapacity(available, max int64)
  • func (a *Cache[K, V]) SetS(k K, v V, size uint32)
  • func (a *Cache[K, V]) Size() int64
• type CacheOptions
• type CacheValue

Types

type Cache

type Cache[K, V any] struct {
	// contains filtered or unexported fields
}

Concurrent safe.

func NewCache

func NewCache[K comparable, V any](o CacheOptions[K, V]) *Cache[K, V]

func (*Cache[K, V]) All

func (a *Cache[K, V]) All() iter.Seq2[K, V]

Results ordered by hot->cold. Will block.

func (*Cache[K, V]) Capacity

func (a *Cache[K, V]) Capacity() int64

func (*Cache[K, V]) Clear

func (a *Cache[K, V]) Clear()

Evicts all and resets. Does not change capacity. Will block.

func (*Cache[K, V]) Get

func (a *Cache[K, V]) Get(k K) (_ V, ok bool)

Promotes.

func (*Cache[K, V]) Len

func (a *Cache[K, V]) Len() int

func (*Cache[K, V]) Peek

func (a *Cache[K, V]) Peek(k K) (V, bool)

Does not Promote.

func (*Cache[K, V]) Promote

func (a *Cache[K, V]) Promote(k K)

func (*Cache[K, V]) Set

func (a *Cache[K, V]) Set(k K, v V)

Alias for SetS(k,v,1).

func (*Cache[K, V]) SetAvailableCapacity

func (a *Cache[K, V]) SetAvailableCapacity(available, max int64)

available (+/-) should not consider taken space in cache.

func (*Cache[K, V]) SetCapacity

func (a *Cache[K, V]) SetCapacity(c int64)

func (*Cache[K, V]) SetLargerCapacity

func (a *Cache[K, V]) SetLargerCapacity(available, max int64)

Noop if smaller. available (+/-) should not consider taken space in cache. DEPRECATED. Please use SetAvailableCapacity.

func (*Cache[K, V]) SetS

func (a *Cache[K, V]) SetS(k K, v V, size uint32)

Replaces existing values, which are evicted. A min size of 1 will be used.

func (*Cache[K, V]) Size

func (a *Cache[K, V]) Size() int64

type CacheOptions

type CacheOptions[K, V any] struct {
	Expiration    time.Duration                      // Defaults to forever.
	Evict         func(K, V)                         // Might be called concurrently.
	Capacity      int64                              // Defaults to 100.
	RLock         bool                               // Whether to use an RLock when possible. Defaults to false.
	MapCreator    func() maps.Map[K, *CacheValue[V]] // defaults to maps.Sync.
	PolicyCreator func() policy.Policy[K]            // defaults to policy.NewARC.
}

type CacheValue

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