Timestamp-Based Caching Framework: Current Data with Peak Performance

Originally Published on JavaWorld.com, January 3, 2005 ⇒

Build a dynamic LRU cache framework using standard Java utility classes

In his timeless masterpiece, The Art of War, Sun Tzu states: “…one who is skilled in warfare principles …takes the enemy’s walled city without attacking… His aim must be to take All-Under-Heaven intact. Therefore, weapons will not be blunted, and gains will be intact.”

When we garbage-collect perfectly good objects, we “blunt our weapons” and waste precious system resources by re-creating these objects all over again. By implementing a caching framework, we hope that most of our “gains” resulting from our creation of complex objects will remain “intact.” If we store completed objects in the cache, we avoid repeatedly re-creating these objects and thus enjoy a boost in application performance.

Time-to-live, or TTL, caching systems answer the needs of most applications that can afford to use slightly stale data. However, if the objects we cache contain time-sensitive pricing or availability information, they must always remain up to date and cannot be shown to the user as stale. These objects have no reliable time-to-live attribute, and to cache them effectively, we must employ different approaches. One successful approach, a timestamp-based caching framework (TBCF), is presented in this article.

Not caching Britney Spears

Imagine, if you will, a simple Website for selling CDs. On our site, users can search for CDs, check prices, and make purchases. For every user search, our application loads a CD cover picture, item details, price, and user ratings from the database. After all the information is loaded, the application creates CD value objects to massage and store the information from one or more JDBC (Java Database Connectivity) result sets. Then the application renders these CD objects as HTML and delivers the result to the user’s browser. After the search results display, our application completes the user’s request by allowing the JVM to garbage-collect the complex CD value objects it went to such great lengths to create. The same process then repeats for every other user who executes the same search for the same CD, for example, a Britney Spears CD.

While this typical design approach is straightforward and simple to implement, its performance is often suboptimal. With every user request, CD value objects undergo a “create-use-destroy” cycle, also known as object churning. This cycle does not typically cause problems for small, simple CD objects under low system loads. However, it does cause significant performance degradation if the CD objects are large and complex, requiring several JDBC calls and complex calculations. As the load on the application increases, object-churning problems rapidly intensify. Since objects are not reused, n users will always require the creation of n sets of CD objects and the use of n sets of system resources by our application. This problem is illustrated in Figure 1.

Figure 1. No cache: n users require n sets of objects, causing problems at higher loads

To address the object-churning problem, assembled CD value objects can be stored in a cache. A cache is typically implemented as a map, where CD objects are stored as values, with their IDs as keys. Each CD search request searches the cache first, before querying the database. If an existing CD value object is found in the cache, that object is used; a query to the database to create a new CD object is not required. Thus, with the cache in place, more CD objects are reused, and fewer objects are created and destroyed as part of the churning cycle. In a typical caching mechanism, all the objects that reside in the cache have a time-to-live (TTL) attribute. When the objects stay in the cache longer then their TTL, they become stale. Stale objects are periodically removed from the cache by a background thread (see “Develop a Generic Caching Service to Improve Performance” (JavaWorld, July 2001) for a good implementation of a TTL cache).

This approach works well for most applications, especially where objects have a well-defined TTL attribute or where users can accept somewhat stale data—for example, running a monthly report of product demand trends on data loaded nightly. Day-old data is perfectly acceptable in this case and can be safely used to create the desired report. We also know that TTL is exactly 24 hours, so our cache can be cleared and then refreshed nightly from the database, safely speeding up data delivery throughout the day.

The problem emerges when we try to cache time-sensitive objects. In most cases where product availability or pricing is concerned, we require an absolutely reliable way to determine staleness, as using stale data can have expensive consequences. Examples include product prices that change instantly with market demands, day-trader stock market quotes, mortgage rates, and any reports that must portray real-time results. In these complex applications, the TTL cache’s background-thread refresh-scheme is simply not rigorous enough because no specific TTL exists for the cached objects, as pricing information changes randomly throughout the day. The challenges of TTL caching are shown in Figure 2.

Figure 2. Since TTL is not known, the object in the cache might be stale

Since we cannot serve a stale stock price to a day trader, we must first determine if the object in our cache is stale. In the famous mental experiment involving Schrodinger’s Cat, the outside observer cannot reliably ascertain whether the cat is alive or dead without opening the sealed box. A TTL cache presents us with the same uncertainty: since TTL is not known, the object in the cache might be stale or it might still be fresh. The only way to know for sure is to open the proverbial box, i.e., look in the database. Thus, if we want to return only fresh data, we must go to the database to determine the staleness of every object we return, thereby negating any efficiency improvements we gained by using the TTL cache. In other words, the act of observing staleness destroys efficiency.

To guarantee the delivery of the most up-to-date information to the users, we need a more systematic approach to determine staleness. We must engineer some kind of a quick “staleness lookup” into every request addressed to our cache. The timestamp-based caching framework (TBCF) I present in this article does exactly that.

Timestamp-based caching framework requirements

We know enough about our Music Shop application to outline the software requirements of our new timestamp-based caching framework (TBCF):

1. Our new caching framework should increase application performance by minimizing the object churning and maximizing object reuse.

2. We want to display only the most up-to-date pricing and availability, thus TBCF must never return a stale object.

3. We need to address compatibility with legacy systems. It would do us no good to have the world’s greatest framework that can’t be used in our application! Therefore, our new framework should have plug-and-play architecture: it should be easy to install and configure on any system. Ideally, TBCF should allow any existing application object to be cached, as long as it implements a simple Cacheable interface.

4. We want to make it easy to plug any caching algorithm into our framework. Because one caching algorithm does not fit all applications, we should have the ability to plug in a least-frequently used (LFU), a least-recently used (LRU), or a first-in-first-out (FIFO) caching class, as long as it implements the required Cache interface.

Timestamp: The key to the cache kingdom

We are seemingly stuck with two main conflicting requirements: cache as much as we can and guarantee freshness of all the retrieved objects.

To satisfy these requirements we use Object‘s Timestamp attribute. Timestamp is simply the date and time the object was last modified by the system. Timestamp is typically stored as either Date or long. (On a related note, the Version attribute is related to Timestamp and can also be used in our framework to determine object freshness. Version is typically stored as an int.)

The easiest way to implement a Timestamp attribute is to use a database trigger. If any of the specified fields in a table row are modified in the database, the trigger automatically updates the timestamp column of the table with the latest SQL Sysdate. Database triggers are by nature application-independent, which renders them the ideal solution if multiple applications are accessing the same database tables. In our Music Shop application, we use a long representation of the Java Date attribute as our Timestamp. This long number is the count of milliseconds that separates “now” from the first moment of 1970—the year that launched the glorious decade that gave us Star Wars, Abba, punk, and Kermit the Frog.

A UML sequence diagram is worth 1,000 words

To help visualize how the Timestamp attribute is used, I created a UML sequence diagram found in Figure 3.

Figure 3. UML sequence diagram of loading objects from the cache and database using TBCF. Click on thumbnail to view full-sized image.

To summarize, a user request for Britney Spears CDs proceeds as follows:

1. Obtain a list of IDs of “Britney” CDs

2. Retrieve Timestamps for these IDs from the database

3. Cache: Use the Id-Timestamp combination to collect the following:

   1. Fresh objects found in the cache

   2. IDs only for objects where the cache’s timestamp differs from the database’s timestamp (i.e., cached object is stale)

   3. IDs were not found in the cache (i.e., object is missing from the cache)

4. Database: Load the data and create missing/stale objects

5. Load all new and reloaded objects into cache

6. Combine 3a’s list with 4’s list

7. Sort the combined list

8. Send CDs to users rendered as HTML

Object-oriented design ideas in action

To make our framework modular and extendable, we have used the best principles of object-oriented design to create our Java classes. For objects to participate in the TBCF, we only require them to implement the Cacheable interface (instead of extending some base class):

 public interface Cacheable extends Timestamped {

   public Collection loadFromIds(Collection idsToRefreshFromDb, Connection conn) throws ResourceLoadException;

}

