How to purge expired items from cache?

Question

I've got a nice little class built that acts as a cache. Each item has an expiration TimeSpan or DateTime. Each time an attempt to access an item in the cache is made, the item's expiration is checked, and if it's expired, the item is removed from the cache and nothing is returned.

That's great for objects that are accessed frequently, but if an item is put in the cache and never accessed again, it's never removed, even though it's expired.

What's a good methodology for expiring such items from the cache?

Should I have a background thread infinitely enumerating every item in the cache to check if it's expired?

Answer 1

You can implement an LRU (Least Recently Used) strategy, keep your items sorted by access time, when a new item is inserted into the cache and the cache is full you evicted the item that is last in that list. See Cache algorithms at Wikipedia.

If you want to expire immediately, i would still only do that when things are accessed. I.e. when the cache object is accessed and it's time has expired refetch it.

Answer 2

You could also on any change to the cache (re-)start a Timer with the Interval set to the closest expiry timestamp. This will not be accurate to milliseconds and depend on a message pump running, but is not very resource-demanding.

Harald Scheirich's answer is better though, if you don't mind that objects are hanging around forever, when the cache is not updated.

Answer 3

You could clear suitably old items out of the cache on the first access after 1 minute after the last time items were cleared.

private DateTime nextFlush;
public object getItem(object key)
{
  DateTime now = DateTime.Now
  if (now > nextFlush)
  {
    Flush();
    nextFlush = now.AddMinutes(1)
  }
  return fetchItem(key);
}

Answer 4

In my experience, maintaining a custom caching mechanism became more trouble than it was worth. There are several libraries out there that have already solved these problems. I would suggest using one of them. A popular one in .Net is the Enterprise Library, although I have limited experience with it's caching abilities.

If you must use a custom caching mechanism, then I see no problem with a watchful thread idea you suggested. That is, if your application is a server based application and not a web app. If it's a web app, you already have built in sliding expiration. You can then just wrap it in a strongly typed wrapper to avoid referencing cache items by key each time.

Answer 5

The best code is no code. Use the ASP.NET cache instead. You can reference it as System.Web.HttpRuntime.Cache in any application, not just web applications.