lru

README

approx-lru

This provides the lru package which implements a fixed-size thread safe LRU cache. It is based on hashicorp/golang-lru, which is in turn based on the cache in Groupcache.

The major difference in bobby-stripe/approx-lru is that instead of strictly ordering all items in the cache in a doubly-linked list (like golang-lru does), approx-lru contains a fixed-sized array of cache entries with a lastUsed timestamp. If the cache is full and needs to evict an item, we randomly probe several entries, and evict the oldest. This is the same strategy as Redis's allkeys-lru, and approximates a perfect LRU with less bookkeeping and memory overhead (each linked list entry in Go is 40-bytes, in addition to the data).

Documentation

Full docs are available on Godoc

Example

Using the LRU is very simple:

l, _ := New(128)
for i := 0; i < 256; i++ {
    l.Add(strconv.Itoa(i), i)
}
if l.Len() != 128 {
    panic(fmt.Sprintf("bad len: %v", l.Len()))
}
if v, ok := l.Get("200"); ok {
	_ = v // use v
}

Documentation

Overview

Package lru provides three different LRU caches of varying sophistication.

Cache is a simple LRU cache. It is based on the LRU implementation in groupcache: https://github.com/golang/groupcache/tree/master/lru

TwoQueueCache tracks frequently used and recently used entries separately. This avoids a burst of accesses from taking out frequently used entries, at the cost of about 2x computational overhead and some extra bookkeeping.

ARCCache is an adaptive replacement cache. It tracks recent evictions as well as recent usage in both the frequent and recent caches. Its computational overhead is comparable to TwoQueueCache, but the memory overhead is linear with the size of the cache.

ARC has been patented by IBM, so do not use it if that is problematic for your program.

All caches in this package take locks while operating, and are therefore thread-safe for consumers.

Index

• type Cache
  • func New[K comparable, V any](size int) (*Cache[K, V], error)
  • func NewWithEvict[K comparable, V any](size int, onEvicted func(key K, value V)) (*Cache[K, V], error)
  • func (c *Cache[K, V]) Add(key K, value V) (evicted bool)
  • func (c *Cache[K, V]) Contains(key K) bool
  • func (c *Cache[K, V]) ContainsOrAdd(key K, value V) (ok, evicted bool)
  • func (c *Cache[K, V]) Get(key K) (value V, ok bool)
  • func (c *Cache[K, V]) Len() int
  • func (c *Cache[K, V]) Peek(key K) (value V, ok bool)
  • func (c *Cache[K, V]) PeekOrAdd(key K, value V) (previous V, ok, evicted bool)
  • func (c *Cache[K, V]) Purge()
  • func (c *Cache[K, V]) Remove(key K) (present bool)
  • func (c *Cache[K, V]) Resize(size int) (evicted int)
• type ShardedCache
  • func NewSharded[V any](size, shardCount int) (*ShardedCache[V], error)
  • func NewShardedWithEvict[V any](size, shardCount int, onEvicted func(key string, value V)) (*ShardedCache[V], error)
  • func (c *ShardedCache[V]) Add(key string, value V) (evicted bool)
  • func (c *ShardedCache[V]) Contains(key string) bool
  • func (c *ShardedCache[V]) ContainsOrAdd(key string, value V) (ok, evicted bool)
  • func (c *ShardedCache[V]) Get(key string) (value V, ok bool)
  • func (c *ShardedCache[V]) Len() int
  • func (c *ShardedCache[V]) Peek(key string) (value V, ok bool)
  • func (c *ShardedCache[V]) PeekOrAdd(key string, value V) (previous V, ok, evicted bool)
  • func (c *ShardedCache[V]) Purge()
  • func (c *ShardedCache[V]) Remove(key string) (present bool)

Types

type Cache

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

Cache is a thread-safe fixed size LRU cache.

func New

func New[K comparable, V any](size int) (*Cache[K, V], error)

New creates an LRU of the given size.

func NewWithEvict

func NewWithEvict[K comparable, V any](size int, onEvicted func(key K, value V)) (*Cache[K, V], error)

