ONJava.com    
 Published on ONJava.com (http://www.onjava.com/)
 See this if you're having trouble printing code examples


Introducing Automatic Data Expiration

by William Grosso, author of Java RMI
01/09/2002

Developers building frameworks or distributed programs (or frameworks for distributed programming) face challenges that are somewhat different from those facing developers building stand-alone applications. One of the more interesting problems is simply trying to find simple and convenient algorithms for determining when data and object references are no longer valid or need to be refreshed. The difference between data your application owns and data that originates in, and is changed by, someone else's code (possibly running in a distinct simultaneous process) is enormous.

The choices you make when handling such information often determine whether an application can scale to enterprise-level performance. For example, suppose you modify a client-server application by adding a client-side cache for frequently accessed data. Because the data is available locally, fewer client-side operations will result in calls to the server. The application will be more responsive to end users, and this performance improvement will be evident regardless of how many clients are using the server, or how busy the server is. Moreover, because the client fetches data less often, the client will put less stress on servers and use less network bandwidth. By making a simple change to the client, and without changing the server at all, you've improved the performance and scalability of the application.

On the other hand, you need to be careful when caching information. If the client frequently displays out-of-date or incorrect information, you will have improved the application's performance at the cost of functionality. This is not a good tradeoff to make.

This is the first article in a three-part series about how to expire or update data automatically, will explore the basics of data expiration. The goal is to present the main issues and work through the standard solutions. I'll start by reviewing six real-world cases where data expiration is necessary and then discuss what they have in common. After laying this groundwork, I'll present a series of solutions -- starting with a very simple solution that doesn't work very well, and gradually improving it until we've reached two fairly nice solutions (one based on using a TreeSet to build an index and one similar to the way Tomcat solves the problem for session keys). I'll wind things down by summarizing what's really required to do data expiration right.

The second article will pick up where the first one left off and introduce a generic datastructure, which I've named HashBelt, that quite nicely solves many of the problems involved in data expiration. As an example of how to use a HashBelt, I'll incorporate it into the RemoteStubCache object that was first introduced as part of my earlier series on Command Objects in distributed programming.

The source code for this article can be downloaded here.

Before You Start

Related Reading

Java RMIJava RMI
By William Grosso
Table of Contents
Index
Sample Chapter
Full Description

This article is not for people who are just starting to program, or just starting to program in Java. While I am going to cover almost everything you need to know about data expiration, I'm not going to explain the basics of Java coding. If you don't know how to use the collection libraries, haven't written a distributed program before, or don't have a good grasp of what the synchronized keyword does, you'll probably have trouble reading these articles. To learn more about the basics of distributed programming and writing multi-threaded code, I recommend my book, Java RMI. In addition to covering RMI, it covers most of the basic design and coding decisions involved in building distributed applications.

In addition, the code examples in these articles use generics quite heavily. This is especially true in the second article. More information about the new generics facilities can be obtained from the generics specification . A friendlier introduction can be found in the third article in my series on command objects.

When Good Information Turns Bad

Data expiration or automatically expiring data means the following: getting rid of information (or data) proactively, based on a time-based notion of staleness.

The first question we need to answer is simply this: why expire data? Why get rid of information? Rather than start by discussing a general theory, I'm going to begin with a series of concrete examples that illustrate types of data that need to be occasionally removed or refreshed programmatically. After these examples, we'll discuss the general theory a little, and then move on to actual code.

Session Keys

Related Articles by William Grosso

Learning Command Objects and RMI

Seamlessly Caching Stubs for Improved Performance

Generics and Method Objects

Session keys are probably the most common example of automatically-expired data. If you've written a Web application, you know that figuring out whether users are still logged on can be a problem. Because the Web is based entirely on a request-response protocol (Web browsers make requests and get pages back in response; the Web server does not originate any activity), a Web application has no way of distinguishing between the "the user is taking a long time to carefully read the document" and "the user closed her Web browser and went home 20 minutes ago."

To work around this problem, Web applications expire sessions based on user inactivity: if a user hasn't requested any HTML pages in a while, their session will be closed and any session information will be removed. Session expiration is often handled by the servlet container; the person writing the servlet simply needs to set a session timeout. But sometimes using the container isn't good enough. For example, suppose that you're writing an application that monitors a factory. One of the HTML screens in your application might automatically update itself every 30 seconds to provide up-to-date information about the assembly line. This HTML screen has the potential to keep a session alive indefinitely. The problem is that even if the user has stepped away from her desk, the application is still requesting pages. This can be a security hole (or at least a memory leak) if the developers blindly relied on the servlet container to close the session.

Session keys are also often used outside of servlets. Many security-conscious financial institutions consider it a security violation for users to stay logged into an application when they're away from their desk. Accordingly, applications at financial institutions often automatically log out users who have been inactive for a certain period of time. And, of course, this has to be done on the server (the first rule of security is that you have to assume the client's been compromised). Even if the application didn't use the Web at all, and used a Swing-based GUI connecting to an EJB server via RMI-IIOP, you still might want to automatically log out clients. And nowhere in the entire 572 pages of the EJB specification is there anything about automatically expiring session keys.

