multithreading - Thread-safe cache libraries for .NET

Question

Background:

I maintain several Winforms apps and class libraries that either could or already do benefit from caching. I'm also aware of the Caching Application Block and the System.Web.Caching namespace (which, from what I've gathered, is perfectly OK to use outside ASP.NET).

I've found that, although both of the above classes are technically "thread safe" in the sense that individual methods are synchronized, they don't really seem to be designed particularly well for multi-threaded scenarios. Specifically, they don't implement a GetOrAdd method similar to the one in the new ConcurrentDictionary class in .NET 4.0.

I consider such a method to be a primitive for caching/lookup functionality, and obviously the Framework designers realized this too - that's why the methods exist in the concurrent collections. However, aside from the fact that I'm not using .NET 4.0 in production apps yet, a dictionary is not a full-fledged cache - it doesn't have features like expirations, persistent/distributed storage, etc.

---

Why this is important:

A fairly typical design in a "rich client" app (or even some web apps) is to start pre-loading a cache as soon as the app starts, blocking if the client requests data that is not yet loaded (subsequently caching it for future use). If the user is plowing through his workflow quickly, or if the network connection is slow, it's not unusual at all for the client to be competing with the preloader, and it really doesn't make a lot of sense to request the same data twice, especially if the request is relatively expensive.

So I seem to be left with a few equally lousy options:

• Don't try to make the operation atomic at all, and risk the data being loaded twice (and possibly have two different threads operating on different copies);

• Serialize access to the cache, which means locking the entire cache just to load a single item;

• Start reinventing the wheel just to get a few extra methods.

---

Clarification: Example Timeline

Say that when an app starts, it needs to load 3 datasets which each take 10 seconds to load. Consider the following two timelines:

00:00 - Start loading Dataset 1
00:10 - Start loading Dataset 2
00:19 - User asks for Dataset 2

In the above case, if we don't use any kind of synchronization, the user has to wait a full 10 seconds for data that will be available in 1 second, because the code will see that the item is not yet loaded into the cache and try to reload it.

00:00 - Start loading Dataset 1
00:10 - Start loading Dataset 2
00:11 - User asks for Dataset 1

In this case, the user is asking for data that's already in the cache. But if we serialize access to the cache, he'll have to wait another 9 seconds for no reason at all, because the cache manager (whatever that is) has no awareness of the specific item being asked for, only that "something" is being requested and "something" is in progress.

---

The Question:

Are there any caching libraries for .NET (pre-4.0) that do implement such atomic operations, as one might expect from a thread-safe cache?

Or, alternatively, is there some means to extend an existing "thread-safe" cache to support such operations, without serializing access to the cache (which would defeat the purpose of using a thread-safe implementation in the first place)? I doubt that there is, but maybe I'm just tired and ignoring an obvious workaround.

Or... is there something else I'm missing? Is it just standard practice to let two competing threads steamroll each other if they happen to both be requesting the same item, at the same time, for the first time or after an expiration?

Answer 1

I know your pain as I am one of the Architects of Dedoose. I have messed around with a lot of caching libraries and ended up building this one after much tribulation. The one assumption for this Cache Manager is that all collections stored by this class implement an interface to get a Guid as a "Id" property on each object. Being that this is for a RIA it includes a lot of methods for adding /updating /removing items from these collections.

Here's my CollectionCacheManager

public class CollectionCacheManager
{
    private static readonly object _objLockPeek = new object();
    private static readonly Dictionary<String, object> _htLocksByKey = new Dictionary<string, object>();
    private static readonly Dictionary<String, CollectionCacheEntry> _htCollectionCache = new Dictionary<string, CollectionCacheEntry>();

    private static DateTime _dtLastPurgeCheck;

    public static List<T> FetchAndCache<T>(string sKey, Func<List<T>> fGetCollectionDelegate) where T : IUniqueIdActiveRecord
    {
        List<T> colItems = new List<T>();

        lock (GetKeyLock(sKey))
        {
            if (_htCollectionCache.Keys.Contains(sKey) == true)
            {
                CollectionCacheEntry objCacheEntry = _htCollectionCache[sKey];
                colItems = (List<T>) objCacheEntry.Collection;
                objCacheEntry.LastAccess = DateTime.Now;
            }
            else
            {
                colItems = fGetCollectionDelegate();
                SaveCollection<T>(sKey, colItems);
            }
        }

        List<T> objReturnCollection = CloneCollection<T>(colItems);
        return objReturnCollection;
    }

