ccache

package module
v3.0.5 Latest Latest
Warning

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

 Go to latest Published: Oct 22, 2023 License: MIT Imports: 6 Imported by: 26

README

CCache

Generic version is on the way: https://github.com/karlseguin/ccache/tree/generic

CCache is an LRU Cache, written in Go, focused on supporting high concurrency.

Lock contention on the list is reduced by:

  • Introducing a window which limits the frequency that an item can get promoted
  • Using a buffered channel to queue promotions for a single worker
  • Garbage collecting within the same thread as the worker

Unless otherwise stated, all methods are thread-safe.

The non-generic version of this cache can be imported via github.com/karlseguin/ccache/.

Configuration

Import and create a Cache instance:

import (
  github.com/karlseguin/ccache/v3
)

// create a cache with string values
var cache = ccache.New(ccache.Configure[string]())

Configure exposes a chainable API:

// creates a cache with int values
var cache = ccache.New(ccache.Configure[int]().MaxSize(1000).ItemsToPrune(100))

The most likely configuration options to tweak are:

  • MaxSize(int) - the maximum number size to store in the cache (default: 5000)
  • GetsPerPromote(int) - the number of times an item is fetched before we promote it. For large caches with long TTLs, it normally isn't necessary to promote an item after every fetch (default: 3)
  • ItemsToPrune(int) - the number of items to prune when we hit MaxSize. Freeing up more than 1 slot at a time improved performance (default: 500)

Configurations that change the internals of the cache, which aren't as likely to need tweaking:

  • Buckets - ccache shards its internal map to provide a greater amount of concurrency. Must be a power of 2 (default: 16).
  • PromoteBuffer(int) - the size of the buffer to use to queue promotions (default: 1024)
  • DeleteBuffer(int) the size of the buffer to use to queue deletions (default: 1024)

Usage

Once the cache is setup, you can Get, Set and Delete items from it. A Get returns an *Item:

Get
item := cache.Get("user:4")
if item == nil {
  //handle
} else {
  user := item.Value()
}

The returned *Item exposes a number of methods:

  • Value() T - the value cached
  • Expired() bool - whether the item is expired or not
  • TTL() time.Duration - the duration before the item expires (will be a negative value for expired items)
  • Expires() time.Time - the time the item will expire

By returning expired items, CCache lets you decide if you want to serve stale content or not. For example, you might decide to serve up slightly stale content (< 30 seconds old) while re-fetching newer data in the background. You might also decide to serve up infinitely stale content if you're unable to get new data from your source.

GetWithoutPromote

Same as Get but does not "promote" the value, which is to say it circumvents the "lru" aspect of this cache. Should only be used in limited cases, such as peaking at the value.

Set

Set expects the key, value and ttl:

cache.Set("user:4", user, time.Minute * 10)
Fetch

There's also a Fetch which mixes a Get and a Set:

item, err := cache.Fetch("user:4", time.Minute * 10, func() (*User, error) {
  //code to fetch the data incase of a miss
  //should return the data to cache and the error, if any
})

Fetch doesn't do anything fancy: it merely uses the public Get and Set functions. If you want more advanced behavior, such as using a singleflight to protect against thundering herd, support a callback that accepts the key, or returning expired items, you should implement that in your application.

Delete

Delete expects the key to delete. It's ok to call Delete on a non-existent key:

cache.Delete("user:4")
DeletePrefix

DeletePrefix deletes all keys matching the provided prefix. Returns the number of keys removed.

DeleteFunc

DeleteFunc deletes all items that the provided matches func evaluates to true. Returns the number of keys removed.

ForEachFunc

ForEachFunc iterates through all keys and values in the map and passes them to the provided function. Iteration stops if the function returns false. Iteration order is random.

Clear

Clear clears the cache. If the cache's gc is running, Clear waits for it to finish.

Extend

The life of an item can be changed via the Extend method. This will change the expiry of the item by the specified duration relative to the current time.

Replace

The value of an item can be updated to a new value without renewing the item's TTL or it's position in the LRU:

