Articles Index
By Jonathan Lurie Reprinted from
JavaWorld
July 2001
Developers create applications that support thousands of concurrent users. To achieve high levels of scalability and performance for those users, applications must use services that cache resources such as lists and variables employed by multiple users. Because many developers don't know where to start when creating caching services, they often turn to third-party software to handle this seemingly complex task. In this article you will learn how to create those services yourself. The code presented here provides a caching service that is effective and ready to use.
Suppose a coworker asks you for a list of all the countries in the world. Because you are no geography expert, you surf over to the United Nations Website, download the list, and print it out for her. However, she only wishes to examine the list; she doesn't actually take it with her. Because the last thing you need is another piece of paper on your desk, you feed the list to the shredder.
A day later, another coworker requests the same thing: a list of every country in the world. Cursing yourself for not keeping the list, you again surf back to the United Nations website. On this visit to the website, you note that the UN updates its country list every six months. You download and print the list for your coworker. He looks at it, thanks you, and again, leaves the list with you. This time you file the list away with a message on an attached Post-it note that reminds you to discard it after six months.
Sure enough, over the next few weeks your coworkers continue to request the list again and again. You congratulate yourself for filing the document since you can extract the document from the filing cabinet more quickly than you can extract it from the website. Your filing cabinet concept catches on; soon everyone starts putting items in your cabinet. To prevent the cabinet from growing disorganized, you set guidelines for using it. In your official capacity as filing cabinet manager, you instruct your coworkers to place labels and Post-it notes on all documents, which identify the documents and their discard/expiration date. The labels help your coworkers locate the document they're looking for, and the Post-it notes qualify whether the information is up to date.
The filing cabinet grows so popular that soon you can't file any new documents in it. You must decide what to throw out and what to keep. Although you throw out all expired documents, the cabinet still overflows with paper. How do you decide which nonexpired documents to discard? Do you discard the oldest document? You could discard the least frequently used or the least recently used; in both cases you would need a log that listed when each document was accessed. Or perhaps you could decide which documents to discard based on some other determinant; the decision is purely personal.
To relate the above real-world analogy to the computer world, the filing cabinet operates as a cache: a high-speed memory that occasionally needs maintenance. The documents in the cache are cached objects, all of which conform to the standards set by you, the cache manager. The process of cleaning out the cache is termed purging. Because cached items are purged after a certain amount of time has elapsed, the cache is called a timed cache.
In this article, you will learn how to create a 100 percent pure Java cache that uses an anonymous background thread to purge expired items. You will see how to architect such a cache while understanding the trade-offs involved with various designs.
Build the Cache
Enough filing cabinet analogies: let's move on to Websites. Website servers need to deal with caching too. Servers repeatedly receive requests for information, which are identical to other requests. For your next task, you must build an Internet application for one of the world's largest companies. After four months of development, including many sleepless nights and far too many Jolt colas, the application goes into development testing with 1,000 users. A 5,000-user certification test and a subsequent 20,000-user production rollout follows the development testing. However, after you receive out-of-memory errors while only 200 users test the application, development testing halts.
To discern the source of the performance degradation, you use a profiling product and discover that the server loads multiple copies of database ResultSet s, each of which has several thousand records. The records make up a product list. Moreover, the product list is identical for every user. The list does not depend on the user, as might have been the case if the product list had resulted from a parameterized query. You quickly decide that one copy of the list could serve all concurrent users, so you cache it.
However, a number of questions arise, which include such complexities as:
- What if the product list changes? How can the cache expire the lists? How will I know how long the product list should remain in the cache before it expires?
- What if two distinct product lists exist, and the two lists change at different intervals? Can I expire each list individually, or must they all have the same shelf life?
- What if the cache is empty and two requesters try the cache at exactly the same time? When they both find it empty, will they create their own lists, and then both try to put their copies into the cache?
- What if items sit in the cache for months without being accessed? Won't they eat up memory?
To address these challenges, you need to construct a software caching service.
In the filing cabinet analogy, people always checked the cabinet first when searching for documents. Your software must implement the same procedure: a request must check the caching service before loading a fresh list from the database. As a software developer, your responsibility is to access the cache before accessing the database. If the product list has already loaded into the cache, then you use the cached list, provided it is not expired. If the product list is not in the cache, then you load it from the database and cache it immediately.
Note: Before proceeding to the caching service's requirements and code, you might want to check out the sidebar below, "Caching Versus Pooling." It explains pooling, a related concept.
Requirements
In keeping with good design principles, I defined a requirements list for the caching service that we will develop in this article:
- Any Java application can access the caching service.
- Objects can be placed in the cache.
- Objects can be extracted from the cache.
- Cached objects can determine for themselves when they expire, thereby allowing maximum flexibility. Caching services that expire all objects using the same expiration formula fail to provide optimal use of cached objects. This approach is inadequate in large-scale systems since, for example, a product list may change daily, whereas a list of store locations might change only once a month.
- A background thread that runs under low priority removes expired cached objects.
- The caching service can be enhanced later through the use of a least-recently used (LRU) or least-frequently used (LFU) purging mechanism.
Implementation
To satisfy Requirement 1, we adopt a 100 percent pure Java environment. By providing public get and set methods in the caching service, we fulfill Requirements 2 and 3 as well.
Before proceeding with a discussion of Requirement 4, I'll briefly mention that we will satisfy Requirement 5 by creating an anonymous thread in the cache manager; this thread starts in the static block. Also, we satisfy Requirement 6 by identifying the points where code would later be added to implement the LRU and LFU algorithms. I will go into more detail about these requirements later in the article.
Now, back to Requirement 4, where things become interesting. If every cached object must determine for itself whether it is expired, then you must have a way to ask the object if it's expired. That means that objects in the cache must all conform to certain rules; you accomplish that in Java by implementing an interface.
Let's begin with the rules that govern the objects placed in the cache.
- All objects must have a public method called
isExpired() , which returns a Boolean value.
- All objects must have a public method called
getIdentifier() , which returns an object that distinguishes the object from all others in the cache.
Note: Before jumping straight into the code, you must understand that you can implement a cache in many ways. I have found more than a dozen different implementations. Enhydra and Caucho provide excellent resources that contain several cache implementations.
You'll find the interface code for this article's caching service in Listing 1.
Listing 1. Cacheable.java
/**
* Title: Caching
Description: This interface defines the methods,
which must be implemented
by
all objects wishing to be placed in the cache.
*
* Copyright: Copyright (c) 2001
* Company: JavaWorld
* FileName: Cacheable.java
@author Jonathan Lurie
@version 1.0
*/
public interface Cacheable
{
/* By requiring all objects to determine their own
expirations, the algorithm is abstracted from the
caching service, thereby providing maximum flexibility
since each object can adopt a different expiration
strategy.
*/
public boolean isExpired();
/* This method will ensure that the caching service
is not responsible for uniquely identifying objects
placed in the cache.
*/
public Object getIdentifier();
}
|
Any object placed in the cache -- a String , for example -- must be wrapped inside an object that implements the Cacheable interface. Listing 2 is an example of a generic wrapper class called CachedObject ; it can contain any object needed to be placed in the caching service. Note that this wrapper class implements the Cacheable interface defined in Listing 1.
Listing 2. CachedManagerTestProgram.java
/**
* Title: Caching
* Description: A Generic Cache Object wrapper.
Implements the Cacheable interface
* uses a TimeToLive stategy for CacheObject expiration.
* Copyright: Copyright (c) 2001
* Company: JavaWorld
* Filename: CacheManagerTestProgram.java
* @author Jonathan Lurie
* @version 1.0
*/
public class CachedObject implements Cacheable
{
// +++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++
/* This variable will be used to determine if the
object is expired.
*/
private java.util.Date dateofExpiration = null;
private Object identifier = null;
/* This contains the real "value". This is the
object which needs to be shared.
*/
public Object object = null;
// ++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++
public CachedObject(Object obj, Object id,
int minutesToLive)
{
this.object = obj;
this.identifier = id;
// minutesToLive of 0 means it lives on
indefinitely.
if (minutesToLive != 0)
{
dateofExpiration = new java.util.Date();
java.util.Calendar cal =
java.util.Calendar.getInstance();
cal.setTime(dateofExpiration);
cal.add(cal.MINUTE, minutesToLive);
dateofExpiration = cal.getTime();
}
}
// ++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++
public boolean isExpired()
{
// Remember if the minutes to live is zero
then it lives forever!
if (dateofExpiration != null)
{
// date of expiration is compared.
if (dateofExpiration.before(
new java.util.Date()))
{
System.out.println(
"CachedResultSet.isExpired: Expired from
Cache! EXPIRE TIME: " + dateofExpiration.toString()
+ " CURRENT TIME: " +
(new java.util.Date()).toString());
return true;
}
else
{
System.out.println(
"CachedResultSet.isExpired:
Expired not from Cache!");
return false;
}
}
else // This means it lives forever!
return false;
}
// ++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++
public Object getIdentifier()
{
return identifier;
}
// +++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++
}
|
The CachedObject class exposes a constructor method that takes three parameters:
public CachedObject(Object obj, Object id, int minutesToLive)
The table below describes those parameters.
Parameter descriptions of the CachedObject constructor
Name |
Type |
Description |
Obj |
Object |
The object that is shared. It is defined as an object to allow maximum flexibility. |
Id |
Object |
Id contains a unique identifier that distinguishes the obj parameter from all other objects residing in the cache. The caching service is not responsible for ensuring the uniqueness of the objects in the cache. |
minutesToLive |
Int |
The number of minutes that the obj parameter is valid in the cache. In this implementation, the caching service interprets a value of zero to mean that the object never expires. You might want to change this parameter in the event that you need to expire objects in less than one minute. |
The constructor method determines the expiration date of the object in the cache using a time-to-live strategy. As its name implies, time-to-live means that a certain object has a fixed time at the conclusion of which it is considered dead. By adding minutesToLive , the constructor's int parameter, to the current time, an expiration date is calculated. This expiration is assigned to the class variable dateofExpiration .
Now, the isExpired() method must simply determine if the dateofExpiration is before or after the current date and time. If the date is before the current time, and the cached object is deemed expired, the isExpired() method returns true; if the date is after the current time, the cached object is not expired, and isExpired() returns false. Of course, if dateofExpiration is null, which would be the case if minutesToLive was zero, then the isExpired() method always returns false, indicating that the cached object lives forever.
We've defined the rules by which the cached objects must abide and created a concrete class that supports those rules. Now all we need is the caching service that keeps the objects. Listing 3 provides this class, named CacheManager :
Listing 3. CacheManager
/**
* Title: Caching
* Description:
* Copyright: Copyright (c) 2001
* Company: JavaWorld
* Filename: CacheManager.java
* @author Jonathan Lurie
* @version 1.0
*/
public class CacheManager {
/* This is the HashMap that contains all objects
in the cache. */
private static java.util.HashMap cacheHashMap =
new java.util.HashMap();
/* This object acts as a semaphore, which
protects the HashMap */
/* RESERVED FOR FUTURE USE private static
Object lock = new Object(); */
static
{
try
{
/* Create background thread, which will be
responsible for purging expired items. */
Thread threadCleanerUpper = new Thread(
new Runnable()
{
/* The default time the thread should
sleep between scans. The sleep
method takes in a millisecond
value so 5000 = 5 Seconds.
*/
static int milliSecondSleepTime = 5000;
public void run()
{
try
{
/* Sets up an infinite loop.
/*The thread will continue
looping forever.*/
while (true)
{
System.out.println(
"ThreadCleanerUpper Scanning
ForExpired Objects...");
/* Get the set of all keys that are
/*in cache. These are the unique
/*identifiers */
java.util.Set keySet =
cacheHashMap.keySet();
/* An iterator is used to move*/
/* through the Keyset */
java.util.Iterator keys =
keySet.iterator();
/* Sets up a loop that will iterate
/*through each key in the KeySet */
while(keys.hasNext())
{
/* Get the individual key.
We need to hold on to this key
in case it needs to be
removed */
Object key = keys.next();
/* Get the cacheable object
associated with the key
inside the cache */
Cacheable value =
(Cacheable)
cacheHashMap.get(key);
/* Is the cacheable
object expired? */
if (value.isExpired())
{
/* Yes it's expired! Remove
it from the cache */
cacheHashMap.remove(key);
System.out.println(
"ThreadCleanerUpper Running.
Found an Expired Object
in the Cache.");
}
}
/*
******************************************************
***** A LRU (least-recently used) or
LFU (least-frequently used) *****
******* would best be inserted here *****
******************************************************
*/
/* Puts the thread to sleep.
Don't need to check it
continuously */
Thread.sleep(
this.milliSecondSleepTime);
}
}
catch (Exception e)
{
e.printStackTrace();
}
return;
} /* End run method */
}); /* End class definition and close
new thread definition */
// Sets the thread's
priority to the minimum value.
threadCleanerUpper.setPriority(
Thread.MIN_PRIORITY);
// Starts the thread.
threadCleanerUpper.start();
}
catch(Exception e)
{
System.out.println(
"CacheManager.Static Block: " + e);
}
} /* End static block */
public CacheManager()
{
}
public static void putCache(Cacheable object)
{
// Remember if the HashMap previously contains
a mapping for the key, the old value
// will be replaced. This is valid functioning.
cacheHashMap.put(object.getIdentifier(), object);
}
public static Cacheable getCache(Object identifier)
{
//synchronized (lock) // UNCOMMENT LINE XXX
//{ // UNCOMMENT LINE XXX
Cacheable object = (
Cacheable)cacheHashMap.get(identifier);
// The code to create the object
would be placed here.
//} // UNCOMMENT LINE XXX
if (object == null)
return null;
if (object.isExpired())
{
cacheHashMap.remove(identifier);
return null;
}
else
{
return object;
}
}
// ++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++
}
|
Before embarking on a subterranean exploration of the code, let's step back to view the big picture. The CacheManager allows objects to be put into and retrieved from the cache. When you need a certain object, then you should first check to see if the object already exists in the cache. If it is not in the cache, then a null value is returned. This operation is subject to much debate in the discussion of cache managers. The question inevitably arises as to what happens when an object is not in the cache. Who is responsible for creating the object? The CacheManager ? Or should the requester create the object and place it in the cache? Both approaches are valid, and both carry drawbacks. Let's begin with the reasons for having the CacheManager create objects.
Recall our earlier questions:
What if the cache is empty and two requesters try the cache at exactly the same time? When they both find it empty, will they create their own lists, and then both try to put their copies into the cache?
If two or even a hundred requesters accessed the cache simultaneously and found it empty, then they would all create their own copies and place them all in the cache. If the CacheManager created the objects itself, you wouldn't have this worry. By uncommenting the lines in Listing 3 that read Uncomment Line XXX and placing the object creation code within the brackets, you would prevent the situation just described. Proponents of this design argue that permitting users to create their own objects could cause severe performance degradation should hundreds of users simultaneously create the same large object. Opponents of this approach argue that this problem can be overcome by using loader programs, which run at the start of execution and prepopulate the cache.
Other reasons against having the CacheManager create objects include code complexity and the merging of object creation with the middle tier. The CacheManager will most likely reside in the middle tier, yet object creation is typically the task of the data management tier, which has access to the database servers. In a distributed environment, it is a bad idea to place code that accesses the backend in the middle tier. In other words, to create a ResultSet object, you must use Java Database Connectivity and operate against a database.
That has little to do with caching. In our example we have opted against implementing object creation in the CacheManager . To delegate object creation to the user, use the Cacheable interface to define a method, such as:
public Object createObject(Object identifier);
That, in effect, delegates object creation to users of the cache and leaves the CacheManager designer free from blame in the event that an n-tier approach is violated.
In addition to placing and retrieving objects, CacheManager must also enforce the purging of expired objects from the cache. CacheManager accomplishes that in two ways: through the getCache() method and through a background thread. The function of the getCache() method is straightforward: if the requested object does exist within the cache, then the isExpired() method is called. If it is not expired, then the object is returned to the requester. If it is expired, the object is removed from the cache.
The putCache() method has the opposite function of getCache() ; putCache places items into the cache and takes a Cacheable parameter. That is important; remember, the Cacheable interface ensures consistency of cached items. There are alternate strategies for the putCache() method. I have seen implementations where the putCache() method creates a Cacheable object instead of taking one as a parameter. That approach is enticing since it means that users of the CacheManager don't need to know what a CachedObject is. In this alternate approach, the CacheManager exposes a putCache() method, which takes an object as a parameter rather than a Cacheable object. Both valid approaches accomplish the same task.
The most interesting aspect of CacheManager and the second approach to purging expired objects is the background thread created in the class's static block. The static block is invoked the first time CacheManager is referenced, so the background thread is only created once. It is defined within the instantiation call, a technique known as creating an anonymous class. I call the background thread the threadCleanerUpper since it searches through the cache and removes expired items. It may also clean or remove old or unused items in the event that the cache reaches full capacity.
Though the getCache() method tests an item for expiration when it is requested from the cache, this approach presents a problem: What if an expired object has been sitting in the cache for a long time without ever having been requested? Though the object is expired, it still consumes valuable memory resources. The background thread is useful in these situations because it automatically finds the expired object and discards it.
If you were to include an LRU or LFU algorithm, you might consider using this thread to remove the LRU or LFU objects. Again, though some implementations could remove LRU/LFU objects every time an object is requested, the thread approach keeps the cache at a relatively fixed size. I have opted not to include this functionality in the example here, although you can find implementations of LRU-purging mechanisms at Enhydra.
To find and remove expired items, the thread defines one method named run() , which is automatically invoked when the thread starts. The run() method runs forever by setting up the while(true) looping construct. true is always true so while(true) loops forever. Inside the loop the cacheManager HashMap is traversed, and the thread checks every item for expiration. It promptly removes any expired objects from the CacheManager . After cycling through the entire HashMap , the thread rests for five seconds. In a production system, five seconds may either be too often or not often enough, depending upon the requirements. You will want to modify this interval to suit your needs.
After defining the thread, the static block sets the thread's priority to the thread constant Thread.MINIMUM_PRIORITY , which dictates that the thread operates only in times of little CPU activity. Setting the thread's priority to minimum also boosts performance, since the thread will not absorb valuable CPU clock cycles in periods of high activity. Finally, the static block starts the thread.
Now comes time to test our CacheManager . I have created a simple test program, defined in Listing 4.
Listing 4. CacheManagerTestProgram.java
/**
* Title: Caching
* Description: A test program for the CacheManager
* Copyright: Copyright (c) 2001
* Company:
* Filename: CacheManagerTestProgram.java
* @author Jonathan Lurie
* @version 1.0
*/
public class CacheManagerTestProgram {
public CacheManagerTestProgram() {
}
public static void main(String[] args) {
CacheManagerTestProgram cacheManagerTestProgram1
= new
CacheManagerTestProgram();
/* This is the object that we are going to cache.
Admittedly this is a trivial object to cache.
You might replace our alphabet with a list of
every character in the world.
*/
String s = new String(
"ABCDEFGHIJKLMNOPQRSTUVWXYZ");
/* Create an instance of CachedObject,
set the minutesToLive to 1 minute.
Give the object some unique identifier.
*/
CachedObject co = new CachedObject(s, new Long(
1234), 1);
/* Place the object into the cache! */
CacheManager.putCache(co);
/* Try to retrieve the object from the cache! */
CachedObject o =
(CachedObject)CacheManager.getCache(
new Long(1234));
/* Let's see if we got it! */
if (o == null)
System.out.println(
"CacheManagerTestProgram.Main: FAILURE!
Object not Found.");
else
System.out.println(
"CacheManagerTestProgram.Main:
SUCCESS! " +
((String)o.object).toString());
}
}
|
This test program creates an object, places it into the cache with a one-minute time-to-live, and tests to see whether it is retrieved from the cache when requested. When you run the program, you want to keep an eye on your output console; you should see the threadCleanerUpper putting out messages every five seconds. After one minute, you'll notice that it cleans out the object placed in the cache. Your CacheManager is up and running!
For the bold and courageous, I encourage you to identify the needs of your system and ask yourself how you identify your objects in the cache. Can you identify objects using a primitive? If so, that is an area for improvement. Another means of improvement is to avoid the use of HashMap s, which are highly ineffective insofar as performance. Many performance-conscious companies have written their own version of the HashMap , which conserves additional memory. However, for now you are already on your way to improving performance and thrilling your users.
Requirements fulfilled
In closing, let's revisit the requirements to ensure that we have met them.
- Any Java application can access the caching service: We satisfied that requirement by building the cache in Java.
- Objects can be placed in the cache: We added a public
putObject() method to the CacheManager .
- Objects can be extracted from the cache: We added a public
getObject() method to the CacheManager .
- Cached objects can determine for themselves when they expire: We accomplished that by requiring that all objects to be placed in the cache implement the
Cacheable interface, which enforces the implementation of an isExpired() method.
- A background thread that runs under low priority removes expired cached objects: The anonymous
threadCleanerUpper found in the CacheManager satisfies this requirement.
- The caching service can be enhanced later through the use of LRU-purging mechanisms: You can add code to
threadCleanerUpper to search out the LRU/LFU cached objects. Of course, you'll need to keep a log of when and how many times each cachedObject was accessed.
Now that you have a caching service, you can successfully navigate the development and certification testing and find yourself in production. The memory will be stable, and everyone will be happy.
It is my hope that you will receive all of these benefits on your next project by utilizing the caching techniques discussed. Remember to visit Enhydra for ideas on how to expand this service! Good luck, and happy coding.
About the author
Jonathan Lurie was formerly a director of product development for an Internet software company specializing in the development of enterprise solutions using 100 percent pure Java; he is now consulting on the Java platform. Jonathan holds numerous certifications, including Sun Certified Java Programmer, Microsoft Certified Trainer, Microsoft Certified Solutions Developer, Microsoft Certified Database Administrator, Microsoft Certified Systems Engineer, and Solomons Certified Developer.
Resources
 |
Caching versus pooling
The terms pooling and caching are often mistakenly used interchangeably. The two are very different in a very simple way. Caching is the situation in which more than one user uses a single object. Pooling occurs when you have multiple users, each exclusively using one in a collection of identical objects. The user must acquire exclusive use of the object because the object changes during its usage. For example, Java Database Connectivity objects are not cached, but pooled; because each connection is used to carry information to and from the database, it cannot be shared among multiple users simultaneously. Only one user can use the connection at a time; after the user is finished using the connection, then it returns to the pool to be subsequently used by another user. However, it is correct to say that caching is used in situations where the object being shared is in a read-only state.
Return to article
|
Reprinted with permission from the July 2001 edition of JavaWorld magazine. Copyright Web
Publishing Inc., an IDG Communications company. Register for editorial e-mail alerts

|
|