Can ThreadPoolExecutor hang ?

The answer is well, it can and does. Below is a simple piece of code to produce one such hang

package com.misc.exercises;

import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.ThreadFactory;
import java.util.concurrent.TimeUnit;

class STPEHangTestThread implements Runnable
{

  private static int count = 0;

  public static void main(String args[])
  {              
        ScheduledExecutorService scheduledExecutor;
        scheduledExecutor = Executors.newScheduledThreadPool(1, new ThreadFactory()
        {
            public Thread newThread(Runnable r)
            {
                Thread t = new Thread(r);
                t.setName("MySchedulerThread");
                t.setDaemon(Boolean.TRUE);
                return t;
            }
        });
        scheduledExecutor.scheduleWithFixedDelay(new STPEHangTestThread(), 1, 5, TimeUnit.SECONDS);   

    while(true)
    {

    }
}     
  public void run()
  {

        if(count > 2 & count % 3 == 0)
            throw new RuntimeException("Exception throw !!!");
        System.out.println("Running");
        count++;   
  }
}

If you run this program the output would look like this,

Running
Running
Running

Why doesn’t is print “Running” although the program should keep executing forever? The answer lies in looking at the output of the jstack execution against the process like below,

C:\>jps
5572
1216 Jps
4036 STPEHangTestThread
756

Now run jstack against the process 4036

C:\>jstack -l 4036
2014-08-09 16:03:01
Full thread dump Java HotSpot(TM) 64-Bit Server VM (23.21-b01 mixed mode):

"MySchedulerThread" daemon prio=6 tid=0x000000000b9c9000 nid=0x1ab4 waiting on condition [0x000000000d55e000]
   java.lang.Thread.State: WAITING (parking)
        at sun.misc.Unsafe.park(Native Method)
        - parking to wait for  <0x00000007d5fb0590> (a java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject)
        at java.util.concurrent.locks.LockSupport.park(LockSupport.java:186)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject.await(AbstractQueuedSynchronizer.java:2043)
        at java.util.concurrent.ScheduledThreadPoolExecutor$DelayedWorkQueue.take(ScheduledThreadPoolExecutor.java:1079)
        at java.util.concurrent.ScheduledThreadPoolExecutor$DelayedWorkQueue.take(ScheduledThreadPoolExecutor.java:807)
        at java.util.concurrent.ThreadPoolExecutor.getTask(ThreadPoolExecutor.java:1068)
        at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1130)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:615)
        at java.lang.Thread.run(Thread.java:722)

   Locked ownable synchronizers:
        - None

The thread dump of the “MySchedulerThread” looks interesting doesn’t it? This indicates a hung ThreadPoolExecutor. This is essentially because, the thread that was running on the scheduler thread threw an exception and terminated never to run again. Although the scheduler thread survived the exception, its pretty much useless at this point. In essence, restart of this application is the only alternative you have to solve this problem.

So how do you fix this? The below code is a modified version of the program posted above but with a try-catch block in the run method that catches the exception and lets the execution continue.

package com.misc.exercises;

import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.ThreadFactory;
import java.util.concurrent.TimeUnit;

class STPECleanRunTestWorker implements Runnable
{

  private static int count = 0;

  public static void main(String args[])
  {              
        ScheduledExecutorService scheduledExecutor;
        scheduledExecutor = Executors.newScheduledThreadPool(1, new ThreadFactory()
        {
            public Thread newThread(Runnable r)
            {
                Thread t = new Thread(r);
                t.setName("MySchedulerThread");
                t.setDaemon(Boolean.TRUE);
                return t;
            }
        });
        scheduledExecutor.scheduleWithFixedDelay(new STPECleanRunTestWorker(), 1, 5, TimeUnit.SECONDS);   

    while(true)
    {

    }
}  

  STPECleanRunTestWorker()
  {

  }

  public void run() {
    try
    {
        if(count > 2 && count % 3 == 0)
            throw new RuntimeException("Exception throw !!!");
        System.out.println("Running");
        count++;
    }
    catch (Exception e)
    {
        System.out.println("Caught !!!");    
        e.printStackTrace();
        count++;
    }
  }
}

A similar exercise like above with jps and jstack would yield the result shown below,

C:\>jstack -l 6412
2014-08-09 16:10:48
Full thread dump Java HotSpot(TM) 64-Bit Server VM (23.21-b01 mixed mode):

