Excellent blog. I just discovered your company and I like it very much.

If you’re using a JVM 1.5 (or newer) then there’s a high chance you could use a java.util.concurrent map instead of synchronizing manually on a map. For example ConcurrentHashMap supports full concurrency for retrievals and ajustable expected concurrency for update (it’s in the JavaDocs). Doug Lea’s java.util.concurrent that appeared in 1.5 is a gigantic improvement on what was available in 1.4. I’d be curious to know if there’s still contention after using such a package (not that it would be that useful for a 10% cache-hit… But still I’m curious). (little detail: the code example, the “em” tags around “…retrieve data from backend…” don’t seem to work here)

Please try to use Javolution instend of concurrent map and sycnronizing map

public Object getFromCache(String key) {
  if ( map.containsKey(key) ) {
    return  map.get(key);
  } 

  synchronized(map) {
  if(!map.containsKey(key)) {
    ... retrieve data from
    backend ...
  }
  return map.get(key);
  }
}

Would help:-)

Charlie – what you published is a typical example
of code that is not thread safe.

Please review http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html

Andreas, I think Charlie’s example is threadsafe if you use Hastable class for map.

[...] Discussed are numbers 6-Improper Caching and 5-Excessive memory usage. More information about number 6 can be found here. and for number 5 see; here. [...]

Have you ever tested the access time to a synchronized map?

We did testing of various caches, and one that stood head and shoulders above the rest is simply a synchronized LRU map. Beaten only by concurrent hash map, but not by much.

Concurrent hashmap lacks LRU, so its application for revolving caches is very limited. Concurrent LRU map is probably the solution, but hard (impossible?) to develop.

If you compare access time to a collection to access time to the database, then the penalty of synchronizing the collection is hardly noticeable, even in multi CPU environments.

The code snippet above is contains some problems, it synchronized database access across threads. If there is one thing you don’t want is one thread waiting for another thread to do database access. Worse than that, one thread waiting for another thread to get data from the database where the two threads actually need different objects from the cache.

The problem in this code snippet is not the synchronization, it is how synchronization is used.

This type of programming requires little thought, and the only lesson here is that this is job for the expert programmer and not the novice. Concurrent hash map, for example, is a true expert work of software that very few developers can actually tackle.

My 2C

Building a cache that is free of both race conditions and unnecessary blocking takes some thought – none of the comments so far have got it right.

I’d suggest an approach involving Futures:

Map<K, Future> cache = new LinkedHashMap<K, Future>(MAX_CACHE_SIZE, 0.75f, true);

public V getFromCache(K key) {
    Future futureValue;
    synchronized (cache) {
        futureValue = cache.get(key);
        if (futureValue == null) {
            futureValue = new CacheFill(key);
            if (cache.size() == MAX_CACHE_SIZE) {
                // pop the least recently use entry from the cache
                Iterator it = cache.entrySet().iterator();
                it.next();
                it.remove();
            }
            cache.put(key, futureValue);
        }
    }
    return futureValue.get();
}

class CacheFill implements Future {
    private final K key;
    private boolean querying;
    private V value;

    public CacheFill(K key) {
        this.key = key;
    }

    public V get() {
        synchronized (this) {
            if (querying) {
                while (value == null) wait();
                return value;
            }
            else {
                querying = true;
            }
        }
        V value = getValueFromBackend(key);
        synchronized (this) {
            this.value = value;
            notifyAll();
        }
        return value;
    }
    // other Future methods (which are never actually used) left as an exercise for the reader
}

I have neither tested this nor proven it correct, but i think it’s about right, and although there’s quite a bit of locking going on, i don’t think there’s any approach with less locking that will work correctly. You could use a ConcurrentHashMap, which would cut down a lot on the locking and data structure traversal needed to work with the cache, but that doesn’t have the LRU ordering, so you’d have to have an auxiliary data structure for that, and that would probably offset any savings from using the concurrent map.