LRU Cache

The file

LRUCache.cs

Sometimes you just want a simple cache

Microsoft did good by moving System.Web.Caching to System.Runtime.Caching but even their cache puts a lot of work on you to check values are in the cache, add them and remove them. What we need is a simple light weight way of storing and retrieving our 'slow to access' data and to be able to control how much of this data we store in memory.

LRU, the classic cache

We are looking for a straight forward least recently used cache. That is our cache will only store a fixed number of items and if we go over our fixed number we will remove the oldest item in the cache. Nice and simple, the classic cache.

The usage we want is something like

//create a cache with a specified size, and a delegate that tells the cache how to use
//a key to go and find the actual data
var cache = new Cache<string, Person>(1000, key => db.Find(p=>p.ItemID==key));

//now just read values from the cache, it will do the rest, that is it will return
//the value from memory if its in the cache, otherwise it will go and retrieve it
//and add it to the cache, removing old values if we have got a full cache
Person p = cache["jbloggs"];

//we can force a key to invalidate (i.e. we just updated the data and need it refetched)
cache.Invalidate("jbloggs");

There is nothing so different or special about this cache and you will be able to find dozens of similar implementations in the internet, but for some reason there is no default implementation in the .NET framework. For the ease of copying and pasting into projects the whole C# file is reproduced here

using System;
using System.Collections.Generic;
using System.Linq;

namespace LiteCache
{

    /// <summary>
    /// Represents a LRU cache. Recently accessed elements remain in the cache while older items
    /// are removed
    /// </summary>
    /// <typeparam name="Key"></typeparam>
    /// <typeparam name="Value"></typeparam>
    public class LRUCache<Key, Value>
    {
        protected class LRUCacheElement
        {
            public Key Key;
            public Value Value;
            public LRUCacheElement(Key key, Value value)
            {
                this.Key = key;
                this.Value = value;
            }
        }


        protected object _lock = new object();
        protected int _maxCacheSize;
        protected Converter<Key, Value> _retrivalMethod;
        protected Dictionary<Key, LinkedListNode<LRUCacheElement>> _cache = new Dictionary<Key, LinkedListNode<LRUCacheElement>>();
        protected LinkedList<LRUCacheElement> _lru = new LinkedList<LRUCacheElement>();

        /// <summary>
        /// Create a cache with unlimited size
        /// </summary>
        /// <param name="retrivalMethod">method used to retrieve items given a key</param>
        public LRUCache(Converter<Key, Value> retrivalMethod) : this(int.MaxValue, retrivalMethod) { }

        /// <summary>
        /// Create a LRU cache with the given size
        /// </summary>
        /// <param name="cacheSize">maximum size of the cache</param>
        /// <param name="retrivalMethod">method to use when retrieving items from keys</param>
        public LRUCache(int cacheSize, Converter<Key, Value> retrivalMethod)
        {
            this._maxCacheSize = cacheSize;
            this._retrivalMethod = retrivalMethod;
        }

        /// <summary>
        /// Maximum number of elemetns this cache can hold
        /// </summary>
        public int MaxCacheSize
        {
            get
            {
                return _maxCacheSize;
            }
        }

        /// <summary>
        /// Number of items currently held in the cache
        /// </summary>
        public int CurrentCacheSize
        {
            get
            {
                return _lru.Count;
            }
        }

        /// <summary>
        /// All the items currently held in this cache, in order of least recently used
        /// </summary>
        public List<Value> CachedItems
        {
            get
            {
                return _lru.ToList().ConvertAll(e=>e.Value);
            }
        }

        /// <summary>
        /// Get an item given a key. If this item is in the cache the cached value is used
        /// otherwise it will run the retrival method and cache the result
        /// </summary>
        /// <param name="key">key to get the item</param>
        /// <returns>the item</returns>
        public virtual Value this[Key key]
        {
            get
            {
                lock (_lock)
                {
                    LinkedListNode<LRUCacheElement> linkedListNode;

                    if (!_cache.TryGetValue(key, out linkedListNode))
                    {
                        Value value = _retrivalMethod(key);
                        _cache[key] = _lru.AddFirst(new LRUCacheElement(key, value));

                        if (_lru.Count > _maxCacheSize)
                        {
                            _cache.Remove(_lru.Last.Value.Key);
                            _lru.RemoveLast();
                        }
                        return value;
                    }
                    else
                    {
                        //only bother moving rencetly accessed items if
                        //our cache has a size limit, otherwise we dont need to bother
                        if (_maxCacheSize < int.MaxValue)
                        {
                            _lru.Remove(linkedListNode);
                            _lru.AddFirst(linkedListNode);
                        }
                        return linkedListNode.Value.Value;
                    }

                }

            }
        }


        /// <summary>
        /// Invalidates an item with the given key. This item is cleared from the cache but will be
        /// reretrieved using the retrival method on its next access
        /// </summary>
        /// <param name="key"></param>
        public virtual void Invalidate(Key key)
        {
            lock (_lock)
            {
                LinkedListNode<LRUCacheElement> linkedListNode;
                if (!_cache.TryGetValue(key, out linkedListNode))
                    return;
                _lru.Remove(linkedListNode);
                _cache.Remove(key);
            }
        }

        /// <summary>
        /// Invalidates all items in the cache
        /// </summary>
        public virtual void InvalidateAll()
        {
            lock (_lock)
            {
                _lru.Clear();
                _cache.Clear();
            }
        }
    }
}

The cache is implemented with a dictionary and a linked list. The dictionary allows quick look ups on linked list items and cache values. The linked list allows us to keep track of age, when an item is accessed we move it to the front of the linked list and when we have too many items in our cache we can delete the item at the end of the linked list. All these operations are wrapped up in a lock to ensure the threads play nice.

Not all cases are simple

As nice as an LRU cache is, you still need to be aware that it is not the final word on your caching solution. This cache is only in memory and items need to be invalidated by the application to remove them from the cache. This means as soon as you use this cache on frequently changing data on a farmed web server all sorts of bad things will happen as each web server is reading a different cached version of the data. In cases like this you will need to have a look at separate cache server solutions such as Azure App Fabric or memcached

In the given cache solution it is up to you to invalidate cache items if they get modified, if you miss a place where an item is updated then your application could potentially be stuck with incorrect data until someone restarts the server. It is not a difficult extension to this cache to add timed expiries but as I was going for a simple cache ill leave the extension to you.