Limited Duration "Holds"

Buying concert tickets over the World Wide Web often involves several steps that are organized as a transaction. For example, when I purchase tickets from my local ballet company, I go through the following sequence of Web pages.

  1. I start by looking at the schedule and choosing a date and time. Then I click a button that submits the Web form and loads the "What type of ticket" page.
  2. I choose the type of tickets I want to purchase (Grand Circle, Circle, Balcony, etc.) and indicate how many seats. Then I click a button, which submits the form and loads the "Choose your seats" page.
  3. I choose my seats and click the button, which submits the form and loads the order confirmation page.
  4. I click the confirm button.

The interesting thing about this sequence is that the confirmation page explicitly warns me that I haven't actually purchased the seats yet. What I've really done is put a temporary hold on the seats. If I don't click the confirm button within five minutes, the hold will be gone and I'll have to do everything again.

Now, this happens at a much finer-grained level than the idea of a "session." The temporary hold is on a resource that many different clients might want to purchase, and needs to be short-lived (especially relative to the session duration).

Short-Lived Information

In the previous example the hold was valid as long as it was maintained. The application's goal was to release the hold quickly; however, there are many cases where information simply becomes invalid over time. For example, consider a maritime buoy that is reporting weather conditions at sea. A sea-conditions Web application such as the one for Half-Moon Bay, California doesn't need to query the buoy every time a Web browser asks for the page; boaters don't need up-to-the-microsecond information. But, by the same token, boaters do expect that the information is relatively up-to-date. I'd be very upset if I made sailing plans based on the buoy's Web site and then I found out the information was updated weekly.

What the sea-conditions Web server needs to do is occasionally update its information. It can do this in either of two ways: it can wait for a request to come in, and then realize the buoy information is out-of-date and needs to be refetched; or it can automatically refresh the buoy information every so often. In either case, the server needs to have some idea of whether the information it has is valid or not. The validity is based on how old the information is.

Freeing up Scarce Resources

Another set of examples comes from data that doesn't become invalid very quickly, and doesn't need to be released because of application logic, but that does need to be released simply because holding on to it is expensive. Examples of this sort of data are harder to come by, but easy to recognize once you have them in hand. The identifying characteristics of such data are:

One simple example of this type of data is a Web browser's cache. The information (HTML text, images, JavaScript, etc.) is grouped into "pages." Users access the pages in an unpredictable order (frequently using the back or forward buttons to skip around). And if the information is discarded, it can always be downloaded again.

When you have this type of data, it's frequently important to occasionally clean up the cache. This cleanup is usually done by discarding data that hasn't been accessed for some specified period of time.

Remote Stub Caches and Distributed Garbage Collection

Our next example is based on the RemoteStubCache object that was first introduced in my series on Command Objects in distributed programming. Recall that the idea behind RemoteStubCache was simple: client applications often fetch stubs from a naming service based on the name of a server. If client applications don't cache the stub somewhere, then remote method invocation can become much more expensive because every logical call to the server requires two remote calls: one to the naming service to fetch a stub, and one to the actual server.

The problem with building local stub caches is that RMI has a distributed garbage collector. As long as client applications are holding onto stubs, servers that rely on the Unreferenced interface to know when to shut down will stay active. This can cause problems, for example, if you are trying to manage the server lifecycle by using the distributed garbage collector.

Database Connections and Pooling Strategies

A similar problem arises if you use a pool for database connections. A good strategy is often to increase the size of the pool to accommodate current demand, then gradually decrease the size of the pool if demand decreases. By doing so, you get the following benefits:

