Click here to Skip to main content
Click here to Skip to main content

Simple LRU Caching with Expiration

, 30 Oct 2005 CPOL
Rate this:
Please Sign up or sign in to vote.
LRU caching code small enough to paste directly into your application

Introduction

Caching is an extremely useful concept to improve performance. There are many commercial and open-source caching packages available for Java. These packages usually involve installing jars, editing config files, and hooking into framework (JNDI, logging, JDBC), etc. This is fine, but sometimes we just want a quick and simple solution - the kind of solution that involves only a couple of classes which we can insert directly into our own code; the kind of code that you could copy and paste right off of a Web page. That is what we present here.

First, we define a caching interface so that later on, if we change our mind, we can use a different caching strategy or hook in to a more sophisticated caching package.

public interface Cache<K extends Comparable, V> {
   V get(K obj);
   void put(K key, V obj);
   void put(K key, V obj, long validTime);
   void remove(K key);
   Pair[] getAll();
   int size();
}

This caching interface gives us the ability to assign a expiration time for the cached objects. This can be very useful for cases where we know the data we are caching will change over time but it is not critical that people always see the absolute latest data and some delay is acceptable. For example, if we are retrieving content from a database to display in a Web page, it is often not necessary that users see the absolute latest data every time. If we are getting 100 queries per second without caching, even if we were to only cache for one second we would reduce the number of queries by 100. Often caching for 5 to 15 minutes is more than acceptable. We have implemented the least recently used (LRU) algorithm for caching, which discards the least recently used items first. This requires keeping track of what was used when.

We have only one public supporting object to allow us to retrieve all of the cached objects from the cache.

public class Pair<K extends Comparable, V> implements Comparable<Pair> {
   public Pair(K key1, V value1) {
      this.key = key1;
      this.value = value1;
   }
   public K key;
   public V value;
   public boolean equals(Object obj) {
      if(obj instanceof Pair) {
         Pair p = (Pair)obj;
         return key.equals(p.key)&&value.equals(p.value);
      }
      return false;
   }
   @SuppressWarnings("unchecked")
   public int compareTo(Pair p) {
      int v = key.compareTo(p.key);
      if(v==0) {
         if(p.value instanceof Comparable) {
            return ((Comparable)value).compareTo(p.value);
         }
      }
      return v;
   }
   @Override
   public int hashCode() {
      return key.hashCode()^value.hashCode();
   }
   @Override
   public String toString() {
      return key+": "+value;
   }
}

Finally, the code for the implementation of the cache is:

public class LRUCache<K extends Comparable, V> implements Cache<K, V>,
      Serializable {
   private static final long serialVersionUID = 3674312987828041877L;
   Map<K, Item> m_map = Collections.synchronizedMap(new HashMap<K, Item>());
   Item m_start = new Item();
   Item m_end = new Item();
   int m_maxSize;
   Object m_listLock = new Object();
   static class Item {
      public Item(Comparable k, Object v, long e) {
         key = k;
         value = v;
         expires = e;
      }
      public Item() {}
      public Comparable key;
      public Object value;
      public long expires;
      public Item previous;
      public Item next;
   }
   void removeItem(Item item) {
      synchronized(m_listLock) {
         item.previous.next = item.next;
         item.next.previous = item.previous;
      }
   }
   void insertHead(Item item) {
      synchronized(m_listLock) {
         item.previous = m_start;
         item.next = m_start.next;
         m_start.next.previous = item;
         m_start.next = item;
      }
   }
   void moveToHead(Item item) {
      synchronized(m_listLock) {
         item.previous.next = item.next;
         item.next.previous = item.previous;
         item.previous = m_start;
         item.next = m_start.next;
         m_start.next.previous = item;
         m_start.next = item;
      }
   }
   public LRUCache(int maxObjects) {
      m_maxSize = maxObjects;
      m_start.next = m_end;
      m_end.previous = m_start;
   }
   @SuppressWarnings("unchecked")
   public Pair[] getAll() {
      Pair p[] = new Pair[m_maxSize];
      int count = 0;
      synchronized(m_listLock) {
         Item cur = m_start.next;
         while(cur!=m_end) {
            p[count] = new Pair(cur.key, cur.value);
            ++count;
            cur = cur.next;
         }
      }
      Pair np[] = new Pair[count];
      System.arraycopy(p, 0, np, 0, count);
      return np;
   }
   @SuppressWarnings("unchecked")
   public V get(K key) {
      Item cur = m_map.get(key);
      if(cur==null) {
         return null;
      }
      if(System.currentTimeMillis()>cur.expires) {
         m_map.remove(cur.key);
         removeItem(cur);
         return null;
      }
      if(cur!=m_start.next) {
         moveToHead(cur);
      }
      return (V)cur.value;
   }
   public void put(K key, V obj) {
      put(key, obj, -1);
   }
   public void put(K key, V value, long validTime) {
      Item cur = m_map.get(key);
      if(cur!=null) {
         cur.value = value;
         if(validTime>0) {
            cur.expires = System.currentTimeMillis()+validTime;
         }
         else {
            cur.expires = Long.MAX_VALUE;
         }
         moveToHead(cur);
         return;
      }
      if(m_map.size()>=m_maxSize) {
         cur = m_end.previous;
         m_map.remove(cur.key);
         removeItem(cur);
      }
      long expires=0;
      if(validTime>0) {
         expires = System.currentTimeMillis()+validTime;
      }
      else {
         expires = Long.MAX_VALUE;
      }
      Item item = new Item(key, value, expires);
      insertHead(item);
      m_map.put(key, item);
   }
   public void remove(K key) {
      Item cur = m_map.get(key);
      if(cur==null) {
         return;
      }
      m_map.remove(key);
      removeItem(cur);
   }
   public int size() {
      return m_map.size();
   }
}

The cache works essentially like a map except that you can pass along an optional expiration time. Create, store, use -- simple.

History

  • 30th October, 2005: Initial post

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Ian Schumacher
Web Developer
Canada Canada
Software developer for Simple Software.
 
Currently developing a Java client application that allows you to view and interact with real-time web metrics sent from your web server.

Comments and Discussions

 
Suggestionreally good article. PinmemberAmit Bose13-Aug-12 0:57 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.1411022.1 | Last Updated 30 Oct 2005
Article Copyright 2005 by Ian Schumacher
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid