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

It looks like the .NET 4.0 concurrent collections utilize new synchronization primitives that spin before switching context, in case a resource is freed quickly. So they're still locking, just in a more opportunistic way. If you think you data retrieval logic is shorter than the timeslice, then it seems like this would be highly beneficial. But you mentioned network, which makes me think this doesn't apply.

I would wait till you have a simple, synchronized solution in place, and measure the performance and behavior before assuming you will have performance issues related to concurrency.

If you're really concerned about cache contention, you can utilize an existing cache infrastructure and logically partition it into regions. Then synchronize access to each region independently.

An example strategy if your data set consists of items that are keyed on numeric IDs, and you want to partition your cache into 10 regions, you can (mod 10) the ID to determine which region they are in. You'd keep an array of 10 objects to lock on. All of the code can be written for a variable number of regions, which can be set via configuration, or determined at app start depending on the total number of items you predict/intend to cache.

If your cache hits are keyed in an abnormal way, you'll have to come up with some custom heuristic to partition the cache.

Update (per comment): Well this has been fun. I think the following is about as fine-grained locking as you can hope for without going totally insane (or maintaining/synchronizing a dictionary of locks for each cache key). I haven't tested it so there are probably bugs, but the idea should be illustrated. Track a list of requested IDs, and then use that to decide if you need to get the item yourself, or if you merely need to wait for a previous request to finish. Waiting (and cache insertion) is synchronized with tightly-scoped thread blocking and signaling using Wait and PulseAll. Access to the requested ID list is synchronized with a tightly-scopedReaderWriterLockSlim.