cache.Replace("user:4", user)

Replace returns true if the item existed (and thus was replaced). In the case where the key was not in the cache, the value is not inserted and false is returned.

Setnx

Set the value if not exists. setnx will first check whether kv exists. If it does not exist, set kv in cache. this operation is atomic.

cache.Set("user:4", user, time.Minute * 10)
GetDropped

You can get the number of keys evicted due to memory pressure by calling GetDropped:

dropped := cache.GetDropped()

The counter is reset on every call. If the cache's gc is running, GetDropped waits for it to finish; it's meant to be called asynchronously for statistics /monitoring purposes.

Stop

The cache's background worker can be stopped by calling Stop. Once Stop is called the cache should not be used (calls are likely to panic). Stop must be called in order to allow the garbage collector to reap the cache.

Tracking

CCache supports a special tracking mode which is meant to be used in conjunction with other pieces of your code that maintains a long-lived reference to data.

When you configure your cache with Track():

cache = ccache.New(ccache.Configure[int]().Track())

The items retrieved via TrackingGet will not be eligible for purge until Release is called on them:

item := cache.TrackingGet("user:4")
user := item.Value()   //will be nil if "user:4" didn't exist in the cache
item.Release()  //can be called even if item.Value() returned nil

In practice, Release wouldn't be called until later, at some other place in your code. TrackingSet can be used to set a value to be tracked.

There's a couple reason to use the tracking mode if other parts of your code also hold references to objects. First, if you're already going to hold a reference to these objects, there's really no reason not to have them in the cache - the memory is used up anyways.

More important, it helps ensure that your code returns consistent data. With tracking, "user:4" might be purged, and a subsequent Fetch would reload the data. This can result in different versions of "user:4" being returned by different parts of your system.

LayeredCache

CCache's LayeredCache stores and retrieves values by both a primary and secondary key. Deletion can happen against either the primary and secondary key, or the primary key only (removing all values that share the same primary key).

LayeredCache is useful for HTTP caching, when you want to purge all variations of a request.

LayeredCache takes the same configuration object as the main cache, exposes the same optional tracking capabilities, but exposes a slightly different API:

cache := ccache.Layered(ccache.Configure[string]())

cache.Set("/users/goku", "type:json", "{value_to_cache}", time.Minute * 5)
cache.Set("/users/goku", "type:xml", "<value_to_cache>", time.Minute * 5)

json := cache.Get("/users/goku", "type:json")
xml := cache.Get("/users/goku", "type:xml")

cache.Delete("/users/goku", "type:json")
cache.Delete("/users/goku", "type:xml")
// OR
cache.DeleteAll("/users/goku")

SecondaryCache

In some cases, when using a LayeredCache, it may be desirable to always be acting on the secondary portion of the cache entry. This could be the case where the primary key is used as a key elsewhere in your code. The SecondaryCache is retrieved with:

cache := ccache.Layered(ccache.Configure[string]())
sCache := cache.GetOrCreateSecondaryCache("/users/goku")
sCache.Set("type:json", "{value_to_cache}", time.Minute * 5)

The semantics for interacting with the SecondaryCache are exactly the same as for a regular Cache. However, one difference is that Get will not return nil, but will return an empty 'cache' for a non-existent primary key.

Size

By default, items added to a cache have a size of 1. This means that if you configure MaxSize(10000), you'll be able to store 10000 items in the cache.

However, if the values you set into the cache have a method Size() int64, this size will be used. Note that ccache has an overhead of ~350 bytes per entry, which isn't taken into account. In other words, given a filled up cache, with MaxSize(4096000) and items that return a Size() int64 of 2048, we can expect to find 2000 items (4096000/2048) taking a total space of 4796000 bytes.

Want Something Simpler?

For a simpler cache, checkout out rcache

Documentation

Overview

An LRU cached aimed at high concurrency

An LRU cached aimed at high concurrency

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Cache 

type Cache[T any] struct {
	*Configuration[T]
	// contains filtered or unexported fields
}

