CacheTower
CacheTower copied to clipboard
Least Recently Used (LRU) Eviction Strategy
Issue created from https://github.com/TurnerSoftware/CacheTower/issues/53#issuecomment-628631354
Currently the only eviction strategy is one of absolute time. If there was a method to define a "size" of cache, it would be worth exploring a "Least Recently Used" system to ensure that the hottest items stay in the cache.
Thoughts:
- Implement an extension (eg.
AutoEvict
/FixedCapacity
) that manages the more advanced eviction strategy - New extension tracks number of items in the cache, cache keys, expiry dates and last access dates
- Could use a LinkedList to track most recently used or a timestamp directly
- Probably easier with a
ConcurrentDictionary
with cache keys as the key and a custom type as the value
- Once a criteria has been hit (eg. X number of items in the cache), use what it knows to evict locally
Challenges:
- Keeping the extension up-to-date with cache data
- Can use the various extension hooks but still is a bit fiddly
- Only evicting locally
- Can do what I already do for
RedisRemoteEvictionExtension
(pass the cache layers in directly) but it is pretty cumbersome
- Can do what I already do for
Notes: To handle a distributed LRU would be excessively complex and likely not useful. Would mean that every access to a cache item (including local) would have to then broadcast that access back through the cache system and whatever distributed backends are used.
Might be worth investigating with or comparing against (when the time comes) this .NET caching solution which uses a LRU strategy: https://github.com/bitfaster/BitFaster.Caching
That would be fantastic. LRU and bounded size are two requirements for my usage scenario.
This is something we are looking for in our team. It would be excellent to have this implemented
Thanks for your feedback - it won't make the next release (coming in the next few days) but it is definitely something I'm looking into!
(For my own reference)
An interesting LFU cache implementation: https://github.com/papers-we-love/papers-we-love/blob/master/caching/a-constant-algorithm-for-implementing-the-lfu-cache-eviction-scheme.pdf
Not sure how applicable it is to this given its a LFU not an LRU plus it is a storage mechanism, not an eviction strategy. There still might be some useful pieces of information to extract from it.