2
\$\begingroup\$

I want to create an In Memory Cache in .Net. The primary usage for this cache would be to store addresses... I want to keep around 1000 addresses in memory and once the cache is full, remove the Least Recently Used address from the cache.

Microsoft provide 2 versions of MemoryCache, one is implemented in System.Runtime.Caching and the other is implemented in Microsoft.Extensions.Caching.Memory.

The second implementation seems to be more flexible, you can define Sliding Expiration (which updates expiration time every time an entry is used) and it also allows to set a size limit for the entries in cache. For example I can set the cache size to 1000 entries... however the problem is that once the cache is full (reached 1000 entries), it does not remove the Least Recently Used entry... instead it ignores additional inserts until some of the existing elements are expired.

So I ended up writing my own Most Recently Used Cache:

MruCache.cs

// Most Recently Used Cache
public class MruCache<T>
{
    private readonly object _lock;
    private readonly int _size;
    private Dictionary<string, MruCacheEntry<T>> _enteries;

    public MruCache(int size = 1024)
    {
        _lock = new object();
        _size = size;
        _enteries = new Dictionary<string, MruCacheEntry<T>>();
    }

    private bool IsFull
    {
        get
        {
            return _enteries.Count >= _size;
        }
    }

    private int OnePercent
    {
        get
        {
            int number = _size / 100;
            return number < 1 ? 1 : number;
        }
    }

    public bool TryGetValue(string key, out T value)
    {
        if (_enteries.TryGetValue(key, out MruCacheEntry<T> entry))
        {
            value = _enteries[key].Value;
            return true;
        }
        else
        {
            value = default(T);
            return false;
        }
    }

    public void AddOrUpdate(string key, T value)
    {
        lock (_lock)
        {
            if (_enteries.ContainsKey(key))
            {
                _enteries[key].Update(value);
            }
            else
            {
                MakeRoomIfFull();
                _enteries.Add(key, new MruCacheEntry<T>(value));
            }
        }
    }

    private void MakeRoomIfFull()
    {
        if (IsFull)
        {
            // get 1% of entries which were Least Recently Used
            var keysToRemove = _enteries.OrderBy(e => e.Value.LastUsageTime).Select(e => e.Key).Take(OnePercent);
            foreach (var k in keysToRemove)
            {
                _enteries.Remove(k);
            }
        }
    }
}

MruCacheEntry.cs

// Most Recently Used Cache Entry
public class MruCacheEntry<T>
{
    private T _value;

    public MruCacheEntry(T value)
    {
        Value = value;
    }

    public T Value 
    {
        get 
        {
            Touch();
            return _value;
        }

        set
        {
            Touch();
            _value = value;
        }
    }

    public DateTime LastUsageTime { get; set; }

    public void Update(T value)
    {
        Value = value;
    }

    private void Touch()
    {
        LastUsageTime = DateTime.Now;
    }
}

UnitTests