"MySchedulerThread" daemon prio=6 tid=0x000000000b5c7000 nid=0x1b98 waiting on condition [0x000000000d34e000]
   java.lang.Thread.State: TIMED_WAITING (parking)
        at sun.misc.Unsafe.park(Native Method)
        - parking to wait for  <0x00000007d5fb0868> (a java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject)
        at java.util.concurrent.locks.LockSupport.parkNanos(LockSupport.java:226)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject.awaitNanos(AbstractQueuedSynchronizer.java:2082)
        at java.util.concurrent.ScheduledThreadPoolExecutor$DelayedWorkQueue.take(ScheduledThreadPoolExecutor.java:1090)
        at java.util.concurrent.ScheduledThreadPoolExecutor$DelayedWorkQueue.take(ScheduledThreadPoolExecutor.java:807)
        at java.util.concurrent.ThreadPoolExecutor.getTask(ThreadPoolExecutor.java:1068)
        at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1130)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:615)
        at java.lang.Thread.run(Thread.java:722)

   Locked ownable synchronizers:
        - None

Notice the difference in the states of the “MySchedulerThread”. In the first case its WAITING, but in this case it’s TIMED_WAITING.

One can argue both ways that, there should be a way to report that an exception has occurred when a thread pool executor’s thread got one. But the other side of the argument that the execution that failed is of the task that was submitted and should be handled by the submitter better. I do not know the design decisions that were behind this behavior, but its always better to catch any exceptions that may encounter or possibly just put a try catch block there to not jeopardize your executor.

A more simpler manifestation of the same problem can be done with the below code. Where a executor with 5 threads is started and never shut down.

package com.misc.exercises;

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;

class TPEHangTest implements Runnable
{  
  String workerName;

  public static void main(String args[])
  {    
      BlockingQueue<Runnable> queue = new ArrayBlockingQueue<Runnable>(5);
      ThreadPoolExecutor executor = new ThreadPoolExecutor(5, 5, 5000, TimeUnit.SECONDS, queue);
      for (int j = 0; j < 5 ; j++)
      {
        executor.execute(new TPEHangTest("Worker - "+j));
      }      
      //executor.shutdown();
  }

  TPEHangTest(String name)
  {
    workerName = name;
  }

  public void run() {
    try
    {
        System.out.println(workerName + " ran");
    }
    catch (Exception e)
    {
        System.out.println("Worker run , Exception !!!");
        e.printStackTrace();
    }
  }
}

The program output would look like this,

Worker - 0 ran
Worker - 1 ran
Worker - 2 ran
Worker - 3 ran
Worker - 4 ran

The jstack output for this program would like this,

C:\>jps
6932 TPEHangTest
5572
3764 Jps
756

C:\>jstack -l 6932
2014-08-09 16:19:54
Full thread dump Java HotSpot(TM) 64-Bit Server VM (23.21-b01 mixed mode):

"DestroyJavaVM" prio=6 tid=0x00000000021ac000 nid=0x530 waiting on condition [0x0000000000000000]
   java.lang.Thread.State: RUNNABLE

   Locked ownable synchronizers:
        - None

"pool-1-thread-5" prio=6 tid=0x000000000ba10000 nid=0x160c waiting on condition [0x000000000db4f000]
   java.lang.Thread.State: WAITING (parking)
        at sun.misc.Unsafe.park(Native Method)
        - parking to wait for  <0x00000007d5fadea0> (a java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject)
        at java.util.concurrent.locks.LockSupport.park(LockSupport.java:186)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject.await(AbstractQueuedSynchronizer.java:2043)
        at java.util.concurrent.ArrayBlockingQueue.take(ArrayBlockingQueue.java:374)
        at java.util.concurrent.ThreadPoolExecutor.getTask(ThreadPoolExecutor.java:1068)
        at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1130)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:615)
        at java.lang.Thread.run(Thread.java:722)

   Locked ownable synchronizers:
        - None

"pool-1-thread-4" prio=6 tid=0x000000000ba0f800 nid=0x16fc waiting on condition [0x000000000d9af000]
   java.lang.Thread.State: WAITING (parking)
        at sun.misc.Unsafe.park(Native Method)
        - parking to wait for  <0x00000007d5fadea0> (a java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject)
        at java.util.concurrent.locks.LockSupport.park(LockSupport.java:186)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject.await(AbstractQueuedSynchronizer.java:2043)
        at java.util.concurrent.ArrayBlockingQueue.take(ArrayBlockingQueue.java:374)
        at java.util.concurrent.ThreadPoolExecutor.getTask(ThreadPoolExecutor.java:1068)
        at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1130)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:615)
        at java.lang.Thread.run(Thread.java:722)

   Locked ownable synchronizers:
        - None