The alternatives usually involve one of the following strategies:

The first alternative is often not a bad idea. Peak database connection usage often corresponds to peak application processing. And a case can be made that if the application is busy, you don't want to start creating database connections. Instead, it can be more efficient to block some requests and wait for connections to become available. I have never heard anyone claim the second alternative is a good idea; it often pops up in codebases (as a consequence of some generic pooling algorithm), but it's usually viewed as a low-priority bug.

Examining the Examples

All of these examples fall into two main camps:

These two problems look very different at first glance: "the weather might have changed" certainly feels different from "we want to release stubs to remote servers as soon as possible." But the point of listing all these examples back to back is this: in a large number of cases, the correct solution is often to use a time-based expiration strategy:

  1. Timestamp the objects.
  2. Update the time stamp when you use the objects or refresh the information.
  3. Throw away objects, the timestamps of which have expired.

For data sets, the idea is to use a valid time. This approach says "this data is only valid for this time interval. After that, it is no longer valid and should be thrown away." So, for example, a programmer might decide that information about the wind speed and direction is only valid for thirty minutes. Once that thirty minutes has elapsed, the information is no good and must be fetched again.

For resources, the idea is to use a last access time. For session keys, if the user hasn't accessed the server in a predetermined time period, the server decides that the session is no longer valid. For server resources, the idea is that the information is still valid, but if the client hasn't used it in a while, it should be cleaned up, so that resources can be made available to other processes. In either case, the information doesn't have a fixed expiration date. Instead, it has a rolling window.

It's important to note that all of our examples involved data that could be incorrect (e.g., data for which mild inaccuracies are acceptable, or for which recovery strategies are available). If the data absolutely must be correct, then simple data-expiration algorithms will not suffice. In most cases, if that information is going to be cached, the usual strategy is to expire it using a distributed event model.

In fact, if you are caching information, you need to ask yourself questions like these:

The answers to these questions will determine whether you use a cache at all; if you the information changes more often than you use it, you might as well just fetch it when you need it. If you use a cache, you need to either manage the cache locally (using a time-based algorithm like the ones in this article) or update it using an event-based algorithm.

Deriving the Standard Expiration Algorithms

