Documentation
¶
Overview ¶
Package sieve implements the SIEVE cache eviction algorithm. SIEVE stands in contrast to other eviction algorithms like LRU, 2Q, ARC with its simplicity. The original paper is in: https://yazhuozhang.com/assets/pdf/nsdi24-sieve.pdf
SIEVE is built on a FIFO queue - with an extra pointer (called "hand") in the paper. This "hand" plays a crucial role in determining who to evict next.
Index ¶
- type Sieve
- func (s *Sieve[K, V]) Add(key K, val V) bool
- func (s *Sieve[K, V]) Cap() int
- func (s *Sieve[K, V]) Delete(key K) bool
- func (s *Sieve[K, V]) Dump() string
- func (s *Sieve[K, V]) Get(key K) (V, bool)
- func (s *Sieve[K, V]) Len() int
- func (s *Sieve[K, V]) Probe(key K, val V) (V, bool)
- func (s *Sieve[K, V]) Purge()
- func (s *Sieve[K, V]) String() string
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Sieve ¶
type Sieve[K comparable, V any] struct { // contains filtered or unexported fields }
Sieve represents a cache mapping the key of type 'K' with a value of type 'V'. The type 'K' must implement the comparable trait. An instance of Sieve has a fixed max capacity; new additions to the cache beyond the capacity will cause cache eviction of other entries - as determined by the SIEVE algorithm.
func New ¶
func New[K comparable, V any](capacity int) *Sieve[K, V]
New creates a new cache of size 'capacity' mapping key 'K' to value 'V'
func (*Sieve[K, V]) Add ¶
Add adds a new element to the cache or overwrite one if it exists Return true if we replaced, false otherwise
func (*Sieve[K, V]) Delete ¶
Delete deletes the named key from the cache It returns true if the item was in the cache and false otherwise
func (*Sieve[K, V]) Get ¶
Get fetches the value for a given key in the cache. It returns true if the key is in the cache, false otherwise. The zero value for 'V' is returned when key is not in the cache.