November 25, 2014
Hot Topics:

Pattern Summaries: Cache Management

  • October 2, 2003
  • By Mark Grand
  • Send Email »
  • More Articles »

This article is part of an ongoing series in which I summarize patterns from my Patterns in Java books.

The essence of a pattern is a reusable solution for a recurring problem. A complete pattern will also provide reasons to use and not use the solution, the consequences of using the solution, and suggestions on how to implement the solution. The summaries in these articles will just describe the essential problem and its solution.

This article is the last of a group of articles that focus on patterns related to the low-level structure of the classes in an application. This article discusses a pattern called Cache Management, which comes from Volume 1 of Patterns in Java.

Cache Management

Suppose you are writing a program that allows people to fetch information about products in a catalog. Fetching all of a product's information can take a few seconds because it may have to be gathered from multiple sources. Keeping a product's information in the program's memory allows the next request for the product's information to be satisfied more quickly, since it is not necessary to spend the time to gather the information.

Keeping information in memory that takes a relatively long time to fetch into memory for quick access the next time it is needed is called caching. The large number of products in the catalog makes it infeasible to cache information for all of the products in memory. What can be done is to keep information for as many products as feasible in memory, selecting products guessed to be the most likely to be used are in memory so they are there when needed. Deciding which and how many objects to keep in memory is called cache management.

Figure 1 shows how cache management would work for the product information example.






Figure 1. Product cache management collabortion.


1 A product ID is passed to a ProductCacheManager object's getProductInfo method.
1.1 The ProductCacheManager object's getProductInfo method attempts to retrieve the product description object from a Cache object. If it successfully retrieves the object from the cache, it returns the object.
1.2 If it was unable to retrieve the product description object from the cache, it calls a ProductInfoFetcher object's getProductInfo method to fetch the product description.
1.3 Many cache managers implement a policy to limit the number of objects in a cache because keeping too many objects in the cache can be wasteful or even counterproductive. If the cache manager decides that the retrieved object should be stored in the cache but the cache already contains as many objects as it should, the cache manager will avoid increasing the number of objects in the cache. It does this by picking a product description object to remove from the cache and pass its product ID to the Cache object's removeProductInfo method.
1.4 Finally, if the cache manager had decided that the fetched object should be stored in the cache, it calls the Cache object's addProductInfo method.

Figure 2 show the general structure of the Cache Management pattern.


Figure 2. Cache Management Pattern.

Here are descriptions of the classes that participate in the Cache Management pattern and the roles that they play:
 

Client Instances of classes in this role delegate the responsibility of obtaining access to specified objects to a CacheManager object.
ObjectKey Instances of the ObjectKey class identify the object to be fetched or created.
CacheManager Client objects request objects a CacheManager object by calling its fetchObject method. The argument to the fetchObject method is an ObjectKey object that identifies the object to fetch. The fetchObject method works by first calling the Cache object's fetchObject method. If that fails, it calls the ObjectCreater object's createObject method.
ObjectCreater ObjectCreater objects are responsible for creating objects that are not in the cache.
Cache A Cache object is responsible for managing a collection of cached objects. Given an ObjectKey object, a Cache object quickly finds the corresponding cached object. The CacheManager object passes an ObjectKey object to the Cache object's fetchObject method to get a cached object from the cache. If the fetchObject method does not return the requested object, the CacheManager object asks the ObjectCreater object to create it. If the ObjectCreater object returns the requested object, the Cache object passes the returned object to this object's addObject method. The addObject method adds the object to the cache if that is consistent with its cache management policy. The addObject method may remove an object from the cache to make room for the object it is adding to the cache.

Sometimes applications of the Cache Management pattern are added to the design of a program after the need for a performance optimization has been discovered. This is usually not a problem because the impact of the Cache Management pattern on the rest of a program is minimal. If the CacheManager class is implemented as a subclass of the ObjectFetcher class then, using the Proxy pattern, an implementation of the Cache Management pattern can be inserted into a working program with minimal modification to existing code.

The primary consequence of using the Cache Management pattern is that a program spends less time fetching objects from expensive sources. The simplest way of measuring the effectiveness of caching is by computing a statistic called its hit rate. The hit rate is the percentage of object fetch requests that the cache manager satisfies with objects stored in the cache. If every request is satisfied with an object from the cache, then the hit rate is 100%. If no request is satisfied, then the hit rate is 0%. The hit rate depends largely on how well the implementation of the Cache Management pattern matches the way that objects are requested. You can find a more detailed analysis of the performance implications of caching in Patterns in Java.