In this section, we're going to repeatedly implement algorithms and containers that expire data. The idea is to explore the space of possible solutions, and come up with a set of requirements for a "good" solution. Along the way, we'll also discuss how Tomcat solved the problem of expiring session keys (and discuss a potential flaw in Tomcat's solution).

The First Solution

When faced with time-sensitive data that might need to be expired, programmers often start by using the "thread per information unit" pattern. This code is fairly simple and easy to write. It involves the following steps:

  1. Every instance of an object that might need to be expired gets a time stamp, an expected lifetime, and a background thread (created in its constructor) that will expire the object and then halt.
  2. If the instance is going to be expired based on inactivity, then the methods which cause it to be "marked as active" update the time stamp somehow.
  3. A background thread occasionally checks the instance to see if it needs to be expired.

Thus, for example, a developer might start by writing the following code:

package grosso.firstexample;

import java.util.*;

/*
  ExpirableObject.

  Abstract superclass for objects which will expire.
  One interesting design choice is the decision to use
  the expected duration of the object, rather than the
  absolute time at which it will expire. Doing things this
  way is slightly easier on the client code this way
  (often, the client code can simply pass in a predefined
  constant, as is done here with DEFAULT_LIFETIME).
*/

public abstract class ExpirableObject {
  public static final long FIFTEEN_MINUTES = 15 * 60 * 1000;
  public static final long DEFAULT_LIFETIME = FIFTEEN_MINUTES;

  protected abstract void expire();

  public ExpirableObject() {
    this(DEFAULT_LIFETIME);
  }

  public ExpirableObject(long timeToLive) {
    Expirer expirer = new Expirer(timeToLive);
    new Thread(expirer).start();
  }

  private class Expirer implements Runnable {  
    private long _timeToSleep;
    public Expirer (long timeToSleep){
      _timeToSleep = timeToSleep;
    }

    public void run() {
      long obituaryTime = System.currentTimeMillis() + _timeToSleep;
      long timeLeft = _timeToSleep;
      while (timeLeft > 0) {
        try {
          timeLeft = obituaryTime - System.currentTimeMillis();  
          if (timeLeft > 0) {
            Thread.sleep(timeLeft);
          }
        }
        catch (InterruptedException ignored){}      
      }
      expire();
    }
  }
}

Non-abstract subclasses of ExpirableObject must have an implementation of the expire method, which contains the "death logic" of the object. Each instance of ExpirableObject allocates a thread that, after a certain amount of time has elapsed, calls the expire method.

This approach is often sufficient for simple applications that have very few pieces of data. But it has a major flaw: using this class creates lots of threads (one per instance of the object in question). As a result, programs which create instances of ExpirableObject for central data structures don't scale very well.

Eliminating the Extra Threads

There's a simple solution to the number-of-threads problem raised by the first solution: instead of each object having its own expiration thread, use a single expiration thread for all of the instances of ExpirableObject. The code now contains two classes, ExpirableObject and GlobalExpirationHandler and looks something like the following:

package grosso.secondexample;

/*
  ExpirableObject.

  Abstract superclass for objects which will expire.
  During construction, instances of this class register
  with the ExpirationHandler, which owns a background
  thread which expires objects
*/

public abstract class ExpirableObject{
  public static final long FIFTEEN_MINUTES = 15 * 60 * 1000;
  public static final long DEFAULT_LIFETIME = FIFTEEN_MINUTES;
  private long _expirationTime;

  protected abstract void expire();

  public ExpirableObject() {
    this(DEFAULT_LIFETIME);
  }

  public ExpirableObject(long timeToLive) {
    _expirationTime = System.currentTimeMillis() + timeToLive;
    GlobalExpirationHandler.registerExpiringObject(this);
  }

  public void setExpiration(long timeToLive) {
    _expirationTime = System.currentTimeMillis() + timeToLive;
  }

  public final boolean shouldExpire() {
    return System.currentTimeMillis() > _expirationTime;
  }  
}

package grosso.secondexample;

import java.util.*;

/*
  GlobalExpirationHandler.

  Static methods that handle expiring objects.
  This class owns a background thread that wakes
  up every so often and expires objects.
*/


public abstract class GlobalExpirationHandler{
  public static final long FIFTEEN_SECONDS = 15 * 1000;
  public static final long REAPER_THREAD_SLEEP_TIME = FIFTEEN_SECONDS ;

  private static Expirer _expirer;

  private GlobalExpirationHandler() {}  // No instances allowed.

  static {
    _expirer = new Expirer();
    Thread backgroundThread = new Thread(_expirer, "GlobalExpirationHandler Collection Thread");
    backgroundThread.setPriority(Thread.MIN_PRIORITY);

    backgroundThread.start();
  }
  
  public static void registerExpiringObject(ExpirableObject newExpiringObject) {
    _expirer.addObject(newExpiringObject);
  }

  public static void shutdownExpirationThread() {
    _expirer.halt();
  }

  private static class Expirer implements Runnable {
  
// Vector for fast iteration, hashtable to guard against double entries
    private Vector<ExpirableObject> _objectVector = new Vector<ExpirableObject>();
    private Hashtable<ExpirableObject, ExpirableObject> _objectHash =
      new Hashtable<ExpirableObject, ExpirableObject>();
    private boolean _shouldKeepRunning = true;

    public void run() {
      while(shouldKeepRunning()) {
        try {
          Thread.sleep(REAPER_THREAD_SLEEP_TIME);
        }
        catch (InterruptedException ignored){}
        expireObjects();
      }      
    }
    
    protected synchronized void addObject(ExpirableObject object) {
      if (_objectHash.containsKey(object)) {
        return;
      }
      _objectVector.add(object);  
      _objectHash.put(object, object);  
    }

    protected synchronized void halt() {
      _objectVector.clear();
      _objectHash.clear();
      _shouldKeepRunning = false;
    }

    private synchronized boolean shouldKeepRunning() {
      return _shouldKeepRunning;    
    }

    private synchronized void expireObjects() {
      ListIterator<ExpirableObject> i = _objectVector.listIterator();    
      while (i.hasNext()) {
        ExpirableObject nextExpirableObject = i.next();
        if (nextExpirableObject .shouldExpire()) {
          expireObject(nextExpirableObject );
          i.remove();
          _objectHash.remove(nextExpirableObject);
        }
      }
    }

    private void expireObject(ExpirableObject expirableObject ) {
      try {
        expirableObject.expire();    
      }
      catch (Throwable t) {
        t.printStackTrace();
      }
    }
  }
}

All that we've really done here is pulled the expiration thread out of ExpirableObject and adapted it, using the Expirer inner class, to expire any number of instances of ExecutableObject. Even in an example as simple as this, however, there are five interesting points to note:

This example also used generic classes (specifically, the generic collection classes). This wasn't really necessary (we didn't really need to use genericized hashtables or vectors), but it's fun and makes the code a little cleaner. As the examples get more elaborate, we'll start incorporating generics into the signatures of all the objects and interfaces. For more information about generics, I recommend the introduction contained in the third article in my series on command objects.

