Multi-thread object->object cache map in Java?

Question

I want a collection in Java which:

• maps arbitrary Objects to Objects (not String or otherwise restricted keys only)
• will be used as a cache; if the key is not in the cache, a value will be computed (this doesn't have to be built into the collection)
• will be accessed from multiple threads simultaneously
• will never have items removed from it
• must be very efficient to read (cache hit); not necessarily efficient to write (cache miss)

It's OK if cache misses simultaneously in multiple threads cause redundant computations; the typical case is that the cache is mostly filled by one thread at first.

A synchronized block around a thread-unsafe hashtable fails the efficient-to-read criterion. Thread-local caches would be straightforward but mean that new threads are expensive since they have full copies of the cache.

Java 1.5 built-ins, or one-or-few class files we can copy into our MIT-licensed project, are preferred, rather than large external libraries.

Answer 1

This is my own idea for a solution, but I'm not an expert on threaded programming, so please comment/vote/compare to other answers as you feel appropriate.

Use a thread-local variable (java.lang.ThreadLocal) which contains a per-thread hashtable used as a first-level cache. If the key is not found in this table, synchronized access is done to a second-level cache, which is a synchronized-access hashtable shared by all threads. In this way, the calculation of the cache value is only ever done once, and it is shared among all threads, but each thread has a local copy of the mapping from keys to values, so there is some memory cost (but less than having independent per-thread caches), but reads are efficient.

Answer 2

How about the cache described in section 5.6 of Concurrency In Practice, by Brian Goetz? It's outlined here.

It only uses classes from the java.util.concurrent package.

The linked article builds up a cache and describes the weaknesses of each version, until final version is an efficient cache in which only one concurrent thread will compute an absent entry.

I've cut and pasted the final code below, but its worth reading through the article and thinking about the issues outlined. Or even better - buy the book - it's great.

import java.util.concurrent.*;

public class Memoizer<A, V> implements Computable<A, V> {
  private final ConcurrentMap<A, Future<V>> cache
      = new ConcurrentHashMap<A, Future<V>>();
  private final Computable<A, V> c;
  public Memoizer(Computable<A, V> c) { this.c = c; }
  public V compute(final A arg) throws InterruptedException {
      while (true) {
          Future<V> f = cache.get(arg);
          if (f == null) {
              Callable<V> eval = new Callable<V>() {
                  public V call() throws InterruptedException {
                      return c.compute(arg);
                  } 
              };
              FutureTask<V> ft = new FutureTask<V>(eval);
              f = cache.putIfAbsent(arg, ft);
              if (f == null) {
                  f = ft;
                  ft.run();
              }
          }
          try {
              return f.get();
          } catch (CancellationException e) {
              cache.remove(arg, f);
          } catch (ExecutionException e) {
          // Kabutz: this is my addition to the code...
          try {
             throw e.getCause();
          } catch (RuntimeException ex) {
              throw ex;
          } catch (Error ex) {
              throw ex;
          } catch (Throwable t) {
              throw new IllegalStateException("Not unchecked", t);
          }
        }
     }
  }
}

Answer 3

Use the java concurrent hashmap

ConcurrentHashMap<object, object> table;

public object getFromCache(object key)
{
    value = table.get(key);

    if (value == null)
    {
        //key isn't a key into this table, ie. it's not in the cache
        value = CalculateValueForKey(key)
        object fromCache = table.putIfAbsent(key, value);
    }

    return value;
}

/**
* This calculates a new value to put into the cache
*/
public abstract object CalculateValueForKey(object key);

N.b. This is not longer a general solution for multithreaded caching, since it relies on the stated fact that objects are immutable, and thus object equivalence is not important.

Answer 4

How about something like this SingletonCache class from one of my projects?

public abstract class SingletonCache<K, V> {

    private final ConcurrentMap<K, V> cache = new ConcurrentHashMap<K, V>();

    public V get(K key) {
        V value = cache.get(key);
        if (value == null) {
            cache.putIfAbsent(key, newInstance(key));
            value = cache.get(key);
        }
        return value;
    }

    protected abstract V newInstance(K key);
}

To use it, you extend it and implement the newInstance method which creates a new value in case of a cache miss. Then call the get method with a key to get an instance which corresponds that key. Here is an example of how it is used.

That class guarantees that for each key, only one instance is returned, but the newInstance method may be called multiple times, in which case the first computed instance is used and the rest are discarded. Also note that this cache does not remove old instances, but stores all values indefinitely (in my use case there is a limited number of instances that must be cached). Reading from a ConcurrentHashMap does not use locking, so it should satisfy your efficiency requirement.