Slava has posted 2 posts at DZone. View Full User Profile

Introducing Caching for Java Applications (Part 1)

07.17.2008
| 32371 views |
  • submit to reddit

An increasing volume of critical data presents new challenges when developing performing applications with Java. Caching may address these challenges if applied right. This series of two articles explores ways for improving performance, concurrency and scalability in Java applications through caching.

Notion of Cache

A cache is an area of local memory that holds a copy of frequently accessed data that is otherwise expensive to get or compute. Examples of such data include a result of a query to a database, a disk file or a report. A typical interface for a Java cache provides access to the data using a unique key:

public interface Cache { 
Object get(final Object key);
Object put(final Object key, final Object value);
}

A cache works as the following: An application requests data from cache using a key. If the key is not found, the application retrieves the data from a slow data source and puts it into the cache. The next request for a key is serviced from the cache.

Improving Performance with Caching

Caching may provide significant performance improvement for a Java application, often in orders of magnitude. The performance improvement comes from serving hard to get data from the local memory of the application.

For example, consider an application that shows a 50-line system status report displayed on a web page after the user logs into the system. For each line it sends a complex SQL query to a database. To execute each query and to fetch results over the network takes 100 milliseconds on average. The total average time to collect all data for the page is about 5 seconds. Getting the same results from a cache takes about 5 microseconds on a modern 2GHz CPU. The performance improvement for this particular use scenario is 1,000,000!

Requirement for Temporal and Spatial Locality

A cache uses a part of the application's memory. That is why the size of the cache has to be small. A special algorithm should be used to remove (evict) data from the cache that has low chances of access. Such algorithm is called an eviction policy. To benefit from caching, the access to data should display properties of temporal and spatial locality. The data should be accessed often (temporal locality) and the probability of accessing a near cache element should be high (spatial locality). Increasing cache size for the data that satisfies this requirement increases hit/miss ratio.

The data from the example in the beginning of the article satisfies the requirement of temporal and spatial locality . Users log into the system around the same time and the number of items from the reports that are accessed in rapid succession is small.

Data that does not satisfy the requirement of temporal and spatial locality of access leads to faster eviction of cache elements and as a result will lower the number of cache hits and increase cache maintenance.

Cache Performance Characteristics

The main performance characteristic of a cache is a hit/miss ratio. The hit/miss ratio is calculated as number of cache hits divided by number of cache misses. The hit/miss ratio is calculated using hit and miss counters accumulated over a period of time. A high hit/miss ratio means that a cache performs well. A low hit/miss ratio means that the cache is applied to data that should not be cached. Also, the low hit/miss ratio may mean that a cache is too small to capture temporal locality of data access.

Cache Eviction Policy

A cache eviction policy is an algorithm according to which an existing element is removed from a cache when a new element is added. The eviction policy is applied to ensure that the size of the cache does not exceed a maximum size. Least Recently Used (LRU) is one of the most popular among a number of eviction policies. LRU earned its popularity for being the best in capturing temporal and spatial locality of data access.

A minor disadvantage or LRU is its sensitivity to a full scan. The sensitivity manifests itself in evicting accumulated frequently accessed cache elements when accessing data that does not satisfy the requirement of temporal locality. This disadvantage is minor because LRU recovers from full scans quickly.

A typical implementation of a cache with the LRU eviction policy consists of a map and a linked list. The map stores cached elements. The linked list keep tracks of the least recently used cache elements. When a cache element is updated, it is removed from the list and added to the top of the list. The new elements are added to the top of the list as well. If the cache grows bigger than its maximum size, an element is removed from the bottom of the list and from the map. This way the least recently used elements are evicted first.

Simple LRU Cache in Ten Lines

Java 5 added a class java.util.LinkedHashMap. The main goal of this class is to provide the key, value and entry iteration that are consistent with an order of entry. In addition, LinkedHashMap includes a provision for implementing a simple LRU cache. Below is an implementation of a simple LRU cache that uses only 10 lines of code:

import java.util.Map;
import java.util.LinkedHashMap;


public final class SimpleLRUCache extends LinkedHashMap{
private int maxSize;
public SimpleLRUCache(final int maxSize) {
super(1, 0.75f, true);
this.maxSize = maxSize;
}
protected boolean removeEldestEntry(final Map.Entry eldest) {
return size() > maxSize;
}
}