Dealing with Data Inconsistency

Now that we've gotten rid of all the extra threads, the biggest problem with our data expiration code is that it suffers from data inconsistency. If an object has a reference to an instance of ExpirableObject and expire is called, what happens ? How do we prevent additional method calls on the "dead" object? And how do we get rid of the references to the "dead" object?

One approach is what I like to call the high discipline approach. It goes something like this:

The reason I call this way of doing things high-discipline is because it doesn't actually change the code for ExpirableObject (the framework code is unchanged). Instead, it requires that every subclass of ExpirableObject be written more carefully, with an eye towards expiration. Often, this isn't particularly hard code to write, but it can be hard code to remember to write. It's simply a bad idea to rely on people using a framework to do all the framework-related bookkeeping correctly.

Rather than pursue the high-discipline approach, programmers often prefer the following three-part solution:

This new approach has several nice benefits. It's easy to understand, it makes sense, and it's easy to extend. This last property is important -- new subclasses of ExpirableObject are easy to write and don't involve any complicated logic (outside of the logic inherent to the class). If you're writing a framework, you need to make sure that it's easier for programmers to use the framework than to solve the problem themselves.

This way of doing things also fits well with the usage model for many different types of expirable data. Session keys naturally lend themselves to a data model where a singleton is used to look up information. For example, in a Web server, an HTTP request is sent from a browser and the servlet runner uses a session cookie to look up the session information from a central repository. Similarly, cached data often wants to be globally accessible (the whole point of using RemoteStubCache was to provide a centralized repository for stubs, and thus enable objects that didn't know about each other to share resources).

Here's the code for a version of ExpirableObject that follows this approach. The only significant change in Expirable is the addition of a new abstract method, getKey, which will be used to index the instances.

package grosso.thirdexample;

/*
  ExpirableObject.

  Abstract superclass for objects which will expire.
  During construction, instances of this class register
  with the ExpirationHandler, which owns a background
  thread which expires objects.

  In contrast to the other implementations, in this
  example, expire is just used to expire local data
  (removing the object from the global cache is handled
  by the expiration thread)

*/
public abstract class ExpirableObject{
  public static final long FIFTEEN_MINUTES = 15 * 60 * 1000;
  public static final long DEFAULT_LIFETIME = FIFTEEN_MINUTES;

  private long _expirationTime;

  protected abstract void expire();
  protected abstract Object getKey();

  public ExpirableObject() {
    this(DEFAULT_LIFETIME);
  }

  public ExpirableObject(long timeToLive) {
    _expirationTime = System.currentTimeMillis() + timeToLive;
    GlobalCache.add(this);
  }

  public void setExpiration(long timeToLive) {
    _expirationTime = System.currentTimeMillis() + timeToLive;
  }

  public final boolean shouldExpire() {
    return System.currentTimeMillis() > _expirationTime;
  }  
}

GlobalExpirationHandler has changed more. It's been renamed, to GlobalCache, as befits its slightly expanded role in the system. There's also a new method named get for clients to access cached objects. And, most significantly, Expirer has been broken out into a new subclass of Thread called CacheExpirationThread.

Here's the code for GlobalCache and Expirer.

package grosso.thirdexample;

import java.util.*;

/*
  GlobalCache (formerly GlobalExpirationHandler).

  Static methods that handle expiring objects.
  This class owns a background thread that wakes
  up every so often and expires objects.
*/


public class GlobalCache{

  private static Hashtable<Object, ExpirableObject> _cachedObjects =
    new Hashtable<Object, ExpirableObject>();

//  _objectVector is redundant, but lets us iterate quickly.
  private static Vector<ExpirableObject> _objectVector =
    new Vector<ExpirableObject>();

  private static CacheExpirationThread _cacheExpirationThread;

  private GlobalCache() {}  // No instances allowed.

  static {
    _cacheExpirationThread = new CacheExpirationThread();
    _cacheExpirationThread.start();
  }
  
  public synchronized static void add(ExpirableObject expirableObject) {
    Object key = expirableObject.getKey();
    if (_cachedObjects.containsKey(key)) {
      return;
    }
    _objectVector.add(expirableObject);  
    _cachedObjects.put(key, expirableObject);  
  }

  public synchronized static ExpirableObject get(Object key) {
    return _cachedObjects.get(key);
  }

  public synchronized static void halt() {
    _objectVector.clear();
    _cachedObjects.clear();
    _cacheExpirationThread.halt();
  }

  protected synchronized static void expireObjects() {
    ListIterator<ExpirableObject> i = _objectVector.listIterator();    
    while (i.hasNext()) {
      ExpirableObject nextExpirableObject = i.next();
      if (nextExpirableObject .shouldExpire()) {
        expireObject(nextExpirableObject );
        i.remove();
        _cachedObjects.remove(nextExpirableObject);
      }
    }
  }

  private static void expireObject(ExpirableObject expirableObject ) {
    try {
      expirableObject.expire();    
    }
    catch (Throwable t) {
      t.printStackTrace();
    }
  }
}

package grosso.thirdexample;

import java.util.*;

/*
  CacheExpirationThread

  It wakes up, it cleans up the cache, it goes back to sleep.
*/


public class CacheExpirationThread extends Thread{
  public static final long FIFTEEN_SECONDS = 15 * 1000;
  public static final long REAPER_THREAD_SLEEP_TIME = FIFTEEN_SECONDS ;
  
  private boolean _shouldKeepRunning = true;
  private long _timeToSleep;
  public CacheExpirationThread() {
    this(REAPER_THREAD_SLEEP_TIME);
  }

  public CacheExpirationThread(long timeToSleep) {
    super("CacheExpirationThread");
    setPriority(Thread.MIN_PRIORITY);
    _timeToSleep = timeToSleep;
  }

  public synchronized void halt() {
    _shouldKeepRunning = false;
  }

  public void run() {
    while(shouldKeepRunning()) {
      try {
        Thread.sleep(REAPER_THREAD_SLEEP_TIME);
      }
      catch (InterruptedException ignored){}
      GlobalCache.expireObjects();
    }      
  }
    
  private synchronized boolean shouldKeepRunning() {
    return _shouldKeepRunning;    
  }
}

In this version, instances of ExpirableObject automatically register with the GlobalCache object. They will be globally accessible to any caller with the correct key, and they will be automatically expired. This new version still suffers from a data inconsistency problem -- an instance can continue to be used even after it has expired. But at this point, it's a slight window. So we're doing pretty well.

A Synchronization Bottleneck

Unfortunately, we've introduced another problem: GlobalCache has a nasty synchronization bottleneck. All of the public methods on GlobalCache are synchronized. If there are a lot of instances being checked for expiration, and most of them are valid, the logic that involves iterating through all instances to find the invalid ones might take a lot of time. And during this iteration, we have prevented all of the other threads from accessing the contents of GlobalCache.

We can't simply remove the synchronization. It's preventing a lot of threading errors. For example, if we don't synchronize the access methods with the expiration thread, the Vector might throw unexpected instances of ConcurrentModificationException. And since ConcurrentModificationException is an unchecked exception, the compiler won't warn us of this possibility.

There are two solutions to this problem. The first solution is to replace the instance of Vector with a sorted data structure. Here, for example, is a slightly different version of GlobalCache, which uses an instance of TreeSet instead.

package grosso.fourthexample;

import java.util.*;

/*
  GlobalCache.


  Slightly modified version of old GlobalCache. It uses a
  Treeset instead of a Vector, to avoid iterating
  through everything. And it eliminates the synchronization
  bottleneck too !
*/


public class GlobalCache {
  private static Hashtable<Object, ExpirableObject> _cachedObjects =
    new Hashtable<Object, ExpirableObject>();
  private static SortedSet<ExpirableObject> _timeStampedStore = new TreeSet<ExpirableObject>();

  private static CacheExpirationThread _cacheExpirationThread;

  private GlobalCache() {}  // No instances allowed.

  static {
    _cacheExpirationThread = new CacheExpirationThread();
    _cacheExpirationThread.start();
  }
  
  public synchronized static void add(ExpirableObject expirableObject) {
    Object key = expirableObject.getKey();
    if (_cachedObjects.containsKey(key)) {
      return;
    }
    _timeStampedStore.add(expirableObject);  
    _cachedObjects.put(key, expirableObject);  
  }

  public static synchronized void remove(ExpirableObject expirableObject) {
    _timeStampedStore.remove(expirableObject);
    _cachedObjects.remove(expirableObject.getKey());
  }

  public synchronized static ExpirableObject get(Object key) {
    return _cachedObjects.get(key);
  }

  public synchronized static void halt() {
    _cachedObjects.clear();
    _timeStampedStore.clear();
    _cacheExpirationThread.halt();
  }

  protected static void expireObjects() {
    while (removeOldestObject()) { }
  }

  private static boolean removeOldestObject() {
    ExpirableObject oldestObject = getOldestObject();;
    if (oldestObject.shouldExpire()) {
      remove(oldestObject);
      expire(oldestObject);
      return true;  
    }
    return false;
  }

  private static synchronized ExpirableObject getOldestObject() {
    return _timeStampedStore.last();
  }

  private static void expire(ExpirableObject expirableObject ) {
    try {
      expirableObject.expire();  
    }
    catch (Throwable t) {
      t.printStackTrace();
    }
  }
}

In order to make this approach work, we needed to change ExpirableObject slightly. The first thing that had to change was that ExpirableObject needs to implement the Comparable interface. In order to do this, the following code was added:

  /*
    Note that ExpirableObjects which expire later this object are
    "less than" this object.
  */
  
  public int compareTo(Object object) {
    if (! (object instanceof ExpirableObject)) {
      return compareToBasedOnHashcodes(object);
    }
    ExpirableObject otherExpirableObject = (ExpirableObject ) object;
    int returnValue = compare(_expirationTime, otherExpirableObject._expirationTime);
    if (0 != returnValue) {
      return returnValue;
    }
    return compareToBasedOnHashcodes(object);
  }

  private int compareToBasedOnHashcodes(Object object) {
    return compare(hashCode(), object.hashCode());  
  }

  private int compare(long firstValue, long secondValue) {
    if (firstValue < secondValue) {
      return 1;
    }
    if (secondValue < firstValue) {
      return -1;
    }
    return 0;
  }

This version of GlobalCache works because TreeSet stores objects in a sorted order. When an instance is added to the cache, it is added to the "correct" location in the tree, based on the time the instance will expire (instances which will expire sooner are greater than instances which expire later). This all means that our background thread now follows a very simple algorithm:

  1. Look at the last instance in the tree. If the last instance needs to be expired, expire it and perform this step again.
  2. Fall asleep.

This does acquire the lock for the data store quite often, but for very short periods of time each time. And since the expiration thread is a low-priority thread, we've effectively eliminated the synchronization bottleneck.

Unfortunately, as written, this approach is not a general solution for data expiration. The problem is that the sorting used by the treeset assumes that the comparison operation is constant (that is, once the comparison operation returns "instance1 is less than instance 2," it will always return "instance1 is less than instance 2"). If we ever call setExpiration on an object that's already contained in the cache, we might violate this assumption. So we also need to change the implementation of setExpiration to remove and then reinsert the object, as follows:

  public void setExpiration(long timeToLive) {
    GlobalCache.remove(this);
    _expirationTime = System.currentTimeMillis() + timeToLive;
    GlobalCache.add(this);
  }

This is very simple and easy to do. But it can be expensive. Suppose, for example, you're writing a Web server and dealing with 1,000 simultaneous sessions. Every time a request comes in, you need to call setExpiration to reset the expiration time for the session. This means that, on every request, you're doing approximately 20 comparisons between instances of ExpirableObject (since TreeSet is a red-black tree, the number of comparisons needed to remove or insert an object is approximately the same as for a b-tree). If Web browsers are requesting pages at the rate of one every thirty seconds, you're paying 40,000 object comparisons per minute to maintain the TreeSet

On the other hand, if you're not updating the expiration time, as in our weather example (or, more generally, for short-lived information), then you can simply remove the setExpiration method from ExpirableObject and this is a good solution.

A Second Solution to the Synchronization Bottleneck

Another solution to the synchronization bottleneck in the original version of GlobalCache is to change the role of the background thread slightly. In this solution, the background thread makes a copy of the data structure instead of directly checking the main data structure, and then uses the copy to check for expirations. This is exactly what the Tomcat 4.0 codebase does for session keys. Here's the code from Tomcat (from the classes org.apache.catalina.session.StandardManager and org.apache.catalina.session.ManagerBase).

From org.apache.catalina.session.StandardManager

    /**
     * The background thread that checks for session timeouts and shutdown.
     */
  public void run() {

        // Loop until the termination semaphore is set
    while (!threadDone) {
      threadSleep();
      processExpires();
    }
  }

  private void processExpires() {

    long timeNow = System.currentTimeMillis();
    Session sessions[] = findSessions();

    for (int i = 0; i < sessions.length; i++) {
      StandardSession session = (StandardSession) sessions[i];
      if (!session.isValid())
        continue;
      int maxInactiveInterval = session.getMaxInactiveInterval();
      if (maxInactiveInterval < 0)
        continue;
      int timeIdle = // Truncate, do not round up
        (int) ((timeNow - session.getLastAccessedTime()) / 1000L);
      if (timeIdle >= maxInactiveInterval) {
      try {
        session.expire();
      } catch (Throwable t) {
        log(sm.getString("standardManager.expireException"), t);
      }
    }
  }


From org.apache.catalina.session.ManagerBase


  /**
   * Return the set of active Sessions associated with this Manager.
   * If this Manager has no active Sessions, a zero-length array is returned.
   */

  public Session[] findSessions() {
    Session results[] = null;
    synchronized (sessions) {
      results = new Session[sessions.size()];
      results = (Session[]) sessions.values().toArray(results);
    }
    return (results);
  }

  /**
   * The set of currently active Sessions for this Manager, keyed by
   * session identifier.
   */
  protected HashMap sessions = new HashMap();

This is almost identical to the first version of GlobalCache we wrote. There's only one slight difference -- the method findSessions makes a duplicate copy of the main data structure, copying the values from the HashMap into an array that the background thread then uses to expire objects. Tomcat's approach solves the synchronization bottleneck: by making a second copy of the array and iterating over it, the Tomcat codebase avoids concurrent modification exceptions without locking the cache for an extended period of time.

The Tomcat approach does have some efficiency problems: copying all of the values in a HashMap is not cheap, and Tomcat still iterates over all the sessions. Moreover, making a duplicate copy of the session keys also actually makes the data inconsistency problem slightly worse: it's possible for a request to come in and use a session at the same time that the background thread is expiring the session. The scenario from the point of view of the user looks like this:

This example illustrates a fairly general problem with expiring data. Most approaches force you to choose between a synchronization bottleneck or a data consistency problem. The ideal sequence of operations for the background thread should perform something like the following sequence of operations:

  1. Wake up.
  2. Lock the main data structure for an incredibly brief period of time, in which the thread removes only the expired data.
  3. Unlock the main data structure. Because the main data structure is locked for such a brief period of time, there is no synchronization bottleneck.
  4. Expire the individual pieces of data in the background thread. Because the data was already removed from the main data structure, there is no data consistency problem.
  5. Sleep.

None of our solutions do this (yet), although Tomcat and the TreeSet version of GlobalCache are pretty nice.

Summary and Desiderata for a Better Data Structure

In this article, we've discussed the types of data that need to be expired and gone over several different algorithms for expiring data. As a result of this discussion, we've come up with three candidate solutions:

Looking at our various implementations gives us set of requirements for a solution:

Related Reading

Java RMIJava RMI
By William Grosso
Table of Contents
Index
Sample Chapter
Full Description

Looking at our attempted solutions also lets us realize that one of our initial assumptions has been relaxed: using a single background thread that wakes up occasionally implies that the data can stay valid for an "extra" minute or two. Data expiration is often a casual requirement: the important thing is that the data lives for a while and then is expired at approximately the right time.

In the second article in this series, we'll use these requirements to define and build a new data structure for data expiration.

William Grosso is a coauthor of Java Enterprise Best Practices.

Related Articles by William Grosso

Learning Command Objects and RMI

Seamlessly Caching Stubs for Improved Performance

Generics and Method Objects


Return to ONJava.com.

Copyright © 2009 O'Reilly Media, Inc.