Build your own caching mechanisms with volatile collections

This month's tool -- a self-cleaning hashtable -- is great for implementing caching in your Java applications

The literal definition of the word volatile is "readily vaporizable," with a secondary connotation of "changeable." This month's tool matches this description nicely, as its implementation will cause the objects contained in a hashtable to vaporize, and the rate of that vaporization is indeed changeable.

But more on that in a moment. First, I'll address reader feedback from last month's column.

Reflections

Half a dozen readers wrote in to inform me that the following block of code (which relates to the GlobalValues tool we discussed two columns back) is a performance bottleneck for multithreaded access.

 
public static synchronized GlobalValues getRef() {
     if( self == null )
         self = new GlobalValues();
     return self;
}

Synchronization is only necessary for the part of the method that instantiates a new instance of the GlobalValues. This will happen the first time the method is called. The block of code should therefore only synchronize if it needs to perform instantiation, as follows:

public static GlobalValues instance() {
     if( self == null ) {
         synchronized( GlobalValues.class ) {
             if( self == null ) {
                 self = new GlobalValues();
             }
         }
     }
     return self;
}

And that's it. No other problems came to my attention this month. (Whew!) On to this month's topic.

The concept of caching

Caching is a time-honored method for improving the performance of an application. Instead of constantly creating and destroying objects as needed, a cache holds on to them and reuses them when appropriate. The Web browser you're running right now uses caching in a number of ways. For example, the JavaWorld logo at the top of this page appears at the top of all the articles. But your browser doesn't reload the image as you travel from one article to the next. The browser caches the image and reuses it when needed.

However, the browser can't cache the image forever. The more sites you visit, the more images the browser saves, and soon you run out of hard drive space. So, the caching mechanism in your browser has to perform some garbage collection. The browser basically sets a maximum space limit for caching images and destroys the oldest images in the cache when that limit is reached.

Caching in Java

In Java, it's incredibly simple to implement a crude caching mechanism using the Hashtable class. Here's how: When you (or your application) need an object, first check to see if it's in the Hashtable. If the required object isn't there, create a new instance of it and put it into the Hashtable. This way, the next time you need it, it's right where you left it.

The tricky part is the cleanup. At some point, your application needs to go through the Hashtable and clean up the objects that haven't been used for a while and are wasting memory. Where do you put this cleanup code? How often do you call it? These are problematic issues, but what if you had a special instance of the Hashtable that knew how to clean itself up? Hello Cachetable!

Ping -- the Cachetable's friendly reminder

The magic behind the Cachetable is a timer thread that periodically reminds the table to clean itself up. I've dubbed this tool Ping. In the olden days of submarine warfare, when a sub was looking for a target it would send out an audible ping sound. This sound would then bounce back from any obstruction, thus revealing the position of the target. In the wonderful land of Unix and the Internet, there exists a little utility called ping that is used to the same effect. The Unix utility sends out a packet to its "target" machine and if the target machine is up and running it "bounces" the packet back.

My Ping utility follows the same traditional concept. Ping sleeps for a predetermined amount of time, then "pings" a target object. How the target object handles the ping depends on the implementation. All that is required is for the target object to implement the Pingable interface. Implementing the Pingable interface forces the target class to implement the ping() method. The ping() method will be called at a regular interval (further explained below):

public interface Pingable

{ public void ping();

}

Implementing the Ping thread is now incredibly simple. The constructor takes two arguments: the target object and the time (in milliseconds) to sleep between pings, as shown below:

public class Ping extends Thread

{ private long sleepTime; private Pingable target; public Ping( Pingable target, long sleepTime ) { this.target = target; this.sleepTime = sleepTime; }

The run() method of Ping loops infinitely between sleeping and pinging:

public void run() { while( true ) { try { sleep( sleepTime ); } catch( InterruptedException e ) { // ignore it! } target.ping(); } }

}

So far, so simple, right?

The TimeWrapper

Properly cleaning up the contents of the cache requires that each object's age be tracked. For this task, we'll use another little tool, which I call TimeWrapper. The TimeWrapper simply stores an object and a timestamp. The constructor takes an object and internally sets the timestamp to the current time. Here's the first part of the TimeWrapper class, which implements these concepts:

public class TimeWrapper { private long age; private Object object; public TimeWrapper( Object object ) { this.object = object; updateAge(); } private void updateAge() { age = System.currentTimeMillis(); }

The wrapper then exposes two accessor methods -- one to retrieve the contained object and another to get the age of the object. Notice that the getObject() method updates the age of the object. When we ask for the age of the contents, we want to know how long it has been since the last time they were accessed. Here are those accessor methods (and the last part of the TimeWrapper

class):

public long getAge() { return( System.currentTimeMillis() - age ); } public Object getObject() { updateAge(); return( object ); }

}

The Cachetable object

The Cachetable object extends a Hashtable and implements the Pingable interface. The Cachetable's implementation of the ping() method will check the age of each contained object (via the TimeWrapper, explained below) and simply vaporize any stale objects. Here's the first part of the tool:

import java.util.Hashtable;

import java.util.Enumeration;

public class CacheTable extends Hashtable implements Pingable {

The constructor takes the desired expiration time for objects stored in the underlying Hashtable, and starts up an instance of the Ping tool:

private long expireTime; private Ping cleaner; public CacheTable( long expireTime ) { super(); this.expireTime = expireTime; cleaner = new Ping( this, ( ( long )( expireTime * 0.75 ) ) ); cleaner.start(); }

To keep track of the age of the objects in the Hashtable, we wrap them in a TimeWrapper. To do this, we must override the get() and put() methods.

When an object is placed into the Cachetable, the key is preserved but the object itself is wrapped in a new instance of TimeWrapper.

public synchronized Object put( Object key, Object value ) { return( super.put( key, new TimeWrapper( value ) ) ); }

When an object is retrieved from the Cachetable, it must also be extracted from its TimeWrapper encasement. As explained above, the TimeWrapper updates the age of the object when the object is extracted:

public synchronized Object get( Object key ) { return( ( (TimeWrapper) super.get( key ) ).getObject() ); }

When the Ping instance calls the ping() method within the Cachetable, the table performs the actual cleanup. It cycles through all the objects in the table and examines their TimeWrappers. If an object hasn't been accessed via a get() call within the expiration time specified, it's removed from the Hashtable (and garbage-collected if no other threads retain a handle to it). Here's the implementation of the ping() method and the cleanup logic:

public synchronized void ping() { Enumeration e = super.keys(); while( e.hasMoreElements() ) { Object key = e.nextElement(); TimeWrapper tw = (TimeWrapper) super.get( key ); if( ( tw != null ) && ( tw.getAge() > expireTime ) ) { remove( key ); } } System.gc(); }

}

Notice that we used super.get() to access the TimeWrapper object. If we had called get(), the instance defined by the subclass would be invoked and we would have received the raw object instead of the wrapper. Also note that we call the Java garbage collector at the end of the method. This is just a trigger to the virtual machine, requesting that it reclaim memory at the next available opportunity.

Conclusion

The Cachetable tool is a clean and simple way to implement caching in your Java applications. I'm sure you'll also find uses for the Ping and TimeWrapper tools. Your homework assignment is to implement a volatile "queue" using the techniques and tools discussed in this article. I'll be using such a queue in an upcoming installment of Cool Tools. As always, comments, criticisms, and especially design-improvement suggestions are welcome.

Learn more about this topic