hypercache

package module
v0.0.3-alpha Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 7, 2023 License: MPL-2.0 Imports: 10 Imported by: 0

README

HyperCache

Go CodeQL

Synopsis

HyperCache is a thread-safe and high-performance in-memory cache implementation in Go that supports items' background expiration and eviction. It is optimized for performance and flexibility. It uses a read/write lock to synchronize access to the cache with a custom implementation of a concurrent map. It also allows the user to specify the expiration and eviction intervals. It also enables devs to collect stats about the cache with the default stats collector or a custom one and to inject their own eviction algorithm and register it alongside the default ones:

Features
  • Store items in the cache with a key and expiration duration
  • Retrieve items from the cache by their key
  • Delete items from the cache by their key
  • Clear the cache of all items
  • Evitc items in the background based on the cache capacity and items access leveraging several custom eviction algorithms
  • Expire items in the background based on their duration
  • EvictionAlgorithm interface to implement custom eviction algorithms.
  • Stats collection with a default stats collector or a custom one that implements the StatsCollector interface.

Installation

Install HyperCache:

go get github.com/hyp3rd/hypercache
performance

Running the benchmarks on a 2019 MacBook Pro with a 2.4 GHz 8-Core Intel Core i9 processor and 32 GB 2400 MHz DDR4 memory, the results are as follows on average, using a pretty busy machine:

make bench
cd tests/benchmark && go test -bench=. -benchmem -benchtime=4s . -timeout 30m
goos: darwin
goarch: amd64
pkg: github.com/hyp3rd/hypercache/tests/benchmark
cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
BenchmarkHyperCache_Get-16                          38833602           123.9 ns/op         0 B/op          0 allocs/op
BenchmarkHyperCache_Get_ProactiveEviction-16        38079158           124.4 ns/op         0 B/op          0 allocs/op
BenchmarkHyperCache_Set-16                           4361000          1217 ns/op         203 B/op          3 allocs/op
BenchmarkHyperCache_Set_Proactive_Eviction-16        4343996          1128 ns/op          92 B/op          3 allocs/op
PASS
ok      github.com/hyp3rd/hypercache/tests/benchmark    23.723s
Examples

To run the examples, use the following command:

make run example=eviction  # or any other example

For a full list of examples, refer to the examples directory.

API

The NewHyperCache function creates a new HyperCache instance with the given capacity and initializes the eviction algorithm, applying any other configuration option. It also starts the expiration and eviction loops in separate goroutines.

To create a new cache with a given capacity, use the NewHyperCache function as described below:

cache, err := hypercache.NewHyperCache(100)
if err != nil {
    // handle error
}
Set

Set adds an item to the cache with the given key and value.

err := cache.Set("key", "value", time.Hour)
if err != nil {
    // handle error
}

The Set function takes a key, a value, and a duration as arguments. The key must be a non-empty string, the value can be of any type, and the duration specifies how long the item should stay in the cache before it expires.

Get

Get retrieves the item with the given key from the cache.

value, ok := cache.Get("key")
if !ok {
    // handle item not found
}

The Get function returns the value associated with the given key or an error if the key is not found or has expired.

Remove

Remove deletes items with the given key from the cache. If an item is not found, it does nothing.

err := cache.Remove("key", "key2", "key3")
if err != nil {
    // handle error
}

The Remove function takes a variadic number of keys as arguments and returns an error if any keys are not found.

For a comprehensive API overview, see the documentation.

Usage

Here is an example of using the HyperCache package. For a more comprehensive overview, see the examples directory.

package main

import (
    "fmt"
    "time"

    "github.com/hyp3rd/hypercache"
)

func main() {
    // create a new cache with a capacity of 100 items
    cache := hypercache.NewHyperCache(100)
    defer cache.Stop()

    // set a key-value pair in the cache with an expiration duration of 1 minute
    cache.Set("key", "value", time.Minute)

    // get the value for the key from the cache
    val, err := cache.Get("key")
    if err != nil {
        fmt.Println(err)
    } else {
        fmt.Println(val) // "value"
    }

    // wait for the item to expire
    time.Sleep(time.Minute)

    // try to get the value for the key again
    val, err = cache.Get("key")
    if err != nil {
        fmt.Println(err) // "key not found"
    }
}

