In-memory cache implementation

Question

A few years ago I required a lightweight in-app-in-memory cache. Requirements:

• Time complexity O(1) for individual element read/write access
• Space complexity O(n) (for n elements)
• Safe for concurrent read/write access
• Cache size limited by fixed number of entries or max age of entries

Before you ask: The code was written in times of .NET 3 and is still required to work in .NET 3.5, so MemoryCache was and is no option.

Anyway the code works fine but now looking back in retrospect the design strikes me as a bit non-optimal.

So I'm looking for some input regarding design/best practices/style.

Base cache class implementation

This is the base cache class. The cache entry holds the value to be cached and also some meta data, mainly time of last access and an index reference. The index reference is a node in a linked list. Whenever a cache element is accessed it is being moved to the front of the list. This allows for an easy LRU eviction strategy for a size based cache. The access time can be used by the age based eviction cache.

My main quarrel with this is that the base class contains knowledge about both strategies although it does not implement any of the eviction strategies itself.

public class Cache<TKey, TValue> : IDisposable
{
    protected class CacheValue<TCacheKey, TCacheValue>
    {
        public CacheValue(TCacheValue value)
        {
            LastAccess = DateTime.Now;
            Value = value;
        }

        public LinkedListNode<KeyValuePair<TCacheKey, CacheValue<TCacheKey, TCacheValue>>> IndexRef { get; set; }
        public DateTime LastAccess { get; set; }
        public TCacheValue Value { get; set; }
    }

    protected readonly LinkedList<KeyValuePair<TKey, CacheValue<TKey, TValue>>> _IndexList = new LinkedList<KeyValuePair<TKey, CacheValue<TKey, TValue>>>();
    private readonly Dictionary<TKey, CacheValue<TKey, TValue>> _ValueCache = new Dictionary<TKey, CacheValue<TKey, TValue>>();
    protected object SyncRoot = new object();
    private DateTime _LastCacheAccess = DateTime.MaxValue;

    public virtual int Count
    {
        get
        {
            lock (SyncRoot)
            {
                return _ValueCache.Count;
            }
        }
    }

    public virtual bool TryGetValue(TKey key, out TValue value)
    {
        CacheValue<TKey, TValue> v;
        value = default(TValue);

        lock (SyncRoot)
        {
            _LastCacheAccess = DateTime.Now;
            v = GetCacheValueUnlocked(key);
            if (v != null)
            {
                value = v.Value;
                UpdateElementAccess(key, v);
                return true;
            }
        }

        return false;
    }

    protected virtual void UpdateElementAccess(TKey key, CacheValue<TKey, TValue> cacheValue)
    {
        // update last access and move it to the head of the list
        cacheValue.LastAccess = DateTime.Now;
        var idxRef = cacheValue.IndexRef;
        if (idxRef != null)
        {
            _IndexList.Remove(idxRef);
        }
        else
        {
            idxRef = new LinkedListNode<KeyValuePair<TKey, CacheValue<TKey, TValue>>>(new KeyValuePair<TKey, CacheValue<TKey, TValue>>(key, cacheValue));
            cacheValue.IndexRef = idxRef;
        }
        _IndexList.AddFirst(idxRef);
    }

    protected virtual CacheValue<TKey, TValue> GetCacheValueUnlocked(TKey key)
    {
        CacheValue<TKey, TValue> v;
        return _ValueCache.TryGetValue(key, out v) ? v : null;
    }

    public virtual void SetValue(TKey key, TValue value)
    {
        lock (SyncRoot)
        {
            SetValueUnlocked(key, value);
        }
    }

    protected virtual CacheValue<TKey, TValue> SetValueUnlocked(TKey key, TValue value)
    {
        _LastCacheAccess = DateTime.Now;
        CacheValue<TKey, TValue> cacheValue = GetCacheValueUnlocked(key);
        if (cacheValue == null)
        {
            cacheValue = new CacheValue<TKey, TValue>(value);
            _ValueCache[key] = cacheValue;
        }
        else
        {
            cacheValue.Value = value;
        }
        UpdateElementAccess(key, cacheValue);
        return cacheValue;
    }

