Documentation
¶
Overview ¶
Package eviction implements various cache eviction algorithms.
Index ¶
- type ARC
- type AlgorithmRegistry
- func (r *AlgorithmRegistry) NewAlgorithm(algorithmName string, capacity int) (IAlgorithm, error)
- func (r *AlgorithmRegistry) Register(name string, createFunc func(capacity int) (IAlgorithm, error))
- func (r *AlgorithmRegistry) RegisterMultiple(algorithms map[string]func(capacity int) (IAlgorithm, error))
- type CAWOLFU
- type CAWOLFULinkedList
- type CAWOLFUNode
- type ClockAlgorithm
- type FrequencyHeap
- type IAlgorithm
- type LFUAlgorithm
- type LRU
- type Node
- type Sharded
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ARC ¶
type ARC struct {
// contains filtered or unexported fields
}
ARC implements the Adaptive Replacement Cache (resident T1/T2 and ghost B1/B2).
func NewARCAlgorithm ¶
NewARCAlgorithm creates a new ARC with capacity.
type AlgorithmRegistry ¶
type AlgorithmRegistry struct {
// contains filtered or unexported fields
}
AlgorithmRegistry manages eviction algorithm constructors.
func NewAlgorithmRegistry ¶
func NewAlgorithmRegistry() *AlgorithmRegistry
NewAlgorithmRegistry creates a new algorithm registry.
func NewEmptyAlgorithmRegistry ¶
func NewEmptyAlgorithmRegistry() *AlgorithmRegistry
NewEmptyAlgorithmRegistry creates a new algorithm registry without default algorithms. This is useful for testing or when you want to register only specific algorithms.
func (*AlgorithmRegistry) NewAlgorithm ¶
func (r *AlgorithmRegistry) NewAlgorithm(algorithmName string, capacity int) (IAlgorithm, error)
NewAlgorithm creates a new eviction algorithm with the given capacity.
func (*AlgorithmRegistry) Register ¶
func (r *AlgorithmRegistry) Register(name string, createFunc func(capacity int) (IAlgorithm, error))
Register registers a new eviction algorithm with the given name.
func (*AlgorithmRegistry) RegisterMultiple ¶
func (r *AlgorithmRegistry) RegisterMultiple(algorithms map[string]func(capacity int) (IAlgorithm, error))
RegisterMultiple registers a set of eviction algorithms.
type CAWOLFU ¶
type CAWOLFU struct {
// contains filtered or unexported fields
}
CAWOLFU is an eviction algorithm that uses the Cache-Aware Write-Optimized LFU (CAWOLFU) policy to select items for eviction.
Concurrency: every method acquires c.mutex for the duration of the operation, so the items map needs no internal concurrency machinery — a plain map is sufficient. Previously this used pkg/cache.ConcurrentMap (v1) whose shard locks were redundant under cawolfu's own mutex.
func NewCAWOLFU ¶
NewCAWOLFU returns a new CAWOLFU with the given capacity.
type CAWOLFULinkedList ¶
type CAWOLFULinkedList struct {
// contains filtered or unexported fields
}
CAWOLFULinkedList is a struct that represents a linked list. It has a head and tail field.
type CAWOLFUNode ¶
type CAWOLFUNode struct {
// contains filtered or unexported fields
}
CAWOLFUNode is a struct that represents a node in the linked list. It has a key, value, and access count field.
type ClockAlgorithm ¶
type ClockAlgorithm struct {
// contains filtered or unexported fields
}
ClockAlgorithm is an in-memory cache with the Clock algorithm.
func NewClockAlgorithm ¶
func NewClockAlgorithm(capacity int) (*ClockAlgorithm, error)
NewClockAlgorithm creates a new in-memory cache with the given capacity and the Clock algorithm.
func (*ClockAlgorithm) Delete ¶
func (c *ClockAlgorithm) Delete(key string)
Delete deletes the item with the given key from the cache.
func (*ClockAlgorithm) Evict ¶
func (c *ClockAlgorithm) Evict() (string, bool)
Evict evicts an item from the cache based on the Clock algorithm.
func (*ClockAlgorithm) Get ¶
func (c *ClockAlgorithm) Get(key string) (any, bool)
Get retrieves the item with the given key from the cache.
func (*ClockAlgorithm) Set ¶
func (c *ClockAlgorithm) Set(key string, value any)
Set sets the item with the given key and value in the cache.
type FrequencyHeap ¶
type FrequencyHeap []*Node
FrequencyHeap is a heap of Nodes.
func (FrequencyHeap) Less ¶
func (fh FrequencyHeap) Less(i, j int) bool
Less returns true if the node at index i has a lower frequency than the node at index j.
func (*FrequencyHeap) Pop ¶
func (fh *FrequencyHeap) Pop() any
Pop removes the last node from the heap.
func (FrequencyHeap) Swap ¶
func (fh FrequencyHeap) Swap(i, j int)
Swap swaps the nodes at index i and j.
type IAlgorithm ¶
type IAlgorithm interface {
// Evict returns the next item to be evicted from the cache.
Evict() (string, bool)
// Set adds a new item to the cache with the given key.
Set(key string, value any)
// Get retrieves the item with the given key from the cache.
Get(key string) (any, bool)
// Delete removes the item with the given key from the cache.
Delete(key string)
}
IAlgorithm is the interface that must be implemented by eviction algorithms.
func NewEvictionAlgorithm ¶
func NewEvictionAlgorithm(algorithmName string, capacity int) (IAlgorithm, error)
NewEvictionAlgorithm creates a new eviction algorithm with the given capacity. It uses a new registry instance with default algorithms for each call. If the capacity is negative, it returns an error. The algorithmName parameter is used to select the eviction algorithm from the default algorithms.
type LFUAlgorithm ¶
type LFUAlgorithm struct {
// contains filtered or unexported fields
}
LFUAlgorithm is an eviction algorithm that uses the Least Frequently Used (LFU) policy to select items for eviction.
func NewLFUAlgorithm ¶
func NewLFUAlgorithm(capacity int) (*LFUAlgorithm, error)
NewLFUAlgorithm creates a new LFUAlgorithm with the given capacity.
func (*LFUAlgorithm) Delete ¶
func (l *LFUAlgorithm) Delete(key string)
Delete deletes a key-value pair from the cache.
func (*LFUAlgorithm) Evict ¶
func (l *LFUAlgorithm) Evict() (string, bool)
Evict evicts an item from the cache based on the LFU algorithm.
func (*LFUAlgorithm) Get ¶
func (l *LFUAlgorithm) Get(key string) (any, bool)
Get gets a value from the cache.
func (*LFUAlgorithm) Set ¶
func (l *LFUAlgorithm) Set(key string, value any)
Set sets a key-value pair in the cache.
type LRU ¶
type LRU struct {
sync.RWMutex // The mutex used to protect the cache
// contains filtered or unexported fields
}
LRU represents a LRU cache.
func NewLRUAlgorithm ¶
NewLRUAlgorithm creates a new LRU cache with the given capacity.
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
Node is a node in the LFUAlgorithm.
type Sharded ¶ added in v0.4.0
type Sharded struct {
// contains filtered or unexported fields
}
Sharded wraps shardCount independent IAlgorithm instances and routes each key to one shard via the same hash that pkg/cache/v2.ConcurrentMap uses. This eliminates the global mutex contention of single-instance algorithms (LRU/LFU/Clock) by replacing it with shardCount distinct mutexes.
Behavior change vs unsharded: items are evicted within their own shard, not in strict global LRU/LFU order. Total capacity is honored (sum of per-shard capacities). For users that need strict global-order eviction, construct the algorithm directly (or use shardCount=1 via WithEvictionShardCount(1)).
func NewSharded ¶ added in v0.4.0
NewSharded constructs a Sharded eviction wrapper. shardCount must be a power of two so the hash can be masked with `& (shardCount-1)`. Each underlying shard receives capacity ceil(totalCapacity / shardCount).
algorithmName is one of the registered algorithms (lru, lfu, clock, cawolfu). Each shard is an independent instance; they do not share state.
func (*Sharded) Evict ¶ added in v0.4.0
Evict picks a shard via round-robin and evicts from it. If that shard is empty, the next shard is tried until a non-empty one is found or all shards have been visited. Returns ("", false) only when all shards are empty.
Round-robin distributes eviction pressure across shards rather than always hitting the first non-empty one — relevant when one shard sees disproportionately fewer Set calls than others.
Source Files