License

The code and documentation in this project are released under Mozilla Public License 2.0.

Author

I'm a surfer, a crypto trader, and a software architect with 15 years of experience designing highly available distributed production environments and developing cloud-native apps in public and private clouds. Feel free to hook me up on LinkedIn.

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	// ErrInvalidKey is returned when an invalid key is used to access an item in the cache.
	// An invalid key is a key that is either empty or consists only of whitespace characters.
	ErrInvalidKey = errors.New("invalid key")

	// ErrKeyNotFound is returned when a key is not found in the cache.
	ErrKeyNotFound = errors.New("key not found")

	// ErrNilValue is returned when a nil value is attempted to be set in the cache.
	ErrNilValue = errors.New("nil value")

	// ErrKeyExpired is returned when a key is found in the cache but has expired.
	ErrKeyExpired = errors.New("key expired")

	// ErrInvalidExpiration is returned when an invalid expiration is passed to a cache item.
	ErrInvalidExpiration = errors.New("expiration cannot be negative")

	// ErrInvalidCapacity is returned when an invalid capacity is passed to the cache.
	ErrInvalidCapacity = errors.New("capacity cannot be negative")

	// ErrAlgorithmNotFound is returned when an algorithm is not found.
	ErrAlgorithmNotFound = errors.New("algorithm not found")

	// ErrStatsCollectorNotFound is returned when an algorithm is not found.
	ErrStatsCollectorNotFound = errors.New("stats collector not found")

	// ErrParamCannotBeEmpty is returned when a parameter cannot be empty.
	ErrParamCannotBeEmpty = errors.New("param cannot be empty")
)
View Source 
var CAWOLFUNodePool = sync.Pool{
	New: func() interface{} {
		return &CAWOLFUNode{}
	},
}

CAWOLFUNodePool is a pool of CAWOLFUNode values.

View Source 
var CacheItemPool = sync.Pool{
	New: func() interface{} {
		return &CacheItem{}
	},
}

CacheItemPool is a pool of CacheItem values.

View Source 
var LFUNodePool = sync.Pool{
	New: func() interface{} {
		return &Node{}
	},
}

LFUNodePool is a pool of Node values.

View Source 
var LRUCacheItemmPool = sync.Pool{
	New: func() interface{} {
		return &LRUCacheItem{}
	},
}

LRUCacheItemmPool is a pool of LRUCacheItemm values.

View Source 
var StatsCollectorRegistry = make(map[string]func() (StatsCollector, error))

StatsCollectorRegistry holds the a registry of stats collectors.

Functions

func RegisterEvictionAlgorithm 

func RegisterEvictionAlgorithm(name string, createFunc func(capacity int) (EvictionAlgorithm, error))

RegisterEvictionAlgorithm registers a new eviction algorithm with the given name.

func RegisterStatsCollector 

func RegisterStatsCollector(name string, createFunc func() (StatsCollector, error))

RegisterStatsCollector registers a new stats collector with the given name.

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 NewARC 

func NewARC(capacity int) (*ARC, error)

NewARC 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) Delete 

func (arc *ARC) Delete(key string)

Delete removes the item with the given key from the cache.

func (*ARC) Evict 

func (arc *ARC) Evict() (string, bool)

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.

func (*ARC) Get 

func (arc *ARC) Get(key string) (interface{}, bool)

Get retrieves the item with the given key from the cache. If the key is not found in the cache, it returns nil.

func (*ARC) Set 

func (arc *ARC) Set(key string, value interface{})

Set adds a new item to the cache with the given key.

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 

func NewCAWOLFU(capacity int) (*CAWOLFU, error)

NewCAWOLFU returns a new CAWOLFU with the given capacity.