func New 

func New[T any](config *Configuration[T]) *Cache[T]

Create a new cache with the specified configuration See ccache.Configure() for creating a configuration

func (Cache) Clear 

func (c Cache) Clear()

Clears the cache This is a control command.

func (*Cache[T]) Delete 

func (c *Cache[T]) Delete(key string) bool

Remove the item from the cache, return true if the item was present, false otherwise.

func (*Cache[T]) DeleteFunc 

func (c *Cache[T]) DeleteFunc(matches func(key string, item *Item[T]) bool) int

Deletes all items that the matches func evaluates to true.

func (*Cache[T]) DeletePrefix 

func (c *Cache[T]) DeletePrefix(prefix string) int

func (*Cache[T]) Fetch 

func (c *Cache[T]) Fetch(key string, duration time.Duration, fetch func() (T, error)) (*Item[T], error)

Attempts to get the value from the cache and calles fetch on a miss (missing or stale item). If fetch returns an error, no value is cached and the error is returned back to the caller. Note that Fetch merely calls the public Get and Set functions. If you want a different Fetch behavior, such as thundering herd protection or returning expired items, implement it in your application.

func (*Cache[T]) ForEachFunc 

func (c *Cache[T]) ForEachFunc(matches func(key string, item *Item[T]) bool)

func (Cache) GC 

func (c Cache) GC()

Forces GC. There should be no reason to call this function, except from tests which require synchronous GC. This is a control command.

func (*Cache[T]) Get 

func (c *Cache[T]) Get(key string) *Item[T]

Get an item from the cache. Returns nil if the item wasn't found. This can return an expired item. Use item.Expired() to see if the item is expired and item.TTL() to see how long until the item expires (which will be negative for an already expired item).

func (Cache) GetDropped 

func (c Cache) GetDropped() int

Gets the number of items removed from the cache due to memory pressure since the last time GetDropped was called This is a control command.

func (Cache) GetSize 

func (c Cache) GetSize() int64

Gets the size of the cache. This is an O(1) call to make, but it is handled by the worker goroutine. It's meant to be called periodically for metrics, or from tests. This is a control command.

func (*Cache[T]) GetWithoutPromote 

func (c *Cache[T]) GetWithoutPromote(key string) *Item[T]

Same as Get but does not promote the value. This essentially circumvents the "least recently used" aspect of this cache. To some degree, it's akin to a "peak"

func (*Cache[T]) ItemCount 

func (c *Cache[T]) ItemCount() int

func (*Cache[T]) Replace 

func (c *Cache[T]) Replace(key string, value T) bool

Replace the value if it exists, does not set if it doesn't. Returns true if the item existed an was replaced, false otherwise. Replace does not reset item's TTL

func (*Cache[T]) Set 

func (c *Cache[T]) Set(key string, value T, duration time.Duration)

Set the value in the cache for the specified duration

func (Cache) SetMaxSize 

func (c Cache) SetMaxSize(size int64)

Sets a new max size. That can result in a GC being run if the new maxium size is smaller than the cached size This is a control command.

func (*Cache[T]) Setnx added in v3.0.5 

func (c *Cache[T]) Setnx(key string, value T, duration time.Duration)

Setnx set the value in the cache for the specified duration if not exists

func (Cache) Stop 

func (c Cache) Stop()

Sends a stop signal to the worker thread. The worker thread will shut down 5 seconds after the last message is received. The cache should not be used after Stop is called, but concurrently executing requests should properly finish executing. This is a control command.

func (Cache) SyncUpdates 

func (c Cache) SyncUpdates()

SyncUpdates waits until the cache has finished asynchronous state updates for any operations that were done by the current goroutine up to now.

For efficiency, the cache's implementation of LRU behavior is partly managed by a worker goroutine that updates its internal data structures asynchronously. This means that the cache's state in terms of (for instance) eviction of LRU items is only eventually consistent; there is no guarantee that it happens before a Get or Set call has returned. Most of the time application code will not care about this, but especially in a test scenario you may want to be able to know when the worker has caught up.

