Functional Caching
- Functional Caching
- Functional Caching Part 2: Concurrency
- Functional Caching Part 3: Decoration
- Functional Caching Part 4: Dependency Injection
- Consider this typical method for fetching orders:
Order GetOrder(int id)
In a certain context, such as a web request, we may want to return the same order instance for the same ID. This would ensure GetOrder(1) == GetOrder(1) holds true. It also removes the need to go to the data store multiple times for the same ID.
Dictionary<,> is very useful for this kind of caching:
private readonly Dictionary<int, Order> _cache = new Dictionary<int, Order>();
public Order GetOrder(int id)
{
Order order;
if(!_cache.TryGetValue(id, out order))
{
order = QueryOrder(id);
_cache[id] = order;
}
return order;
}
First, we check if we’ve queried for the order before. If so, we use it. If not, we perform the query and add the order to the cache.
This process isn’t specific to orders and begs to be generalized:
public class Cache<TKey, TValue>
{
private readonly Func<TKey, TValue> _valueFunction;
private readonly Dictionary<TKey, TValue> _cache = new Dictionary<TKey, TValue>();
public Cache(Func<TKey, TValue> valueFunction)
{
_valueFunction = valueFunction;
}
public TValue GetValue(TKey key)
{
TValue value;
if(!_cache.TryGetValue(id, out value))
{
value = _valueFunction(id);
_cache[key] = value;
}
return value;
}
}
This factors out the unique part of the operation, the actual retrieval of the value, into whatever method is encapsulated by valueFunction. We went from caching one specific method, GetOrder, to caching any method which takes a single argument and has a return value.
GetOrder can now delegate caching duties:
private readonly Cache<int, Order> _cache =
new Cache<int, Order>(id => QueryOrder(id));
public Order GetOrder(int id)
{
return _cache.GetValue(id);
}
Here, the results of the lambda expression id => QueryOrder(id) will be cached.
A Simpler Approach
We’ve established the key/value caching pattern and implemented it in object-oriented fashion as the Cache<,> class. While this solution is adequate for the scenario presented, there is an easier and (arguably) clearer way to express the same concept.
Memoization is an approach to caching that uses function composition to build methods which remember their output. The basic idea is to take a function and wrap it in a new function which caches the results:
public class OrderRepository
{
private
readonly Func<int, Order> _query;
public OrderRepository()
{
_query = id => QueryOrder(id);
_query = _query.Cached();
}
public Order GetOrder(int id)
{
return _query(id);
}
// …
}
We create a function representing the order query, then call an extension method to get a cached version. This states our intent, "cache the results of this query", much clearer than the original GetOrder.
Cache<,> is no longer necessary, since both cached and uncached operations are the same type, Func<,>. This symmetry enables some nice scenarios, such as the seamless caching above.
Nitty Gritty
Cached has all the elements of Cache<,>:
public static Func<TKey, TValue> Cached<TKey, TValue>(
this Func<TKey, TValue> valueFunction)
{
var cache = new Dictionary<TKey, TValue>();
return key =>
{
TValue value;
if(!cache.TryGetValue(key, out value))
{
value = valueFunction(key);
cache[key] = value;
}
return value;
};
}
The extension method applies to any one-argument function. It returns a function with the same signature, and whose body wraps the original and caches its results.
The new function is a closure, a lambda expression which can capture variables. The code is packaged to be run later, and referenced variables such as valueFunction and cache will be evaluated at that time. This means that although cache is only scoped to a method call, it will be referenced by the closure and thus avoid garbage collection.
Summary
A common approach to caching is using a dictionary. We identified that as an implementation detail and focused on the intent to cache an operation’s results. We also composed building blocks such as functions and extension methods to help us hide the how and bring out the why.
Posts