func (*CAWOLFU) Delete 

func (c *CAWOLFU) Delete(key string)

Delete removes the given key from the cache.

func (*CAWOLFU) Evict 

func (c *CAWOLFU) Evict() (string, bool)

Evict returns the next item to be evicted from the cache.

func (*CAWOLFU) Get 

func (c *CAWOLFU) Get(key string) (interface{}, bool)

Get returns the value for the given key from the cache. If the key is not in the cache, it returns false.

func (*CAWOLFU) Set 

func (c *CAWOLFU) Set(key string, value interface{})

Set adds a new item to the cache with the given key.

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 CacheItem 

type CacheItem struct {
	// Key        string        // key of the item
	Value      interface{}   // value of the item
	Expiration time.Duration // expiration duration of the item
	// Expiration  int64     // monotonic clock value in nanoseconds
	LastAccess  time.Time // last access time of the item
	AccessCount uint      // number of times the item has been accessed
}

CacheItem is a struct that represents an item in the cache. It has a key, value, expiration duration, and a last access time field.

func (*CacheItem) Expired 

func (item *CacheItem) Expired() bool

Expired returns true if the item has expired, false otherwise.

func (*CacheItem) FieldByName 

func (item *CacheItem) FieldByName(name string) reflect.Value

FieldByName returns the value of the field of the CacheItem struct with the given name. If the field does not exist, an empty reflect.Value is returned.

func (*CacheItem) Touch 

func (item *CacheItem) Touch()

Touch updates the last access time of the item and increments the access count.

func (*CacheItem) Valid 

func (item *CacheItem) Valid() error

Valid returns an error if the item is invalid, nil otherwise.

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 the least recently used item from the cache.

func (*ClockAlgorithm) Get 

func (c *ClockAlgorithm) Get(key string) (interface{}, bool)

Get retrieves the item with the given key from the cache.

func (*ClockAlgorithm) Set 

func (c *ClockAlgorithm) Set(key string, value interface{})

Set sets the item with the given key and value in the cache.

type EvictionAlgorithm 

type EvictionAlgorithm 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 interface{})
	// Get retrieves the item with the given key from the cache.
	Get(key string) (interface{}, bool)
	// Delete removes the item with the given key from the cache.
	Delete(key string)
}

EvictionAlgorithm is the interface that must be implemented by eviction algorithms.

func NewEvictionAlgorithm 

func NewEvictionAlgorithm(algorithmName string, capacity int) (EvictionAlgorithm, error)

NewEvictionAlgorithm creates a new eviction algorithm with the given capacity. If the capacity is negative, it returns an error. The algorithmName parameter is used to select the eviction algorithm from the registry.

type FilteringOption 

type FilteringOption func(*HyperCache)

FilteringOption is a function type that can be used to filter out the items held in the `HyperCache`.

func WithFilter 

func WithFilter(fn func(item *CacheItem) bool) FilteringOption

WithFilter is an option that sets the filter function to use. The filter function is a predicate that takes a `CacheItem` as an argument and returns a boolean indicating whether the item should be included in the cache.

func WithSortAscending 

func WithSortAscending() FilteringOption

WithSortAscending is an option that sets the sort order to ascending. When sorting the items in the cache, they will be sorted in ascending order based on the field specified with the `WithSortBy` option.

func WithSortBy 

func WithSortBy(field types.SortingField) FilteringOption

WithSortBy is an option that sets the field to sort the items by. The field can be any of the fields in the `CacheItem` struct.

func WithSortDescending 

func WithSortDescending() FilteringOption

WithSortDescending is an option that sets the sort order to descending. When sorting the items in the cache, they will be sorted in descending order based on the field specified with the `WithSortBy` option.

type HyperCache 

type HyperCache struct {
	// contains filtered or unexported fields
}

HyperCache is an in-memory cache that stores items with a key and expiration duration. It has a custom ConcurrentMap 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 stop channel is used to signal the expiration and eviction loops to stop. The evictCh channel is used to signal the eviction loop to start.