While this simple cache does evict least recently used elements, it is missing important features that a cache needs to have in order to be usable in a real application. Please see section Caching Products for Java for a detailed discussion.

AttachmentSize
hybrid_cache.gif10.44 KB
level_2_cache.gif9.82 KB
application_cache.gif10.44 KB
Published at DZone with permission of its author, Slava Imeshev.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Alex Miller replied on Thu, 2008/07/17 - 3:40pm

Your SimpleLRUCache is not LRU.  The constructor needs to call the special LinkedHashMap constructor that takes a boolean arg (set to true for "last access order") instead of by insertion order.  As is, this is really a Least Recently Inserted cache.  Which might also be useful, but isn't LRU. 

François Ostyn replied on Thu, 2008/07/17 - 4:00pm

Hello,

Congratulations for your article.
Manage an "in memory" cache in JVM is a good way to improve performances.
Personnally, I've used this method for a critical project in my last company and results were excellents.
(fyi, it was a business web-site with 30K users...).
The "in memory" cache in JVM is very good for a small application.
To replicate caches, I use generally JMS (with OpenMQ)...
Actually, I'm testing memcached (an other free cache server) used by LinkedIn for example.
If you use hibernate (or not), I advise to use EhCache, a very good product;)

This is very intersting subject  (and JAVA applications tuning in general) and deserving of an entiere book...

Cheers
François OSTYN
J2EE Architect

Slava Imeshev replied on Thu, 2008/07/17 - 5:38pm in response to: Alex Miller

Alex,

[quote=puredanger]Your SimpleLRUCache is not LRU. The constructor needs to call the special LinkedHashMap constructor that takes a boolean arg (set to true for "last access order") instead of by insertion order. As is, this is really a Least Recently Inserted cache. Which might also be useful, but isn't LRU. [/quote]

 

Yes, this is a bug. Thanks for pointing to this, it has been fixed.

 

Slava

 

Alex Miller replied on Thu, 2008/07/17 - 8:00pm in response to: Slava Imeshev

Yep, that fixed it.  Although you presized the map to 1, which probably isn't big enough. :)  The default for LinkedHashMap is 16. 

Also, I should mention that Terracotta provides an easy way to distribute many of these open-source caches across multiple JVMs. 

Slava Imeshev replied on Thu, 2008/07/17 - 8:24pm in response to: Alex Miller

Alex,

The second and the last article in the series will cover dsitributed caching and data grids :)

Regards,

Slava Imeshev

Kode Ninja replied on Fri, 2008/07/18 - 5:18am in response to: Slava Imeshev

How about generifying your cache interface:

public interface Cache<K, V> {   
V get(final K key);
V put(final K key, final V value);
}

That's a type-safe cache interface!

Slava Imeshev replied on Fri, 2008/07/18 - 6:28am

 

Yes, that would definitely make sense. Strongly typed interfaces is a way to go, no doubt about it.

Unfortunatelly, there is a lot of shops still using 1.4, so us forced to support is did affect my thinking when writing that piece. Not sure if this counts as an excuse :-)

 

Regards,

 

Slava Imeshev

François Ostyn replied on Fri, 2008/07/18 - 6:47am in response to: Slava Imeshev

Excellent ;)
And you can speak about cacheonix... your "baby" !
Thanks
François OSTYN

Dmitry Namiot replied on Fri, 2008/07/18 - 6:48am

for LRU cache right in your JSP (or Coldfusion) applications you can use this component: LRU taglib

Alex(JAlexoid) ... replied on Sun, 2008/07/20 - 7:30pm in response to: Alex Miller

[quote=Alex] As is, this is really a Least Recently Inserted cache[/quote]

Last time I checked  "Least Recently Inserted" is called FIFO eviction algorithm based cache or FIFO cache.

Slava Imeshev replied on Sun, 2008/07/20 - 8:23pm in response to: Alex(JAlexoid) Panzin

[quote=jalexoid]

[quote=Alex] As is, this is really a Least Recently Inserted cache[/quote]

Last time I checked "Least Recently Inserted" is called FIFO eviction algorithm based cache or FIFO cache.

[/quote]

 

In case of FIFO eviction cache elements do not change there position and are evicted in order they are added. So, "Least Recently Inserted" is not FIFO.

 

Regards,

Slava Imeshev

 

 

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.