    public static List<Guid> FetchAndCache(string sKey, Func<List<Guid>> fGetCollectionDelegate)
    {
        List<Guid> colIds = new List<Guid>();

        lock (GetKeyLock(sKey))
        {
            if (_htCollectionCache.Keys.Contains(sKey) == true)
            {
                CollectionCacheEntry objCacheEntry = _htCollectionCache[sKey];
                colIds = (List<Guid>)objCacheEntry.Collection;
                objCacheEntry.LastAccess = DateTime.Now;
            }
            else
            {
                colIds = fGetCollectionDelegate();
                SaveCollection(sKey, colIds);
            }
        }

        List<Guid> colReturnIds = CloneCollection(colIds);
        return colReturnIds;
    }


    private static List<T> GetCollection<T>(string sKey) where T : IUniqueIdActiveRecord
    {
        List<T> objReturnCollection = null;

        if (_htCollectionCache.Keys.Contains(sKey) == true)
        {
            CollectionCacheEntry objCacheEntry = null;

            lock (GetKeyLock(sKey))
            {
                objCacheEntry = _htCollectionCache[sKey];
                objCacheEntry.LastAccess = DateTime.Now;
            }

            if (objCacheEntry.Collection != null && objCacheEntry.Collection is List<T>)
            {
                objReturnCollection = CloneCollection<T>((List<T>)objCacheEntry.Collection);
            }
        }

        return objReturnCollection;
    }


    public static void SaveCollection<T>(string sKey, List<T> colItems) where T : IUniqueIdActiveRecord
    {

        CollectionCacheEntry objCacheEntry = new CollectionCacheEntry();

        objCacheEntry.Key = sKey;
        objCacheEntry.CacheEntry = DateTime.Now;
        objCacheEntry.LastAccess = DateTime.Now;
        objCacheEntry.LastUpdate = DateTime.Now;
        objCacheEntry.Collection = CloneCollection(colItems);

        lock (GetKeyLock(sKey))
        {
            _htCollectionCache[sKey] = objCacheEntry;
        }
    }

    public static void SaveCollection(string sKey, List<Guid> colIDs)
    {

        CollectionCacheEntry objCacheEntry = new CollectionCacheEntry();

        objCacheEntry.Key = sKey;
        objCacheEntry.CacheEntry = DateTime.Now;
        objCacheEntry.LastAccess = DateTime.Now;
        objCacheEntry.LastUpdate = DateTime.Now;
        objCacheEntry.Collection = CloneCollection(colIDs);

        lock (GetKeyLock(sKey))
        {
            _htCollectionCache[sKey] = objCacheEntry;
        }
    }

    public static void UpdateCollection<T>(string sKey, List<T> colItems) where T : IUniqueIdActiveRecord
    {
        lock (GetKeyLock(sKey))
        {
            if (_htCollectionCache.ContainsKey(sKey) == true)
            {
                CollectionCacheEntry objCacheEntry = _htCollectionCache[sKey];
                objCacheEntry.LastAccess = DateTime.Now;
                objCacheEntry.LastUpdate = DateTime.Now;
                objCacheEntry.Collection = new List<T>();

                //Clone the collection before insertion to ensure it can't be touched
                foreach (T objItem in colItems)
                {
                    objCacheEntry.Collection.Add(objItem);
                }

                _htCollectionCache[sKey] = objCacheEntry;
            }
            else
            {
                SaveCollection<T>(sKey, colItems);
            }
        }
    }

    public static void UpdateItem<T>(string sKey, T objItem)  where T : IUniqueIdActiveRecord
    {
        lock (GetKeyLock(sKey))
        {
            if (_htCollectionCache.ContainsKey(sKey) == true)
            {
                CollectionCacheEntry objCacheEntry = _htCollectionCache[sKey];
                List<T> colItems = (List<T>)objCacheEntry.Collection;

                colItems.RemoveAll(o => o.Id == objItem.Id);
                colItems.Add(objItem);

                objCacheEntry.Collection = colItems;

                objCacheEntry.LastAccess = DateTime.Now;
                objCacheEntry.LastUpdate = DateTime.Now;
            }
        }
    }

    public static void UpdateItems<T>(string sKey, List<T> colItemsToUpdate) where T : IUniqueIdActiveRecord
    {
        lock (GetKeyLock(sKey))
        {
            if (_htCollectionCache.ContainsKey(sKey) == true)
            {
                CollectionCacheEntry objCacheEntry = _htCollectionCache[sKey];
                List<T> colCachedItems = (List<T>)objCacheEntry.Collection;

                foreach (T objItem in colItemsToUpdate)
                {
                    colCachedItems.RemoveAll(o => o.Id == objItem.Id);
                    colCachedItems.Add(objItem);
                }

                objCacheEntry.Collection = colCachedItems;

                objCacheEntry.LastAccess = DateTime.Now;
                objCacheEntry.LastUpdate = DateTime.Now;
            }
        }
    }

