Package secache implements sampling eviction cache, a generic cache with arbitrary expiration criteria defined by validity function provided by user. It offers O(1) am. time complexity for all operations and very flexible notion of element validity, which is useful when usual approaches based on item age do not provide reasonable approximation or fit at all.
package main
import (
"fmt"
"strings"
"time"
"github.com/Snawoot/secache"
)
func main() {
// demonstrates use of cache as a usual TTL cache
const TTL = 1 * time.Minute
type CacheItem struct {
expires time.Time
value string
}
c := secache.New[string, *CacheItem](3, func(key string, item *CacheItem) bool {
return time.Now().Before(item.expires)
})
key := "some key"
item, ok := c.GetValidOrDelete(key)
fmt.Println(item)
if !ok {
c.Set(key, &CacheItem{
expires: time.Now().Add(TTL),
value: strings.ToTitle(key),
})
}
item, ok = c.GetValidOrDelete(key)
fmt.Printf("%q %t", item.value, ok)
}
Output: <nil> "SOME KEY" true
- Constants
- type Cache
- func (c *Cache[K, V]) Delete(key K)
- func (c *Cache[K, V]) Do(f func(*randmap.RandMap[K, V]))
- func (c *Cache[K, V]) Flush()
- func (c *Cache[K, V]) Get(key K) (value V, ok bool)
- func (c *Cache[K, V]) GetOrCreate(key K, newValFunc func() V) (value V)
- func (c *Cache[K, V]) GetValidOrDelete(key K) (value V, ok bool)
- func (c *Cache[K, V]) Len() (l int)
- func (c *Cache[K, V]) Set(key K, value V)
- func (c *Cache[K, V]) SetLocked(m *randmap.RandMap[K, V], key K, value V)
- type ValidityFunc
MinN is the minimal number of sampling evictions per element addition to ensure stable cache overhead.
This section is empty.
This section is empty.
Cache implements a generic multipurpose cache which uses sampling eviction to maintain stable ratio of evictable and valid elements.
Each time new element is added, cache makes n attempts to pick random cache element, test its validity and remove invalid one. This way it maintains dynamic equilibrium around certain rate of evictable elements, trading space for eviction efforts and flexibility. In many cases, however, space saved by more accurate custom eviction criteria may make up for space overhead compared to classical TTL cache which approximate object validity with its age.
All cache operations have O(1) am. time complexity.
Cache object is safe for concurrent use by multiple goroutines.
New creates new cache instance with n sampling eviction attempts per element addition. Validity of sampled elements is tested with function f.
In practical terms, n corresponds to cache overhead goal, how many invalid elements on average will be there in a long run.
Useful n values are:
2 - ~50% of invalid elements, ~100% overhead 3 - ~33.(3)% of invalid elements, ~50% overhead 4 - ~25% of invalid elements, ~33.(3)% overhead 5 - ~20% of invalid elements, ~25% overhead 6 - ~16.(6)% of invalid elements, ~20% overhead 7 - ~14.28% of invalid elements, ~16.(6)% overhead 8 - ~12.5% of invalid elements, ~14.28% overhead 9 - ~11.(1)% of invalid elements, ~12.5% overhead 10 - ~10% of invalid elements, ~11.(1)% overhead 11 - ~9.(09)% of invalid elements, ~10% overhead
func (c *Cache[K, V]) Delete(key K)
Delete removes key from cache.
Do acquires lock and exposes storage to a provided function f. f should not operate on cache object, but only on provided storage. Provided storage reference is valid only within f.
package main
import (
"fmt"
"github.com/Snawoot/secache"
"github.com/Snawoot/secache/randmap"
)
func main() {
// demonstrates cache item increment
c := secache.New[string, int](2, func(_ string, _ int) bool {
return true
})
c.Set("a", 1)
c.Set("b", 2)
incrKey := "c"
c.Do(func(m *randmap.RandMap[string, int]) {
old, _ := m.Get(incrKey)
m.Set(incrKey, old+1)
})
val, _ := c.Get(incrKey)
fmt.Printf("c[%q] = %d\n", incrKey, val)
}
Output: c["c"] = 1
func (c *Cache[K, V]) Flush()
Flush empties cache.
func (c *Cache[K, V]) GetOrCreate(key K, newValFunc func() V) (value V)
GetOrCreate fetches valid key from cache or creates new one with provided function.
GetValidOrDelete fetches valid key from cache or deletes it if it was found, but not valid.
func (c *Cache[K, V]) Set(key K, value V)
Set adds new item to cache or updates existing one and then runs sampling eviction if new item was added.
SetLocked is an utility function which adds or updates key with proper expiration logic. It is intended to be used within Do(f) transaction.
ValidityFunc is a function which used to check if element should stay in cache.