Documentation
¶
Index ¶
- type SIEVECache
- func (c *SIEVECache[K, V]) Algorithm() string
- func (c *SIEVECache[K, V]) All() map[K]V
- func (c *SIEVECache[K, V]) Capacity() int
- func (c *SIEVECache[K, V]) Delete(key K) bool
- func (c *SIEVECache[K, V]) DeleteMany(keys []K) map[K]bool
- func (c *SIEVECache[K, V]) Get(key K) (value V, ok bool)
- func (c *SIEVECache[K, V]) GetMany(keys []K) (map[K]V, []K)
- func (c *SIEVECache[K, V]) Has(key K) bool
- func (c *SIEVECache[K, V]) HasMany(keys []K) map[K]bool
- func (c *SIEVECache[K, V]) Keys() []K
- func (c *SIEVECache[K, V]) Len() int
- func (c *SIEVECache[K, V]) Peek(key K) (value V, ok bool)
- func (c *SIEVECache[K, V]) PeekMany(keys []K) (map[K]V, []K)
- func (c *SIEVECache[K, V]) Purge()
- func (c *SIEVECache[K, V]) Range(f func(K, V) bool)
- func (c *SIEVECache[K, V]) Set(key K, value V)
- func (c *SIEVECache[K, V]) SetMany(items map[K]V)
- func (c *SIEVECache[K, V]) SizeBytes() int64
- func (c *SIEVECache[K, V]) Values() []V
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type SIEVECache ¶
type SIEVECache[K comparable, V any] struct { // contains filtered or unexported fields }
SIEVECache implements the SIEVE eviction algorithm as described in https://cachemon.github.io/SIEVE-website/
SIEVE maintains a list of entries with a "hand" pointer that scans for eviction victims. Each entry has a visited bit: on access it's set to true, and during eviction scanning, entries with visited=true are given a second chance (visited is cleared) while entries with visited=false are evicted.
References:
- [SIEVE is Simpler than LRU: an Efficient Turn-Key Eviction Algorithm for Web Caches](https://junchengyang.com/publication/nsdi24-SIEVE.pdf) (Zhang et al., NSDI 2024)
- [Why Aren't We SIEVE-ing?](https://brooker.co.za/blog/2023/12/15/sieve.html) (Mark Brooker, 2023)
It is not safe for concurrent access and should be wrapped with a thread-safe layer if needed.
The zero value is not usable.
func NewSIEVECache ¶
func NewSIEVECache[K comparable, V any](capacity int) *SIEVECache[K, V]
NewSIEVECache creates a new SIEVE cache with the specified capacity.
func NewSIEVECacheWithEvictionCallback ¶
func NewSIEVECacheWithEvictionCallback[K comparable, V any](capacity int, onEviction base.EvictionCallback[K, V]) *SIEVECache[K, V]
NewSIEVECacheWithEvictionCallback creates a new SIEVE cache with the specified capacity and eviction callback. The callback will be called whenever an item is evicted from the cache.
func (*SIEVECache[K, V]) Algorithm ¶
func (c *SIEVECache[K, V]) Algorithm() string
Algorithm returns the name of the eviction algorithm used by the cache.
func (*SIEVECache[K, V]) All ¶
func (c *SIEVECache[K, V]) All() map[K]V
All returns all key-value pairs in the cache.
func (*SIEVECache[K, V]) Capacity ¶
func (c *SIEVECache[K, V]) Capacity() int
Capacity returns the maximum number of items the cache can hold.
func (*SIEVECache[K, V]) Delete ¶
func (c *SIEVECache[K, V]) Delete(key K) bool
Delete removes a key from the cache. Returns true if the key was found and removed, false otherwise. Time complexity: O(1) average case.
func (*SIEVECache[K, V]) DeleteMany ¶
func (c *SIEVECache[K, V]) DeleteMany(keys []K) map[K]bool
DeleteMany removes multiple keys from the cache. Returns a map where keys are the input keys and values indicate if the key was found and removed.
func (*SIEVECache[K, V]) Get ¶
func (c *SIEVECache[K, V]) Get(key K) (value V, ok bool)
Get retrieves a value from the cache and marks it as visited. Returns the value and a boolean indicating if the key was found.
func (*SIEVECache[K, V]) GetMany ¶
func (c *SIEVECache[K, V]) GetMany(keys []K) (map[K]V, []K)
GetMany retrieves multiple values from the cache. Returns a map of found key-value pairs and a slice of missing keys.
func (*SIEVECache[K, V]) Has ¶
func (c *SIEVECache[K, V]) Has(key K) bool
Has checks if a key exists in the cache.
func (*SIEVECache[K, V]) HasMany ¶
func (c *SIEVECache[K, V]) HasMany(keys []K) map[K]bool
HasMany checks if multiple keys exist in the cache. Returns a map where keys are the input keys and values indicate existence.
func (*SIEVECache[K, V]) Keys ¶
func (c *SIEVECache[K, V]) Keys() []K
Keys returns all keys currently in the cache.
func (*SIEVECache[K, V]) Len ¶
func (c *SIEVECache[K, V]) Len() int
Len returns the current number of items in the cache.
func (*SIEVECache[K, V]) Peek ¶
func (c *SIEVECache[K, V]) Peek(key K) (value V, ok bool)
Peek retrieves a value from the cache without marking it as visited. Returns the value and a boolean indicating if the key was found.
func (*SIEVECache[K, V]) PeekMany ¶
func (c *SIEVECache[K, V]) PeekMany(keys []K) (map[K]V, []K)
PeekMany retrieves multiple values from the cache without marking them as visited. Returns a map of found key-value pairs and a slice of missing keys.
func (*SIEVECache[K, V]) Purge ¶
func (c *SIEVECache[K, V]) Purge()
Purge removes all keys and values from the cache.
func (*SIEVECache[K, V]) Range ¶
func (c *SIEVECache[K, V]) Range(f func(K, V) bool)
Range iterates over all key-value pairs in the cache. The iteration stops if the function returns false.
func (*SIEVECache[K, V]) Set ¶
func (c *SIEVECache[K, V]) Set(key K, value V)
Set stores a key-value pair in the cache. If the key already exists, its value is updated and visited bit is set. If the cache is at capacity, SIEVE eviction is performed to make room. Time complexity: O(1) average case, O(n) worst case when eviction scans entire cache.
func (*SIEVECache[K, V]) SetMany ¶
func (c *SIEVECache[K, V]) SetMany(items map[K]V)
SetMany stores multiple key-value pairs in the cache. This is more efficient than calling Set multiple times.
func (*SIEVECache[K, V]) SizeBytes ¶
func (c *SIEVECache[K, V]) SizeBytes() int64
SizeBytes returns the total size of all cache entries in bytes.
func (*SIEVECache[K, V]) Values ¶
func (c *SIEVECache[K, V]) Values() []V
Values returns all values currently in the cache.
Source Files