This applies only to cache methods that were previously called by the same goroutine that is now calling SyncUpdates. If other goroutines are using the cache at the same time, there is no way to know whether any of them still have pending state updates when SyncUpdates returns. This is a control command.

func (*Cache[T]) TrackingGet 

func (c *Cache[T]) TrackingGet(key string) TrackedItem[T]

Used when the cache was created with the Track() configuration option. Avoid otherwise

func (*Cache[T]) TrackingSet 

func (c *Cache[T]) TrackingSet(key string, value T, duration time.Duration) TrackedItem[T]

Used when the cache was created with the Track() configuration option. Sets the item, and returns a tracked reference to it.

type Configuration 

type Configuration[T any] struct {
	// contains filtered or unexported fields
}

func Configure 

func Configure[T any]() *Configuration[T]

Creates a configuration object with sensible defaults Use this as the start of the fluent configuration: e.g.: ccache.New(ccache.Configure().MaxSize(10000))

func (*Configuration[T]) Buckets 

func (c *Configuration[T]) Buckets(count uint32) *Configuration[T]

Keys are hashed into % bucket count to provide greater concurrency (every set requires a write lock on the bucket). Must be a power of 2 (1, 2, 4, 8, 16, ...) [16]

func (*Configuration[T]) DeleteBuffer 

func (c *Configuration[T]) DeleteBuffer(size uint32) *Configuration[T]

The size of the queue for items which should be deleted. If the queue fills up, calls to Delete() will block

func (*Configuration[T]) GetsPerPromote 

func (c *Configuration[T]) GetsPerPromote(count int32) *Configuration[T]

Give a large cache with a high read / write ratio, it's usually unnecessary to promote an item on every Get. GetsPerPromote specifies the number of Gets a key must have before being promoted [3]

func (*Configuration[T]) ItemsToPrune 

func (c *Configuration[T]) ItemsToPrune(count uint32) *Configuration[T]

The number of items to prune when memory is low [500]

func (*Configuration[T]) MaxSize 

func (c *Configuration[T]) MaxSize(max int64) *Configuration[T]

The max size for the cache [5000]

func (*Configuration[T]) OnDelete 

func (c *Configuration[T]) OnDelete(callback func(item *Item[T])) *Configuration[T]

OnDelete allows setting a callback function to react to ideam deletion. This typically allows to do a cleanup of resources, such as calling a Close() on cached object that require some kind of tear-down.

func (*Configuration[T]) PromoteBuffer 

func (c *Configuration[T]) PromoteBuffer(size uint32) *Configuration[T]

The size of the queue for items which should be promoted. If the queue fills up, promotions are skipped [1024]

func (*Configuration[T]) Track 

func (c *Configuration[T]) Track() *Configuration[T]

By turning tracking on and using the cache's TrackingGet, the cache won't evict items which you haven't called Release() on. It's a simple reference counter.

type Item 

type Item[T any] struct {
	// contains filtered or unexported fields
}

func (*Item[T]) Expired 

func (i *Item[T]) Expired() bool

func (*Item[T]) Expires 

func (i *Item[T]) Expires() time.Time

func (*Item[T]) Extend 

func (i *Item[T]) Extend(duration time.Duration)

func (*Item[T]) Key added in v3.0.4 

func (i *Item[T]) Key() string

func (*Item[T]) Release 

func (i *Item[T]) Release()

func (*Item[T]) String 

func (i *Item[T]) String() string

String returns a string representation of the Item. This includes the default string representation of its Value(), as implemented by fmt.Sprintf with "%v", but the exact format of the string should not be relied on; it is provided only for debugging purposes, and because otherwise including an Item in a call to fmt.Printf or fmt.Sprintf expression could cause fields of the Item to be read in a non-thread-safe way.

func (*Item[T]) TTL 

func (i *Item[T]) TTL() time.Duration

func (*Item[T]) Value 

func (i *Item[T]) Value() T