    public virtual void Invalidate(TKey key)
    {
        lock (SyncRoot)
        {
            _LastCacheAccess = DateTime.Now;
            InvalidateUnlocked(key);
        }
    }

    protected void InvalidateUnlocked(TKey key)
    {
        var value = GetCacheValueUnlocked(key);
        if (value != null)
        {
            _ValueCache.Remove(key);
            _IndexList.Remove(value.IndexRef);
        }
    }

    public virtual void Expire(TimeSpan maxAge)
    {
        lock (SyncRoot)
        {
            var toExpire = _ValueCache.Where(x => IsExpired(x.Key, x.Value.Value, x.Value.LastAccess, maxAge)).Select(x => x.Key).ToList();
            toExpire.ForEach(InvalidateUnlocked);
        }
    }

    public virtual void Expire(int maxSize)
    {
        lock (SyncRoot)
        {
            while (_IndexList.Count > maxSize)
            {
                InvalidateUnlocked(_IndexList.Last.Value.Key);
            }
        }
    }

    public virtual void Flush()
    {
        lock (SyncRoot)
        {
            _ValueCache.Clear();
            _IndexList.Clear();
        }
    }

    protected virtual bool IsExpired(TKey key, TValue value, DateTime lastValueAccess, TimeSpan maxAge)
    {
        return lastValueAccess + maxAge < _LastCacheAccess;
    }

    public List<TKey> GetKeys()
    {
        lock (SyncRoot)
        {
            return new List<TKey>(_ValueCache.Keys);
        }
    }

    public void Dispose()
    {
        Dispose(true);
        GC.SuppressFinalize(this);
    }

    protected virtual void Dispose(bool disposing)
    {
    }
}

Implementation for the size limited cache

On every element access we invalidate the elements at the end of the index list as long as the list is longer than number of max entries. Normally this will only evict one element unless the max size has been changed since the last access.

public class SizeLimitedCache<TKey, TValue> : Cache<TKey, TValue>
{
    private int _MaxSize;
    public int MaxSize
    {
        get { return _MaxSize; }
        set { _MaxSize = value; }
    }

    public SizeLimitedCache(int maxSize)
    {
        _MaxSize = maxSize;
    }

    protected override void UpdateElementAccess(TKey key, CacheValue<TKey, TValue> cacheValue)
    {
        base.UpdateElementAccess(key, cacheValue);
        while (_IndexList.Count > _MaxSize)
        {
            InvalidateUnlocked(_IndexList.Last.Value.Key);
        }
    }

    public virtual void Expire()
    {
        base.Expire(MaxSize);
    }
}

Implementation for the automatic age based eviction cache

A background thread is spawned which evicts all entries older than a certain age in regular intervals.

public class AutoExpiryCache<TKey, TValue> : Cache<TKey, TValue>
{
    private Thread _ExpiryThread;
    private readonly object _WaitLock;
    private volatile bool _Quit;
    private volatile bool _RestartWait;

    private TimeSpan _MaxEntryAge;
    public TimeSpan MaxEntryAge
    {
        get { return _MaxEntryAge; }
        set { _MaxEntryAge = value; }
    }

    private TimeSpan _ExpiryInterval;
    public TimeSpan ExpiryInterval
    {
        get { return _ExpiryInterval; }
        set
        {
            _ExpiryInterval = value;
            RestartWaiting();
        }
    }

    private int _NumberOfExpiryRuns = 0;
    public int NumberOfExpiryRuns
    {
        get { return _NumberOfExpiryRuns; }
    }


    public bool ExpiryThreadIsRunning
    {
        get { return _ExpiryThread != null && _ExpiryThread.IsAlive; }
    }

    private void RestartWaiting()
    {
        _RestartWait = true;
        WakeUpThread();
    }

    private void WakeUpThread()
    {
        lock (_WaitLock)
        {
            Monitor.PulseAll(_WaitLock);
        }
    }

    public AutoExpiryCache(string cacheName)
    {
        _Quit = false;
        _RestartWait = false;
        _WaitLock = new object();
        _MaxEntryAge = TimeSpan.FromHours(1);
        _ExpiryInterval = TimeSpan.FromMinutes(30);

        _ExpiryThread = new Thread(ThreadMain);
        _ExpiryThread.Name = cacheName + "ExpiryThread";
        _ExpiryThread.IsBackground = true;
        _ExpiryThread.Start();
    }