"pool-1-thread-3" prio=6 tid=0x000000000ba0a800 nid=0x1804 waiting on condition [0x000000000d6df000]
   java.lang.Thread.State: WAITING (parking)
        at sun.misc.Unsafe.park(Native Method)
        - parking to wait for  <0x00000007d5fadea0> (a java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject)
        at java.util.concurrent.locks.LockSupport.park(LockSupport.java:186)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject.await(AbstractQueuedSynchronizer.java:2043)
        at java.util.concurrent.ArrayBlockingQueue.take(ArrayBlockingQueue.java:374)
        at java.util.concurrent.ThreadPoolExecutor.getTask(ThreadPoolExecutor.java:1068)
        at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1130)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:615)
        at java.lang.Thread.run(Thread.java:722)

   Locked ownable synchronizers:
        - None

"pool-1-thread-2" prio=6 tid=0x000000000ba06000 nid=0x434 waiting on condition [0x000000000d5df000]
   java.lang.Thread.State: WAITING (parking)
        at sun.misc.Unsafe.park(Native Method)
        - parking to wait for  <0x00000007d5fadea0> (a java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject)
        at java.util.concurrent.locks.LockSupport.park(LockSupport.java:186)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject.await(AbstractQueuedSynchronizer.java:2043)
        at java.util.concurrent.ArrayBlockingQueue.take(ArrayBlockingQueue.java:374)
        at java.util.concurrent.ThreadPoolExecutor.getTask(ThreadPoolExecutor.java:1068)
        at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1130)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:615)
        at java.lang.Thread.run(Thread.java:722)

   Locked ownable synchronizers:
        - None

"pool-1-thread-1" prio=6 tid=0x000000000ba04800 nid=0x1a20 waiting on condition [0x000000000cf5f000]
   java.lang.Thread.State: WAITING (parking)
        at sun.misc.Unsafe.park(Native Method)
        - parking to wait for  <0x00000007d5fadea0> (a java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject)
        at java.util.concurrent.locks.LockSupport.park(LockSupport.java:186)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject.await(AbstractQueuedSynchronizer.java:2043)
        at java.util.concurrent.ArrayBlockingQueue.take(ArrayBlockingQueue.java:374)
        at java.util.concurrent.ThreadPoolExecutor.getTask(ThreadPoolExecutor.java:1068)
        at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1130)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:615)
        at java.lang.Thread.run(Thread.java:722)

   Locked ownable synchronizers:
        - None

In the above code, if the executor.shutdown() is not commented out, this program would gracefully terminate.

The lesson thus is that if you have an executor that is giving you non-daemon worker threads make sure you shut the executor down or else it could just be there WAITING.

On a recent project I worked, I needed to use the things extensively and in the process came across these things. I hope this helps you, if you already knew this then kudos !!!

Happy Coding !!!

Advertisements

WeakReferences and typical use cases

I am sure every Java programmer albeit a bit advanced would have definitely come across the term “WeakReference”. After hearing this majority of them would have read the Javadoc, which says,

Weak reference objects, which do not prevent their referents from being made finalizable, finalized, and then reclaimed. Weak references are most often used to implement canonicalizing mappings.

Suppose that the garbage collector determines at a certain point in time that an object is weakly reachable. At that time it will atomically clear all weak references to that object and all weak references to any other weakly-reachable objects from which that object is reachable through a chain of strong and soft references. At the same time it will declare all of the formerly weakly-reachable objects to be finalizable. At the same time or at some later time it will enqueue those newly-cleared weak references that are registered with reference queues.

Where the weakly reachable is explained by the below set of rules on reachability,

  • An object is strongly reachable if it can be reached by some thread without traversing any reference objects. A newly-created object is strongly reachable by the thread that created it.
  • An object is softly reachable if it is not strongly reachable but can be reached by traversing a soft reference.
  • An object is weakly reachable if it is neither strongly nor softly reachable but can be reached by traversing a weak reference. When the weak references to a weakly-reachable object are cleared, the object becomes eligible for finalization.

So apparently not very clear, this is what I felt when I read it the first time. So this warrants an example at the minimum and that is what I am going to try and post below. 

Typically you would start to think that how would a resource that is already gone, what would you do with that? So as the quote above mentioned that it is used to implement canonicalizing mappings, you would want to handle resource that this depend or are mapped against this resource that just been collected. The most common way of doing this is, subclassing the WeakReference class as I have done for my sample below,