type LayeredCache 

type LayeredCache[T any] struct {
	*Configuration[T]
	// contains filtered or unexported fields
}

func Layered 

func Layered[T any](config *Configuration[T]) *LayeredCache[T]

See ccache.Configure() for creating a configuration

func (LayeredCache) Clear 

func (c LayeredCache) Clear()

Clears the cache This is a control command.

func (*LayeredCache[T]) Delete 

func (c *LayeredCache[T]) Delete(primary, secondary string) bool

Remove the item from the cache, return true if the item was present, false otherwise.

func (*LayeredCache[T]) DeleteAll 

func (c *LayeredCache[T]) DeleteAll(primary string) bool

Deletes all items that share the same primary key

func (*LayeredCache[T]) DeleteFunc 

func (c *LayeredCache[T]) DeleteFunc(primary string, matches func(key string, item *Item[T]) bool) int

Deletes all items that share the same primary key and where the matches func evaluates to true.

func (*LayeredCache[T]) DeletePrefix 

func (c *LayeredCache[T]) DeletePrefix(primary, prefix string) int

Deletes all items that share the same primary key and prefix.

func (*LayeredCache[T]) Fetch 

func (c *LayeredCache[T]) Fetch(primary, secondary string, duration time.Duration, fetch func() (T, error)) (*Item[T], error)

Attempts to get the value from the cache and calles fetch on a miss. If fetch returns an error, no value is cached and the error is returned back to the caller. Note that Fetch merely calls the public Get and Set functions. If you want a different Fetch behavior, such as thundering herd protection or returning expired items, implement it in your application.

func (*LayeredCache[T]) ForEachFunc 

func (c *LayeredCache[T]) ForEachFunc(primary string, matches func(key string, item *Item[T]) bool)

func (LayeredCache) GC 

func (c LayeredCache) GC()

Forces GC. There should be no reason to call this function, except from tests which require synchronous GC. This is a control command.

func (*LayeredCache[T]) Get 

func (c *LayeredCache[T]) Get(primary, secondary string) *Item[T]

Get an item from the cache. Returns nil if the item wasn't found. This can return an expired item. Use item.Expired() to see if the item is expired and item.TTL() to see how long until the item expires (which will be negative for an already expired item).

func (LayeredCache) GetDropped 

func (c LayeredCache) GetDropped() int

Gets the number of items removed from the cache due to memory pressure since the last time GetDropped was called This is a control command.

func (*LayeredCache[T]) GetOrCreateSecondaryCache 

func (c *LayeredCache[T]) GetOrCreateSecondaryCache(primary string) *SecondaryCache[T]

Get the secondary cache for a given primary key. This operation will never return nil. In the case where the primary key does not exist, a new, underlying, empty bucket will be created and returned.

func (LayeredCache) GetSize 

func (c LayeredCache) GetSize() int64

Gets the size of the cache. This is an O(1) call to make, but it is handled by the worker goroutine. It's meant to be called periodically for metrics, or from tests. This is a control command.

func (*LayeredCache[T]) GetWithoutPromote 

func (c *LayeredCache[T]) GetWithoutPromote(primary, secondary string) *Item[T]

Same as Get but does not promote the value. This essentially circumvents the "least recently used" aspect of this cache. To some degree, it's akin to a "peak"

func (*LayeredCache[T]) ItemCount 

func (c *LayeredCache[T]) ItemCount() int

func (*LayeredCache[T]) Replace 

func (c *LayeredCache[T]) Replace(primary, secondary string, value T) bool

Replace the value if it exists, does not set if it doesn't. Returns true if the item existed an was replaced, false otherwise. Replace does not reset item's TTL nor does it alter its position in the LRU

func (*LayeredCache[T]) Set 

func (c *LayeredCache[T]) Set(primary, secondary string, value T, duration time.Duration)

Set the value in the cache for the specified duration

func (LayeredCache) SetMaxSize 

func (c LayeredCache) SetMaxSize(size int64)

