README
¶
secache
Sampling Eviction Cache
Features
- Policy-agnostic: item validity is determined by user-provided function. That allows:
- Use of common expiration strategies such as TTL, LRU, ...
- Use of validity criterias specific for particular use case, such as item internal state, item usage statistics and so on.
- No full cache sweeps, no background goroutines for cleanup: expiration is handled probabilistically with certain dirty ratio guarantee.
- O(1) amortized time complexity for all operations.
- Adjustable space overhead for tradeoff between time and space.
- Simple and clear implementation well within 200 LOC.
- Support for complex operations within single critical section.
Example
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)
}
Documentation
¶
Overview ¶
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.
Example ¶
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
Index ¶
- 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
Examples ¶
Constants ¶
const MinN = 2
MinN is the minimal number of sampling evictions per element addition to ensure stable cache overhead.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Cache ¶
type Cache[K comparable, V any] struct { // contains filtered or unexported fields }
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.
func New ¶
func New[K comparable, V any](n int, f ValidityFunc[K, V]) *Cache[K, V]
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 (*Cache[K, V]) Delete ¶ added in v0.2.0
func (c *Cache[K, V]) Delete(key K)
Delete removes key from cache.
func (*Cache[K, V]) Do ¶
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.
Example ¶
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 (*Cache[K, V]) GetOrCreate ¶
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.
func (*Cache[K, V]) GetValidOrDelete ¶
GetValidOrDelete fetches valid key from cache or deletes it if it was found, but not valid.
type ValidityFunc ¶
type ValidityFunc[K comparable, V any] = func(K, V) bool
ValidityFunc is a function which used to check if element should stay in cache.
Source Files
Directories