When objects are created with data from an external source, another consequence of using the Cache Management pattern is that the cache may become inconsistent with the original data source. The consistency problem breaks down into two separate problems that can be solved independently of each other. Those problems are read consistency and write consistency.

Read consistency means that the cache always reflects updates to information in the original object source. If the objects being cached are stock prices, then the prices in the object source can change while the prices in the cache will no longer be current. Write consistency means that the original object source always reflects updates to the cache. To achieve absolute read or write consistency for objects in a cache with the original object source requires that you implement a mechanism that keeps them synchronized. Such mechanisms can be complicated to implement and add considerable execution time. They generally involve techniques such as locking and optimistic concurrency, which are beyond the scope of this article.

As an example, we will now consider a problem that can benefit from an application of the Cache Managment pattern. Suppose you are writing software for an employee timekeeping system. The system consists of timekeeping terminals and a timekeeping server. The terminals are small boxes mounted on the walls of a place of business. When an employee arrives at work or leaves work, the employee notifies the timekeeping system by running his or her ID card through a timekeeping terminal. The terminal reads the employee's ID on the card and acknowledges the card by displaying the employee's name and options. The employee then selects an option to indicate that he or she is starting work, ending work, going on break or other options. The timekeeping terminals transmit these timekeeping events to the timekeeping server. At the end of each pay period, the business's payroll system gets the number of hours each employee worked from the timekeeping system and prepares paychecks.

The exact details of what an employee sees will depend on an employee profile that a terminal receives from the timekeeping server. The employee profile will include the employee's name, the language in which to display prompts for the employee and what special options apply to the employee.

Most businesses assign their employees a fixed location in the business place to do their work. Employees with a fixed work location will normally use the timekeeping terminal nearest to their work location. To avoid long lines in front of timekeeping terminals, it is recommended that the terminals be positioned so that fewer than 70 employees with fixed work locations will use the same timekeeping terminal.

A substantial portion of the cost of the timekeeping system will be the cost of the terminals. To keep their cost down, the timekeeping terminals will have a minimal amount of memory. However, to keep response time down, we will want the terminals to cache employees profiles so that most of the time they will be able to respond immediately when presented with an employee's ID card. That means that you will have to impose a maximum cache size that is rather modest. A reasonable basis for an initial maximum cache size is the recommendation that the terminals be positioned so that no more than 70 employees with fixed work locations use the same terminal. Based on that, we come up with an initial cache size of up to 80 employee profiles.

The reason for picking a number larger than 70 is that under some situations more than 70 employees may use the same timekeeping terminal. Sometimes one part of a business will borrow employees from another part of a business when they experience a peak workload. Also, there will be employees, such as maintenance staff, that float from one location to another.

Figure 3 is a class diagram that shows how the Cache Management pattern is applied to this problem.


Figure 3. Timekeeping Cache Management

Lets look at some code that implements the design in Figure 3. First, here is the code for the EmployeeProfileManager class:

class EmployeeProfileManager {
    private EmployeeCache cache = new EmployeeCache();
    private EmployeeProfileFetcher server
      = new EmployeeProfileFetcher();

    /**
     * Fetch an employee profile for the given employee id from the
     * internal cache or timekeeping server if not in the internal cache.
     * @return employee's profile or null if employee profile not found.
     */
    EmployeeProfile fetchEmployee(EmployeeID id) {
        EmployeeProfile profile = cache.fetchEmployee(id);
        if (profile == null) {   // if profile not in cache try server
            profile = server.fetchEmployee(id);
            if (profile != null) { // Got the profile from the server
                // put profile in the cache
                cache.addEmployee(profile);
            } // if != null
        } // if == null
        return profile;
    } // fetchEmployee(EmployeeID)
} // class EmployeeProfileManager


The logic in the EmployeeProfileManager class is straightforward conditional logic. The logic of the EmployeeCache class is more intricate, since it has to manipulate a data structure to determine which employee profile to remove from the cache when adding an employee profile to a full cache.

class EmployeeCache {
    /**
     * We use a linked list to determine the least recently used employee
     * profile.  The cache that itself is implemented by a Hashtable
     * object. The Hashtable values are linked list objects that refer
     * to the actual EmployeeProfile object.
     */
    private Hashtable cache = new Hashtable();

    /**
     * This is the head of the linked list that refers to the most
     * recently used EmployeeProfile.
     */
    LinkedList mru = null;

