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.
Read More »
