A cache is an amount of faster memory used to improve data access by storing portions of a data set the whole of which is slower to access. Sometimes the total data set are not actually stored at all; instead, each data item is calculated as necessary, in which case the cache stores results from the calculations.

When we need a datum then first we check the cache if it contains the required datum. If it exists, the datum is used from the cache, without having to access the main data store. This is known as a ‘cache hit’. If the datum is not found in the cache, it is transferred from the main data store; this is known as a ‘cache miss’. When the cache fills up, items are ejected from the cache to make space for new items.

LRU is known as Least Recently Used where items are added to the cache as they are accessed; when the cache is full, the least recently used item is ejected. This type of cache is typically implemented as a linked list, so that an item in cache, when it is accessed again, can be moved back up to the head of the queue; items are ejected from the tail of the queue. Cache access overhead is again constant time. This algorithm is simple and fast, and it has a significant advantage over FIFO in being able to adapt somewhat to the data access pattern; frequently used items are less likely to be ejected from the cache. The main disadvantage is that it can still get filled up with items that are unlikely to be re-accessed soon; in particular, it can become useless in the face of scans over a larger number of items than fit in the cache. Nonetheless, this is by far the most frequently used caching algorithm.

This tutorial will show you how we can implement LRU cache using Java. For this tutorial we will create a standalone maven project in Eclipse.

If you already have an idea on how to create a maven project in Eclipse will be great otherwise I will tell you here how to create a maven project in Eclipse.

Sometimes we need to retrieve one or few records from the database. We can retrieve one or multiple records from database with the help of JdbcTemplate.

Prerequisites

The following configurations are required in order to run the application

Eclipse Juno
JDK 1.7
Have maven installed and configured
Spring dependencies in pom.xml

Now we will see the below steps how to create a maven based spring project in Eclipse

Step 1. Create a standalone maven project in Eclipse

Go to File -> New -> Other. On popup window under Maven select Maven Project. Then click on Next. Select the workspace location – either default or browse the location. Click on Next. Now in next window select the row as highlighted from the below list of archtypes and click on Next button.

maven-arctype-quickstart

Now enter the required fields (Group Id, Artifact Id) as shown below

Group Id : com.roytuts
Artifact Id : roytuts

Step 2. Modify the pom.xml file as shown below.

<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>com.roytuts</groupId>
    <artifactId>roytuts</artifactId>
    <version>0.0.1-SNAPSHOT</version>
    <packaging>jar</packaging>

    <name>roytuts</name>
    <url>http://maven.apache.org</url>

    <properties>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
        <jdk.version>1.7</jdk.version>
        <commons.version>3.0</commons.version>
        <junit.version>4.11</junit.version>
    </properties>

    <dependencies>
        <dependency>
            <groupId>commons-collections</groupId>
            <artifactId>commons-collections</artifactId>
            <version>${commons.version}</version>
        </dependency>
        <dependency>
            <groupId>junit</groupId>
            <artifactId>junit</artifactId>
            <version>${junit.version}</version>
            <scope>test</scope>
        </dependency>
    </dependencies>

    <build>
        <plugins>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-compiler-plugin</artifactId>
                <configuration>
                    <source>${jdk.version}</source>
                    <target>${jdk.version}</target>
                </configuration>
            </plugin>
        </plugins>
    </build>
</project>

Step 3. If you see JRE System Library[J2SE-1.4] then change the version by below process

Do right-click on the project and go to Build -> Configure build path, under Libraries tab click on JRE System Library[J2SE-1.4], click on Edit button and select the appropriate jdk 1.7 from the next window. Click on Finish then Ok.

Step 4. Create LRU cache cache implementation class

package com.roytuts.cache.lru;

