I wanted to ask you what is the best approach to implement a cache in C#? Is there a possibility by using given .NET classes or something like that? Perhaps something like a dictionary that will remove some entries, if it gets too large, but where whose entries won't be removed by the garbage collector?
12 Answers
As mentioned in other answers, the default choice using the .NET Framework is MemoryCache and the various related implementations in Microsoft NuGet packages (e.g. Microsoft.Extensions.Caching.MemoryCache). All of these caches bound size in terms of memory used, and attempt to estimate memory used by tracking how total physical memory is increasing relative to the number of cached objects. A background thread then periodically 'trims' entries.
MemoryCache etc. share some limitations:
- Keys are strings, so if the key type is not natively string, you will be forced to constantly allocate strings on the heap. This can really add up in a server application when items are 'hot'.
- Has poor 'scan resistance' - e.g. if some automated process is rapidly looping through all the items in that exist, the cache size can grow too fast for the background thread to keep up. This can result in memory pressure, page faults, induced GC or when running under IIS, recycling the process due to exceeding the private bytes limit.
- Does not scale well with concurrent writes.
- Contains perf counters that cannot be disabled (which incur overhead).
Your workload will determine the degree to which these things are problematic. An alternative approach to caching is to bound the number of objects in the cache (rather than estimating memory used). A cache replacement policy then determines which object to discard when the cache is full.
Below is the source code for a simple cache with least recently used eviction policy:
public sealed class ClassicLru<K, V>
{
private readonly int capacity;
private readonly ConcurrentDictionary<K, LinkedListNode<LruItem>> dictionary;
private readonly LinkedList<LruItem> linkedList = new LinkedList<LruItem>();
private long requestHitCount;
private long requestTotalCount;
public ClassicLru(int capacity)
: this(Defaults.ConcurrencyLevel, capacity, EqualityComparer<K>.Default)
{
}
public ClassicLru(int concurrencyLevel, int capacity, IEqualityComparer<K> comparer)
{
if (capacity < 3)
{
throw new ArgumentOutOfRangeException("Capacity must be greater than or equal to 3.");
}
if (comparer == null)
{
throw new ArgumentNullException(nameof(comparer));
}
this.capacity = capacity;
this.dictionary = new ConcurrentDictionary<K, LinkedListNode<LruItem>>(concurrencyLevel, this.capacity + 1, comparer);
}
public int Count => this.linkedList.Count;
public double HitRatio => (double)requestHitCount / (double)requestTotalCount;
///<inheritdoc/>
public bool TryGet(K key, out V value)
{
Interlocked.Increment(ref requestTotalCount);
LinkedListNode<LruItem> node;
if (dictionary.TryGetValue(key, out node))
{
LockAndMoveToEnd(node);
Interlocked.Increment(ref requestHitCount);
value = node.Value.Value;
return true;
}
value = default(V);
return false;
}
public V GetOrAdd(K key, Func<K, V> valueFactory)
{
if (this.TryGet(key, out var value))
{
return value;
}
var node = new LinkedListNode<LruItem>(new LruItem(key, valueFactory(key)));
if (this.dictionary.TryAdd(key, node))
{
LinkedListNode<LruItem> first = null;
lock (this.linkedList)
{
if (linkedList.Count >= capacity)
{
first = linkedList.First;
linkedList.RemoveFirst();
}
linkedList.AddLast(node);
}
// Remove from the dictionary outside the lock. This means that the dictionary at this moment
// contains an item that is not in the linked list. If another thread fetches this item,
// LockAndMoveToEnd will ignore it, since it is detached. This means we potentially 'lose' an
// item just as it was about to move to the back of the LRU list and be preserved. The next request
// for the same key will be a miss. Dictionary and list are eventually consistent.
// However, all operations inside the lock are extremely fast, so contention is minimized.
if (first != null)
{
dictionary.TryRemove(first.Value.Key, out var removed);
if (removed.Value.Value is IDisposable d)
{
d.Dispose();
}
}
return node.Value.Value;
}
return this.GetOrAdd(key, valueFactory);
}
public bool TryRemove(K key)
{
if (dictionary.TryRemove(key, out var node))
{
// If the node has already been removed from the list, ignore.
// E.g. thread A reads x from the dictionary. Thread B adds a new item, removes x from
// the List & Dictionary. Now thread A will try to move x to the end of the list.
if (node.List != null)
{
lock (this.linkedList)
{
if (node.List != null)
{
linkedList.Remove(node);
}
}
}
if (node.Value.Value is IDisposable d)
{
d.Dispose();
}
return true;
}
return false;
}
// Thead A reads x from the dictionary. Thread B adds a new item. Thread A moves x to the end. Thread B now removes the new first Node (removal is atomic on both data structures).
private void LockAndMoveToEnd(LinkedListNode<LruItem> node)
{
// If the node has already been removed from the list, ignore.
// E.g. thread A reads x from the dictionary. Thread B adds a new item, removes x from
// the List & Dictionary. Now thread A will try to move x to the end of the list.
if (node.List == null)
{
return;
}
lock (this.linkedList)
{
if (node.List == null)
{
return;
}
linkedList.Remove(node);
linkedList.AddLast(node);
}
}
private class LruItem
{
public LruItem(K k, V v)
{
Key = k;
Value = v;
}
public K Key { get; }
public V Value { get; }
}
}
This is just to illustrate a thread safe cache - it probably has bugs and can be a bottleneck under heavy concurrent workloads (e.g. in a web server).
A thoroughly tested, production ready, scalable concurrent implementation is a bit beyond a stack overflow post. To solve this in my projects, I implemented a thread safe pseudo LRU (think concurrent dictionary, but with constrained size). Performance is very close to a raw ConcurrentDictionary, ~10x faster than MemoryCache, ~10x better concurrent throughput than ClassicLru above, and better hit rate. A detailed performance analysis provided in the github link below.
Usage looks like this:
int capacity = 666;
var lru = new ConcurrentLru<int, SomeItem>(capacity);
var value = lru.GetOrAdd(1, (k) => new SomeItem(k));
GitHub: https://github.com/bitfaster/BitFaster.Caching
Install-Package BitFaster.Caching
I wrote this some time ago and it seems to work well. It allows you to differentiate different cache stores by using different Types: ApplicationCaching<MyCacheType1>, ApplicationCaching<MyCacheType2>....
You can decide to allow some stores to persist after execution and others to expire.
You will need a reference to the Newtonsoft.Json serializer (or use an alternative one) and of course all objects or values types to be cached must be serializable.
Use MaxItemCount to set a limit to the number of items in any one store.
A separate Zipper class (see code below) uses System.IO.Compression. This minimises the size of the store and helps speed up loading times.
public static class ApplicationCaching<K>
{
//====================================================================================================================
public static event EventHandler InitialAccess = (s, e) => { };
//=============================================================================================
static Dictionary<string, byte[]> _StoredValues;
static Dictionary<string, DateTime> _ExpirationTimes = new Dictionary<string, DateTime>();
//=============================================================================================
public static int MaxItemCount { get; set; } = 0;
private static void OnInitialAccess()
{
//-----------------------------------------------------------------------------------------
_StoredValues = new Dictionary<string, byte[]>();
//-----------------------------------------------------------------------------------------
InitialAccess?.Invoke(null, EventArgs.Empty);
//-----------------------------------------------------------------------------------------
}
public static void AddToCache<T>(string key, T value, DateTime expirationTime)
{
try
{
//-----------------------------------------------------------------------------------------
if (_StoredValues is null) OnInitialAccess();
//-----------------------------------------------------------------------------------------
string strValue = JsonConvert.SerializeObject(value);
byte[] zippedValue = Zipper.Zip(strValue);
//-----------------------------------------------------------------------------------------
_StoredValues.Remove(key);
_StoredValues.Add(key, zippedValue);
//-----------------------------------------------------------------------------------------
_ExpirationTimes.Remove(key);
_ExpirationTimes.Add(key, expirationTime);
//-----------------------------------------------------------------------------------------
}
catch (Exception ex)
{
throw ex;
}
}
//=============================================================================================
public static T GetFromCache<T>(string key, T defaultValue = default)
{
try
{
//-----------------------------------------------------------------------------------------
if (_StoredValues is null) OnInitialAccess();
//-----------------------------------------------------------------------------------------
if (_StoredValues.ContainsKey(key))
{
//------------------------------------------------------------------------------------------
if (_ExpirationTimes[key] <= DateTime.Now)
{
//------------------------------------------------------------------------------------------
_StoredValues.Remove(key);
_ExpirationTimes.Remove(key);
//------------------------------------------------------------------------------------------
return defaultValue;
//------------------------------------------------------------------------------------------
}
//------------------------------------------------------------------------------------------
byte[] zippedValue = _StoredValues[key];
//------------------------------------------------------------------------------------------
string strValue = Zipper.Unzip(zippedValue);
T value = JsonConvert.DeserializeObject<T>(strValue);
//------------------------------------------------------------------------------------------
return value;
//------------------------------------------------------------------------------------------
}
else
{
return defaultValue;
}
//---------------------------------------------------------------------------------------------
}
catch (Exception ex)
{
throw ex;
}
}
//=============================================================================================
public static string ConvertCacheToString()
{
//-----------------------------------------------------------------------------------------
if (_StoredValues is null || _ExpirationTimes is null) return "";
//-----------------------------------------------------------------------------------------
List<string> storage = new List<string>();
//-----------------------------------------------------------------------------------------
string strStoredObject = JsonConvert.SerializeObject(_StoredValues);
string strExpirationTimes = JsonConvert.SerializeObject(_ExpirationTimes);
//-----------------------------------------------------------------------------------------
storage.AddRange(new string[] { strStoredObject, strExpirationTimes});
//-----------------------------------------------------------------------------------------
string strStorage = JsonConvert.SerializeObject(storage);
//-----------------------------------------------------------------------------------------
return strStorage;
//-----------------------------------------------------------------------------------------
}
//=============================================================================================
public static void InializeCacheFromString(string strCache)
{
try
{
//-----------------------------------------------------------------------------------------
List<string> storage = JsonConvert.DeserializeObject<List<string>>(strCache);
//-----------------------------------------------------------------------------------------
if (storage != null && storage.Count == 2)
{
//-----------------------------------------------------------------------------------------
_StoredValues = JsonConvert.DeserializeObject<Dictionary<string, byte[]>>(storage.First());
_ExpirationTimes = JsonConvert.DeserializeObject<Dictionary<string, DateTime>>(storage.Last());
//-----------------------------------------------------------------------------------------
if (_ExpirationTimes != null && _StoredValues != null)
{
//-----------------------------------------------------------------------------------------
for (int i = 0; i < _ExpirationTimes.Count; i++)
{
string key = _ExpirationTimes.ElementAt(i).Key;
//-----------------------------------------------------------------------------------------
if (_ExpirationTimes[key] < DateTime.Now)
{
ClearItem(key);
}
//-----------------------------------------------------------------------------------------
}
//-----------------------------------------------------------------------------------------
if (MaxItemCount > 0 && _StoredValues.Count > MaxItemCount)
{
IEnumerable<KeyValuePair<string, DateTime>> countedOutItems = _ExpirationTimes.OrderByDescending(o => o.Value).Skip(MaxItemCount);
for (int i = 0; i < countedOutItems.Count(); i++)
{
ClearItem(countedOutItems.ElementAt(i).Key);
}
}
//-----------------------------------------------------------------------------------------
return;
//-----------------------------------------------------------------------------------------
}
//-----------------------------------------------------------------------------------------
}
//-----------------------------------------------------------------------------------------
_StoredValues = new Dictionary<string, byte[]>();
_ExpirationTimes = new Dictionary<string, DateTime>();
//-----------------------------------------------------------------------------------------
}
catch (Exception)
{
throw;
}
}
//=============================================================================================
public static void ClearItem(string key)
{
//-----------------------------------------------------------------------------------------
if (_StoredValues.ContainsKey(key))
{
_StoredValues.Remove(key);
}
//-----------------------------------------------------------------------------------------
if (_ExpirationTimes.ContainsKey(key))
_ExpirationTimes.Remove(key);
//-----------------------------------------------------------------------------------------
}
//=============================================================================================
}
You can easily start using the cache on the fly with something like...
//------------------------------------------------------------------------------------------------------------------------------
string key = "MyUniqueKeyForThisItem";
//------------------------------------------------------------------------------------------------------------------------------
MyType obj = ApplicationCaching<MyCacheType>.GetFromCache<MyType>(key);
//------------------------------------------------------------------------------------------------------------------------------
if (obj == default)
{
obj = new MyType(...);
ApplicationCaching<MyCacheType>.AddToCache(key, obj, DateTime.Now.AddHours(1));
}
Note the actual types stored in the cache can be the same or different from the cache type. The cache type is ONLY used to differentiate different cache stores.
You can then decide to allow the cache to persist after execution terminates using Default Settings
string bulkCache = ApplicationCaching<MyType>.ConvertCacheToString();
//--------------------------------------------------------------------------------------------------------
if (bulkCache != "")
{
Properties.Settings.Default.*MyType*DataCachingStore = bulkCache;
}
//--------------------------------------------------------------------------------------------------------
try
{
Properties.Settings.Default.Save();
}
catch (IsolatedStorageException)
{
//handle Isolated Storage exceptions here
}
Handle the InitialAccess Event to reinitialize the cache when you restart the app
private static void ApplicationCaching_InitialAccess(object sender, EventArgs e)
{
//-----------------------------------------------------------------------------------------
string storedCache = Properties.Settings.Default.*MyType*DataCachingStore;
ApplicationCaching<MyCacheType>.InializeCacheFromString(storedCache);
//-----------------------------------------------------------------------------------------
}
Finally here is the Zipper class...
public class Zipper
{
public static void CopyTo(Stream src, Stream dest)
{
byte[] bytes = new byte[4096];
int cnt;
while ((cnt = src.Read(bytes, 0, bytes.Length)) != 0)
{
dest.Write(bytes, 0, cnt);
}
}
public static byte[] Zip(string str)
{
var bytes = Encoding.UTF8.GetBytes(str);
using (var msi = new MemoryStream(bytes))
using (var mso = new MemoryStream())
{
using (var gs = new GZipStream(mso, CompressionMode.Compress))
{
CopyTo(msi, gs);
}
return mso.ToArray();
}
}
public static string Unzip(byte[] bytes)
{
using (var msi = new MemoryStream(bytes))
using (var mso = new MemoryStream())
{
using (var gs = new GZipStream(msi, CompressionMode.Decompress))
{
CopyTo(gs, mso);
}
return Encoding.UTF8.GetString(mso.ToArray());
}
}
}
- Memory cache implementation for .Net core
public class CachePocRepository : ICachedEmployeeRepository
{
private readonly IEmployeeRepository _employeeRepository;
private readonly IMemoryCache _memoryCache;
public CachePocRepository(
IEmployeeRepository employeeRepository,
IMemoryCache memoryCache)
{
_employeeRepository = employeeRepository;
_memoryCache = memoryCache;
}
public async Task<Employee> GetEmployeeDetailsId(string employeeId)
{
_memoryCache.TryGetValue(employeeId, out Employee employee);
if (employee != null)
{
return employee;
}
employee = await _employeeRepository.GetEmployeeDetailsId(employeeId);
_memoryCache.Set(employeeId,
employee,
new MemoryCacheEntryOptions()
{
AbsoluteExpiration = DateTimeOffset.UtcNow.AddDays(7),
});
return employee;
}
Related