func NewHyperCache 

func NewHyperCache(capacity int, options ...Option) (cache *HyperCache, err error)

NewHyperCache creates a new in-memory cache with the given capacity. If the capacity is negative, it returns an error. The function initializes the items map, and starts the expiration and eviction loops in separate goroutines.

func (*HyperCache) Capacity 

func (cache *HyperCache) Capacity() int

Capacity returns the capacity of the cache.

func (*HyperCache) Clear 

func (cache *HyperCache) Clear()

Clear removes all items from the cache.

func (*HyperCache) Get 

func (cache *HyperCache) Get(key string) (value interface{}, ok bool)

Get retrieves the item with the given key from the cache. If the item is not found, it returns nil.

func (*HyperCache) GetMultiple 

func (cache *HyperCache) GetMultiple(keys ...string) (result map[string]interface{}, errors map[string]error)

GetMultiple retrieves the items with the given keys from the cache. If an item is not found, it is not included in the returned map.

func (*HyperCache) GetOrSet 

func (cache *HyperCache) GetOrSet(key string, value interface{}, expiration time.Duration) (interface{}, error)

GetOrSet retrieves the item with the given key from the cache. If the item is not found, it adds the item to the cache with the given value and expiration duration. If the capacity of the cache is reached, the cache will evict the least recently used item before adding the new item.

func (*HyperCache) GetStats added in v0.0.4 

func (cache *HyperCache) GetStats() stats.Stats

GetStats returns the stats collected by the cache. It returns a map where the keys are the stat names and the values are the stat values.

func (*HyperCache) List 

func (cache *HyperCache) List(options ...FilteringOption) ([]*CacheItem, error)

List lists the items in the cache that meet the specified criteria.

func (*HyperCache) Remove 

func (cache *HyperCache) Remove(keys ...string)

Remove removes items with the given key from the cache. If an item is not found, it does nothing.

func (*HyperCache) Set 

func (cache *HyperCache) Set(key string, value interface{}, expiration time.Duration) error

Set adds an item to the cache with the given key and value. If an item with the same key already exists, it updates the value of the existing item. If the expiration duration is greater than zero, the item will expire after the specified duration. If the capacity of the cache is reached, the cache will evict the least recently used item before adding the new item.

func (*HyperCache) SetCapacity 

func (cache *HyperCache) SetCapacity(capacity int)

SetCapacity sets the capacity of the cache. If the new capacity is smaller than the current number of items in the cache, it evicts the excess items from the cache.

func (*HyperCache) Size 

func (cache *HyperCache) Size() int

Size returns the number of items in the cache.

func (*HyperCache) Stop 

func (cache *HyperCache) Stop()

Stop function stops the expiration and eviction loops and closes the stop channel.

func (*HyperCache) TriggerEviction 

func (cache *HyperCache) TriggerEviction()

TriggerEviction sends a signal to the eviction loop to start.

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 returns a new LFUAlgorithm with the given capacity.

func (*LFUAlgorithm) Delete 

func (l *LFUAlgorithm) Delete(key string)

Delete removes the given key from the cache.

func (*LFUAlgorithm) Evict 

func (l *LFUAlgorithm) Evict() (string, bool)

Evict returns the next item to be evicted from the cache.

func (*LFUAlgorithm) Get 

func (l *LFUAlgorithm) Get(key string) (interface{}, bool)

Get returns the value for the given key from the cache. If the key is not in the cache, it returns false.

func (*LFUAlgorithm) Set 

func (l *LFUAlgorithm) Set(key string, value interface{})

Set adds a new item to the cache with the given key.

type LRU 

type LRU struct {
	// contains filtered or unexported fields
}

LRU represents a LRU cache

func NewLRU 

func NewLRU(capacity int) (*LRU, error)

NewLRU creates a new LRU cache with the given capacity

func (*LRU) Delete 

func (lru *LRU) Delete(key string)

Delete removes the given key from the cache.