class WeakResource extends WeakReference
{
String mappingToHandle;

public WeakResource(Object weakRes, ReferenceQueue queue, String mapping)
{
super(weakRes,queue);
mappingToHandle = mapping;
}

public void close()
{
System.out.println("Closing the mapping: "+mappingToHandle);
mappingToHandle = null;
}
}

In the above segment in the constructor the referrent and the ReferenceQueue instance are passed to the super class constructor. ReferenceQueue instance is an object where collections show up after the garbage collector has applied the reachability rules. In our case an instance of the object WeakResource would show up after it is deemed weakly reachable. It is important to note that the close method is the one that is used to close the mapped resources or clean up the canonicalizing mappings as the Javadoc mentions.

Next is the reaper thread that needs to pick up things off the RefereceQueue and clean up the mappings, 

class ReferenceReaper extends Thread
{
private ReferenceQueue queueToPoll;

public ReferenceReaper(ReferenceQueue queue)
{
super("RefReaper Thread");
queueToPoll = queue;
setDaemon(true);
}

public void run()
{
WeakResource resource;
while (true)
{
System.out.println("Running");
while ((resource = (WeakResource) queueToPoll.poll()) != null)
{
System.out.println("Found resource");
System.out.println("Mapping is: " + resource.mappingToHandle);
resource.close();
}
try {
Thread.sleep(5 * 1000);
} catch (InterruptedException e) {
// Ignore for sample program
}
}
}
}

In the above code, the reaper is created as a daemon thread looking at appearances of WeakResource objects on the reference queue. It wakes up at regular intervals and calls the poll() method on the reference queue whose javadoc is like below,

Polls this queue to see if a reference object is available. If one is available without further delay then it is removed from the queue and returned. Otherwise this method immediately returns null.

So when this reaper thread runs it will retrieve all items that show up in the queue and call close to clean up the mapped resources

Finally, putting it all together. 

public class WeakRefImpl
{
private List<WeakResource> weakResources;
private ReferenceQueue queue;

public WeakRefImpl()
{
weakResources = new ArrayList<WeakResource>();
queue = new ReferenceQueue();
new ReferenceReaper(queue).start();
}

public void createResources()
{
Object []resources = new Object[]{new Object(),new Object(),new Object(),new Object(), new Object()};
int i = 0;
String mapping = "map - ";
for(Object res : resources)
{
WeakResource weakRes = new WeakResource(res,queue,mapping + i);
weakResources.add(weakRes);
i++;
}
resources = null;
}

public static void main(String []args) throws Exception
{
WeakRefImpl impl = new WeakRefImpl();
impl.createResources();
//Try gc'ing. This is only for sample, usually no one should call this and just let JVM do its job and then gather the references
System.gc();
Thread.sleep(1000*1000);
}

}

In the above segment, in the createResources method the WeakResource object is created and added to a list. Then right at the end of the method the resources array is nullified which makes is eligible for garbage collection.

FInally in the main method call the createResources method and the explicitly call the GC for demo purposes. Ideally this will never be done and when the GC happens all the WeakResource objects will queue up at the ReferenceQueue and mapped resources would get closed. I put in a big sleep right at the end to let the program finish collecting the resources.

When all the above pieces are put together and run the output in my machine would like this,

Running
Running
Found resource
Mapping is: map - 0
Closing the mapping: map - 0
Found resource
Mapping is: map - 4
Closing the mapping: map - 4
Found resource
Mapping is: map - 3
Closing the mapping: map - 3
Found resource
Mapping is: map - 2
Closing the mapping: map - 2
Found resource
Mapping is: map - 1
Closing the mapping: map - 1

This could be different in your machine and different on my machine if I run again as the order GC puts them on the reference queue would change.

Some of the common use cases that I have used them is for implementing JDBC connection to JDBC statement mappings. All statements would need to know about connections and hence would have to have strong reference to connection, but the connection would only need to have a weak reference. That way, when the statement goes away, the connection can do the cleanup or handle the case for Statement pooling. Other use is that for determining leaks during diagnostic runs, where one can use the same concept of closing things with weak mappings when they were not explicitly closed. This would help determine leaks of un-closed resources.

Hope this example clarifies typical use cases for WeakRefernce and makes things more clear !!! 

Happy Coding 🙂

Analyzing the Manchester Derby

DISCLAIMER : I am not a fan of any club, I am only interested in the strategies, counter-strategies, tactics, formations and mind games that go on in addition to what happens on the field.