For objects that lack a loadFromIds() method, we also provide an alternative static database-loading method based on the Java Reflection API. To use this loading method, objects need only implement a simpler Timestamped interface, shown in the code below. Access to a static loading method allows TBCF to be compatible with an even greater range of legacy systems.

 public interface Timestamped {

   public String getId();
   public long getTimestamp();

}

To allow users the ability to plug in any caching scheme (LRU, LFU, etc.) a simple Cache interface (which extends java.util.Map) is used to denote the caching class:

 public interface Cache extends java.util.Map {

   /* Additional methods for Cache (not found in Map). */
   //Returns the maximum size of the cache.
   public int getMaxSize();

}

The caching class is based on a popular LRU algorithm, called LRULInkedMapCache because it was created by extending the LinkedHashMap class, which has been provided in the standard java.util package since J2SE 1.4. Whenever possible, we use standard java.util interfaces (Collection, List, and Map) as return types for our framework methods.

To address multithreading and synchronization concerns, we use synchronized wrappers in the Sun Java naming convention (xxxTable wraps xxxMap).

We have developed our CacheManager using the Data Access Object (DAO) design pattern: the CacheManager automatically loads some objects from the cache and others from the database, insulating the caller from implementation. CacheManager is a singleton, implementing the static Cache initialization.

The entire timestamp-based caching framework has a dynamic Java runtime configuration that can be loaded from a properties file or entered on the command line. Whenever possible, we use immutable objects (like TimestampedId) for simplicity and reliability. We always throw layer-appropriate exceptions (like ResourceLoadException). To make our design intentions clear, we have created our Util class to be non-instantiatable and final, because it contains only static utility methods.

The resulting UML class diagram is shown in Figure 4.

Figure 4. UML class diagram of the timestamp-based caching framework. Click on thumbnail to view full-sized image.

A look at the code

Note that in the code snippets below, I have omitted error handling, comments, and many other essential details in the interest of moving the narrative along. I encourage you to look at the actual source code (downloadable from Resources) while you peruse this section.

Step 1. User’s search: getCdIdsThatMatchUserSearch()

In this section, we load all the IDs/timestamps for CDs authored by Britney Spears. If we were not using a cache, our first step would be to create the complete list of CDs containing all of the required data. However, since our first TBCF requirement is to decrease object churning, we instead load a list of small immutable objects: TimestampedIds. As the name suggests, this object aggregates exactly two attributes: Id and Timestamp. The Id is used to retrieve CD objects from the cache or database, whereas the Timestamp attribute is used to determine the freshness of the cache’s CD objects to ensure none of the delivered objects are stale. TimestampedId objects are designed to be light; they can be created quickly and put minimum load on our application:

 public static List getCdIdsThatMatchUserSearch(String artist)
   throws ResourceLoadException { 

   rs = stmt.executeQuery("SELECT id, timestamp FROM cd WHERE artist = '" +  artist + "'");         

   TimestampedId id = null;
   while (rs.next()) {
      id = new TimestampedId(rs.getString(1), rs.getLong(2));
      returnVec.addElement(id);
   }

   return returnVec;
}

Step 2. CacheManager main method: loadFromCacheAndDB()

The loadFromCacheAndDB() method represents the brains of our framework. It has been developed with a Data Access Object (DAO) design pattern: we give the loadFromCacheAndDB() method a list of the object IDs we want, and it does the rest, automatically picking valid objects from the cache and loading the remainder from the database.

Here is how this method works: First, loadFromCacheAndDB() sets up two lists: currentCached and refreshFromDb. Using the list of TimestampedIds from Step 1 (which contains all of the CDs we need to load), we fill both current and refresh lists using the fillFreshAndStaleFromCache() method. Second, the IDs in the refresh list (containing stale and missing IDs) are used to load objects from the database, using the Cacheable interface’s loadFromIds() method specific to the object being cached. In this way, we optimize our retrieval strategy: we only hit the database to create objects we did not already have in our cache.

