evcache

README

evcache

Benchmarks

import "github.com/mgnsk/evcache/v2"

How it works

The cache is a wrapper for sync.Map with transactions, autoexpiry, capacity limit and record ordering. It is similar to a non-blocking ordered map where writes do not block reads. Each value is wrapped in a record type and uses its own RWMutex.

Record ordering

The default order is insertion order. Records are inserted to the back of cache's list and when overflow occurs, the front element is evicted.

When LFU ordering is used, then records which had accumulated hits since its last move will be periodically moved forwards in the list based on the hit count delta. Eventually the list becomes LFU ordered.

Eviction callback

The cache provides an eviction callback for each record which can be used to safely dispose of stored values after all usage has stopped.

Transactions and eviction mode

The cache uses waitgroups wrapped in io.Closer to track records returned to the user which forms a transaction. Transactions behave depending of EvictionMode. There are two kinds of modes: the ModeNonBlocking which is the default mode and ModeBlocking.

Non-blocking mode

In ModeNonBlocking mode, an active transaction does not prevent a key from being concurrently overwritten.

For example, if there are multiple goroutines running Cache.Fetch in a loop and a key expires, the next fetcher will set a new value which will eventually propagate to all loops.

The hot swap is unnoticeable while in the background, the eviction callback waits for transactions for the old value to finish and then runs.

It is not safe to use Cache.Evict concurrently in this mode - the concurrent new value may be falsely evicted! To safely evict records in the non-blocking mode see the documentation on Cache.CompareAndEvict.

Blocking mode

In ModeBlocking mode, an active transaction and eviction callback prevent a key from being concurrently overwritten.

The swap is noticeable to users since calls to Fetch (only when it stores) and Set for that key will block until the transactions and callback finish.

It is guaranteed that while holding an active transaction, a concurrent call to Cache.Evict for that key returns the exact same value to the first caller. Subsequent callers, in a transaction for that key, return false.

Documentation

Overview

Package evcache provides a sync.Map wrapper with specific concurrency guarantees.

Index

• Variables
• type Builder
  • func New() Builder
  • func (build Builder) Build() *Cache
  • func (build Builder) WithCapacity(cap uint32) Builder
  • func (build Builder) WithEvictionCallback(cb EvictionCallback) Builder
  • func (build Builder) WithEvictionMode(mode EvictionMode) Builder
  • func (build Builder) WithLFU() Builder
• type Cache
  • func (c *Cache) Close() error
  • func (c *Cache) CompareAndEvict(key, value interface{}) bool
  • func (c *Cache) Do(f func(key, value interface{}) bool)
  • func (c *Cache) Evict(key interface{}) (value interface{}, ok bool)
  • func (c *Cache) Exists(key interface{}) bool
  • func (c *Cache) Fetch(key interface{}, ttl time.Duration, f FetchCallback) (value interface{}, closer io.Closer, err error)
  • func (c *Cache) Flush()
  • func (c *Cache) Get(key interface{}) (value interface{}, closer io.Closer, exists bool)
  • func (c *Cache) Len() int
  • func (c *Cache) Pop() (key, value interface{})
  • func (c *Cache) Range(f func(key, value interface{}) bool)
  • func (c *Cache) Set(key, value interface{}, ttl time.Duration)
• type EvictionCallback
• type EvictionMode
• type FetchCallback

Variables

var SyncInterval = time.Second

SyncInterval is the interval for background loop which runs when autoexpiry or LFU is enabled.

If cache overflows while LFU is enabled and records are created faster than SyncInterval can update record ordering, the eviction starts losing LFU order and will become the insertion order with eldest first.

Types

type Builder

type Builder func(*Cache)

Builder builds a cache.

func New

func New() Builder

New creates an empty cache.

Cache must be closed after usage has stopped to prevent leaking resources.

It is not safe to close the cache while in use.

func (Builder) Build

func (build Builder) Build() *Cache

Build the cache.

func (Builder) WithCapacity

func (build Builder) WithCapacity(cap uint32) Builder

WithCapacity configures the cache with specified capacity.

If cache exceeds the limit, the eldest record is evicted or if LFU is enabled, the least frequently used record is evicted.

func (Builder) WithEvictionCallback

func (build Builder) WithEvictionCallback(cb EvictionCallback) Builder

WithEvictionCallback specifies an asynchronous eviction callback. After record is evicted from cache, the callback is guaranteed to run.

func (Builder) WithEvictionMode

func (build Builder) WithEvictionMode(mode EvictionMode) Builder

WithEvictionMode specifies an eviction blocking mode.

The default mode is ModeNonBlocking.

func (Builder) WithLFU

