Documentation
¶
Overview ¶
Package eviction ARC is an in-memory cache that uses the Adaptive Replacement Cache (ARC) algorithm to manage its items. It has a map of items to store the items in the cache, and a capacity field that limits the number of items that can be stored in the cache. The ARC algorithm uses two lists, t1 and t2, to store the items in the cache. The p field represents the "promotion threshold", which determines how many items should be stored in t1. The c field represents the current number of items in the cache.
Package eviction CAWOLFU is an eviction algorithm that uses the Cache-Aware Write-Optimized LFU (CAWOLFU) policy to select items for eviction.
Package eviction - The clock eviction algorithm is a page replacement algorithm that uses a clock-like data structure to keep track of which pages in a computer's memory have been used recently and which have not. It works by maintaining a circular buffer of pages, with a "hand" that points to the next page to be replaced. When a page needs to be evicted from memory, the hand is advanced to the next page in the buffer, and that page is evicted if it has not been used recently. If the page has been used recently, the hand is advanced to the next page, and the process repeats until a page is found that can be evicted. The clock eviction algorithm is often used in virtual memory systems to manage the allocation of physical memory.
Package eviction - Least Frequently Used (LFU) eviction algorithm implementation ¶
Package eviction - The Least Recently Used (LRU) eviction algorithm is a page replacement algorithm that discards the least recently used pages first. It works by maintaining a queue of pages in memory, with the most recently used page at the front of the queue and the least recently used page at the back. When a new page is added to memory and the memory is full, the page at the back of the queue (the least recently used page) is removed to make space for the new page. To implement the LRU eviction algorithm, a data structure called a doubly linked list is often used. Each page in the list is represented by a node, which contains a pointer to the previous node and a pointer to the next node. When a page is accessed, it is moved to the front of the list by updating the pointers of the surrounding nodes. This way, the page at the back of the list is always the least recently used page, and can be easily removed when necessary. The LRU eviction algorithm is widely used because it performs well in practice, with a low average page fault rate. However, it can be somewhat expensive to implement, as it requires updating the data structure every time a page is accessed.
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
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 is an in-memory cache that uses the Adaptive Replacement Cache (ARC) algorithm to manage its items.
func NewARCAlgorithm ¶
NewARCAlgorithm creates a new in-memory cache with the given capacity and the Adaptive Replacement Cache (ARC) algorithm. If the capacity is negative, it returns an error.
func (*ARC) Evict ¶
Evict removes an item from the cache and returns the key of the evicted item. If no item can be evicted, it returns an error.
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.
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.
Source Files