One caveat of this methodology is that it requires an instance of the Cacheable class on which to call an automatic loader method. Why do we need this instance? To allow us the flexibility of using a Java interface to call various load() methods. The JVM simply needs to know which load() method to call. For example, cd.loadFromIds() will load from a different table than author.loadFromIds(), so we need an instance of the Cacheable class to help the JVM select the right method.

In many cases, a static load() method is preferred, but since static methods can’t be a part of the interface, we must provide a dummy instance of the Cacheable object on which to call our loading method. In a later section, I discuss an alternative loading mechanism that uses Java reflection to allow us to call static load() methods.

Once all the stale or missing objects are loaded, we update our cache with these objects according to the LRU algorithm implemented in LRULInkedMapCache. If the cache is already full, this algorithm will always remove the least-recently used item from the cache and replace it with one of the incoming stale or missing objects. Finally, we combine our currentCached and newlyLoaded lists to make a single list of fresh, completely loaded objects from the cache and database:

 public static List loadFromCacheAndDB(List timestampedIds,
   Cacheable cacheable) throws ResourceLoadException {

   Vector currentObjectsFromCache = new Vector();
   Vector idsToRefreshFromDb      = new Vector(); 

   fillFreshAndStaleFromCache(
      timestampedIds,
      idsToRefreshFromDb,
      currentObjectsFromCache);

   Collection objectsFromDb = cacheable.loadFromIds(idsToRefreshFromDb);

   updateCache(objectsFromDb);

   currentObjectsFromCache.addAll(objectsFromDb); //combine lists

   return currentObjectsFromCache;
}

Step 3. CacheManager filtering: fillFreshAndStaleFromCache()

In the fillFreshAndStaleFromCache() method, we iterate through an incoming list of TimestampedIds of Britney CDs to determine which objects need to be reloaded from the database and which can be retrieved from the cache. We use the TimstamedId.Id attribute to look up objects in the cache. If the object is not found in the cache, we add the missing ID to the idsToRefresh list. If the object is found, we compare the cached object’s timestamp with the incoming TimestampedId.timestamp attribute. If the timestamps are equal, the object in the cache is fresh, and we add it to the currentObject list. If the timestamps are not equal, the object is stale, and we add its ID to the idsToRefresh list.

This method uses two lists, currentObjectsFromCache and idsToRefreshFromDb, which we pass by reference from the caller method. This design is less then perfect since we are modifying two global lists, but it’s justified here because this method is private and this design is efficient. It allows us to fill both current and refresh lists by iterating through the TimestampedId list just once:

 private static void fillFreshAndStaleFromCache(
   List timestampedIds,
   Vector idsToRefreshFromDb,
   Vector currentObjectsFromCache) {

   TimestampedId timestampedId = null;
   Timestamped c = null;

   for(Iterator i = timestampedIds.iterator(); i.hasNext();) {

      timestampedId = (TimestampedId)i.next();
      c = (Timestamped)cache.get(timestampedId.getId());

      if(null == c) {
         //<NOT FOUND>
         idsToRefreshFromDb.add(timestampedId.getId());
         continue;
      } else if(c.getTimestamp() != timestampedId.getTimestamp()) {
         //<STALE>
         idsToRefreshFromDb.add(timestampedId.getId());
         continue;
      } else {
         //<FRESH>
         currentObjectsFromCache.add(c);
      }
  }
}

Step 4. Cacheable loadFromIds()

loadFromIds() is a straightforward instance method that we use to create the stale or missing CDs we found in Step 3. We pass this method a list of IDs, and a Collection of completely loaded CD objects returns. To load all of the CDs in a single shot, we use a handy Util class method to marshal the IDs list into a commaDelimitedIds string with commas and single quotes, such as "'1','2,'3'", suitable for use in the SQL IN statement:

 public Collection loadFromIds(Collection idsToRefreshFromDb)
   throws ResourceLoadException {

   Vector objectsFromDb = new Vector();
   String commaDelimitedIds =
      Util.makeCommaDelimitedStringsList(idsToRefreshFromDb);

   String sql = new StringBuffer()
      .append("SELECT id, title, artist")
      .append("FROM cd WHERE id IN (")
      .append(commaDelimitedIds) //"'1','2,'3'"
      .append(")").toString();

   stmt = conn.createStatement();                

   rs = stmt.executeQuery(sql);       

   //Load complete CDs from the result set
   CD cd = null;
   while (rs.next()) {
      cd = new CD();
      cd.id = rs.getString(1);
      cd.title = rs.getString(2);
      cd.artist = rs.getString(3);
      objectsFromDb.addElement(cd);
   }

   return objectsFromDb;
}