    private void ThreadMain()
    {
        while (!_Quit)
        {
            lock (_WaitLock)
            {
                _RestartWait = false;
                Monitor.Wait(_WaitLock, ExpiryInterval);
                if (!_Quit && !_RestartWait)
                {
                    Expire(MaxEntryAge);
                    ++_NumberOfExpiryRuns;
                }
            }
        }
    }

    protected override void Dispose(bool disposing)
    {
        if (disposing)
        {
            _Quit = true;
            WakeUpThread();
            if (_ExpiryThread != null)
            {
                if (!_ExpiryThread.Join(100))
                {
                    _ExpiryThread.Abort();
                }
                _ExpiryThread = null;
            }
        }
        base.Dispose(disposing);
    }
}

Answer 1

Before I get to the main issue, first some smaller notes:

1. A type that is nested in a generic type doesn't need to redeclare the type parameters of the parent, it can use them directly:

   public class Cache<TKey, TValue>
   {
       protected class CacheValue
       {
           public CacheValue(TValue value)
           {
               LastAccess = DateTime.Now;
               Value = value;
           }
   
           public LinkedListNode<KeyValuePair<TKey, CacheValue>> IndexRef { get; set; }
           public DateTime LastAccess { get; set; }
           public TValue Value { get; set; }
       }
   }
   

2. Even with your design, you should still put code that's specific only to one implementation to the corresponding derived class. This means that the method UpdateElementAccess() should be abstract and each override should contain only the part specific to that implementation.

3. Why are so many of your methods virtual when you never override them?

4. Why does IsExpired() take key and value when it never uses them? YAGNI.

5. The full disposable pattern (with Dispose(bool)) is used when you expect unmanaged resources and a finalizer. You don't have either of those, so you can just make the normal Dispose() virtual.

Now, I can think of two ways to solve the CacheValue issue, but neither of them feels very clean to me:

Solution one would be to add a third type parameter to Cache that represents a type derived from CacheValue that's used in the derived class. Something like:

public abstract class Cache<TKey, TValue, TCacheValue>
    where TCacheValue : CacheValue
{
    protected abstract class CacheValue
    {
        public CacheValue(TValue value)
        {
            Value = value;
        }

        public TValue Value { get; set; }
    }

    private readonly Dictionary<TKey, TCacheValue> _ValueCache = new Dictionary<TKey, TCacheValue>();
}

public class SizeLimitedCache<TKey, TValue> : Cache<TKey, TValue, SizeLimitedCacheValue>
{
    private class SizeLimitedCacheValue : CacheValue
    {
        public SizeLimitedCacheValue(TValue value)
            : base(value)
        { }

        public LinkedListNode<KeyValuePair<TKey, SizeLimitedCacheValue>> IndexRef { get; set; }
    }
}

This code explains the idea, but it doesn't actually compile (for several reasons). The simplest way to fix them would be to move both CacheValues into the outer scope, which is not very nice.

The second solution is to add a generic property to CacheValue, which will contain the data the derived class needs:

public abstract class Cache<TKey, TValue, TCacheValueData>
{
    public abstract class CacheValue
    {
        public CacheValue(TValue value)
        {
            Value = value;
        }

        public TValue Value { get; set; }
        public TCacheValueData Data { get; set; }
    }

    private readonly Dictionary<TKey, CacheValue> _ValueCache = new Dictionary<TKey, CacheValue>();
}

public class AutoExpiryCache<TKey, TValue> : Cache<TKey, TValue, DateTime>
{
}

But this again isn't very clean. Moreover, I believe it's impossible to use this for SizeLimitedCache as you designed it, because you would have to write something like:

public class SizeLimitedCache<TKey, TValue>
    : Cache<TKey, TValue, LinkedListNode<KeyValuePair<TKey, Cache<TKey, TValue, ???>.CacheValue>>>

And there is nothing you could write instead of those ??? that would make the code work correctly.

With both solutions, Cache now has an additional type parameter that's just an implementation detail. Because of that, I would also add an interface like ICache<TKey, TValue> and use that in code that uses the cache.