Recently I came across an interesting programming problem I want to share with you. In short this post discusses thread-safe and fast java implementation of a cache for some special case.

To give you some background, this problem arose in scope of my pet project PUNKSearch (local network indexer and searcher based on Lucene). PUNKSearch shows online/offline status of the hosts displayed in search results. These statuses are cached for several minutes to avoid “dogpile effect” on remote hosts and increase overall responsiveness of the application. Cache is organized as HashMap for which keys are IPs and values are pairs of Date and Boolean wrapped in some extra object named HostStatus. The Date is used to determine if we need to refresh the status for the host and Boolean defines whatever host is online. Obtaining status is a Slow Process (timeout usually is 5 seconds).

Since PUNKSearch is a web application this cache must be thread-safe. Another property we want it to have is speed. Locking the whole cache for the period some thread tries to determine if a host is online is no way.

Lets try to construct such a cache.
Try 1: The simple not thread-safe implementation (cache renewal is dropped for the sake of clearness)

class MapCacheSimpleFastBroken {

	private Map<String, Object> cache       = new HashMap<String, Object>();
	private SlowProcess         slowProcess = new SlowProcess();

	public Object get(String key) {
		Object value = cache.get(key);
		if (value == null) {
			value = slowProcess.get(key);
			cache.put(key, value);
		}
		return value;
	}
}

This class obviously not thread-safe. What can we do to make it thread-safe? Of course, make the method “synchronized”!

Try 2: The simple thread-safe implementation (cache renewal is dropped for the sake of clearness)

class MapCacheSimpleSlowSafe {

	private Map<String, Object> cache       = new HashMap<String, Object>();
	private SlowProcess         slowProcess = new SlowProcess();

	public synchronized Object get(String key) {
		Object value = cache.get(key);
		if (value == null) {
			value = slowProcess.get(key);
			cache.put(key, value);
		}
		return value;
	}
}

This implementation is thread-safe, good. But it is extremely slow! How can we avoid locking the whole cache object? What if we lock only required portion of the map? The map key in particular. Lets try.

Try 3: The fine-grained want-to-be thread-safe implementation (cache renewal is dropped for the sake of clearness)

class MapCacheTrickyFastBroken {

	private Map<String, Object> cache       = new HashMap<String, Object>();
	private SlowProcess         slowProcess = new SlowProcess();
	private static final Object STUB        = new Object();

	public Object get(String key) throws InterruptedException {
		String lock = "";
		// sync on the whole cache to: 1) get cached data, 2) insert stub if necessary
		synchronized (cache) {
			Object value = cache.get(key);
			if (value != null && value != STUB) { // "null" only if this is the first time we see this key
				return value;
			} else if (value == null) { // we see the key for the first time, add the stub to create a key in map keySet
				cache.put(key, STUB);
			}
			// init lock with the key for the required object
			for (String cacheKey : cache.keySet()) {
				if (cacheKey.equals(key)) {
					lock = cacheKey;
					break;
				}
			}
		}
		// grab the lock only on the part of the cache map, so online checks for different hosts can go simultaneously
		// can't use "key" argument as lock here, since we want to sync on cache's key object
		synchronized (lock) {
			Object value = cache.get(key);
			// maybe object was already updated by other thread while we were waiting for lock?
			// call the slow process only if that was not happened
			if (value == STUB) {
				value = slowProcess.get(key);
				cache.put(key, value);
			}
			return value;
		}
	}
}

This implementation seems to be ok. We lock the whole map for a short period of time to verify if we have required object in the cache and possibly modify the map. If the object was not found we put a stub into the map to sync against its key later.
Bad news. This implementation has a serious flaw. Can you find it? Look under the cut for the explanation and the correct implementation.

Indeed, the Try 3 is broken. Assume two threads want to obtain an object for the same key “foo”.
Now imagine first thread has left the 33 line and the second thread just fall into “else” branch at the line 14 (i.e. it is at the line 15 now). Obviously the second thread drops all that hard work done by the first thread and have to call the slow process again. Not good. Additionally notice the crap we have at lines 18-23 to obtain the key object. What we can do to avoid these 2 issues? Lets try.

Last Try: The fine-grained thread-safe implementation (cache renewal is dropped for the sake of clearness)

class MapCacheTrickyFastSafe {

	private ConcurrentHashMap<String, Object> cache       = new ConcurrentHashMap<String, Object>();
	private Map<String, String>               keys        = new HashMap<String, String>();
	private SlowProcess                       slowProcess = new SlowProcess();
	private static final Object               STUB        = new Object();

	public Object get(String key) throws InterruptedException {
		String lock = "";
		// sync on the whole cache to: 1) get cached data, 2) insert stub if necessary
		synchronized (cache) {
			Object value = cache.putIfAbsent(key, STUB);
			if (value != null && value != STUB) { // "null" only if this is the first time we see this key
				return value;
			} else if (value == null) { // we see the key for the first time, store it
				keys.put(key, key);
			}
			// init lock with the stored reference to the key for the required object
			lock = keys.get(key);
		}
		// grab the lock only on the part of the cache map, so online checks for different hosts can go simultaneously
		// can't use "key" argument as lock here, since we want to sync on cache's key object
		synchronized (lock) {
			Object value = cache.get(key);
			// maybe object was already updated by other thread while we were waiting for lock?
			// call the slow process only if that was not happened
			if (value == STUB) {
				value = slowProcess.get(key);
				cache.put(key, value);
			}
			return value;
		}
	}
}

Obviously, we added the “keys” map to search for required lock object quickly. This solves that crap 18-23 lines of Try 3.

What about thread safety? It is putIfAbsent() method of ConcurrentHashMap which helps us a lot.
The method is equal to the following code snippet (except that the action is performed atomically):

if (!map.containsKey(key))
	return map.put(key, value);
else
	return map.get(key);

Finally, we have fast and thread-safe cache implementation!
Please note, however, all implementations lack renewal of cached objects and this was done by intention for this post. Moreover, implementations suffer from memory leak. Can you see it? That simple — all distinct keys create respective objects in cache and that objects never dropped from the cache (may be replaced, yes). So the map is growing constantly. For the production implementation one may want to implement periodical cleanup of the map from very old objects using TimerTask or as side effect of the get() method call.

I hope this post was not extra boring and more than that I hope the last try is indeed thread-safe :) Have I missed something? Let me know ;)