This is a read-only cache. If you doing creates/updates/deletes, you'll have to make sure you remove IDs from requestedIds once they're received (before the call to Monitor.PulseAll(_cache) you'll want to add another try..finally and acquire the _requestedIdsLock write-lock). Also, with creates/updates/deletes, the easiest way to manage the cache would be to merely remove the existing item from _cache if/when the underlying create/update/delete operation succeeds.

(Oops, see update 2 below.)

public class Item 
{
    public int ID { get; set; }
}

public class AsyncCache
{
    protected static readonly Dictionary<int, Item> _externalDataStoreProxy = new Dictionary<int, Item>();

    protected static readonly Dictionary<int, Item> _cache = new Dictionary<int, Item>();

    protected static readonly HashSet<int> _requestedIds = new HashSet<int>();
    protected static readonly ReaderWriterLockSlim _requestedIdsLock = new ReaderWriterLockSlim();

    public Item Get(int id)
    {
        // if item does not exist in cache
        if (!_cache.ContainsKey(id))
        {
            _requestedIdsLock.EnterUpgradeableReadLock();
            try
            {
                // if item was already requested by another thread
                if (_requestedIds.Contains(id))
                {
                    _requestedIdsLock.ExitUpgradeableReadLock();
                    lock (_cache)
                    {
                        while (!_cache.ContainsKey(id))
                            Monitor.Wait(_cache);

                        // once we get here, _cache has our item
                    }
                }
                // else, item has not yet been requested by a thread
                else
                {
                    _requestedIdsLock.EnterWriteLock();
                    try
                    {
                        // record the current request
                        _requestedIds.Add(id);
                        _requestedIdsLock.ExitWriteLock();
                        _requestedIdsLock.ExitUpgradeableReadLock();

                        // get the data from the external resource
                        #region fake implementation - replace with real code
                        var item = _externalDataStoreProxy[id];
                        Thread.Sleep(10000);
                        #endregion

                        lock (_cache)
                        {
                            _cache.Add(id, item);
                            Monitor.PulseAll(_cache);
                        }
                    }
                    finally
                    {
                        // let go of any held locks
                        if (_requestedIdsLock.IsWriteLockHeld)
                            _requestedIdsLock.ExitWriteLock();
                    }
                }
            }
            finally
            {
                // let go of any held locks
                if (_requestedIdsLock.IsUpgradeableReadLockHeld)
                    _requestedIdsLock.ExitReadLock();
            }
        }

        return _cache[id];
    }

    public Collection<Item> Get(Collection<int> ids)
    {
        var notInCache = ids.Except(_cache.Keys);

        // if some items don't exist in cache
        if (notInCache.Count() > 0)
        {
            _requestedIdsLock.EnterUpgradeableReadLock();
            try
            {
                var needToGet = notInCache.Except(_requestedIds);

                // if any items have not yet been requested by other threads
                if (needToGet.Count() > 0)
                {
                    _requestedIdsLock.EnterWriteLock();
                    try
                    {
                        // record the current request
                        foreach (var id in ids)
                            _requestedIds.Add(id);

                        _requestedIdsLock.ExitWriteLock();
                        _requestedIdsLock.ExitUpgradeableReadLock();

                        // get the data from the external resource
                        #region fake implementation - replace with real code
                        var data = new Collection<Item>();
                        foreach (var id in needToGet)
                        {
                            var item = _externalDataStoreProxy[id];
                            data.Add(item);
                        }
                        Thread.Sleep(10000);
                        #endregion

                        lock (_cache)
                        {
                            foreach (var item in data)
                                _cache.Add(item.ID, item);

                            Monitor.PulseAll(_cache);
                        }
                    }
                    finally
                    {
                        // let go of any held locks
                        if (_requestedIdsLock.IsWriteLockHeld)
                            _requestedIdsLock.ExitWriteLock();
                    }
                }

                if (requestedIdsLock.IsUpgradeableReadLockHeld)
                    _requestedIdsLock.ExitUpgradeableReadLock();

                var waitingFor = notInCache.Except(needToGet);
                // if any remaining items were already requested by other threads
                if (waitingFor.Count() > 0)
                {
                    lock (_cache)
                    {
                        while (waitingFor.Count() > 0)
                        {
                            Monitor.Wait(_cache);
                            waitingFor = waitingFor.Except(_cache.Keys);
                        }

                        // once we get here, _cache has all our items
                    }
                }
            }
            finally
            {
                // let go of any held locks
                if (_requestedIdsLock.IsUpgradeableReadLockHeld)
                    _requestedIdsLock.ExitReadLock();
            }
        }

        return new Collection<Item>(ids.Select(id => _cache[id]).ToList());
    }
}

Update 2:

I misunderstood the behavior of UpgradeableReadLock... only one thread at a time can hold an UpgradeableReadLock. So the above should be refactored to only grab Read locks initially, and to completely relinquish them and acquire a full-fledged Write lock when adding items to _requestedIds.

Answer 2

Finally came up with a workable solution to this, thanks to some dialogue in the comments. What I did was create a wrapper, which is a partially-implemented abstract base class that uses any standard cache library as the backing cache (just needs to implement the Contains, Get, Put, and Remove methods). At the moment I'm using the EntLib Caching Application Block for that, and it took a while to get this up and running because some aspects of that library are... well... not that well-thought-out.

Anyway, the total code is now close to 1k lines so I'm not going to post the entire thing here, but the basic idea is:

1. Intercept all calls to the Get, Put/Add, and Remove methods.

2. Instead of adding the original item, add an "entry" item which contains a ManualResetEvent in addition to a Value property. As per some advice given to me on an earlier question today, the entry implements a countdown latch, which is incremented whenever the entry is acquired and decremented whenever it is released. Both the loader and all future lookups participate in the countdown latch, so when the counter hits zero, the data is guaranteed to be available and the ManualResetEvent is destroyed in order to conserve resources.

3. When an entry has to be lazy-loaded, the entry is created and added to the backing cache right away, with the event in an unsignaled state. Subsequent calls to either the new GetOrAdd method or the intercepted Get methods will find this entry, and either wait on the event (if the event exists) or return the associated value immediately (if the event does not exist).

4. The Put method adds an entry with no event; these look the same as entries for which lazy-loading has already been completed.

5. Because the GetOrAdd still implements a Get followed by an optional Put, this method is synchronized (serialized) against the Put and Remove methods, but only to add the incomplete entry, not for the entire duration of the lazy load. The Get methods are not serialized; effectively the entire interface works like an automatic reader-writer lock.

It's still a work in progress, but I've run it through a dozen unit tests and it seems to be holding up. It behaves correctly for both the scenarios described in the question. In other words:

• A call to long-running lazy-load (GetOrAdd) for key X (simulated by Thread.Sleep) which takes 10 seconds, followed by another GetOrAdd for the same key X on a different thread exactly 9 seconds later, results in both threads receiving the correct data at the same time (10 seconds from T₀). Loads are not duplicated.

• Immediately loading a value for key X, then starting a long-running lazy-load for key Y, then requesting key X on another thread (before Y is finished), immediately gives back the value for X. Blocking calls are isolated to the relevant key.

It also gives what I think is the most intuitive result for when you begin a lazy-load and then immediately remove the key from the cache; the thread that originally requested the value will get the real value, but any other threads that request the same key at any time after the removal will get nothing back (null) and return immediately.

All in all I'm pretty happy with it. I still wish there was a library that did this for me, but I suppose, if you want something done right... well, you know.