Step 5. Sort and display results: performFinalSort()

The performFinalSort() method is run after TBCF retrieves the list of CDs. Here, we order the combined, completely loaded CD list by title, using Comparator to produce a sorted List of CDs. It is worth noting that we have to use Java sorting in our framework, because the incoming CD list is always unordered. To form this List, we must combine lists of objects from the cache and database. Even if each of the original lists were ordered, once they are added together, the order of the resulting combined list is indeterminate. Here is the code that performs the final sorting. It uses Comparator implemented via an anonymous inner class:

 private static void performFinalSort(List cds) {

   Collections.sort(cds,
      new Comparator() {

         public int compare(Object cd1, Object cd2) {
            return ( ((CD)cd1).getTitle() )
               .compareTo( ((CD)cd2).getTitle() );
         }

      }
   );
}

A complete list of CDs sorted by the performFinalSort() method is now ready to be used elsewhere in our application or rendered as HTML and sent to the user’s browser. Our new timestamp-based caching framework increased the efficiency of our Music Store application by loading all of the available fresh CD objects from the cache and the rest from the database. Only stale or missing objects are created; object churning is minimized, without compromising the data’s freshness.

Alternative approach to loading objects from the database

Although the methods I have described work well for most applications, all of our CD objects must implement the Cacheable interface to auto-load CD objects from the database to participate in TBCF. As described above, to implement the design using the Cacheable interface, we need an instance of the Cacheable object to load the CDs via the loadFromIds() method defined in the Cacheable interface. This solution is elegant and easy to incorporate into most legacy applications. Most business classes already loosely follow the EJB (Enterprise JavaBean) entity-bean method-set and include some permutation of the load() method, which loads the object based on the passed object ID. However, some legacy frameworks may not include convenient instance load() methods we can use, or it may simply be more desirable to call a static load() method instead.

Does the absence of the instance load() method mean we can’t use our new framework? Not at all! For these situations, the Java Reflection API provides a handy alternative for invoking the desired static method. Admittedly, the Reflection approach is more error prone, less elegant, and slightly more resource intensive. However, it is also exceptionally flexible and easy to use.

The Java Reflection API provides a way to perform a runtime load() method configuration and allows the load() method itself to be declared static. This permits TBCF to cache an even greater variety of objects and provides maximum plug-and-play functionality for compatibility with a greater number of legacy systems. The objects we want to cache will still need to implement the Timestamped interface. The framework needs access to Id and Timestamp attributes to determine object freshness—there is no way around that. But Reflection neatly addresses the problem of accessing any user-defined static load() method. Reflection-based and instance-based loadFromCacheAndDB() methods are overloaded, so they can happily coexist in our framework.

CacheManager Reflection API load: loadFromCacheAndDB()

