README
¶
lru
A thread-safe, fixed-size, in-memory LRU cache that supports eviction, expiration, and out-of-band updates.
This cache is implemented as a lock-protected map whose values are elements in
two doubly linked lists (unlike a traditional LRU, which only uses one). The
first doubly linked list keeps track of upcoming evictions. It orders items by
how recently they have been used. When an item is added to the cache, or
retrieved via the Get method, it is moved to the front of this list. When an
item needs to be evicted during a call to Add (because the cache is full),
the item chosen for eviction is pulled from the back of this list.
The second doubly linked list keeps track of how soon items will expire. When items are added to the cache, they are added to the front of this list. A single worker goroutine - the "expiration worker" - reads from the back. If the item at the back is expired, it is removed from the cache. If it is not yet expired, the worker puts itself to sleep until it is scheduled to expire. Note that the worker may expire items early in order to avoid putting itself to sleep for very small amounts of time (configurable). A caveat of this design is that all items in the cache must share the same time-to-live (i.e. newly added items always expire after existing items).
If an update function is provided via SetUpdateFunc, expired items are
queued in a channel by the expiration worker, rather than simply being removed
from the cache (the default behavior). Updates are handled by a separate pool
of worker goroutines - the "update workers". These workers read from the
channel and call the user-provided update function with the key of an expired
item. Depending on the value of the status flag returned, they either update
the item with a new value, remove the item from the cache, or reset the item's
time-to-live without updating its value. If the item is not removed from the
cache, it is moved back to the front of the expiration list after the update.
Its position in the eviction list is not changed. It is also possible to
configure the cache to only update items if they have received a threshold
number of hits since the last addition/update. This ensures that unused items
are not needlessly incurring the cost of being updated.
Unit tests and benchmarks are provided.
For more information, see the documentation.
Documentation
¶
Overview ¶
A thread-safe, fixed-size, in-memory LRU cache that supports eviction, expiration, and out-of-band updates.
For more information, see: https://github.com/nathanjcochran/lru.
Index ¶
- Constants
- type Cache
- func (c *Cache) Add(key, val interface{}) (evicted bool)
- func (c *Cache) Contains(key interface{}) (ok bool)
- func (c *Cache) Get(key interface{}) (val interface{}, ok bool)
- func (c *Cache) Keys() []interface{}
- func (c *Cache) Len() int
- func (c *Cache) Peek(key interface{}) (val interface{}, ok bool)
- func (c *Cache) Purge()
- func (c *Cache) Remove(key interface{}) (ok bool)
- func (c *Cache) Stop()
- type Callback
- type Interface
- type Option
- func SetBufferSize(bufSize int) Option
- func SetOnBufferFull(onBufferFull Callback) Option
- func SetOnEvict(onEvict Callback) Option
- func SetOnExpire(onExpire Callback) Option
- func SetSize(size int) Option
- func SetTTL(ttl time.Duration) Option
- func SetTTLMargin(ttlMargin time.Duration) Option
- func SetUpdateFunc(update UpdateFunc) Option
- func SetUpdateThreshold(hits int) Option
- func SetWorkers(workers int) Option
- type Status
- type UpdateFunc
Constants ¶
const ( DefaultSize = 1024 DefaultTTL = time.Hour DefaultTTLMargin = time.Second DefaultWorkers = 1 DefaultBufSize = 256 DefaultUpdateThreshold = 0 )
Default configuration parameter values
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Cache ¶
type Cache struct {
// contains filtered or unexported fields
}
Cache is a thread-safe fixed-size LRU cache with a single worker goroutine that checks for expired items (see SetTTL and SetTTLMargin). If an UpdateFunc is provided (see SetUpdateFunc), updates are queued in a buffer (see SetBufferSize) and processed out-of-band via separate worker goroutines (see SetWorkers). If no UpdateFunc is provided, expired items are simply dropped from the cache (in which case, SetBufferSize and SetWorkers have no effect). Updates are not performed if the expired entry has fewer than a threshold number of hits since the last update (see SetUpdateThreshold).
func NewCache ¶
NewCache returns a new instance of a Cache, initialized with the provided configuration options. When the cache is no longer needed, it should be stopped via a call to Stop.
func (*Cache) Add ¶
Add inserts an entry into the cache with the specified key and value. If the cache is full (see SetSize), this will cause an eviction of the least recently used item. Returns a boolean indicating whether or not an eviction occurred.
func (*Cache) Contains ¶
Contains checks to see whether an item exists in the cache. The item's position in the list of recently-used items is not updated (see Get).
func (*Cache) Get ¶
Get returns the value corresponding to the provided key, if it exists in the cache. Also returns a boolean indicating whether or not it exists. The item's position in the list of recently-used items is updated.
func (*Cache) Keys ¶
func (c *Cache) Keys() []interface{}
Keys returns the keys of all of the entries in the cache, in least recently used order (i.e. the least recently used item first).
func (*Cache) Peek ¶
Peek returns the value corresponding to the provided key, if it exists in the cache. Also returns a boolean indicating whether or not it exists. The item's position in the list of recently-used items is not updated (see Get).
func (*Cache) Purge ¶
func (c *Cache) Purge()
Purge removes all items from the cache, resets the lists of least-recently-used and soon-to-expire items, and drains the update queue. Does not stop the background worker goroutines (see Stop).
type Callback ¶
type Callback func(key, val interface{})
Callback is used to indicate that a cache entry expired or was evicted, or that the update buffer is full (a sign that the workers were not able to update the items as fast as they were expiring). See SetOnEvict, SetOnExpire, and SetOnBufferFull.
type Interface ¶
type Interface interface {
Add(key, value interface{}) bool
Get(key interface{}) (value interface{}, ok bool)
Contains(key interface{}) (ok bool)
Peek(key interface{}) (value interface{}, ok bool)
Remove(key interface{}) bool
Keys() []interface{}
Len() int
Purge()
Stop()
}
Interface represents the interface for a Cache.
type Option ¶
type Option func(c *Cache)
Option is a configuration option which can be passed to NewCache to customize the operation of the LRU cache.
func SetBufferSize ¶
SetBufferSize sets the maximum size of the update buffer. If items expire faster than the workers can update them, they queue up in the buffer. If it fills up completely (see SetOnBufferFull), the expiration worker blocks, and therefore ceases to be able to expire items or queue updates.
func SetOnBufferFull ¶
SetOnBufferFull provides a callback that is called when the update buffer reaches its maximum size (see SetBufferSize) and the expiration worker cannot proceed. If it is being called often, it may be a good idea to increase the number of workers (see SetWorkers) or the time to live (see SetTTL), in addition to the buffer size itself. The key and value of item which could not be added to the queue are passed to the callback.
func SetOnEvict ¶
SetOnEvict provides a callback that is called when an item is evicted from the cache. Eviction happens when the cache has reached its maximum size (see SetSize) and a call is made to Add. The key and value of the evicted entry are passed to the callback. It it not called when an item is updated or removed from the cache.
func SetOnExpire ¶
SetOnExpire provides a callback that is called when an item expires from the cache. Expiration happens when an item's ttl has passed (see SetTTL) but the item is not updated, either because no UpdateFunc was given (see SetUpdateFunc) or because the entry did not meet the update hit threshold (see SetUpdateThreshold). The key and value of the expired entry are passed to the callback. It it not called when an item is updated or removed from the cache.
func SetSize ¶
SetSize sets the cache size. This is the maximum number of items the cache can hold before calls to Add cause the least recently used item to be evicted.
func SetTTL ¶
SetTTL sets the time to live for cache entires. Cache items expire after this amount of time, at which point they are either removed from the cache, or updated via the user-provided UpdateFunc.
func SetTTLMargin ¶
SetTTLMargin sets the minimum amount of time that the expiration worker will put itself to sleep for. If an entry expires sooner than that, the worker will expire it before its actual scheduled expiration time, in effect shortening its ttl by up to this amount.
func SetUpdateFunc ¶
func SetUpdateFunc(update UpdateFunc) Option
SetUpdateFunc provides a callback to be called when an item expires and needs to be updated with a new value. The function should return an up-to-date version of the value corresponding to the given key, as well as a status flag (see Status) indicating whether the entry should be updated with the new value (Update), left as-is until the next expiration (Pass), or removed from the cache (Remove). Pass is useful if there was an error fetching an item, but the error did not indicate that the item no longer exists, and availability is more important than returning up-to-date data.
func SetUpdateThreshold ¶
SetUpdateThreshold sets the hit threshold for cache updates. If an entry has not been hit (i.e. fetched via Get) at least this many times since its last addition/update, it will be removed (onExpire will be called), rather than incurring the cost of another call to UpdateFunc.
func SetWorkers ¶
SetWorkers sets the number of update worker groutines (note, however, that there is always one expiration worker). This is the maximum number of concurrent calls to UpdateFunc, and can be used to throttle/limit floods of calls to UpdateFunc. If this is not set high enough, however, the cache will not be able to keep up with expirations, causing the buffer to back up (see SetOnBufferFull). In general, this number should be greater than (size * updateTime) / ttl, where updateTime is the average duration of a call to UpdateFunc.
type Status ¶
type Status int8
Status is a status flag returned by UpdateFunc. Used to indicate how the cache should handle expired entries
const ( Update Status = iota // Update the value with the newly provided value Pass // Leave the existing value unchanged Remove // Remove the item from the cache entirely )
Implementations of UpdateFunc must return one of these three Status values to indicate how the cache should handle expired entries.
type UpdateFunc ¶
type UpdateFunc func(key interface{}) (newVal interface{}, status Status)
UpdateFunc is called when a cache entry expires. It should return an updated version of the value corresponding to the provided key, to replace the expired entry in the cache. Alternatively, it can trigger the removal of the entry from the cache, or opt to leave the item in the cache unchanged until its next expiration. See Status.
Source Files