Practical Concurrency Patterns: Safe/Unsafe Cache
After having examined a classical reader-writer-lock-based cache and a thread-local cache, we have come to terms with the deficiencies of both alternatives. A classical RWL-cache requires a lock (albeit a cheap one) for every operation, including a read, even though contention doesn't occur until there's a write. A TLS-cache is fine where the worker threads are countable and controllable, but becomes inapplicable when hundreds of threads from the thread pool are spawned and destroyed.
An alternative to these approaches is not using locks at all, or at least avoid from locking the entire collection. For example, consider the following scenario:
- A bank maintains a dictionary mapping a currency to its current rate
- The data is updated very often as the various currencies are traded, and the updates are received from many different sources
- The data is read very often as different clients request the values of various currencies
Using an RWL-cache or a TLS-cache in this scenario is unrealistic. The TLS-cache is not feasible because the number of clients is unknown, so we cannot dedicate a worker thread to each client and use the thread pool instead. The RWL-cache is not feasible because there's a gigantic amount of reads and writes and the contention would dash any hopes of scaling this kind of application. (And it certainly sounds like it would need scaling...)
However, there is one noticeable thing in this scenario. The values in the dictionary are changing very frequently; but the dictionary itself is kept unchanged. While it is theoretically possible that through the course of a day new currencies will enter the bank's trading system, it is a fairly unlikely event that we shouldn't be optimizing for.
This effectively means that in this example, the dictionary can be kept read-only, with the values changing - requiring a lock only on something associated with the value (e.g. the currency string representation), and not the entire dictionary. Additionally, since changing the value in the dictionary is often an operation that we can perform atomically (e.g. a reference swap or an integer assignment), we can eliminate locking in the general case. (We'll discuss lock-free operations in a subsequent installment.)
However, we still have to handle the specific scenario where a new currency is added during trade hours. It has to be addressed because if the general dictionary is used without locking, we can't simply perform an insert. We need another dictionary that will be used for these exceptional currencies that have been added during trade hours - the rest of the currencies will still be stored in the read-only dictionary.
I've first encountered this pattern in code written by Alon Fliess, so I will use his terminology - he called it a Safe/Unsafe Cache, even though it's effectively an adapter over any collection type. A sample implementation goes along the following lines:
public interface ICache<K, V>
{
V Get(K key);
V GetOrCreate(K key, Func<K, V> creator);
}
public class SafeUnsafeAdapter<T, K, V> : ICache<K, V>
where T : ICache<K, V>, new()
{
Dictionary<K, V> _safeCache = new Dictionary<K, V>();
T _unsafeCache = new T();
volatile bool _isUnsafe;
public void SwitchToUnsafe()
{
_isUnsafe = true;
//Thread-safe from here on,
//single-threaded until this point
}
public V Get(K key)
{
if (!_isUnsafe)
{
return _safeCache[key];
}
else
{
V val;
if (!_safeCache.TryGetValue(key, out val))
{
return _unsafeCache.Get(key);
}
return val;
}
}
public V GetOrCreate(K key, Func<K, V> creator)
{
V val;
if (!_safeCache.TryGetValue(key, out val))
{
if (!_isUnsafe)
{
val = creator(key);
_safeCache.Add(key, val);
return val;
}
else
{
return _unsafeCache.GetOrCreate(key, creator);
}
}
return val;
}
}
This can be best summarized as follows:
- Single-threaded initialization work proceeds against the "safe" cache, which cannot be accessed from multiple threads. This work doesn't require synchronization.
- At some point, the "safe" cache is locked for modification - further inserts will not modify it. From this point on, the cache can be accessed from multiple threads but the safe cache doesn't require locking - because it's only accessed for reading.
- Inserts to the "unsafe" cache go to a separate dictionary. Whenever a lookup in the "safe" cache fails, it is attempted from the "unsafe" cache - by taking a lock.
Going back to our example, most currencies are statically known when the system is initialized. This means that during initialization, we insert the currency data into the safe cache and switch to unsafe, thereby preventing its further modification and making all work lock-free. In the exceptional case where a currency is added during the day, we resort to the unsafe cache to perform the insert and the subsequent lookups - but most of the time, our work is lock-free.