func (build Builder) WithLFU() Builder

WithLFU enables eventual LFU ordering of records.

type Cache

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

Cache is an in-memory ordered cache.

func (*Cache) Close

func (c *Cache) Close() error

Close shuts down the cache, evicts all keys and waits for eviction callbacks to finish.

It is not safe to close the cache while in use.

func (*Cache) CompareAndEvict

func (c *Cache) CompareAndEvict(key, value interface{}) bool

CompareAndEvict evicts the key only if its value is deeply equal to old. It is safe to use when every new value for key is unique.

If values are recycled using sync.Pool, then in the presence of writers for key where the new value originates from the pool, this method must return before it is safe to pool the value again.

func (*Cache) Do

func (c *Cache) Do(f func(key, value interface{}) bool)

Do calls f sequentially for each key and value present in the cache, by default in insertion order. In LFU mode, keys are visited from least to most frequently accessed. If f returns false, the iteration stops.

Do blocks writers and skips keys with a pending FetchCallback. f is not allowed to modify the cache unless it does so in a new goroutine.

func (*Cache) Evict

func (c *Cache) Evict(key interface{}) (value interface{}, ok bool)

Evict evicts a key and returns its value. It skips keys with a pending FetchCallback.

func (*Cache) Exists

func (c *Cache) Exists(key interface{}) bool

Exists returns whether a value in the cache exists for key. It does not block.

func (*Cache) Fetch

func (c *Cache) Fetch(key interface{}, ttl time.Duration, f FetchCallback) (value interface{}, closer io.Closer, err error)

Fetch attempts to get or set the value and calls f on a miss to receive the new value. If f returns an error, no value is cached and the error is returned back to caller. It begins a transaction for key.

When the returned value is not used anymore, the caller MUST call closer.Close() or a memory leak will occur.

If the cache has a capacity limit and it is exceeded then depending on mode, the eldest or the least frequently used record is evicted.

It waits for concurrent FetchCallbacks for key to finish. In ModeBlocking, if the loaded key was concurrently evicted, it waits for transactions and EvictionCallback to finish.

If the value exists, Fetch will not block.

func (*Cache) Flush

func (c *Cache) Flush()

Flush evicts all keys from the cache. It skips keys with a pending FetchCallback.

func (*Cache) Get

func (c *Cache) Get(key interface{}) (value interface{}, closer io.Closer, exists bool)

Get returns the value stored in the cache for a key and begins a transaction. The boolean indicates whether a value was found. It does not block and returns a zero result when FetchCallback for key runs.

When the returned value is not used anymore, the caller MUST call closer.Close() or a memory leak will occur.

func (*Cache) Len

func (c *Cache) Len() int

Len returns the number of keys in the cache.

func (*Cache) Pop

func (c *Cache) Pop() (key, value interface{})

Pop evicts and returns the first key and value. By default, it returns the oldest key. In LFU mode, the least frequently used key is returned. It skips keys with a pending FetchCallback.

func (*Cache) Range

func (c *Cache) Range(f func(key, value interface{}) bool)

Range calls f for each key and value present in the cache in no particular order. If f returns false, Range stops the iteration. It does not block and skips keys with a pending FetchCallback. Range is allowed to modify the cache.

Range does not necessarily correspond to any consistent snapshot of the cache's contents: no key will be visited more than once, but if the value for any key is stored or deleted concurrently, Range may reflect any mapping for that key from any point during the Range call.

func (*Cache) Set

func (c *Cache) Set(key, value interface{}, ttl time.Duration)

Set the value in the cache for a key.

If the cache has a capacity limit and it is exceeded then depending on mode, the eldest or the least frequently used record is evicted.

When overwriting a key, Set may wait for concurrent FetchCallbacks to finish and evicts the old key. In ModeBlocking, it waits for transactions and EvictionCallback to finish.

type EvictionCallback

type EvictionCallback func(key, value interface{})

EvictionCallback is guaranteed to run in a new goroutine when a cache record is evicted.

It runs after all transactions for key have finished regardless of eviction mode.

type EvictionMode

type EvictionMode int

EvictionMode specifies how transactions and eviction callback behave.

A transaction is the io.Closer returned with each record.

const (
	// ModeNonBlocking allows keys to be overwritten while having active transactions.
	//
	// This is the default mode.
	ModeNonBlocking EvictionMode = iota

	// ModeBlocking configures transactions and EvictionCallback
	// to block writers for the same key after being evicted.
	ModeBlocking
)

type FetchCallback

type FetchCallback func() (interface{}, error)

FetchCallback is called when *Cache.Fetch has a miss and must return a new value or an error.

It blocks the key from being Set or Fetched concurrently.