It was an interesting derby – one of the most awaited games of the English calendar, unfortunately it did not live up to its billing. Here are a my thoughts on where it was won or last.

 

A retirement

In the summer of 2013, a certain person named Sir Alex Ferguson (SAF) decided to step down. This was after being at the top of the game for 26 years and that too a giant like Manchester United. This would obviously have repercussions and I think the magnitude of which was probably under estimated by everyone. If people had observed the performances from last season, they would have observed an under performing side that was being used at 110% of their ability throughout the season. SAF was a master at doing this. He was able to do this out of pure fear and also through the aura that he had developed all these years managing a club. When things were not going their way, he was out there barking orders, changing tactics on the fly. When the players looked towards the touchline, it was enough to send shivers down their spine and up their game.

This was badly needed in a game of Sunday’s nature and it was missed. The bottom line is David Moyes in no SAF.

 

Summer of 2013

When SAF retried, everyone thought United would go and recruit players may be two or may be more and everything would be hunky dory. What happened was embarrassing to say the least. First, the unsuccessful attempt to sign Thiago Alacantara from Barcelona, then the pursuit of Cesc Fabregas who was always a mirage. Although I would not blame United for the pursuit of Fabregas, I believe he was not getting enough playing time at Barca and his representatives probably used this to bargain with Barcelona. I cannot see how someone would make 2-3 bids for s player without encouragement from his representatives. But whatever he did not come. Then the embarrassing deadline day activity. Moruane Fellaini for 27.5 million was an over-priced buy and how he would fit into their team is still a question. One can understand why Moyes wanted Leighton Baines – Evra is aging and Buttner or Fabio or not yet experienced enough in EPL. The Hererra fiasco is well documented and huge embarrassment.

But what United miss is two kinds of players – a creative midfielder someone like Thiago whom they missed out on, Hererra could also fit the bill. They need a destroyer and an enforcer in midfield, the kind whom they missed against Man City. Daniel De Rossi would have fit the bill, but that too ended in a failure.

They are now left (until atleast January) with a mediocre squad and my opinion is that if not all 4 of the names discussed above , atleast 2 of them (Thiago and De Rossi I guess) would have come if SAF was still at the helm .

 

Tactics, Personnel and Formation

I have been following the EPL since almost a decade now and have seen various tactics, strategies and formation. SAF was nimble with his formations, tactics in EPL and also Europe. Sometimes deploying 4-3-3, sometimes 4-5-1 and also using the traditional 4-4-2 formations. Most of his teams in past relied on blistering counter-attack to hit teams.  The other common strategy used by United to good effect was getting the midfielders to quickly distribute the ball to wingers and have enough people in the box by the time they deliver their cross. This system has served the team well.

However over the weekend it was a wrong formation, with the wrong personnel. City had Yaya Toure, Fernandinho, Jesus Navas and Samir Nasri in a great midfield setup. United’s midfield was no match to theirs either personnel wise or tactics wise. City pressed harder, pushed United back, cut off their supply lines and the battle was won in midfield. Alvaro Negredo was the star of the match for me, he ran Vidic ragged and dragged him around which created the space for Aguero to deliver the blows. Man City’s defence was playing high up the pitch because of a lack of pressing from United and space that United afforded them.

Personnel in the United team both on and off the field were a problem. Off the field they lost Rene Muelesteen the dutch master who was technical training coach and also Mike Phelan who may not be the most brilliant tactician around, but still better than many around, atleast the current backroom staff there. Most of what United did wrong on Sunday were things that are practiced, observed and fixed on the training ground. So I doubt whether the quality is there. On the field the formation was wrong, because of the lack of quality in that midfield they had to compensate it with numbers. It should have been a 5 man midfield with Rooney up top. And even the personnel in that midfield was wrong. When Nani did not play on Tuesday against Bayern Leverkusen I thought its because he was starting the derby, I was appalled when I saw the team on Sunday. Kagawa, where is he? People who have watched Borussia Dortmund play would remember the devastating effect he had in the Bundesliga. He was crucial to Dortumnd’s aggressive pressing game and the main supplier to Robert Lewandowski.

Summary

Was discussing with a friend and I told him that United would loose by a 3 goal margin and I was proved right because, City took the foot off the pedal at 4-0, else I would have been proved wrong. But the manner of the defeat was bad, even Stoke gave a fight to Arsenal on Saturday.

