Practical Concurrency Patterns: Read-Write Cache
Assume that you have a set of worker threads producing and consuming information. In the process, there's some generated data that can be cached instead of being calculated every time it is accessed.
A typical solution for this problem is a thread-safe read-write cache (e.g. a .NET Dictionary) that will contain the calculated data. Due to its changing nature, a lock must be taken when reading from the cache and when writing to the cache. This is typically a reader-writer lock, unless the data is changing very frequently.
The following is a straightforward sketch of an implementation:
public class ReadWriteCache<TKey, TValue>
{
private Dictionary<TKey, TValue> _dict = new Dictionary<TKey, TValue>();
private ReaderWriterLockSlim _rwl = new ReaderWriterLockSlim();
public TValue Get(TKey key)
{
//Throw if not found:
_rwl.EnterReadLock();
try
{
return _dict[key];
}
finally
{
_rwl.ExitReadLock();
}
}
public TValue GetOrCreate(TKey key, Func<TKey, TValue> creator)
{
//Start with a read lock to optimize
_rwl.EnterReadLock();
try
{
TValue oldVal;
if (_dict.TryGetValue(key, out oldVal))
return oldVal;
}
finally
{
_rwl.ExitReadLock();
}
//Multiple threads can calculate the value concurrently
TValue val = creator(key);
_rwl.EnterUpgradeableReadLock();
try
{
TValue newVal;
if (_dict.TryGetValue(key, out newVal))
return newVal; //Someone else has added
_rwl.EnterWriteLock();
try
{
_dict.Add(key, val);
return val;
}
finally
{
_rwl.ExitWriteLock();
}
}
finally
{
_rwl.ExitUpgradeableReadLock();
}
}
}
This solution uses a ReaderWriterLockSlim, introduced in .NET 3.5, and attempts to minimize the write locks as much as possible. Nonetheless, accessing the cache is always associated with a lock, even if the lock is not taken and only readers enter it.
Using this cache is very easy. The following is a simple Parallel Extensions loop that uses 10 threads to access the cache and retrieve integer squares from it:
ReadWriteCache<int, int> squares = new ReadWriteCache<int, int>();
Parallel.For(0, 10, (i) =>
{
for (int k = 0; k < 100; ++k)
{
Thread.Sleep(Math.Abs(k - i));
Console.WriteLine(squares.GetOrCreate(k, x =>
{
Console.WriteLine("CALCULATING square {0}", x);
return x * x;
}));
}
});
If the data stored under the lock is accessed very frequently, and the cost of calculating it is not very high, this approach might introduce too much contention into the system, diminishing the effects of caching in the first place. In the next two posts, we will examine two different techniques for removing this overhead in specific scenarios.