README
¶
lfuda-go
Package lfuda provides a LFU with Dynamic Aging cache library
Why LFUDA?
There are many LRU and LFU cache policy implementations in go, but not any LFU with Dynamic Aging (as far as I could find). LFUDA builds upon simple LFU by accommodating shifts in the set of popular objects in the cache. This only becomes important when the cache is full since previously popular objects could remain for a long time or even indefinitely. This could prevent newly popular objects from being cached or replacing them. LFU with Aging policies attempt to address this with a tunable cache age factor to prevent previously popular documents from polluting the cache.
With Dynamic Aging/LFUDA, this is done in a parameter-less way, making it easier to manage compared to LFU with Aging.
How it works
In addition to basic LFU functionality it behaves according to the following logic:
- The cache dynamically "ages" through a global "age" counter
- Depending on the policy used, LFUDA or GreedyDual-Size with Frequency (GDSF), the priority key is determined by the item's frequency and the cache's age. If using GDSF the item's size is also a factor.
- Every cache eviction sets the global "age" counter to the evicted item's priority key,
- When setting a new item, its priority key counter should be set to the cache's "age" value
- When an existing item is updated, its hits counter is incremented by 1, and its priority key updated depending on the policy.
Usage
The default cache uses a LFUDA policy, like so:
onEvicted := func(k interface{}, v interface{}) {
if k != v {
fmt.Printf("Evicted values (%v: %v)\n", k, v)
}
}
l := lfuda.NewWithEvict(128, onEvicted)
for i := 0; i < 256; i++ {
if !l.Set(i, i) {
fmt.Printf("Setting key/value: %v: %v resulted in eviction\n", i, i)
}
}
for i := 0; i < 256; i++ {
if val, ok := l.Get(i); ok {
fmt.Printf("Key's %v value is %v\n", i, val)
} else {
fmt.Printf("Key %v not found in cache\n", i)
}
}
The GDSF policy is also available as an alternative
l := lfuda.NewGDSF(128)
for i := 0; i < 256; i++ {
if !l.Set(i, i) {
fmt.Printf("Setting key/value: %v: %v resulted in eviction\n", i, i)
}
}
Acknowledgements
- Paper outlining LFU with Dynamic Aging https://www.hpl.hp.com/techreports/98/HPL-98-173.pdf
- Squid proxy implementation https://www.hpl.hp.com/techreports/1999/HPL-1999-69.html
- O(1) LFU algorithm paper http://dhruvbird.com/lfu.pdf
- Nice LFU implementation in Go https://github.com/dgrijalva/lfu-go
- Interface patterned after golang-lru
Documentation
¶
Overview ¶
Package lfuda provides a Least Frequently Used with Dynamic Aging cache
In addition to basic LFU functionality it behaves according to the following logic: - The cache dynamically "ages" through a global "age" counter - Every cache eviction sets the global "age" counter to the evicted item's hits counter, - When setting a new item, its "hits" counter should be set to the cache's "age" value - When an existing item is updated, its "hits" counter is incremented by 1 to at least "age" + 1.
The cache in this package take locks while operating. Its therefore thread-safe and can be used with multiple goroutines
For use with a single goroutine (to avoid the locking overhead), the simplelfuda package can be used
Index ¶
- type Cache
- func New(size float64) *Cache
- func NewGDSF(size float64) *Cache
- func NewGDSFWithEvict(size float64, onEvicted func(key interface{}, value interface{})) *Cache
- func NewLFU(size float64) *Cache
- func NewLFUWithEvict(size float64, onEvicted func(key interface{}, value interface{})) *Cache
- func NewWithEvict(size float64, onEvicted func(key interface{}, value interface{})) *Cache
- func (c *Cache) Age() (age float64)
- func (c *Cache) Contains(key interface{}) bool
- func (c *Cache) ContainsOrSet(key, value interface{}) (ok, set bool)
- func (c *Cache) Get(key interface{}) (value interface{}, ok bool)
- func (c *Cache) Keys() []interface{}
- func (c *Cache) Len() (length int)
- func (c *Cache) Peek(key interface{}) (value interface{}, ok bool)
- func (c *Cache) PeekOrSet(key, value interface{}) (previous interface{}, ok, set bool)
- func (c *Cache) Purge()
- func (c *Cache) Remove(key interface{}) (present bool)
- func (c *Cache) Set(key, value interface{}) (ok bool)
- func (c *Cache) Size() (size float64)
Constants ¶
This section is empty.
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 lfuda cache.
func NewGDSF ¶ added in v0.3.0
NewGDSF creates an lfuda of the given size and the GDSF cache policy.
func NewGDSFWithEvict ¶ added in v0.3.0
NewGDSFWithEvict constructs a fixed GDSF size cache with the given eviction callback.
func NewLFUWithEvict ¶ added in v0.3.0
NewLFUWithEvict constructs a fixed size LFU cache with the given eviction callback.
func NewWithEvict ¶
NewWithEvict constructs a fixed size LFUDA cache with the given eviction callback.
func (*Cache) Contains ¶
Contains checks if a key is in the cache, without updating the recent-ness or deleting it for being stale.
func (*Cache) ContainsOrSet ¶
ContainsOrSet checks if a key is in the cache without updating the recent-ness or deleting it for being stale, and if not, adds the value. Returns whether found and whether the key/value was set or not.
func (*Cache) Keys ¶
func (c *Cache) Keys() []interface{}
Keys returns a slice of the keys in the cache, from oldest to newest.
func (*Cache) Peek ¶
Peek returns the key value (or undefined if not found) without updating the "recently used"-ness of the key.
func (*Cache) PeekOrSet ¶
PeekOrSet checks if a key is in the cache without updating the hits or deleting it for being stale, and if not, adds the value. Returns whether found and whether the key/value was set or not.
Source Files
Directories