Coding for a Scalable Concurrent Cache in Java

In a recent project I had the need to implement to a high scalable and a concurrent cache in Java. The design considerations were simple,

  • Cache should be consistent ( no dead or useless entries)
  • Operations should be executed only once
  • Should handle concurrency gracefully
  • Should purge unused entries over a period of time.

With these goals I set out to implement the cache. Handling the concurrency part properly pretty much solves the other problems implicitly. However over the years I have seen people write different kinds of caches for different reasons and have seen things bungled badly because of the way code was written.

In this write up I will try to point out the problems with traditional solutions and some mistakes people make to give priority to one time over another for the requirements I mentioned above. Its important that all of them be given the same level of importance.

The first type of code people write for thread-safe caches is like below,

    public synchronized String getOrExecute(String costlyOperation)
    {
        String result = null;
        // Poor synchronization
        // Assign result after computation

        return result;
    }

This will give thread- safety but at what cost? Scalability will suffer and having a synchronized keyword on a method pretty much blocks everything off. If you are executing a costly operation and another thread wants to execute a different operation – All the Best !!!

The second type is slightly better than this, but even with some “not-so-bad” timing of threads, there will still be a blocking for executions,

public String getOrExecuteBetter(String costlyOperation)
    {
        String result = null;
        if(result == null)
        {
            synchronized(lockObject)
            {
                if(result == null)
                {
                    // Execute and assign result.
                    // Its ok, but again synchronization could be a blocker
                }
            }
        }
        return result;
    }

The synchronized keyword is gone off from the method signature, but hey there is still a synchronization on a lock object out there that could be a blocker under load.

Both these solutions are really not the solutions if you want something that handle both thread safety and also scale. So is there a solution at all? Yes there is.

Fortunately with the advent of Java 5 there were a host of changes made to the Java Platform and specifically the concurrency packages in them are of use in this case. Yes, if you closely analyze what you really want – executions for same operations should block if there is already an execution in process and execution of other operations should not block. This means you are looking at retrieving the result of a costly operation that happened in the “past” sometime in the “FUTURE” and there lies the solution. Use concurrent collections and futures or variants of them to achieve what you really want.

I am ardent reader of the book Java Concurrency In Practice – Brian Goetz and I went back to this book and viola !!! I got my answer from reading a chapter in that book that sets out to solve the exact same problem. I took the help of that example and ended up writing the code below. This idea is entirely credited to the book and I am putting it up here for people to quickly look it up and also for those who who don’t have the book

public class ScalableConcurrentCache 
{    
    // Ideally pass a parameter for the initial size and the load factor, its important because the expansion of concurrent objects is a costly operation
    private ConcurrentMap<String, FutureTask<String>> cache = new ConcurrentHashMap<String, FutureTask<String>>();

    public String getOrComputeScalable(String costlyOperation)
    {
        try
        {
            String result = null;
            FutureTask<String> futureResult = cache.get(costlyOperation);
            if (futureResult == null) 
            {
                FutureTask<String> task = new FutureTask<String>(
                        new Callable<String>()
                        {

                            @Override
                            public String call() throws Exception
                            {
                                String resultOfCostlyOperation = "";
                                // execute - costlyOperation
                                return resultOfCostlyOperation;
                            }

                        });
                FutureTask resultInCache = cache.putIfAbsent(costlyOperation, task);
                if(resultInCache == null)
                {
                    futureResult = task;
                    task.run();
                }
            }
            return futureResult.get();
        } catch (Exception e) 
        {
            // You may add specific exception handlers, I have added a generic one to keep the code simple
            // This is ideally to remove inconsistent entries from the cache
            cache.remove(costlyOperation);
        }
        return null;
    }
}

Lets analyze the code a bit and see how this is thread safe and also scalable.  In this case, we use a concurrent hashmap which fits the use case perfectly in this case. You want to do multiple reads/writes, as this is a concurrent hashmap, it unlikely for a read to block and since the map is lock-striped only those parts that are being modified are locked so this gives a good backing to this cache.  The next thing is to see the “types” of the key and value for this map. The key is a String which represents the “costly operation” the value is a Future whose type is String, this means that the output of the costly operation is also a String but retrievable via a Future.

Next we check to see if there is an entry in the cache and if there is one, we just retrieve the result by calling the get() on the Future. More discussion about this a little later.

If there is no entry in the cache, we create a new FutureTask and implement the Callable interface to perform the costly operation. After doing that we use the putIfAbsent method of the concurrent map. If you carefully read the documentation of this method or have used this before, it puts the value into the map that you want to add, however if the value was already there it just returns it.

The next step is also crucial, we check the return value from putIfAbsent method to see if there was an entry in the cache by someone else. If yes, we use that otherwise we just run the FutureTask we created before and assign the task to the Future on which we will call get() later.

Now how is this Scalable and thread-safe. Below are a few points that explain how,

  • A ConcurrentHashMap is used as the backing for the cache that allows non-blocking reads and writes don’t block the entire map
  • We use Future’s and if two threads want to execute the same operation and with some tricky timing interleave each other very closely, only one of them is put into the map because we use putIfAbsent and the other one just uses that entry
  • We execute the operation using a callable whose result would be stored in the Future  and if multiple threads want to execute the same operation, they would all end up getting the same FutureTask and the get() method blocks till the operation has executed and result is stored in the future
  • So multiple threads wanting the same result will use the same FutureTask to retrieve the result and block on get() if its result is not yet computed and threads wanting different results can execute and populate the cache simultaneously that making it thread- safe and also scalable

Hope this help people who are trying to solve a similar problem!!!