Implementing a Most Recently Used Cache

Question

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);
}

Answer 1

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.