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.

19 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
  3. Excellent and very exciting site. Love to watch. Keep Rocking. pool builders horseshoe bay tx

    ReplyDelete
  4. Carpet cleaning is important in helping to maintain good health in your home. Here are some commonly asked questions with answers to help you.
    https://www.jhos.com.au/commercial-cleaning.php

    ReplyDelete
  5. Your articles are inventive. I am looking forward to reading the plethora of articles that you have linked here. Thumbs up! Horseshoe Bay custom homes

    ReplyDelete
  6. Attend The Data Analytics Course in Bangalore From ExcelR. Practical Data Analytics Course in Bangalore Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Data Analytics Course in Bangalore.
    ExcelR Data Analytics Course in Bangalore

    ReplyDelete
  7. Excellent Blog! I would like to thank for the efforts you have made in writing this post. I am hoping the same best work from you in the future as well. I wanted to thank you for this websites! Thanks for sharing. Great websites!
    ExcelR data science course in mumbai

    ReplyDelete
  8. I feel very grateful that I read this. It is very helpful and very informative and I really learned a lot from it.
    ExcelR data analytics courses

    ReplyDelete
  9. After reading your article I was amazed. I know that you explain it very well. And I hope that other readers will also experience how I feel after reading your article.
    data science course in mumbai

    ReplyDelete
  10. I feel very grateful that I read this. It is very helpful and very informative and I really learned a lot from it.
    artificial intelligence training in hyderabad
    business analytics course
    data analytics course

    ReplyDelete
  11. This is a wonderful article. I really enjoyed reading this article. Thanks for sharing such detailed information.
    Data Science Course
    Data Science Course in Marathahalli

    ReplyDelete
  12. This is a wonderful article, Given so much info in it, Thanks for sharing. CodeGnan offers courses in new technologies and makes sure students understand the flow of work from each and every perspective in a Real-Time environmen python training in vijayawada. , data scince training in vijayawada . , java training in vijayawada. ,

    ReplyDelete
  13. wonderful article. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article resolved my all queries.
    Data science Interview Questions
    Data Science Course

    ReplyDelete
  14. Thanks for Sharing This Article.It is very so much valuable content. I hope these Commenting lists will help to my website
    servicenow online training
    best servicenow online training
    top servicenow online training

    ReplyDelete
  15. wonderful article. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article resolved my all queries. keep it up.
    data analytics course in Bangalore

    ReplyDelete
  16. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article inspired me to read more. keep it up.
    Correlation vs Covariance
    Simple linear regression

    ReplyDelete
  17. Such a very useful article. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article.learn 360digitmg data science coursesin India

    ReplyDelete
  18. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article inspired me to read more. keep it up.
    Correlation vs Covariance
    Simple linear regression
    data science interview questions

    ReplyDelete