Thread safety through callbacks

While callbacks are good at proving prerequisites, they are also good at proving thread safety. Take, for example, this cache:

public class CachedObject<TValue>
{
    public TValue Value { get; private set; }
    public DateTime DateCached { get; private set; }

    public CachedObject(TValue value, DateTime dateCached)
    {
        Value = value;
        DateCached = dateCached;
    }
}

public class Cache<TKey, TValue>
{
    private TimeSpan _expiry;
    private Dictionary<TKey, CachedObject<TValue>> _store =
        new Dictionary<TKey, CachedObject<TValue>>();

    public Cache(TimeSpan expiry)
    {
        _expiry = expiry;
    }

    public TValue Get(TKey key)
    {
        CachedObject<TValue> found;

        // If the object is in the cache, check the date.
        if (_store.TryGetValue(key, out found) &&
            found.DateCached + _expiry < DateTime.Now)
        {
            return found.Value;
        }
        else
        {
            return default(TValue);
        }
    }

    public void Put(TKey key, TValue value)
    {
        _store.Add(key, new CachedObject<TValue>(value, DateTime.Now));
    }
}

The caller has to use it properly for it to work. They have to call Get before Put (prerequisite), and they have to synchronize around the two calls. If they don't, they run the risk of creating a race condition.

A race condition occurs when the outcome of an operation depends upon other operations happening in parallel. If one thread gets finished first, there is one result. If another thread finishes first, there is another. In this case, two threads could try to Get the same value. Finding none, they can both race to fetch the value and put it in the cache.

To prove that a race condition cannot occur, we can use a callback.

public class Cache<TKey, TValue>
{
    private TimeSpan _expiry;
    private Dictionary<TKey, CachedObject<TValue>> _store =
        new Dictionary<TKey, CachedObject<TValue>>();

    public Cache(TimeSpan expiry)
    {
        _expiry = expiry;
    }

    public TValue Get(TKey key, Func<TKey, TValue> fetch)
    {
        lock (_store)
        {
            CachedObject<TValue> found;

            // If the object is not in the cache, or it is expired,
            // fetch it and add it to the cache.
            DateTime now = DateTime.Now;
            if (!_store.TryGetValue(key, out found) ||
                found.DateCached + _expiry >= now)
            {
                found = new CachedObject<TValue>(fetch(key), now);
               _store.Add(key, found);
            }
            return found.Value;
        }
    }
}

This version of the cache takes a callback to fetch the value if it is not found. Synchronization is now built into the Get method. The caller doesn't need to synchronize around it. More importantly, we can prove the correctness of the code without seeing the caller. There is no way to get it wrong.

This cache still has problems. The lock is to broad. In preventing a race condition on two thread getting the same value, we've inadvertently blocked two threads getting different values. We'll fix that next.

This entry was posted on Wednesday, September 16th, 2009 at 11:00 am and is filed under qed. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.