Cache implementation for multi threaded environment
- 8 Comment
Sometimes, we need to fetch data from a slow external system and data doesn’t even change often. At the cost of increased memory foot print, we can cache the data that can be expired time to time, knowing it can always be recreated when needed again.
Data caching limits the remote method invocations. It improves performance of application , reduce latency and increases throughput by reducing slow response of remote / persistent data store. However, apparently increased performance in a single threaded model can be a bottleneck in multi threaded environment.
Further here, we will discuss creation of simple cache, issues and resolution if problems with the help of Future/ callable interface available with Tiger.
Basic cache implementation involves following steps:
-
Create a HashMap to be used as cache.
-
Wrap the cache over slow-remote-calls
-
Check if key exists in cache , if Yes return cached value
-
If No, fetch data from external system.
-
Put data in cache and return value
Below code snippet represents simple cache implementation.
|
public interface ICacheManager<A, V> { V fetch(A arg) throws InterruptedException, Exception; }
public class CacheManagerImpl<A, V> implements ICacheManager<A, V> {
private final Map<A, V> cache = new HashMap<A, V>(); private final ICacheManager<A, V> c;
public CacheManagerImpl(ICacheManager<A, V> c) { this.c = c; }
public synchronized V fetch(final A arg ) throws InterruptedException { V value = cache.get(arg); if ( value == null) { value = c.fetch(arg); cache.put(arg, result); } return value; } } public class CacheManager implements ICacheManager {
private final ICacheManager<String, List> c = new ICacheManager<String, list>() { public List fetch(String arg) throws Exception {
// Slow extenal call goes here List listResult = … return listResult } };
private final ICacheManager<String, List> ListCache = new CacheManagerImpl<String,List>(c); }
|
Usage of above Cache is fine in single Threaded environment but as soon as we move to multi threaded environment, synchronization of fetch function may lead us to queue of requests. With a number of threads trying to access fetch, we may find throughput to be very low.
Notice that we synchronized fetch to prevent ConcurrentModificationException.
To get rid of above issue we can use ConcurrentHashMap provided by Java 5.
| public class CacheManagerImpl<A, V> implements ICacheManager<A, V> {
private final Map<A, V> cache = new ConcurrentHashMap<A, V>(); private final ICacheManager<A, V> c;
public CacheManagerImpl(ICacheManager<A, V> c) { this.c = c; } public V fetch(final A arg ) throws InterruptedException { V value = cache.get(arg); if ( value == null) { value = c.fetch(arg); cache.put(arg, result); } return value; } } |
ConcurrentHashMap.putIfAbsent is the answer. It checks if value against given key exists, if yes it returns value else null. This way only one Thread will be able to put value and another one should be abandoned.
| public V fetch(final A arg ) throws InterruptedException {
V value = cache.get(arg); if ( value == null) {
V val = c.fetch(arg); value = cache.putIfAbsent(arg, val); if (value == null) value = val; }
return value; } |
Side effect of putIfAbsent is that the effort of one of the Threads fetching data from external system is wasted. Therefore the target should be, if one of the threads has started fetching data from slow external system, all other threads should patiently wait for it to return.
Solution is FutureTask interface provided in Java 5. It represents a function that may or may not be finished yet. Therefore FutureTask.get blocks until function is finished. FutureTask is created with a reference of callable Interface.
|
public class CacheManagerImpl<A, V> implements ICacheManager<A, V> {
private final Map<A, Future<V>> cache = new ConcurrentHashMap<A, Future<V>>(); private final ICacheManager<A, V> c;
public CacheManagerImpl(ICacheManager<A, V> c) { this.c = c; } public V fetch(final A arg) throws InterruptedException { Future<V> value = cache.get(arg); try { if ( value == null) { Callable<V> getVal = new Callable<V>() { public V call() throws InterruptedException { return c.fetch(arg); } }; FutureTask<V> val = new FutureTask<V>(getVal); value = cache.putIfAbsent(arg, val);
if ( value == null) { value = val; val.run(); } }
return value.get(); } catch ( InterruptedException e) {
cache.remove(arg); throw e; } }
} } |
Map now keeps FutureTask instead of value. If thread finds no value against key, it creates a FutureTask and put it in Map. Now other threads get FutureTask against key and blocks at FutureTask.get. Notice that putIfAbsent is still required for those threads that got null value against key and both created FutureTask. Another point to note is removal of key from Map if exception occurs during completion of Call function.
helpful.
Hi Ankur.
This is really helpful. Actually I am working on multi threaded environment & memory was always a concern. Will try to implement this in my next assignment.
Thanks again.
Mudit Jaiswal
Good article on caching and usage of FutureTask n Callable Api provided in java 5.
Hey Mudit,
Above solution don’t provide memory management, it’s a caching solution for multithreaded environment.
Thanks,
Vineet
Yup!
It does not explain cache expiration policy.
~Ankur
he is gr8 person
Hi Ankur
Finally I got the actual source from where this article you have taken.
Users can be benefit from the main source rather then copied one.
Any way good work
http://www.codeproject.com/KB/recipes/LRUCache.aspx
Mudit
Great post! I’ll subscribe right now wth my feedreader software!
Nice post! GA is also my biggest earning. However, it’s not a much.
rH3uYcBX