Threadsafe double buffered cache (not for graphics) in Java?

Question

I was recently looking for a way to implement a doubly buffered thread-safe cache for regular objects.

The need arose because we had some cached data structures that were being hit numerous times for each request and needed to be reloaded from cache from a very large document (1s+ unmarshalling time) and we couldn't afford to let all requests be delayed by that long every minute.

Since I couldn't find a good threadsafe implementation I wrote my own and now I am wondering if it's correct and if it can be made smaller... Here it is:

package nl.trimpe.michiel

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

/**
 * Abstract class implementing a double buffered cache for a single object.
 * 
 * Implementing classes can load the object to be cached by implementing the
 * {@link #retrieve()} method.
 * 
 * @param <T>
 *            The type of the object to be cached.
 */
public abstract class DoublyBufferedCache<T> {

    private static final Log log = LogFactory.getLog(DoublyBufferedCache.class);

    private Long timeToLive;

    private long lastRetrieval;

    private T cachedObject;

    private Object lock = new Object();

    private volatile Boolean isLoading = false;

    public T getCachedObject() {
     checkForReload();
     return cachedObject;
    }

    private void checkForReload() {
     if (cachedObject == null || isExpired()) {
      if (!isReloading()) {
       synchronized (lock) {
        // Recheck expiration because another thread might have
        // refreshed the cache before we were allowed into the
        // synchronized block.
        if (isExpired()) {
         isLoading = true;
         try {
          cachedObject = retrieve();
          lastRetrieval = System.currentTimeMillis();
         } catch (Exception e) {
          log.error("Exception occurred retrieving cached object", e);
         } finally {
          isLoading = false;
         }
        }
       }
      }
     }
    }

    protected abstract T retrieve() throws Exception;

    private boolean isExpired() {
     return (timeToLive > 0) ? ((System.currentTimeMillis() - lastRetrieval) > (timeToLive * 1000)) : true;
    }

    private boolean isReloading() {
     return cachedObject != null && isLoading;
    }

    public void setTimeToLive(Long timeToLive) {
     this.timeToLive = timeToLive;
    }

}

Answer 1

What you've written isn't threadsafe. In fact, you've stumbled onto a common fallacy that is quite a famous problem. It's called the double-checked locking problem and many such solutions as yours (and there are several variations on this theme) all have issues.

There are a few potential solutions to this but imho the easiest is simply to use a ScheduledThreadExecutorService and reload what you need every minute or however often you need to. When you reload it put it into the cache result and the calls for it just return the latest version. This is threadsafe and easy to implement. Sure it's not on-demand loaded but, apart from the initial value, you'll never take a performance hit while you retrieve the value. I'd call this over-eager loading rather than lazy-loading.

For example:

public class Cache<T> {
  private final ScheduledExecutorsService executor =
    Executors.newSingleThreadExecutorService();
  private final Callable<T> method;
  private final Runnable refresh;
  private Future<T> result;
  private final long ttl;

  public Cache(Callable<T> method, long ttl) {
    if (method == null) {
      throw new NullPointerException("method cannot be null");
    }
    if (ttl <= 0) {
      throw new IllegalArgumentException("ttl must be positive");
    }
    this.method = method;
    this.ttl = ttl;

    // initial hits may result in a delay until we've loaded
    // the result once, after which there will never be another
    // delay because we will only refresh with complete results
    result = executor.submit(method);

    // schedule the refresh process
    refresh = new Runnable() {
      public void run() {
        Future<T> future = executor.submit(method);
        future.get();
        result = future;
        executor.schedule(refresh, ttl, TimeUnit.MILLISECONDS);
      }
    }
    executor.schedule(refresh, ttl, TimeUnit.MILLISECONDS);
  }

  public T getResult() {
    return result.get();
  }
}

That takes a little explanation. Basically, you're creating a generic interface for caching the result of a Callable, which will be your document load. Submitting a Callable (or Runnable) returns a Future. Calling Future.get() blocks until it returns (completes).

So what this does is implement a get() method in terms of a Future so initial queries won't fail (they will block). After that, every 'ttl' milliseconds the refresh method is called. It submits the method to the scheduler and calls Future.get(), which yields and waits for the result to complete. Once complete, it replaces the 'result' member. Subsequence Cache.get() calls will return the new value.

There is a scheduleWithFixedRate() method on ScheduledExecutorService but I avoid it because if the Callable takes longer than the scheduled delay you will end up with multiple running at the same time and then have to worry about that or throttling. It's easier just for the process to submit itself at the end of a refresh.

Answer 2

I'm not sure I understand your need. Is your need to a have a faster loading (and reloading) of the cache, for a portion of the values?

If so, I would suggest breaking your datastructure into smaller pieces. Just load the piece that you need at the time. If you divide the size by 10, you will divide the loading time by something related to 10.

This could apply to the original document you are reading, if possible. Otherwise, it would be the way you read it, where you skip a large part of it and load only the relevant part.

I believe that most data can be broken down into pieces. Choose the more appropriate, here are examples:

• by starting letter : A*, B* ...
• partition your id into two part : first part is a category, look for it in the cache, load it if needed, then look for your second part inside.

Answer 3

If your need is not the initial loading time, but the reloading, maybe you don't mind the actual time for reloading, but want to be able to use the old version while loading the new?

If that is your need, I suggest making your cache an instance (as opposed to static) that is available in a field.

1. You trigger reloading every minute with a dedicated thread (or a least not the regular threads), so that you don't delay your regular threads.

2. Reloading creates a new instance, load it with data (takes 1 second), and then simply replace the old instance with the new. (The old will get garbage-collected.) Replacing an object with another is an atomic operation.

Analysis: What happens in that case is that any other thread can get access to the old cache until the last instant ?
In the worst case, the instruction just after getting the old cache instance, another thread replaces the old instance with a new. But this doesn't make your code faulty, asking the old cache instance will still give a value that was correct just before, which is acceptable by the requirement I gave as first sentence.

To make your code more correct, you can create your cache instance as immutable (no setters available, no way to modify internal state). This makes it clearer that it is correct to use it in a multi-threaded context.

Answer 4

You appare to be locking more then is required, in your good case (cache full and valid) every request aquires a lock. you can get away with only locking if the cache is expired.

If we are reloading, do nothing.
If we are not reloading, check if expired if not expired go ahead. If we are not reloading and we are expired, get the lock and double check expired to make sure we have not sucessfuly loaded seince last check.

Also note you may wish to reload the cache in a background thread so not event the one requrest is heldup waiting for cache to fill.

    private void checkForReload() {
        if (cachedObject == null || isExpired()) {
                if (!isReloading()) {

                       // Recheck expiration because another thread might have
                       // refreshed the cache before we were allowed into the
                        // synchronized block.
                        if (isExpired()) {
                                synchronized (lock) {
                                        if (isExpired()) {
                                                isLoading = true;
                                                try {
                                                        cachedObject = retrieve();
                                                        lastRetrieval = System.currentTimeMillis();
                                                } catch (Exception e) {
                                                        log.error("Exception occurred retrieving cached object", e);
                                                } finally {
                                                        isLoading = false;
                                                }
                                        }
                                }
                        }
                }
        }