Justin Rogers

Architecting your own cache. Speed, efficiency, memory consumption, AND it has to actually work?

For the Project Distributor application we want to implement some caching. We have a number of options that we can use for this process, including making use of the default ASP .NET caching, but since I had some spare time I figured I'd throw 30 minutes at writing my own cache. I'm looking at a number of techniques based on my performance knowledge and hopefully I've identified most of the common methods of running a cache. The first problem is allowing keyed entries and it can be solved in many ways.

1. Use a Hashtable or a NameValueCollection or any other key indexed collection that might suit your fancy.
2. Use something like a SortedArray that I've written about previously. These are fast and they work well for small numbers.
3. Use a tree or skip-list as noted by some other individuals.

I'll let the cat out of the bag. I've chosen the SortedArray because it really is fast until you reach an insanely large number of items. Because it is sorted, key lookups are a matter of doing a quick BinarySearch. Picking the collection is only half the problem. Next you have to decide how much additional data to store with your items so they can be properly collected. You at least need to store a last modified time, else you'll get into trouble quick. Remember cache items expire after a certain period of time in most cases (and more rarely at the occurence of an event).

If we store just the date, what does a recycling process look like? Well, we have to iterate through the entire collection and look at the dates to see if the items should be collected. This is fairly bogus and would take a large amount of time for us to accomplish. Another option would be to store an ordered list of last access times. Then the problem becomes that during each update we have to find the original item in that list, remove it, and add a new item to the end of the list with the new time. Darn, that hurts as well, but since it is ordered, and new items get appended to the end, the only management will be shrinking during a removal.

If we decide to store more data with the item we can do something else entirely. A version number that gets incremented on each access. You might ask what this accomplishes. Well, now rather than storing a collection of dates that must be managed we can store a queue of access information. Each access results in the item's key and the version number being placed in the queue. Now, during a recycle operation we can check the front of the queue, and then look up the associated item. If the version numbers are different, we continue, otherwise we do the date check. We'll cycle through the queue all the way up to the first matching version number where the date hasn't timed out. This isn't without it's trade-offs though, so I'll enumerate some of them.

1. The queue can grow as large as the number of accesses that occur during your cache expiration period.
2. Working through the queue requires a BinarySearch for each item. If the same item is being requested many times over it will have many entries into the queue and you'll spend time searching for the same item over and over.

Depending on your back-end those can be pretty hefty problems. What I'll point out here is that for a small queue of frequently accessed items, you won't use an LRU queue at all. You'll instead cycle through the entire queue for recycling. If you don't need items to preemptively remove themselves, you can wait until they are accessed beyond their timeout period and then remove them at that time. There are other structures you can add, such as an MRU queue where you keep the last N used items. Any items not in the MRU queue get removed from the system during a recycle.

How does a recycle work? Well, plenty of heuristic options for that as well.

1. Shortest period timeout. This option relies on finding the next item that will be removed and setting a timeout for it. One that item is removed you get the next shortest interval and set a timeout for that as well. Timeouts get allocated into buckets depending on how far in the future they reside to increase lookup performance.
2. Access timeouts work based on the user's use of the cache. If the user doesn't access the cache there aren't any timeouts and things sit. The more the user operates on the cache the more often the timeouts occur. This is simple enough using a basic byte. You can increment the byte each access and then recycle on a wrap-around to 0.
3. Cache barrier recycling. A cache barrier is when you allow only a specific number of items in the collection before you try to recycle. ASP .NET implements a mixture of cache barrier recycling (with priorities) and shortest period timeout. The benefits of cache barrier recycling are that you can throw out items until you come back under your barrier, irregardless of whether or not they've timed out. The bad thing here is that your application will be forced to fetch data more frequently.

A generic cache of any sort is actually harder to create than you might think. After all, the options that work at low loads don't scale to higher loads. The options at higher loads are very fast when there are lots of objects, but not as fast as a more specialized cache over smaller numbers of objects. In the end, the cache I'll be finalizing for storing objects will rely on a sorted array with binary search capabilities, a customized add method that handles version number consistency (write over top instead of add alongside), a customizable cache timeout (the only way for items to get removed), a linear search recycle method that upgrades to an LRU cache after a threshold, and retrieval timeouts just in case you want to turn cache recycling off.