Caching the non-existence of data

Generally, when you look an item up in a cache, you:

• Check the cache for the item
• If it's not found, go get the item from the backing store
• Put the item into the cache, and return it to your caller

But what should the behavior be when the caller wants to look for a non-existent item?

A simple implementation is to use the same algorithm as above, except that the last step then becomes:

• Return to your caller the fact that no such item was found.

This is a fine implementation, and probably works well for many cases.

However, if (a) it's expensive to go get the item from the backing store, and (b) requests for non-existent items are routine, then you may find this implementation unsatisfactory.

Instead, you might want to consider caching the non-existence of the item, by which I mean you could have your cache have a special cache entry which allows you to hold a "no such item with this key exists" token, so that when your caller asks for an item which does not exist, you can satisfy that request from your cache.

There are a variety of details that exist in this implementation, but I think that the basic idea is sound. For the cache that I maintain at work, I'm considering whether I need to pursue this idea, because I have some reason to believe that some of my performance issues are due to requests for non-existent data.

But first I'm going to try to figure out why my callers are asking for the non-existent data routinely, because I don't think that should be a common behavior, and might indicate a bug in the callers.

Yet it got me wondering: how do other caches behave? Is it fairly routine for a modern object cache implementation to cache information about non-existing objects? Or do most caches only cache information about existing objects?