Sets a new max size. That can result in a GC being run if the new maxium size is smaller than the cached size This is a control command.

func (LayeredCache) Stop 

func (c LayeredCache) Stop()

Sends a stop signal to the worker thread. The worker thread will shut down 5 seconds after the last message is received. The cache should not be used after Stop is called, but concurrently executing requests should properly finish executing. This is a control command.

func (LayeredCache) SyncUpdates 

func (c LayeredCache) SyncUpdates()

SyncUpdates waits until the cache has finished asynchronous state updates for any operations that were done by the current goroutine up to now.

For efficiency, the cache's implementation of LRU behavior is partly managed by a worker goroutine that updates its internal data structures asynchronously. This means that the cache's state in terms of (for instance) eviction of LRU items is only eventually consistent; there is no guarantee that it happens before a Get or Set call has returned. Most of the time application code will not care about this, but especially in a test scenario you may want to be able to know when the worker has caught up.

This applies only to cache methods that were previously called by the same goroutine that is now calling SyncUpdates. If other goroutines are using the cache at the same time, there is no way to know whether any of them still have pending state updates when SyncUpdates returns. This is a control command.

func (*LayeredCache[T]) TrackingGet 

func (c *LayeredCache[T]) TrackingGet(primary, secondary string) TrackedItem[T]

Used when the cache was created with the Track() configuration option. Avoid otherwise

func (*LayeredCache[T]) TrackingSet 

func (c *LayeredCache[T]) TrackingSet(primary, secondary string, value T, duration time.Duration) TrackedItem[T]

Set the value in the cache for the specified duration

type List 

type List[T any] struct {
	Head *Node[T]
	Tail *Node[T]
}

func NewList 

func NewList[T any]() *List[T]

func (*List[T]) Insert 

func (l *List[T]) Insert(value T) *Node[T]

func (*List[T]) MoveToFront 

func (l *List[T]) MoveToFront(node *Node[T])

func (*List[T]) Remove 

func (l *List[T]) Remove(node *Node[T])

type Node 

type Node[T any] struct {
	Next  *Node[T]
	Prev  *Node[T]
	Value T
}

type SecondaryCache 

type SecondaryCache[T any] struct {
	// contains filtered or unexported fields
}

func (*SecondaryCache[T]) Delete 

func (s *SecondaryCache[T]) Delete(secondary string) bool

Delete a secondary key. The semantics are the same as for LayeredCache.Delete

func (*SecondaryCache[T]) Fetch 

func (s *SecondaryCache[T]) Fetch(secondary string, duration time.Duration, fetch func() (T, error)) (*Item[T], error)

Fetch or set a secondary key. The semantics are the same as for LayeredCache.Fetch

func (*SecondaryCache[T]) Get 

func (s *SecondaryCache[T]) Get(secondary string) *Item[T]

Get the secondary key. The semantics are the same as for LayeredCache.Get

func (*SecondaryCache[T]) Replace 

func (s *SecondaryCache[T]) Replace(secondary string, value T) bool

Replace a secondary key. The semantics are the same as for LayeredCache.Replace

func (*SecondaryCache[T]) Set 

func (s *SecondaryCache[T]) Set(secondary string, value T, duration time.Duration) *Item[T]

Set the secondary key to a value. The semantics are the same as for LayeredCache.Set

func (*SecondaryCache[T]) TrackingGet 

func (c *SecondaryCache[T]) TrackingGet(secondary string) TrackedItem[T]

Track a secondary key. The semantics are the same as for LayeredCache.TrackingGet

type Sized 

type Sized interface {
	Size() int64
}

type TrackedItem 

type TrackedItem[T any] interface {
	Value() T
	Release()
	Expired() bool
	TTL() time.Duration
	Expires() time.Time
	Extend(duration time.Duration)
}

Source Files

View all Source files

Directories

Path Synopsis
A wrapper around *testing.T. I hate the if a != b { t.ErrorF(....) } pattern.
 A wrapper around *testing.T. I hate the if a != b { t.ErrorF(....) } pattern.

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.