NewWithEvict constructs a fixed size cache with the given eviction callback.

func (*Cache[K, V]) Add

func (c *Cache[K, V]) Add(key K, value V) (evicted bool)

Add adds a value to the cache. Returns true if an eviction occurred.

func (*Cache[K, V]) Contains

func (c *Cache[K, V]) Contains(key K) bool

Contains checks if a key is in the cache, without updating the recent-ness or deleting it for being stale.

func (*Cache[K, V]) ContainsOrAdd

func (c *Cache[K, V]) ContainsOrAdd(key K, value V) (ok, evicted bool)

ContainsOrAdd checks if a key is in the cache without updating the recent-ness or deleting it for being stale, and if not, adds the value. Returns whether found and whether an eviction occurred.

func (*Cache[K, V]) Get

func (c *Cache[K, V]) Get(key K) (value V, ok bool)

Get looks up a key's value from the cache.

func (*Cache[K, V]) Len

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

Len returns the number of items in the cache.

func (*Cache[K, V]) Peek

func (c *Cache[K, V]) Peek(key K) (value V, ok bool)

Peek returns the key value (or undefined if not found) without updating the "recently used"-ness of the key.

func (*Cache[K, V]) PeekOrAdd

func (c *Cache[K, V]) PeekOrAdd(key K, value V) (previous V, ok, evicted bool)

PeekOrAdd checks if a key is in the cache without updating the recent-ness or deleting it for being stale, and if not, adds the value. Returns whether found and whether an eviction occurred.

func (*Cache[K, V]) Purge

func (c *Cache[K, V]) Purge()

Purge is used to completely clear the cache.

func (*Cache[K, V]) Remove

func (c *Cache[K, V]) Remove(key K) (present bool)

Remove removes the provided key from the cache.

func (*Cache[K, V]) Resize

func (c *Cache[K, V]) Resize(size int) (evicted int)

Resize changes the cache size.

type ShardedCache

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

Cache is a thread-safe fixed size LRU cache.

func NewSharded

func NewSharded[V any](size, shardCount int) (*ShardedCache[V], error)

New creates an LRU of the given size.

func NewShardedWithEvict

func NewShardedWithEvict[V any](size, shardCount int, onEvicted func(key string, value V)) (*ShardedCache[V], error)

NewWithEvict constructs a fixed size cache with the given eviction callback.

func (*ShardedCache[V]) Add

func (c *ShardedCache[V]) Add(key string, value V) (evicted bool)

Add adds a value to the cache. Returns true if an eviction occurred.

func (*ShardedCache[V]) Contains

func (c *ShardedCache[V]) Contains(key string) bool

Contains checks if a key is in the cache, without updating the recent-ness or deleting it for being stale.

func (*ShardedCache[V]) ContainsOrAdd

func (c *ShardedCache[V]) ContainsOrAdd(key string, value V) (ok, evicted bool)

ContainsOrAdd checks if a key is in the cache without updating the recent-ness or deleting it for being stale, and if not, adds the value. Returns whether found and whether an eviction occurred.

func (*ShardedCache[V]) Get

func (c *ShardedCache[V]) Get(key string) (value V, ok bool)

Get looks up a key's value from the cache.

func (*ShardedCache[V]) Len

func (c *ShardedCache[V]) Len() int

Len returns the number of items in the cache.

func (*ShardedCache[V]) Peek

func (c *ShardedCache[V]) Peek(key string) (value V, ok bool)

Peek returns the key value (or undefined if not found) without updating the "recently used"-ness of the key.

func (*ShardedCache[V]) PeekOrAdd

func (c *ShardedCache[V]) PeekOrAdd(key string, value V) (previous V, ok, evicted bool)

PeekOrAdd checks if a key is in the cache without updating the recent-ness or deleting it for being stale, and if not, adds the value. Returns whether found and whether an eviction occurred.

func (*ShardedCache[V]) Purge

func (c *ShardedCache[V]) Purge()

Purge is used to completely clear the cache.

func (*ShardedCache[V]) Remove

func (c *ShardedCache[V]) Remove(key string) (present bool)

Remove removes the provided key from the cache.