patterncsharpMinor

In-memory cache implementation

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

implementationcachememory

Problem

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 : IDisposable
{
protected class CacheValue
{
public CacheValue(TCacheValue value)
{
LastAccess = DateTime.Now;
Value = value;
}

public LinkedListNode>> IndexRef { get; set; }
public DateTime LastAccess { get; set; }
public TCacheValue Value { get; set; }
}

protected readonly LinkedList>> _IndexList = new LinkedList>>();
private readonly Dictionary> _ValueCache = new Dictionary>();
protected object SyncRoot = new object();
private DateTime _LastCacheAccess = DateTime.MaxValue;

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

Solution

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

-
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
{
    protected class CacheValue
    {
        public CacheValue(TValue value)
        {
            LastAccess = DateTime.Now;
            Value = value;
        }

        public LinkedListNode> IndexRef { get; set; }
        public DateTime LastAccess { get; set; }
        public TValue Value { get; set; }
    }
}

-
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.

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

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

-
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
    where TCacheValue : CacheValue
{
    protected abstract class CacheValue
    {
        public CacheValue(TValue value)
        {
            Value = value;
        }

        public TValue Value { get; set; }
    }

    private readonly Dictionary _ValueCache = new Dictionary();
}

public class SizeLimitedCache : Cache
{
    private class SizeLimitedCacheValue : CacheValue
    {
        public SizeLimitedCacheValue(TValue value)
            : base(value)
        { }

        public LinkedListNode> 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
{
    public abstract class CacheValue
    {
        public CacheValue(TValue value)
        {
            Value = value;
        }

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

    private readonly Dictionary _ValueCache = new Dictionary();
}

public class AutoExpiryCache : Cache
{
}

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
    : Cache.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 and use that in code that uses the cache.

Code Snippets

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

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

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>
{
}

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

Context

StackExchange Code Review Q#38619, answer score: 9

Revisions (0)

No revisions yet.