hypercache

package module
v0.0.2-alpha Latest Latest
Warning

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

 Go to latest Published: Jan 4, 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:

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      33191691          125.6 ns/op          0 B/op          0 allocs/op
BenchmarkHyperCache_Set-16       4290988          1045 ns/op          88 B/op          3 allocs/op
PASS
ok      github.com/hyp3rd/hypercache/tests/benchmark       10.303s

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 itme 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

Overview

Copyright 2023 F. All rights reserved. Use of this source code is governed by a Mozilla Public License 2.0 license that can be found in the LICENSE file. HyperCache is an in-memory cache implementation in Go that supports the expiration and eviction of items.

Recently Used (LRU) eviction algorithm

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")
)
View Source 
var CacheItemPool = sync.Pool{
	New: func() interface{} {
		return &CacheItem{}
	},
}

CacheItemPool is a pool of CacheItem values.

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

ClockCacheItemPool is a pool of ClockCacheItem values.

Functions

func RegisterEvictionAlgorithm 

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

RegisterEvictionAlgorithm registers a new eviction algorithm 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. 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.

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, error)

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 CacheItem 

type CacheItem struct {
	Value      interface{}   // value of the item
	Expiration time.Duration // expiration duration of the item
	// contains filtered or unexported fields
}

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 ClockCache 

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

Clock represents a clock cache

func NewClockCache 

func NewClockCache(capacity int) (*ClockCache, error)

NewClockCache creates a new clock cache with the given capacity

func (*ClockCache) Delete 

func (clock *ClockCache) Delete(key string)

Delete removes the key-value pair from the cache.

func (*ClockCache) Evict 

func (clock *ClockCache) Evict() (string, error)

Evict first acquires a lock on the mutex, then it enters an infinite loop. Inside the loop, it checks if the cache is empty. If it is, it returns an error. Otherwise, it starts iterating through the linked list and looks for an item that has a reference count of 0. If it finds such an item, it removes it from the linked list and the map, releases the lock, and returns the key and a nil error. If it doesn't find an item with a reference count of 0, it sets all reference counts to 0 and waits on the condition variable. When the function is woken up, it will start the loop again and check for an item with a reference count of 0. This process continues until an item with a reference count of 0 is found.

func (*ClockCache) Get 

func (clock *ClockCache) Get(key string) (interface{}, bool)

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

func (*ClockCache) Set 

func (clock *ClockCache) Set(key string, value interface{})

Set adds the key-value pair to the cache. If the cache is at capacity, it evicts the least recently used item.

type ClockCacheItem 

type ClockCacheItem struct {
	Value interface{}
	// contains filtered or unexported fields
}

ClockCacheItem represents an item in the cache

type EvictionAlgorithm 

type EvictionAlgorithm interface {
	// Evict returns the next item to be evicted from the cache.
	Evict() (string, error)
	// 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)
}

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) Close 

func (cache *HyperCache) Close()

Close stops the expiration and eviction loops and closes the stop channel.

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) 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 (c *HyperCache) Stop()

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

func (*HyperCache) TriggerEviction 

func (c *HyperCache) TriggerEviction()

TriggerEviction sends a signal to the eviction loop to start.

type LRU 

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

func NewLRU 

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

func (*LRU) Delete 

func (lru *LRU) Delete(key string)

func (*LRU) Evict 

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

func (*LRU) Get 

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

func (*LRU) Set 

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

type LRUCacheItem 

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

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) - "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 WithExpirationriggerBufferSize 

func WithExpirationriggerBufferSize(expirationTriggerBufferSize uint) Option

WithExpirationTriggerBufferSize is an option that sets the expiration trigger buffer size field of the `HyperCache` struct. The expiration trigger buffer size determines how many items need to be added to the cache before an expiration run is triggered.

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(statsCollector StatsCollector) 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 stats.Stat, value int64)
	// Decr decrements the count of a statistic by the given value.
	Decr(stat stats.Stat, value int64)
	// Timing records the time it took for an event to occur.
	Timing(stat stats.Stat, value int64)
	// Gauge records the current value of a statistic.
	Gauge(stat stats.Stat, value int64)
	// Histogram records the statistical distribution of a set of values.
	Histogram(stat stats.Stat, value int64)
}

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

Source Files

View all Source files

Directories

Path Synopsis
examples
get
list

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.