Static cache

Let's try to resolve a pretty regular case - some kind of key-value static cache. If there is no stored value for the specified key, the cache will call some external routine to get value and add it to the internal dictionary.

Here is a naive approach of the cache. It is straightforward enough.

public class Cache<TKey, TValue>
{
  Func<TKey, TValue> _resolver;
  Dictionary<TKey, TValue> _cache = new Dictionary<TKey, TValue>();

  public Cache(Func<TKey, TValue> resolver)
  {
    _resolver = resolver;
  }

  public TValue this[TKey key]
  {
    get
    {
       TValue value;
       if (!_cache.TryGetValue(key, out value))
       {
         value = _resolver(key);
         _cache.Add(key, value);
       }
       return value;
    }
  }
}

And also somewhere in a client code:

class ClientCode
{
  static Cache<TKey, TValue> _cache = new Cache<TKey, TValue>(Resolver);
}

Where Resolver is an user-defined function to get a value from the outer source.



Hope, you see where the approach is weak - it is not thread-safe. The naive code is not protected from concurrent writing and reading. Let's try to fix our class.

From the first view, it is enough to wrap whole getter in a lock:

class ClientCode
  public TValue this[TKey key]
  {
    get
    {
       lock(_monitor)
       {
           TValue value;
           if (!_cache.TryGetValue(key, out value))
           {
             value = _resolver(key);
             _cache.Add(key, value);
           }
           return value;
      }
    }
  }

_monitor is just a private field initialized with new object.

This solution makes our class thread-safe, but let's imagine the following use case. Let's assume that our external routine (_resolver) is very slow. In this case the _cache becomes locked for very long time in cases of cache misses. Moreover, in case of cache miss, the cache will be locked even for reading.

To resolve the reading locking issue, some inexperienced developer could try to use double-checked locking pattern:

Invalid solution

public TValue this[TKey key]
{
 get
 {
  TValue value;
  if (!_cache.TryGetValue(key, out value))
  {
   lock (_monitor)
   {
    if (!_cache.TryGetValue(key, out value))
    {
     value = _resolver(key);
     _cache.Add(key, value);
    }
   }
  }
  return value;
 }
}

While double-checked locking pattern is a good one for lazy initializations, it never should be used for manipulations with collections (I'll post about it a bit later, in two words - while writing is under lock, reading is not).

So, the next choice could be Read-Write lock, but there is a better solution for this particular case. Let's look on the locking issue more deeper.

The issue is that cache values are actually not coupled with each other, but all of these items share the same lock. Another issue is that potential slow routine (_resolver) is called under this shared lock. So let's separate these locks - first lock will be used to protect _cache and then let's use individual locks for every cached value and lock this individual locks only if the value is not yet fetched from the _resolver. Here is the mentioned solution:

public class Cache<TKey, TValue>
{
  object _monitor = new object();
  Func<TKey, TValue> _resolver;
  Dictionary<TKey, CacheItem> _cache = new Dictionary<TKey, CacheItem>();

  public Cache(Func<TKey, TValue> resolver)
  {
   _resolver = resolver;
  }

  public TValue this[TKey key]
  {
   get
   {
    CacheItem item;
    lock (_monitor)
    {
     if (!_cache.TryGetValue(key, out item))
     {
      item = new CacheItem();
      _cache.Add(key, item);
     }
    }
    return item.GetValue(key, _resolver);
   }
  }

  internal class CacheItem
  {
   readonly object _itemMonitor = new object();
   private volatile bool _isInitialized;
   private TValue _value;

   public TValue GetValue(TKey key, Func<TKey, TValue> resolver)
   {
    if (!_isInitialized)
    {
     lock (_itemMonitor)
     {
      if (!_isInitialized)
      {
       _value = resolver(key);
       _isInitialized = true;
      }
     }
    }
    return _value;
   }
  }
}

Let's track the flow:

1. The _cache is protected by _monitor. Meantime, it is locked only for the very quick operation - get or create a cache item.
2. Every cache item has its individual lock.
3. The cache item is protected from being initialized twice by using double-checked locking pattern and it perfectly fits here.

Note: The class could be slightly simplified by using Lazy<T> from .NET 4.0.

public class Cache<TKey, TValue>
private Dictionary<TKey, Lazy<TValue>> _cache = new Dictionary<TKey, Lazy<TValue>>();
public TValue this[TKey key]
{
 get
 {
  Lazy<TValue> item;
  lock (_monitor)
  {
   if (!_cache.TryGetValue(key, out item))
   {
    item = new Lazy<TValue>(() => _resolver(key), LazyThreadSafetyMode.ExecutionAndPublication);
    _cache.Add(key, item);
   }
  }
  return item.Value;
 }
}