The writing is on the wall for United, they have to fix things on and off the field pretty quickly. January cannot come faster for them. I would say, they would be happy if they finish in top 4 this season, else Moyes is gone by the end of the season.

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!!!

Working with Java Collections – element removal, for-each and Iterators

I am sure many of you would have come across the use case of having to remove entries from a collection into which you had previously added data. There could be a variety of use cases where this pops up, a very common one is the case of a cache clean up or a pool clean up.

In either of the two use cases above, entries would have been added / accessed when needed and typically programmers write clean up tasks that loop over such structures to evaluate a policy that they would have set at creation time. If the entry in the pool / cache meets the policy constraints its retained, if it doesn’t its evicted. Sounds a simple enough problem to solve.

The advent of for-each loops structures in Java 5 came as a blessing, especially considering the ugly iterator code that people had to write before. The readability and maintainability definitely increased. But is it a good idea to replace all iterator code with the for-each loop ?

The answer is no. There are a few cases where it cannot and should not be replaced. In some cases the ramifications are visible and obvious, in other cases it is not as obvious.

DISCLAIMER : It may not be the best way to write code, but is only for demonstration of the use case 🙂

To illustrate one such use case, take a look at the code snippets below,

    public void populateCollection()
    {
        for (int i = 0 ; i < 20 ; i++)
        {
            listOfStrings.add("String-"+i);
        }
        System.out.println("Size of the collection is: "+listOfStrings.size());
    }

The above code snippets, adds elements to an ArrayList.

The below snippet tries to remove the 10th element from the list while iterating over it.

public void removeItem()
    {
        // Remove item number 10
        // Expect it to work ?
        int counter = 0;
        try {
            for (String entry : listOfStrings) {
                System.out.println("Entry number " + (counter + 1) + " is : "
                        + entry);
                if (counter == 9) {
                    System.out.println("Removing Entry : " + entry);

                    listOfStrings.remove(entry);

                }
                counter++;
            }
        } catch (ConcurrentModificationException e) {
            System.out.println("Oops did not expect this");
            e.printStackTrace();
        }
    }

Will this work ? Why not would be many people’s reaction.  Programmers may think why is this sample code even trying to catch a runtime exception? Again, this is to demonstrate that this exception is indeed thrown !!!

Surprised? You really should not be, because the whole problem is, there is an implicit Iterator here that is traversing the collection and you are going a removing an entry from the collection via a backdoor channel. Since these kind of collections have what are called fail-fast iterators, you will get a ConcurrentModificationException like below.

java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
    at java.util.ArrayList$Itr.next(Unknown Source)
    at CollectionTester.removeItem(CollectionTester.java:XXX)

How do you solve this? Use the good old iterator traversal  and remove it using the Iterator, like below.

public void removeProperly()
    {
        int counter = 0;
        
        Iterator<String> listItr = listOfStrings.iterator();
        while(listItr.hasNext())
        {
            String entry = listItr.next();
            System.out.println("Entry number "+(counter+1) +" is : "+entry);
            if(counter == 9)
            {
                System.out.println("Removing Entry Properly : "+entry);
                try
                {
                    listItr.remove();
                }
                catch (ConcurrentModificationException e)
                {
                    System.out.println("Oops did not expect this");
                    e.printStackTrace();
                }
            }
            counter++;
        }
    }

This will work as expected and remove the entry. Having a try – catch block just to ensure everything is fine. This demonstrates a pitfall that programmers should avoid while replacing iterators with the for-each loop construct.

This has one more caveat though, the concurrent collections in the java.util.concurrent package have something called a weakly-consistent iterator whose definition is like this, ” iterator that will never throw  ConcurrentModificationException and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction”. So its a call that a programmer has to take while dealing with these collections, but it is probably better to stick with the usual iterator way.

Hope this entry helps people who have been hit by nasty, unexpcted ConcurrentModificationException  that is giving them nightmares !!!

Temples of Dakshinna Kannada and Udupi – Day 4 Travelogue