func (*LRU) Evict 

func (lru *LRU) Evict() (string, bool)

Evict removes the least recently used item from the cache and returns its key.

func (*LRU) Get 

func (lru *LRU) Get(key string) (interface{}, bool)

Get retrieves the value for the given key from the cache. If the key is not

func (*LRU) Set 

func (lru *LRU) Set(key string, value interface{})

Set sets the value for the given key in the cache. If the key is not already in the cache, it is added. If the cache is full, the least recently used item is evicted.

type LRUCacheItem 

type LRUCacheItem struct {
	Key   string
	Value interface{}
	// contains filtered or unexported fields
}

LRUCacheItem represents an item in the LRU cache

type LinkedList 

type LinkedList struct {
	// contains filtered or unexported fields
}

LinkedList is a struct that represents a linked list. It has a head and tail field.

type Node 

type Node struct {
	// contains filtered or unexported fields
}

Node is a struct that represents a node in the linked list. It has a key, value, and access count field.

type Option 

type Option func(*HyperCache)

Option is a function type that can be used to configure the `HyperCache` struct.

func EvictionAlgorithmName 

func EvictionAlgorithmName(name string) Option

EvictionAlgorithmName is an option that sets the eviction algorithm name field of the `HyperCache` struct. The eviction algorithm name determines which eviction algorithm will be used to evict items from the cache. The eviction algorithm name must be one of the following: - "LRU" (Least Recently Used) - Implemented in the `lru.go` file - "LFU" (Least Frequently Used) - Implemented in the `lfu.go` file - "CAWOLFU" (Cache-Aware Write-Optimized LFU) - Implemented in the `cawolfu.go` file - "FIFO" (First In First Out) - "RANDOM" (Random) - "CLOCK" (Clock) - Implemented in the `clock.go` file - "ARC" (Adaptive Replacement Cache) - Implemented in the `arc.go` file - "TTL" (Time To Live) - "LFUDA" (Least Frequently Used with Dynamic Aging) - "SLRU" (Segmented Least Recently Used)

func WithEvictionInterval 

func WithEvictionInterval(evictionInterval time.Duration) Option

WithEvictionInterval is an option that sets the eviction interval field of the `HyperCache` struct. The eviction interval determines how often the cache will run the eviction process to remove the least recently used items.

func WithExpirationInterval 

func WithExpirationInterval(expirationInterval time.Duration) Option

WithExpirationInterval is an option that sets the expiration interval field of the `HyperCache` struct. The expiration interval determines how often the cache will check for and remove expired items.

func WithMaxEvictionCount 

func WithMaxEvictionCount(maxEvictionCount uint) Option

WithMaxEvictionCount is an option that sets the max eviction count field of the `HyperCache` struct. The max eviction count determines the maximum number of items that can be removed during a single eviction run.

func WithStatsCollector 

func WithStatsCollector(name string) Option

WithStatsCollector is an option that sets the stats collector field of the `HyperCache` struct. The stats collector is used to collect statistics about the cache.

type StatsCollector 

type StatsCollector interface {
	// Incr increments the count of a statistic by the given value.
	Incr(stat types.Stat, value int64)
	// Decr decrements the count of a statistic by the given value.
	Decr(stat types.Stat, value int64)
	// Timing records the time it took for an event to occur.
	Timing(stat types.Stat, value int64)
	// Gauge records the current value of a statistic.
	Gauge(stat types.Stat, value int64)
	// Histogram records the statistical distribution of a set of values.
	Histogram(stat types.Stat, value int64)
	// GetStats returns the collected statistics.
	GetStats() stats.Stats
}

StatsCollector is an interface that defines the methods that a stats collector should implement.

func NewStatsCollector 

func NewStatsCollector(statsCollectorName string) (StatsCollector, error)

NewStatsCollector creates a new stats collector. The statsCollectorName parameter is used to select the stats collector from the registry.

Source Files

View all Source files

Directories

Path Synopsis
examples
eviction
get
list
stats

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.