ttl

package module
v3.0.0 Latest Latest
Warning

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

 Go to latest Published: Jul 13, 2021 License: MIT Imports: 5 Imported by: 0

README

TTL Cache + ExpirationHeap

Provides an in-memory cache with expiration and an ExpirationHeap that order the items using a TTL value

Documentation Release

ttl.Cache is a simple key/value cache in golang with the following functions:

  1. Expiration of items based on time, or custom function
  2. Loader function to retrieve missing keys can be provided. Additional Get calls on the same key block while fetching is in progress (groupcache style).
  3. Individual expiring time or global expiring time, you can choose
  4. Auto-Extending expiration on Get -or- DNS style TTL, see SkipTTLExtensionOnHit(bool)
  5. Can trigger callback on key expiration
  6. Cleanup resources by calling Close() at end of lifecycle.
  7. Thread-safe with comprehensive testing suite. This code is in production at bol.com on critical systems.

Note (issue #25): by default, due to historic reasons, the TTL will be reset on each cache hit and you need to explicitly configure the cache to use a TTL that will not get extended.

ttl.ExpirationHeap is a heap priority queue implementation but using an expiration time as the priority, this means that the entries in the queue are ordered using a TTL value. A NotifyCh es used to know when the first element in the queue is updated.

Build Status Go Report Card Coverage Status license

Usage

go get github.com/asgarciap/ttl/v3

You can copy it as a full standalone demo program. The first snippet is basic usage, where the second exploits more options in the cache.

ttl.Cache

Basic:

package main

import (
	"fmt"
	"time"

	"github.com/asgarciap/ttl/v3"
)

var notFound = ttl.ErrNotFound

func main() {
	var cache ttl.SimpleCache = ttl.NewCache()

	cache.SetTTL(time.Duration(10 * time.Second))
	cache.Set("MyKey", "MyValue")
	cache.Set("MyNumber", 1000)

	if val, err := cache.Get("MyKey"); err != notFound {
		fmt.Printf("Got it: %s\n", val)
	}

	cache.Remove("MyNumber")
	cache.Purge()
	cache.Close()
}

Advanced:

package main

import (
	"fmt"
	"time"

	"github.com/asgarciap/ttl/v3"
)

var (
	notFound = ttl.ErrNotFound
	isClosed = ttl.ErrClosed
)

func main() {
	newItemCallback := func(key string, value interface{}) {
		fmt.Printf("New key(%s) added\n", key)
	}
	checkExpirationCallback := func(key string, value interface{}) bool {
		if key == "key1" {
			// if the key equals "key1", the value
			// will not be allowed to expire
			return false
		}
		// all other values are allowed to expire
		return true
	}

	expirationCallback := func(key string, reason ttlcache.EvictionReason, value interface{}) {
		fmt.Printf("This key(%s) has expired because of %s\n", key, reason)
	}

	loaderFunction := func(key string) (data interface{}, ttl time.Duration, err error) {
		ttl = time.Second * 300
		data, err = getFromNetwork(key)

		return data, ttl, err
	}

	cache := ttl.NewCache()
	cache.SetTTL(time.Duration(10 * time.Second))
	cache.SetExpirationReasonCallback(expirationCallback)
	cache.SetLoaderFunction(loaderFunction)
	cache.SetNewItemCallback(newItemCallback)
	cache.SetCheckExpirationCallback(checkExpirationCallback)
	cache.SetCacheSizeLimit(2)

	cache.Set("key", "value")
	cache.SetWithTTL("keyWithTTL", "value", 10*time.Second)

	if value, exists := cache.Get("key"); exists == nil {
		fmt.Printf("Got value: %v\n", value)
	}
	if v, ttl, e := cache.GetWithTTL("key"); e == nil {
		fmt.Printf("Got value: %v which still have a ttl of: %v\n", v, ttl)
	}
	count := cache.Count()
	if result := cache.Remove("keyNNN"); result == notFound {
		fmt.Printf("Not found, %d items left\n", count)
	}
	cache.Set("key6", "value")
	cache.Set("key7", "value")
	metrics := cache.GetMetrics()
	fmt.Printf("Total inserted: %d\n", metrics.Inserted)

	cache.Close()

}

func getFromNetwork(key string) (string, error) {
	time.Sleep(time.Millisecond * 30)
	return "value", nil
}
ttl.ExpirationHeap

Any struct can be used as the heap entry as long the ExpirationHeapEntry interface is implemented.

package main

import (
	"fmt"
	"time"

	"github.com/asgarciap/ttl/v3"
)

type struct MyStruct {
	data string
	index int
	validUntil time.Time
}

func (m *MyStruct) SetIndex(index int) {
	m.index = index
}

func (m *MyStruct) GetIndex() int {
	return m.index
}

func (m *MyStruct) ExpiresAt() {
	return m.validUntil
}

func main() {
	heap := ttl.NewExpirationHeap()
	//Just start a simple goroutine to check when the first position is updated
	go func() {
		for {
			<-heap.NotifyCh
			fmt.Printf("Heap first element was updated")
		}
	}()
	entry := &MyStruct{
		data: "MyValue",
		validUntil: time.Now().Add(10*time.Second),
	}
	heap.Add(entry)
	entry2 := &MyStruct{
		data: "MyValue_2",
		validUntil: time.Now().Add(5*time.Second),
	}
	//Get the first element without removing it from the heap
	v := heap.Peek()
	//This should print: Got it MyValue_2
	fmt.Printf("Got it: %v":,v.(*MyStruct).value)
	//after updating the TTL, the item should be moved to the first position
	entry.validUntil = time.Now().Add(1*time.Second)
	heap.Update(entry)
	//Get the first position and remove it from the heap
	v = heap.First()
	//This should print: Got it: MyValue
	fmt.Printf("Got it: %v":,v.(*MyStruct).value)
}
TTL Cache - Some design considerations
  1. The complexity of the current cache is already quite high. Therefore not all requests can be implemented in a straight-forward manner.
  2. The locking should be done only in the exported functions and startExpirationProcessing of the Cache struct. Else data races can occur or recursive locks are needed, which are both unwanted.
  3. I prefer correct functionality over fast tests. It's ok for new tests to take seconds to proof something.
Original Project

TTLCache was forked from ReneKroon/ttlcache which in turn is a fork from wunderlist/ttlcache to add extra functions not avaiable in the original scope.

The main differences that ReneKroon/ttlcache has from the original project are:

  1. A item can store any kind of object, previously, only strings could be saved
  2. Optionally, you can add callbacks too: check if a value should expire, be notified if a value expires, and be notified when new values are added to the cache
  3. The expiration can be either global or per item
  4. Items can exist without expiration time (time.Zero)
  5. Expirations and callbacks are realtime. Don't have a pooling time to check anymore, now it's done with a heap.
  6. A cache count limiter

This fork differs in the following aspects:

  1. We add a new GetWithTTL function to get the available TTL (as time.Duration) that an item has when recovering from the cache
  2. We rename the priority_queue.go file/struct to ExpirationHeap and expose it so we can use it independently
  3. Metrics for eviction are more detailed (EvictedFull, EvictedClosed, EvictedExpired)
  4. 100% test coverage
  5. Build checks are now done with github actions

Documentation

Index

Constants

View Source 
const (
	// ErrClosed is raised when operating on a cache where Close() has already been called.
	ErrClosed = constError("cache already closed")
	// ErrNotFound indicates that the requested key is not present in the cache
	ErrNotFound = constError("key not found")
)
View Source 
const (
	// ItemNotExpire Will avoid the item being expired by TTL, but can still be exired by callback etc.
	ItemNotExpire time.Duration = -1
	// ItemExpireWithGlobalTTL will use the global TTL when set.
	ItemExpireWithGlobalTTL time.Duration = 0
)
View Source 
const EntryNotIndexed = -1

EntryNotIndexed is the index value assigned to an entry that was removed from the heap

Variables

This section is empty.

Functions

This section is empty.

Types

type Cache 

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

Cache is a synchronized map of items that can auto-expire once stale

func NewCache 

func NewCache() *Cache

NewCache is a helper to create instance of the Cache struct

func (*Cache) Close 

func (cache *Cache) Close() error

Close calls Purge after stopping the goroutine that does ttl checking, for a clean shutdown. The cache is no longer cleaning up after the first call to Close, repeated calls are safe and return ErrClosed.

func (*Cache) Count 

func (cache *Cache) Count() int

Count returns the number of items in the cache. Returns zero when the cache has been closed.

func (*Cache) Get 

func (cache *Cache) Get(key string) (interface{}, error)

Get is a thread-safe way to lookup items Every lookup, also touches the item, hence extending it's life

func (*Cache) GetByLoader 

func (cache *Cache) GetByLoader(key string, customLoaderFunction LoaderFunction) (interface{}, time.Duration, error)

GetByLoader can take a per key loader function (ie. to propagate context)

func (*Cache) GetKeys 

func (cache *Cache) GetKeys() []string

GetKeys returns all keys of items in the cache. Returns nil when the cache has been closed.

func (*Cache) GetMetrics 

func (cache *Cache) GetMetrics() Metrics

GetMetrics exposes the metrics of the cache. This is a snapshot copy of the metrics.

func (*Cache) GetWithTTL 

func (cache *Cache) GetWithTTL(key string) (interface{}, time.Duration, error)

GetWithTTL has exactly the same behaviour as Get but also returns the remaining TTL for an specific item at the moment it its retrieved

func (*Cache) Purge 

func (cache *Cache) Purge() error

Purge will remove all entries

func (*Cache) Remove 

func (cache *Cache) Remove(key string) error

Remove removes an item from the cache if it exists, triggers expiration callback when set. Can return ErrNotFound if the entry was not present.

func (*Cache) Set 

func (cache *Cache) Set(key string, data interface{}) error

Set is a thread-safe way to add new items to the map.

func (*Cache) SetCacheSizeLimit 

func (cache *Cache) SetCacheSizeLimit(limit int)

SetCacheSizeLimit sets a limit to the amount of cached items. If a new item is getting cached, the closes item to being timed out will be replaced Set to 0 to turn off

func (*Cache) SetCheckExpirationCallback 

func (cache *Cache) SetCheckExpirationCallback(callback CheckExpireCallback)

SetCheckExpirationCallback sets a callback that will be called when an item is about to expire in order to allow external code to decide whether the item expires or remains for another TTL cycle

func (*Cache) SetExpirationCallback 

func (cache *Cache) SetExpirationCallback(callback ExpireCallback)

SetExpirationCallback sets a callback that will be called when an item expires

func (*Cache) SetExpirationReasonCallback 

func (cache *Cache) SetExpirationReasonCallback(callback ExpireReasonCallback)

SetExpirationReasonCallback sets a callback that will be called when an item expires, includes reason of expiry

func (*Cache) SetLoaderFunction 

func (cache *Cache) SetLoaderFunction(loader LoaderFunction)

SetLoaderFunction allows you to set a function to retrieve cache misses. The signature matches that of the Get function. Additional Get calls on the same key block while fetching is in progress (groupcache style).

func (*Cache) SetNewItemCallback 

func (cache *Cache) SetNewItemCallback(callback ExpireCallback)

SetNewItemCallback sets a callback that will be called when a new item is added to the cache

func (*Cache) SetTTL 

func (cache *Cache) SetTTL(ttl time.Duration) error

SetTTL sets the global TTL value for items in the cache, which can be overridden at the item level.

func (*Cache) SetWithTTL 

func (cache *Cache) SetWithTTL(key string, data interface{}, ttl time.Duration) error

SetWithTTL is a thread-safe way to add new items to the map with individual ttl.

func (*Cache) SkipTTLExtensionOnHit 

func (cache *Cache) SkipTTLExtensionOnHit(value bool)

SkipTTLExtensionOnHit allows the user to change the cache behaviour. When this flag is set to true it will no longer extend TTL of items when they are retrieved using Get, or when their expiration condition is evaluated using SetCheckExpirationCallback.

func (*Cache) Touch 

func (cache *Cache) Touch(key string) error

Touch resets the TTL of the key when it exists, returns ErrNotFound if the key is not present.

type CheckExpireCallback 

type CheckExpireCallback func(key string, value interface{}) bool

CheckExpireCallback is used as a callback for an external check on item expiration

type EvictionReason 

type EvictionReason int

EvictionReason is an enum that explains why an item was evicted 

const (
	// Removed : explicitly removed from cache via API call
	Removed EvictionReason = iota
	// EvictedSize : evicted due to exceeding the cache size
	EvictedSize
	// Expired : the time to live is zero and therefore the item is removed
	Expired
	// Closed : the cache was closed
	Closed
)

func EvictionReasonString 

func EvictionReasonString(s string) (EvictionReason, error)

EvictionReasonString retrieves an enum value from the enum constants string name. Throws an error if the param is not part of the enum.

func EvictionReasonValues 

func EvictionReasonValues() []EvictionReason

EvictionReasonValues returns all values of the enum

func (EvictionReason) IsAEvictionReason 

func (i EvictionReason) IsAEvictionReason() bool

IsAEvictionReason returns "true" if the value is listed in the enum definition. "false" otherwise

func (EvictionReason) String 

func (i EvictionReason) String() string

type ExpirationHeap 

type ExpirationHeap struct {

	//A channel used to notify when the first element (index=0)
	//in the heap has been modified
	NotifyCh chan struct{}
	// contains filtered or unexported fields
}

ExpirationHeap is the struct used in container/heap

func NewExpirationHeap 

func NewExpirationHeap() *ExpirationHeap

NewExpirationHeap creates a new ExpirationHeap

func (*ExpirationHeap) Add 

func (h *ExpirationHeap) Add(entry ExpirationHeapEntry)

Add a new entry in the heap

func (*ExpirationHeap) First 

func (h *ExpirationHeap) First() ExpirationHeapEntry

First get the first element in the heap (ie: the one with the lowest ttl)

func (ExpirationHeap) Len 

func (h ExpirationHeap) Len() int

Len meets the container/heap interface and returns the number of items in the queue

func (ExpirationHeap) Less 

func (h ExpirationHeap) Less(i, j int) bool

Less meets the container/heap interface and compare to item within the queue Dont call this directly!

func (*ExpirationHeap) NextExpiration 

func (h *ExpirationHeap) NextExpiration() time.Time

NextExpiration gets the lower ttl in the heap. The ttl from the element with index 0

func (*ExpirationHeap) Peek 

func (h *ExpirationHeap) Peek() ExpirationHeapEntry

Peek get the first element in the heap without removing it

func (*ExpirationHeap) Pop 

func (h *ExpirationHeap) Pop() interface{}

Pop meets the container/heap interface and removes the first item in the heap Don not call this directly!

func (*ExpirationHeap) Push 

func (h *ExpirationHeap) Push(x interface{})

Push meets the container/heap interface and inserts an item in the heap Dont call this directly!

func (*ExpirationHeap) Remove 

func (h *ExpirationHeap) Remove(entry ExpirationHeapEntry)

Remove removes an entry from the heap. Note that this just try to remove the entry acording to the index it has. It wont check if the object is really the same we are sending.

func (ExpirationHeap) Swap 

func (h ExpirationHeap) Swap(i, j int)

Swap meets the container/heap interface and change the position of 2 elements in the queue Dont call this directly!

func (*ExpirationHeap) Update 

func (h *ExpirationHeap) Update(entry ExpirationHeapEntry)

Update uptade an entry in the heap

type ExpirationHeapEntry 

type ExpirationHeapEntry interface {
	ExpiresAt() time.Time
	GetIndex() int
	SetIndex(int)
}

ExpirationHeapEntry is the interface that any entry we want to insert in the heap should meet. The ExpirationHeap will need to set and get the index used and to know when the entry will expire. Since we are not keeping the index ourself you must be sure than you dont modify the index value in your own entry implementation!! Use this with caution. We are relying in the Set/Get Index methods to keep the objects in the underlying heap. Do not change those ones in your entry object.

type ExpireCallback 

type ExpireCallback func(key string, value interface{})

ExpireCallback is used as a callback on item expiration or when notifying of an item new to the cache Note that ExpireReasonCallback will be the succesor of this function in the next major release.

type ExpireReasonCallback 

type ExpireReasonCallback func(key string, reason EvictionReason, value interface{})

ExpireReasonCallback is used as a callback on item expiration with extra information why the item expired.

type LoaderFunction 

type LoaderFunction func(key string) (data interface{}, ttl time.Duration, err error)

LoaderFunction can be supplied to retrieve an item where a cache miss occurs. Supply an item specific ttl or Duration.Zero

type Metrics 

type Metrics struct {
	// successful inserts
	Inserted int64
	// retrieval attempts
	Retrievals int64
	// all get calls that were in the cache (excludes loader invocations)
	Hits int64
	// entries not in cache (includes loader invocations)
	Misses int64
	// items removed from the cache due to a full size
	EvictedFull int64
	// items removed from the cache due to expiration
	EvictedExpired int64
	// items removed from the cache due to a close call
	EvictedClosed int64
}

Metrics contains common cache metrics so you can calculate hit and miss rates

type SimpleCache 

type SimpleCache interface {
	Get(key string) (interface{}, error)
	GetWithTTL(key string) (interface{}, time.Duration, error)
	Set(key string, data interface{}) error
	SetTTL(ttl time.Duration) error
	SetWithTTL(key string, data interface{}, ttl time.Duration) error
	Remove(key string) error
	Close() error
	Purge() error
}

SimpleCache interface enables a quick-start. Interface for basic usage.

Source Files

View all Source files

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.