After having visited Kollur and Udupi, our next stop was Subramanya, but we had decided to visit Kateel enroute.

   So the day started with the usual breakfast at the restaurant in Hotel Century Executive. We finished the breakfast and asked for the bills to be prepared for check out. The check out was a breeze and we soon set out towards Kateel. Again GPS was the guide, as we hit NH 17 in about 5 minutes. This time we were riding on NH 17 in the opposite direction (towards Mangalore ) as against last time. The road conditions are similar, good in patches with the eternal widening going on. After about 25km, we neared the town of Mulki. Just before entering the town, there is a left turn, that is marked with directions to Kateel. This road is SH 70 that continues towards Moodbidri. Kateel is about 14 km from NH 17. We passed through the small settlement of Karnad (some really narrow roads) and were headed towards Kateel. We passed by a  fairly decent sized town of Kinnigoli, the roads were pretty good. After about 11km on this road, there is a arch on the right hand side, which points towards Kateel. Take this road and in about 3 km you will reach  the parking lot of the temple. Since this was a weekday and not either Tuesday or Friday, there were hardly any people around. We had a nice darshana, spent a few minutes walking around the temple.

   Just a few words on the temple itself. It is situated on an island sort of a structure, the stream flows around the temple. There is a bridge one has to walk on to enter the temple. Similarly, there is a bridge behind the temple to reach the other bank of the stream. It’s quite picturesque.

  We were now headed to Subramanya. We had two options, one to take SH 70 to Moodabidri, then go to Bantwal, join NH 48 and other was, join NH 17 , then hit NH48 just outside Mangalore and head towards Subramanya. Having heard from friends that Moodabidri route is not all that great as far as roads are concerned, we decided to join NH 17 and then head towards NH 48. We traced the route back towards the arch from where we came to Kateel and took a left turn towards Mulki. After about 4.5km one will see a board named Pakshikere, where another road merges with the road going towards Mulki. Make a sharp left here, you will now be on Pakshikere road. After about 5km on this road you will be on NH 17. On Pakshikere road, you will go over a level crossing, about a kilometer before hitting NH17.

   Once you are on NH 17, its pretty straight forward. Take the left turn towards Surathkal / Mangalore and you are all set. Just keep going straight on this road, you will pass by MRPL and KIOCL factories and also Mangalore Port (all towards your right hand side). After this, there are directions towards Bangalore, follow them and at a round about NH 17 and NH 48 will intersect, stay to your left and take the first left turn in the round about. This is NH 48, the Bangalore – Mangalore highway. Just keep going on this road, following directions for Bantwal / Uppinangady / Gundya. You will pass through Bantwal and Uppinangadi on this road. All though this stretch is a two-lane highway its well laid and you can maintain good average speeds on this road. However keep in mind that this is a winding road and one has to be careful while overtaking and also watch out for morons overtaking in blind turns.

There are multiple options to get to Subramanya after you are in this road; one is from Bantwal taking the Kadaba – Subramanya road, the other one is SH 113 from Uppinangady and the shortest one is just after the town of Nelyady. We decided to take the last one, this is a right turn immediately after the turn from NH 48 towards Dharmasthala. Please note that all the above mentioned routes are clearly marked and all are right turns ( coming from Mangalore ). The route we took was narrow at places, but was very scenic, driving through some forest patches, rubber and coffee plantations. The quality of the road is not all that great, but its manageable. This is apparently called the Ichilimpady Road ( I came to know later ). After about 12km on this road we hit SH 37/ SH 113 which is Uppinangadi / Kadaba – Subramanya road. The road quality gets exponentially better once on this road. It is pretty scenic too !!! There was apparently some rain just before we drove through this road, so the dark black road, with green grass on both sides looked like paradise. After about 15 km on this road, this road merges with the Gundya – Subramanya road ( SH 114). Then after traveling for about 3km you have to keep right to stay on this road towards Subramanya. Going straight will take you onto Bisle Ghat road otherwise. (There is a barricade with a check post at the enterance of this road, so don’t take this road). After a further 2.5 km you will be in Subramanya town.

   We had booked ourselves in Sheshanag Aashraya, a good hotel in Subramanya. The time was 3.30 PM We checked into the hotel freshened up and went to the temple for a darshana. Again there was no crowd and we had a relaxed darshana and decided to grab a bite. We then proceeded to the temple of Adi Subramanya, which is behind the main temple and a 5 minute walk from the main temple.

    We had some free time, so walked around the main street of Subramanya and decided to go back to the temple for the evening aarati. If you have not watched this, you have missed something. The aarati happens around 7.30PM and the temple gates close by 7 PM, so the trick is to get in by then and grab a place to sit inside the temple. The aarati goes on for about 10 minutes. Once this was over, we had dinner at the temple dining hall and headed back to our room.

All in all a pretty good day, with some nice drives on scenic roads with good weather too !!!

Day 4

Udupi – Kateel – Subramanya : 180 km

Stay : Sheshanag Aashrya ( A/c rooms – Rs.1850/night and Non A/c rooms – 1250/night)

   

