Thursday, September 29, 2011

Creating a Custom LRU Cache in Java

Caching is an extremely useful concept to improve performance. There are many commercial and open-source caching packages available for Java. These packages need setting up the whole cache infrastructure in dev, qa, prod environments and then hooking it into the code. This is fine, but sometimes we just want a quick and simple solution - to address what we need.

In one of projects in past, we had a Gallery promotion every few days and under peak traffic, site started to melt because of read read timeouts. One option was to use cache tools like Memcached. But did we really need that? We quickly wrote a custom LRU cache that fits all the needs. The solution was well accepted and lives in production today.

Here I'll illustrate the construction of custom LRU cache. I used LinkedHashMap's accessOrder and removeEldestEntry capabilities to create the LRU feature of a cache.

// Used Generics for illustration. Static cannot be used with Generics.
// For real usage, make the cache to be static. This will make get, put everything as static.
// Also, the functions have to be synchronized, since we are deleting old elements and updating as per access order. Under multiple threads - it will lead to race condition.
public class LRUCache<K, V> {

 private final int CACHE_SIZE;
 private final int initialCapacity = 16;
 private final float loadFactor = 0.75F;

 public LRUCache(int size) {
  this.CACHE_SIZE = size;
 }

 // LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
 // accessOrder - to maintain in order of elements from least-recently accessed to most-recently. Invoking the put or get method results in an access.
 public LinkedHashMap<K, V> cache = new LinkedHashMap<K, V>(initialCapacity, loadFactor, true) {

  private static final long serialVersionUID = 1L;

  // The removeEldestEntry(Map.Entry) - is a method from LinkedHashMap, that should be overridden to impose a policy for removing OLD mappings automatically when new mappings are added to the map.
  // Returns true if this map should remove its eldest entry. This method is invoked by put and putAll after inserting a new entry into the map. 
  @Override
  protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
   boolean ifRemove = this.size() > CACHE_SIZE;
   return ifRemove;
  }
  
 };

 // Adds an entry to this cache. The new entry becomes the MRU (most recently used) entry. If an entry with the specified key already exists in the
 // cache, it is replaced by the new entry. If the cache is full, the LRU (least recently used) entry is removed from the cache.
 // it has to be synchronized, since we are deleting old elements and updating as per access order. Under multiple threads - it will be an issue.
 public synchronized void put(K key, V value) {
  if (value == null)
   return;
  else
   cache.put(key, value);
 }
 
 // Retrieves an entry from the cache. The retrieved entry becomes the MRU (most recently used) entry.
 public synchronized V get(K key) {
  return cache.get(key);
 }

 public synchronized void clear() {
  cache.clear();
 }
 
 
 // Test routine for the LRUCache class.
 public static void main(String[] args) {
  LRUCache<String, String> c = new LRUCache<String, String>(3);
  c.put("1", "one"); // 1
  c.put("2", "two"); // 2 1
  c.put("3", "three"); // 3 2 1
  c.put("4", "four"); // 4 3 2
  c.get("3");
  for (Map.Entry<String, String> e : c.cache.entrySet()) {
   System.out.println(e.getKey() + " : " + e.getValue());
  }
 }
}


Used Generics for illustration. Static cannot be used with Generics. For real usage, make the cache to be static. This will make get, put as static.

Also, the functions have to be synchronized, since we are deleting old elements and updating as per access order. Under multiple threads - it will lead to race condition.

3 comments:

  1. Interesting artcile , by the way I have also shared my experience as How substring method works in Java
    let me know how do you find it.

    ReplyDelete
  2. Hi ashish , nice implemetation of the article , but have one doubt

    public synchronized void clear() {
    cache.clear();
    }


    this is method is synchronized , because of i did not see any afrer clear or before clear "aferNodeAccess" type of calls in the in the linkedhasmap clear method , can u please help in understanding why the above is synchronized

    ReplyDelete