The loadFromCacheAndDB() method works as follows: As before, we set up two lists—currentCached and refreshFromDb—and fill them both from the cache. However, the loading mechanism is now implemented differently; instead of a dummy instance of the Cacheable class, we pass the name of the static load() method we wish to invoke and the name of the class that houses that method. This static load() method is then called using the Java Reflection API. After the missing and stale objects are loaded, we again proceed as we did previously: to update Cache with new objects, combine the currentCached and newlyLoaded lists and sort the resulting list. The final result is exactly the same: we obtain a sorted list of completely loaded, guaranteed fresh CD objects obtained from the cache and database:

 public static List loadFromCacheAndDB(
   List timestampedIds,
   String loaderClassName,
   String loaderMethodName,
   Connection conn)
   throws ResourceLoadException {

   Vector currentObjectsFromCache = new Vector();
   Vector idsToRefreshFromDb      = new Vector(); 

   fillFreshAndStaleFromCache(
      timestampedIds,
      idsToRefreshFromDb,
      currentObjectsFromCache);

   /* Java Reflection-based call replaces cacheable.loadFromIds() */
   Collection objectsFromDb = loadStaleOrMissingFromDB(
      idsToRefreshFromDb,
      loaderClassName,
      loaderMethodName,
      conn);

   updateCache(objectsFromDb);

   currentObjectsFromCache.addAll(objectsFromDb);

   return currentObjectsFromCache;
}

Loading using Reflection: loadStaleOrMissingFromDB()

This section demonstrates the mechanism by which the static load() method is called using the Java Reflection API. We pass to loadStaleOrMissingFromDB() the name of our static load() method and the name of the class we will use to invoke it. We use the familiar Reflection invocation code to set up the Class array of loader-method parameter types and obtain a reference to the load() Method object. We then set up the Object array of loader method arguments, passing it the list of Britney CD IDs to load and a database connection. Then we call invoke() on the load() Method object to execute the load() method. Because the load() method we’re calling is static, our invoke() method’s first argument (the object on which the load() must be invoked) is null:

 private static Collection loadStaleOrMissingFromDB(
   Vector idsToRefreshFromDb,
   String loaderClassName,
   String loaderMethodName,
   Connection conn)
   throws ResourceLoadException {

   Class loaderClass = Class.forName(loaderClassName);
   Class[] loaderMethodParameters = new Class[2];
   loaderMethodParameters[0] = Collection.class;
   loaderMethodParameters[1] = Connection.class;

   Method loaderMethod = loaderClass.getMethod(
      loaderMethodName,
      loaderMethodParameters);

   Object[] loaderMethodArguments = new Object[2];
   loaderMethodArguments[0] = idsToRefreshFromDb;
   loaderMethodArguments[1] = conn;

   objectsFromDb = (Collection)loaderMethod.invoke(
      null, //NULL = static method
      loaderMethodArguments);

   return objectsFromDb;
}

Using Java Reflection helps us access static load() methods and adds compatibility with a greater range of legacy systems.

Requirements fulfilled

In closing, let’s revisit the requirements I defined at the beginning of this article to make sure we have met them.

1. The new timestamp-based caching framework has maximized our application’s efficiency by loading all of the available fresh objects from the cache and the rest from the database. Only stale or missing objects were created; object churning was minimized without compromising the data’s freshness.

3. To determine staleness we used the Timestamp attribute of a particular instance of an object, instead of the generic TTL. Therefore, we are certain to always deliver the most up-to-date information. As long as the timestamp is updated using a SQL database trigger or other reliable mechanism, TBCF will never return a stale object.

4. We addressed the compatibility of TBCF with legacy systems. TBCF is easy to install and can be configured at runtime via a Java process command line or properties file. TBCF allows any existing legacy application object to be cached, as long as it implements a simple Cacheable interface. In addition, we also provided a straightforward way to access static loading-methods at runtime via the Java Reflection API, allowing an even greater number of legacy classes to be cached.

5. Although we created the framework with an LRU caching class, we also made it easy to plug any caching algorithm into our framework, as long as it implements the required Cache interface.

Conclusion

TBCF can be used to achieve high levels of performance and decrease the churning of time-sensitive objects, without compromising freshness of the data delivered to the user. This framework uses a sophisticated strategy of automatically optimizing the loading of objects from the cache and database, using the object’s timestamp to reliably determine freshness. The timestamp-based caching framework has a simple, straightforward design and low resource overhead. It is built using Java’s excellent utility classes, can be easily plugged into many legacy systems, and can be used with any caching algorithm. Using this framework, developers can dramatically boost application performance by minimizing the number of objects that the JVM must destroy and re-create, while guaranteeing the availability of the most up-to-date information.

[signature]