Useful building blocks for in-process caches.
Nuget: Install-Package Scaleout.Collections
API Documentation: https://scaleoutsoftware.github.io/ScaleoutCollectionsDotNet/
This library provides generic dictionaries designed to simplify the creation of an in-process cache. Two classes are available:
- RecentDictionary: A collection of keys and values that tracks the order in which entries are accessed, suitable for creating a cache with an LRU or MRU eviction policy.
- RouletteDictionary: A collection of keys and values that allows random entries to be retrieved or removed, suitable for creating a cache with a random eviction policy.
Both classes implement a SetAndMaintainCount method that can be used to set values while keeping the dictionary at a fixed size. If the operation results in a value being added, another entry will be removed to make room: The RecentDictionary will evict either the most-recently or least-recently used entry (depending on the eviction mode passed into the constructor), and RouletteDictionary will evict a random entry.
These collections simplfiy the creation of in-memory caches that require an eviction policy, often with better performance and lower memory usage than traditional approaches.
The RecentDictionary is a hybrid linked list and hash table--the LRU previous/next references are stored directly in hashtable bucket nodes. Performance for get/set operations are typically 20% faster than a traditional LRU cache where the dictionary and linked list are maintained as separate data structures. Memory savings will vary depending on key size.
Random eviction using a standard .NET Dictionary is not possible without maintaining a separate collection of keys. The RouletteDictionary addresses this by making it straightforward to retrieve or remove random elements.
The following sample illustrates how an LRU cache could be created using the RecentDictionary class.
usingScaleout.Collections;// A basic LRU cacheclassMyLruCache<TKey,TValue>{publicintMaxSize{get;}privateRecentDictionary<TKey,TValue>_entries;privateobject_guard=newobject();publicMyLruCache(intmaxSize){MaxSize=maxSize;_entries=newRecentDictionary<TKey,TValue>(capacity:maxSize,evictionMode:RecentDictionaryEvictionMode.LRU,comparer:null);}// Gets an item from the cache.publicTValueGet(TKeykey){lock(_guard){// TryGetValue() makes the entry the most-recently accessed:boolfound=_entries.TryGetValue(key,outTValueentry);if(found)returnentry;elsereturndefault;}}// Adds/updates an item in the cache.publicvoidSet(TKeykey,TValuevalue){lock(_guard){if(_entries.Count==MaxSize){// We're at our cache's capacity. SetAndMaintainCount will// cause the least recently used item to be evicted if a new// entry needs to be added._entries.SetAndMaintainCount(key,value);}else{// Not at a max capacity yet.// The ordinary setter does not perform eviction._entries[key]=value;}}}// Removes an item from the cache.publicvoidRemove(TKeykey){lock(_guard){_entries.Remove(key);}}}Apache 2