import java.util.ArrayList;
import java.util.Calendar;
import java.util.Date;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class LRUCacheDoublyLinkedList<K, V> {

  //Capacity of LRUCache
  private final int capacity = 50;
  //Interval for testing existence of an object
  private final int sleepTime = 5000;
  //Current size of LRUCache
  private int currentSize;
  //Cache expire time
  private int expireTime;
  //Time unit like Seconds, Minutes, Hours etc.
  private TimeUnit timeUnit;

  //Node of DoublyLinkedList
  class DoublyLinkedListNode {
    DoublyLinkedListNode prev;
    DoublyLinkedListNode next;
    Date dateOfExpiration;
    K key;
    V value;

    public DoublyLinkedListNode(K key, V value) {
      this.key = key;
      this.value = value;
      dateOfExpiration = new Date();
      Calendar cal = Calendar.getInstance();
      cal.setTime(dateOfExpiration);
      switch (timeUnit) {
      case MILLISECOND:
        cal.add(Calendar.MILLISECOND, expireTime);
        break;
      case SECOND:
        cal.add(Calendar.SECOND, expireTime);
        break;
      case MINUTE:
        cal.add(Calendar.MINUTE, expireTime);
        break;
      case HOUR:
        cal.add(Calendar.HOUR, expireTime);
        break;
      }
      dateOfExpiration = cal.getTime();
    }

    //check whether an object is expired or not
    public boolean isExpired() {
      if (dateOfExpiration != null) {
        if (dateOfExpiration.before(new Date())) {
          return true;
        } else {
          return false;
        }
      } else {
        return false;
      }
    }
  }

  //First node of DoublyLinkedList
  private DoublyLinkedListNode start;
  //Last node of DoublyLinkedList
  private DoublyLinkedListNode end;
  //Map for key and DoublyLinkedList node mapping
  private HashMap<K, DoublyLinkedListNode> nodeMap;

  public LRUCacheDoublyLinkedList(int expireTime, TimeUnit timeUnit) {
    currentSize = 0;
    this.expireTime = expireTime;
    this.timeUnit = timeUnit;
    nodeMap = new HashMap<K, DoublyLinkedListNode>();
    Thread threadCleaner = new Thread(new Runnable() {
      @SuppressWarnings({ "rawtypes", "unchecked" })
      public void run() {
        List<K> deleteKey = null;
        try {
          while (true) {
            System.out.println("CacheCleaner scanning for expired objects...");
            synchronized (nodeMap) {
              deleteKey = new ArrayList<K>((nodeMap.size() / 2) + 1);
              Set keySet = nodeMap.keySet();
              Iterator keys = keySet.iterator();
              while (keys.hasNext()) {
                K key = (K) keys.next();
                DoublyLinkedListNode value = (DoublyLinkedListNode) nodeMap.get(key);
                if (value.isExpired()) {
                  deleteKey.add(key);
                  System.out.println("CacheCleaner Running. Found an expired object in the Cache : " + value.value);
                }
              }
            }
            for (K key : deleteKey) {
              synchronized (nodeMap) {
                System.out.println("CacheCleaner removed an expired object from the Cache : " + nodeMap.get(key).value);
                nodeMap.remove(key);
              }
              Thread.yield();
            }
            Thread.sleep(sleepTime);
          }
        } catch (Exception e) {
          e.printStackTrace();
        }
      }
    });
    threadCleaner.setPriority(Thread.MIN_PRIORITY);
    threadCleaner.start();
  }

  //Add an item to LRUCache
  public void put(K key, V value) {
    synchronized (nodeMap) {
      if (nodeMap.containsKey(key)) {
        DoublyLinkedListNode node = nodeMap.get(key);
        node.value = value;
        bringItemToFront(node);
      } else {
        DoublyLinkedListNode nodeToInsert = new DoublyLinkedListNode(key, value);
        if (currentSize < capacity) {
          addItemToFront(nodeToInsert);
          currentSize++;
        } else {
          removeLastNode();
          addItemToFront(nodeToInsert);
        }
      }
    }
  }

  //Get an item from LRUCache
  public V get(K key) {
    synchronized (nodeMap) {
      if (nodeMap.containsKey(key)) {
        DoublyLinkedListNode node = nodeMap.get(key);
        bringItemToFront(node);
        return node.value;
      } else {
        return null;
      }
    }
  }

  //Remove last node from queue
  private void removeLastNode() {
    System.out.println("Capacity exceeded so removing oldest cache object " + end.value + " for adding the new object to the cache");
    nodeMap.remove(end.key);
    end = end.prev;
    if (end != null) {
      end.next = null;
    }
  }

  //Add node in front of queue
  private void addItemToFront(DoublyLinkedListNode node) {
    node.next = start;
    node.prev = null;
    if (start != null) {
      start.prev = node;
    }
    start = node;
    if (end == null) {
      end = node;
    }
    nodeMap.put(node.key, node);
  }

  //Reorder existing node to front of queue
  private void bringItemToFront(DoublyLinkedListNode node) {
    DoublyLinkedListNode prevNode = node.prev;
    DoublyLinkedListNode nextNode = node.next;
    if (prevNode != null) {
      prevNode.next = nextNode;
    } else {
      start = nextNode;
    }
    if (nextNode != null) {
      nextNode.prev = prevNode;
    } else {
      end = prevNode;
    }
    addItemToFront(node);
  }

}

Step 5. Create a test class for testing LRU cache

package com.roytuts.cache.lru;

public class LRUCacheDoublyLinkedListTest {

  public static void main(String[] args) {
    LRUCacheDoublyLinkedList<String, Integer> lru = new LRUCacheDoublyLinkedList<String, Integer>(5, TimeUnit.SECOND);
    for (int i = 1; i < 10; i++) {
      lru.put(String.valueOf(i), i * 2);
    }
  }

}

Step 6. Run the above class, you will see the output

CacheCleaner scanning for expired objects...
CacheCleaner scanning for expired objects...
CacheCleaner Running. Found an expired object in the Cache : 6
CacheCleaner Running. Found an expired object in the Cache : 4
CacheCleaner Running. Found an expired object in the Cache : 2
CacheCleaner Running. Found an expired object in the Cache : 14
CacheCleaner Running. Found an expired object in the Cache : 12
CacheCleaner Running. Found an expired object in the Cache : 10
CacheCleaner Running. Found an expired object in the Cache : 8
CacheCleaner Running. Found an expired object in the Cache : 18
CacheCleaner Running. Found an expired object in the Cache : 16
CacheCleaner removed an expired object from the Cache : 6
CacheCleaner removed an expired object from the Cache : 4
CacheCleaner removed an expired object from the Cache : 2
CacheCleaner removed an expired object from the Cache : 14
CacheCleaner removed an expired object from the Cache : 12
CacheCleaner removed an expired object from the Cache : 10
CacheCleaner removed an expired object from the Cache : 8
CacheCleaner removed an expired object from the Cache : 18
CacheCleaner removed an expired object from the Cache : 16
CacheCleaner scanning for expired objects...

That’s all. Thanks for your reading.

I am a professional Web developer, Enterprise Application developer, Software Engineer and Blogger. Connect me on Roy Tutorials Twitter Facebook  Google Plus Linkedin Or Email Me

Leave a Reply

Your email address will not be published. Required fields are marked *