    public static void RemoveItemFromCollection<T>(string sKey, T objItem) where T : IUniqueIdActiveRecord
    {
        lock (GetKeyLock(sKey))
        {
            List<T> objCollection = GetCollection<T>(sKey);
            if (objCollection != null && objCollection.Count(o => o.Id == objItem.Id) > 0)
            {
                objCollection.RemoveAll(o => o.Id == objItem.Id);
                UpdateCollection<T>(sKey, objCollection);
            }
        }
    }

    public static void RemoveItemsFromCollection<T>(string sKey, List<T> colItemsToAdd) where T : IUniqueIdActiveRecord
    {
        lock (GetKeyLock(sKey))
        {
            Boolean bCollectionChanged = false;

            List<T> objCollection = GetCollection<T>(sKey);
            foreach (T objItem in colItemsToAdd)
            {
                if (objCollection != null && objCollection.Count(o => o.Id == objItem.Id) > 0)
                {
                    objCollection.RemoveAll(o => o.Id == objItem.Id);
                    bCollectionChanged = true;
                }
            }
            if (bCollectionChanged == true)
            {
                UpdateCollection<T>(sKey, objCollection);
            }
        }
    }

    public static void AddItemToCollection<T>(string sKey, T objItem) where T : IUniqueIdActiveRecord
    {
        lock (GetKeyLock(sKey))
        {
            List<T> objCollection = GetCollection<T>(sKey);
            if (objCollection != null && objCollection.Count(o => o.Id == objItem.Id) == 0)
            {
                objCollection.Add(objItem);
                UpdateCollection<T>(sKey, objCollection);
            }
        }
    }

    public static void AddItemsToCollection<T>(string sKey, List<T> colItemsToAdd) where T : IUniqueIdActiveRecord
    {
        lock (GetKeyLock(sKey))
        {
            List<T> objCollection = GetCollection<T>(sKey);
            Boolean bCollectionChanged = false;
            foreach (T objItem in colItemsToAdd)
            {
                if (objCollection != null && objCollection.Count(o => o.Id == objItem.Id) == 0)
                {
                    objCollection.Add(objItem);
                    bCollectionChanged = true;
                }
            }
            if (bCollectionChanged == true)
            {
                UpdateCollection<T>(sKey, objCollection);
            }
        }
    }

    public static void PurgeCollectionByMaxLastAccessInMinutes(int iMinutesSinceLastAccess)
    {
        DateTime dtThreshHold = DateTime.Now.AddMinutes(iMinutesSinceLastAccess * -1);

        if (_dtLastPurgeCheck == null || dtThreshHold > _dtLastPurgeCheck)
        {

            lock (_objLockPeek)
            {
                CollectionCacheEntry objCacheEntry;
                List<String> colKeysToRemove = new List<string>();

                foreach (string sCollectionKey in _htCollectionCache.Keys)
                {
                    objCacheEntry = _htCollectionCache[sCollectionKey];
                    if (objCacheEntry.LastAccess < dtThreshHold)
                    {
                        colKeysToRemove.Add(sCollectionKey);
                    }
                }

                foreach (String sKeyToRemove in colKeysToRemove)
                {
                    _htCollectionCache.Remove(sKeyToRemove);
                }
            }

            _dtLastPurgeCheck = DateTime.Now;
        }
    }

    public static void ClearCollection(String sKey)
    {
        lock (GetKeyLock(sKey))
        {
            lock (_objLockPeek)
            {
                if (_htCollectionCache.ContainsKey(sKey) == true)
                {
                    _htCollectionCache.Remove(sKey);
                }
            }
        }
    }


    #region Helper Methods
    private static object GetKeyLock(String sKey)
    {
        //Ensure even if hell freezes over this lock exists
        if (_htLocksByKey.Keys.Contains(sKey) == false)
        {
            lock (_objLockPeek)
            {
                if (_htLocksByKey.Keys.Contains(sKey) == false)
                {
                    _htLocksByKey[sKey] = new object();
                }
            }
        }

        return _htLocksByKey[sKey];
    }

    private static List<T> CloneCollection<T>(List<T> colItems) where T : IUniqueIdActiveRecord
    {
        List<T> objReturnCollection = new List<T>();
        //Clone the list - NEVER return the internal cache list
        if (colItems != null && colItems.Count > 0)
        {
            List<T> colCachedItems = (List<T>)colItems;