How handle cache misses: NotFoundException, contains() or `if (null == result)`?

Question

Maybe this is slightly academic, but if I implement a cache for speeding up an application, how should I best handle cache misses? (In my case, the language would be Java, but maybe the answer can be more general.)

Throw an exception:

ResultType res;
try {
    res = Cache.resLookup(someKey);
} catch (NotFoundException e) {
    res = Cache.resInsert(someKey, SlowDataSource.resLookup(someKey));
}

Ask before fetch:

ResultType res;
if (Cache.contains(someKey) {
    res = Cache.resLookup(someKey);
} else {
    res = Cache.resInsert(someKey, SlowDataSource.resLookup(someKey));
}

Return null:

ResultType res;
res = Cache.resLookup(someKey);
if (null == res) {
    res = Cache.resInsert(someKey, SlowDataSource.resLookup(someKey));
}

Throwing an Exception seems wrong, after all, this isn't an error. Letting the Cache do a look up for contains() and then again to retrieve the data seems wasteful, especially as this would occur every time. And checking for null of course requires that null can never be a valid result...

Answer 1

I would tend towards a checked exception, since you can't inadvertently ignore it and accidently return a null. I'm assuming (unlike most people here) that a cache miss is an unusual scenario.

I also assume you're talking about the cache internal implementation. From the client perspective this should be invisible.

Answer 2

The first is excessive I think and not a good use for exceptions. Do you have an expectation that there will be a cache hit? A cache miss is a fairly normal occurrence I would think and thus an exception becomes simply flow control. Not good imho.

The second is a race condition. There is a time delay between checking on the existence of the cache entry and querying it. That could lead to all sorts of trouble.

Returning null is probably appropriate in the general sense but that comes with some qualifications.

Firstly, what type of cache is it? Ideally you'd be talking to a read-through cache in which case if it's not in the cache it'll simply get it from the source, which is not the style of code you've written there.

Secondly, the get then insert is another race condition. Look at the interface for ConcurrentHashMap for a good general way of dealing with this kind of thing. Most notably, the putIfAbsent() call is an atomic operation that does the equivalent of you're third call.

Answer 3

The last option (if null == result) is best, in my opinion.

A cache miss is not an exceptional condition, and should be handled in the normal code flow.

And if the action of checking if something exists in the cache may be a somewhat expensive operation (e.g. the network overhead of a memcached call), it shouldn't be a separate operation. Also, the value of contains() may change before you actually retrieve the item, if the cache is shared among threads.

Answer 4

Since you are speeding up an existing api via caching the invisible one (2nd one) would apply. I say this as I'm assuming that the api exists and you're not prematurely optimising.

Answer 5

(3) looks like the easiest to read and most performant (even though the actual difference in performance between these alternatives is problably neglible).

With (2) you have to make two lookups in the cache (first "contains" and then "resLookup").

With (1) you create an additional object, the code gets more complicated and harder to read, and a cache miss isn't a exceptional case.

Answer 6

From a 'clear code' perspective

1. A cache-miss is not an exception but a normal case. So I'd not use an Exception here.
2. null-values should be avoided when ever possible. Choose something meaningful instead
3. This leaves option 'ask before fetch' or a variation of your third option, where you don't return 'null' but a special ResultType object that signals a cache-miss

Example:

public class ResultType {

  public final static ResultType CACHE_MISS = new ResultType();

  // ... rest of the class implementation

}

and later on

ResultType res;
res = Cache.resLookup(someKey);
if (ResultType.CACHE_MISS == res) {
    res = Cache.resInsert(someKey, SlowDataSource.resLookup(someKey));
}

Advantage over 'null' solution: the reader now immediatly knows that is 'if' handles a cache miss.

Answer 7

What about a 4th option? You could use a holder for the return value, and have the lookup return a boolean for success:

ResultHolder result = new ResultHolder();
if(!cache.resLookup(someKey, result))
{
    // get from slower source and insert to cache
}

if(result.value == null)
{
    // special case if you wanted null as a valid value
}

This is basically your third option, keeping a single call, but if you wanted to have null as a value you could.