    /**
     * this is the end of the linked list that referes to the least
     * recently used EmployeeProfile.
     */
    LinkedList lru = null;

    /**
     * Maximum number of EmployeeProfile objects that may be in the cache.
     */
    private final int MAX_CACHE_SIZE = 80;

    /**
     * The number of EmployeeProfile objects currently in the cache.
     */
    private int currentCacheSize = 0;

    /**
     * Objects are passed to this method for addition to the cache.
     * However, this method is not required to actually add an object
     * to the cache if that is contrary to its policy for what object
     * should be added.  This method may also remove objects already in
     * the cache in order to make room for new objects.
     */
    public void addEmployee(EmployeeProfile emp) {
        EmployeeID id = emp.getID();
        if (cache.get(id) == null) {
// if profile not in cache
            // Add profile to cache, making it the most recently used.
            if (currentCacheSize == 0) {
                // treate empty cache as a special case
                lru = mru = new LinkedList();
                mru.profile = emp;
            } else {  
          // currentCacheSize > 0
                LinkedList newLink;
                if (currentCacheSize >= MAX_CACHE_SIZE) {
                    // remove least recently used EmployeeProfile from the cache
                    newLink = lru;
                    lru = newLink.previous;
                    cache.remove(newLink);
                    lru.next = null;
                } else {
                    newLink = new LinkedList();
                }
// if >= MAX_CACHE_SIZE
                newLink.profile = emp;
                newLink.next = mru;
                newLink.previous = null;
                mru = newLink;
            }
// if 0
            // put the now most recently used profile in the cache
            cache.put(id, mru);
            currentCacheSize++;
        } else {
                // profile already in cache
            // addEmployee shouldn't be called when the object is already
            // in the cache.  Since that has happened, do a fetch so
            // that so object becomes the most recently used.
            fetchEmployee(id);
        } // if cache.get(id)
    } // addEmployee(EmployeeProfile)

    /**
     * Return the EmployeeProfile associated with the given EmployeeID or
     * null if no EmployeeProfile is associated with the given EmployeeID.
     */
    public EmployeeProfile fetchEmployee(EmployeeID id) {
        LinkedList foundLink = (LinkedList)cache.get(id);
        if (foundLink == null)
          return null;
        if (mru != foundLink) {
            if (foundLink.previous != null)
              foundLink.previous.next = foundLink.next;
            if (foundLink.next != null)
              foundLink.next.previous = foundLink.previous;
            foundLink.previous = null;
            foundLink.next = mru;
            mru = foundLink;
        }
// if currentCacheSize > 1
        return foundLink.profile;
    }
// fetchEmployee(EmployeeID)

    /**
     * private doublely linked list class for managing list of most
     * recently used employee profiles.
     */
    private class LinkedList {
        EmployeeProfile profile;
        LinkedList previous;
        LinkedList next;
    }
// class LinkedList
} // class EmployeeCache



Finally, here are the EmployeeProfile and EmployeeID classes:
 

class EmployeeProfile {
    private EmployeeID id;      // Employee Id
    private Locale locale;      // Language Preference
    private boolean supervisor;
    private String name;        // Employee name

    public EmployeeProfile(EmployeeID id,
                           Locale locale,
                           boolean supervisor,
                           String name) {
        this.id = id;
        this.locale = locale;
        this.supervisor = supervisor;
        this.name = name;
    } // Constructor(EmployeeID, Locale, boolean, String)

    public EmployeeID getID() { return id; }

    public Locale getLocale() { return locale; }

    public boolean isSupervisor() { return supervisor; }
} // class EmployeeProfile
class EmployeeID {
    private String id;

    /**
     * constructor
     * @param id A string containing the employee ID.
     */
    public EmployeeID(String id) {
        this.id = id;
    } // constructor(String)

    /**
     * Returns a hash code value for this object.
     */
    public int hashCode() { return id.hashCode(); }

    /**
     * Return true if the given object is an EmployeeId equal to this one.
     */
    public boolean equals(Object obj) {
        return ( obj instanceof EmployeeID
                 && id.equals(((EmployeeID)obj).id) );
    } // equals(Object)

    /**
     * Return the string representation of this EmployeeID.
     */
    public String toString() { return id; }
} // class EmployeeID

About the Author

Mark Grand is the author of a series of books titled "Patterns in Java." He is a consultant who specializes in object-oriented design and Java. He is currently working on a framework to create integrated enterprise applications.






Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 


Enterprise Development Update

Don't miss an article. Subscribe to our newsletter below.

Sitemap | Contact Us

Rocket Fuel