[TestMethod]
public void Test_cache_size_4()
{
    var _mruCache = new MruCache<string>(4);
    _mruCache.AddOrUpdate("item1", "1");
    _mruCache.AddOrUpdate("item2", "2");
    _mruCache.AddOrUpdate("item3", "3");
    _mruCache.AddOrUpdate("item1", "new1");
    _mruCache.AddOrUpdate("item4", "4");
    _mruCache.AddOrUpdate("item5", "5");

    _mruCache.TryGetValue("item1", out string valueOfItem1);
    _mruCache.TryGetValue("item2", out string valueOfItem2);
    _mruCache.TryGetValue("item3", out string valueOfItem3);
    _mruCache.TryGetValue("noSuchKey", out string valueOfNoSuchKey);

    valueOfItem1.Should().Be("new1");
    valueOfItem2.Should().Be(null);
    valueOfItem3.Should().Be("3");
    valueOfNoSuchKey.Should().Be(null);
}
\$\endgroup\$
9
  • \$\begingroup\$ is it possible to use timestamp key instead of string ? I'm thinking if you were using a timestamp key, then you can just compare the last usage time and the timestamp (which is the time created). also, why DateTime.Now ? are you planning to cache address for more than one day ? \$\endgroup\$
    – iSR5
    Oct 19 '21 at 6:53
  • \$\begingroup\$ @iSR5: I am using this cache to store frequently used addresses.... the Key is normalized StreetAddress (by normalized I mean lowercase and alphanumric, removing evening else)... this way I know if an address is already added to cache or not. At the same time uppercase, lower case, commas and dashes won't make any difference is the address key. I want to keep the frequently used addressed in the cache for much more than a day... for example the city of Auckland (which has Lat/Long) remains in the cache for months as it is frequently used. \$\endgroup\$ Oct 19 '21 at 10:08
  • \$\begingroup\$ In that case, you could save some efforts by initiating a case-insensitive Dictionary, which would reduce some efforts _enteries = new Dictionary<string, MruCacheEntry<T>>(StringComparer.InvariantCultureIgnoreCase); \$\endgroup\$
    – iSR5
    Oct 19 '21 at 13:22
  • \$\begingroup\$ This code isn't thread-safe. Is it intended to use in multithreaded environment? How about ConcurrentDictionary instead of lock? \$\endgroup\$
    – aepot
    Oct 19 '21 at 16:31
  • \$\begingroup\$ Wouldn't it be easier to just make a new add Set Extension method to the Microsoft.Extensions.Caching.Memory.MemoryCache that would create a CacheEntry with a PostEvictionCallbacks and if the post evict is called with EvictionReason.Capacity then to do a Spin.Wait and retry? \$\endgroup\$ Oct 19 '21 at 19:30
1
\$\begingroup\$

The Least Recently Used cache replacement policy

I want to keep around 1000 addresses in memory and once the cache is full, remove the Least Recently Used address from the cache.

Based on your description of what you're trying to do, this is called a Least Recently Used cache, not Most Recently Used... See also wikipedia.

Removing the least recently used items efficiently

Disclaimer: I don't know much C#. This looks inefficient:

var keysToRemove = _enteries
  .OrderBy(e => e.Value.LastUsageTime)
  .Select(e => e.Key)
  .Take(OnePercent);

To remove the k smallest items from an unordered set of n items, an efficient way I know is quickselect. It's efficient because quickselect doesn't sort all the elements. It uses clever partitioning to find the k smallest, without any precise ordering. It basically comes up with "these bunch of values are all definitely smaller than the rest". It's a \$k \log(n)\$ operation.

I suspect the code above does a regular sort of the full set of items, a \$n \log(n)\$ operation. This is performed every time some items need to be evicted.

Although using quickselect would be an improvement, there's a far better data structure for your purpose: linked hashtable. The idea is to use a combination of two data structures to keep the cache entries, keep track of their ordering and manage eviction efficiently:

  • a doubly-linked list:
    • when a cache entry is added, append at the end
    • when a cache entry is updated, remove from the list and append at the end
    • when the list is long, delete entries from the front
  • a dictionary of keys to linked list nodes:
    • used for quick lookup of cache entries, with direct access to list nodes

Note that the doubly-linked list is never traversed; nodes are accessed directly. Timestamps are not needed, the position of nodes in the list already express their ordering.

Avoid repeated computations

OnePercent computes the same value on every call, because _size cannot change after construction. You could compute the one percent once at construction.

Make chained calls easier to read

Instead of this:

var keysToRemove = _enteries.OrderBy(e => e.Value.LastUsageTime).Select(e => e.Key).Take(OnePercent);

I find it a lot easier to read if you break the line after each step:

var keysToRemove = _enteries
  .OrderBy(e => e.Value.LastUsageTime)
  .Select(e => e.Key)
  .Take(OnePercent);

This is in the same spirit of the general good rule of having one statement per line.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Thanks a lot. I was not aware of the Cache Replacement Policies that you linked... I called it Most Recently Used as I thought it would be the most descriptive name... I spent a lot of time thinking maybe Least Recently Used would be a better name... but your Wikipedia link made it all clear. \$\endgroup\$ Oct 19 '21 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.