Temples of Dakshina Kannada and Udupi – Day 3 Travelogue

Day 3 was dedicated exclusively to visit Kollur, initially we had plans to stay in Kollur. After not being able to find a convincing place to stay, decided to make the trip to Kollur out of Udupi. The plan was to get to Kollur before the Maha Mangalaarati (The final aarati before temple closes for the noon). 

We started from Udupi around 9.30 AM. Again we took the route the GPS showed us. Joining the NH 17 from the hotel was straight forward. We were on the NH 17 in about 10 minutes. One thing I must say about the NH 17 is that, it seems to be in widening mode for eternity now and its still not complete, I would say I did not see much work going on it either. The stretch from Udupi to the point where there is a deviation for Manipal, the road is bumpy at best and the patches on the potholes definitely don’t help the ride quality. It gets better afterwards, but there is too much of zig-zag, moving from one side of the road to another to another as the opposite side is being “widened”. I would say its a drivers nightmare to drive on roads like these. There are some stretches before and after Brahmavar where it is two sided, but there are idiots (99% of them are two-wheelers) who choose the high speed lane to pop up, with the sun beating down and mirages on the road, its better to be off a couple of feet from the median.

   Soon we crossed the towns of Kota, Saligrama, Koteshwar and approached Kundapur. You have to be on the watch out for muddied boards that points towards Kollur. If you keep going straight on NH 17 you enter the town. As one approaches Kundapur town, bear right at the fork to take the bypass. As I had driven on this stretch before I knew the route and took the bypass. This was probably the worst stretch of road I travelled on during this entire trip. I wouldn’t say this road is littered with potholes, its an insult to them, they are craters. There are two bridges on this stretch and this probably the only place where you can shift up beyond 2 gear. If you are in a vehicle with less GC, you should be extra careful about getting the under body bruised. After navigating this pathetic stretch, we took the right turn towards Kollur.

  We had done this route before and knew the roads were good. It did not disappoint us, the roads got better and its a pleasure to drive on this stretch, with lots of greenery and very little traffic. The road gets better as one enters the Mookimba Wildlife Sanctuary. I somehow love driving here than anywhere else, it gives a feeling of calmness, may be its Mookambika’s grace 🙂 . Soon we were in Kollur, the time as 11.10 AM. Total distance was 75km.

    We parked up in the general parking area, there were not that many vehicles around and we sensed that the temple was not crowded. And it was true, we just walked into the temple had a good darshana of the deity in a relaxed manner with no one hassling around. The maha mangallarti was at 12.15 PM. We settled down and waited for the aarti to get over. Once that was done, had delicious prasada (lunch) at the temple and headed back towards Udupi.

     During our last trip on this route, we had visited two Ganesha temples on this stretch at Hattyangadi and Aanegudde. So we decided to see if the temples were open and visit them this time too. So on our way back from Kollur towards NH 17, about 5-6km before the highway intersection there are boards to take a left turn towards Hattyangadi and we took that turn. This is a narrow road, that passes through some paddy fields and coconut farms and hits a road that again comes from NH 17. The point where it intersects that road, one can see an arch that has the name of ganesha temple on it. Take the road under the arch and it will lead you to the temple after about a 3 km drive. Its a nice little temple and it was open, but no pooja or aarti there.

 

We started from here, joined back the road near the arch, took a left turn on the road to join NH 17. In a few minutes we were on the horrible stretch of NH 17. After negotiating the stretch , crossed Kundapur and we wanted to visit the second Ganesha temple of Aanegudde, near the small town of Kumbashi. After about 6km from Kundapur, one can see a arch on the left side (when going towards Udupi), take the road under the arch and you will reach the temple after about a kilometer. This temple was open as well and we spent about 15 -20 minutes there. 

We were now back on NH17 and heading towards Udupi, we reached Udupi by around 4.30 PM. We rested for a while and had coffee at Shanti Sagar in Udupi (opposite Udupi Bus Stand). I opted to stay back in the room, while my folks decide to pay another visit to Krishna Mutt and do some shopping in Udupi. They left around 6 PM and were back by 8 PM. We decided to try out a different place for dinner and went to Woodlands, which is a 5 min drive from our Hotel. It was not much crowded and we found parking easily. I had some dosas, while my folks opted for South Indian Thali. The food was great and very reasonably priced. We finished dinner, returned to our rooms and retired for the day.

 

Day 3

Udupi – Kollur – Udupi

Total Distance : 150 km

Stay : Hotel Century Executive, Udupi