How to prevent loading non-cached value simultanously many times?

Question

How to prevent loading the value that is not present in the cache many times simultanously, in the efficient way?

A typical cache usage is the following pseudocode:

Object get(Object key) {
 Object value = cache.get(key);
 if (value == null) {
  value = loadFromService(key);
  cache.set(key,value);
 }
 return value;
}

The problem: before the value is loaded from service (Database, WebService, RemoteEJB or anything else) a second call may be made in the same time, which will make the value loaded once again.

For example, when I'm caching all items for user X, and this user is often viewed, and have many items, there's high probability of calling the load of his all items simultanously, resulting in heavy load on the server.

I could make get function synchronized, but this would force other searches to wait, making not much sense. I could create new lock for every key, but I don't know if it's a good idea to manage such large number of locks in Java (this part is language specific, the reason I've tagged it as java).

Or there is another approach I could use? If so, what would be the most efficient?

Answer 1

Something you can do generically is to use the hashCode of the Object.

You can have an array of locks which used based on the hashCode to reduce the chance of collisions. Or as a hack you can use the fact that auto-boxed bytes always return the same objects.

Object get(Object key) {
    Object value = cache.get(key);
    if (value == null) {
        // every possible Byte is cached by the JLS.
        Byte b = Byte.valueOf((byte) key.hashCode());
        synchronized (b) {
            value = cache.get(key);
            if (value == null) {
                value = loadFromService(key);
                cache.set(key, value);
            }
        }
    }
    return value;
}

Answer 2

Don't reinvent the wheel, use guava's LoadingCache or memoizing supplier.

If you are using Ehcache, read about read-through, this is the pattern you are asking for. You must implement the CacheEntryFactory interface to instruct the cache how to read objects on a cache miss, and you must wrap the Ehcache instance with an instance of SelfPopulatingCache.

Answer 3

For the time of loading, insert an intermediate object in the map instead of the result to indicate that the loading started but not finished. Below java.util.concurrent.FutureTask is used for the intermediate object:

Object get(final Object key) throws Exception {
    boolean doRun = false;
    Object value;
    synchronized (cache) {
        value = cache.get(key);
        if (value == null) {
            value = new FutureTask(new Callable() {
                @Override
                public Object call() throws Exception {
                    Object loadedValue = loadFromService(key);
                    synchronized (cache) {cache.put(key, loadedValue);};
                    return loadedValue;
                }

            });
            cache.put(key, value);
            doRun=true;
        }
    }
    if (value instanceof FutureTask) {
        FutureTask task = (FutureTask) value;
        if (doRun) {
            task.run();
        }
        return task.get();
    }
    return value;
}`