Creating your own Cache with LRU Algorithm in Java
Tags: java, cache
Published: 2023-10-10 13:18:28

The LRU caching scheme is to remove the least recently used frame when the cache is full and a new page is referenced which is not there in cache. Please see the Galvin book for more details.
This class defines a simple cache entry for the cache. A cache entry holds cached object along with some metadata attributes. These metadata attributes assist in managing the cache.
These cache entries are not serializable and thus these are not cluster aware. 

> This is a simple hash map based cache with LRU cleanup algorithm.

`CacheEntry.java`

```java
package com.dapinder.example.own.cache;

public class CacheEntry
{
 //the object that is saved in this cache entry
 private K cachedObject;

 //the time when the cached object was accessed or modified last time.
 private long lastAccessTime;

 /**
  * This returns the object stored in a cached entry.
  * 
  * @return the cachedObject
  */
 public K getCachedObject()
 {
  lastAccessTime = System.currentTimeMillis();
  return cachedObject;
 }

 /**
  * This sets an object into the cache entry
  * 
  * @param cachedObject
  *           the cachedObject to set
  */
 public void setCachedObject(final K cachedObject)
 {
  this.cachedObject = cachedObject;
  lastAccessTime = System.currentTimeMillis();
 }

 /**
  * Returns the time when this object was last accessed.
  * 
  * @return the lastAccessTime
  */
 public long getLastAccessTime()
 {
  return lastAccessTime;
 }


 @Override
 public int hashCode()
 {
  final int prime = 31;
  int result = 1;
  result = prime * result + ((cachedObject == null) ? 0 : cachedObject.hashCode());
  result = prime * result + (int) (lastAccessTime ^ (lastAccessTime >>> 32));
  return result;
 }


 @Override
 public boolean equals(final Object obj)
 {
  if (this == obj)
  {
   return true;
  }
  if (obj == null)
  {
   return false;
  }
  if (getClass() != obj.getClass())
  {
   return false;
  }
  final CacheEntry other = (CacheEntry) obj;
  if (cachedObject == null)
  {
   if (other.cachedObject != null)
   {
    return false;
   }
  }
  else if (!cachedObject.equals(other.cachedObject))
  {
   return false;
  }
  if (lastAccessTime != other.lastAccessTime)
  {
   return false;
  }
  return true;
 }

 @Override
 public String toString()
 {
  return "CacheEntry [cachedObject=" + cachedObject + ", lastAccessTime=" + lastAccessTime + "]";
 }
}
```

`CacheManager.java`

This manages a cache.

```java
import java.util.Collection;

public interface CacheManager {
 /**
  * Returns a cached item by key. If no cached item by key is found, returns
  * null.
  * 
  * @param key
  *            unique key for the cached item. This key is case sensitive.
  * @return the cached object; Null if key not found
  * 
  * @exception NullPointerException
  *                if key passed is null or empty.
  */
 K getCachedObject(String key);

  /**
  * Adds an item to the cache. If the key already exists, it updates the
  * cached object with the new item.
  * 
  * @param key
  *            unique key for the cached item. The key is case sensitive.
  * @param objectToCache
  *            the object to cache
  * 
  * @exception NullPointerException
  *                if key passed is null or empty.
  */
 void addObjectToCache(String key, K objectToCache);

  /**
  * Returns the keys of all cached objects.
  */
 Collection getAllKeys();

}
```

`CacheManagerImpl.java`

This is an implementation of CacheManager. Ideally this class should be used through Spring beans. This is a simple hash map based cache with LRU cleanup algorithm.

```java
package com.dapinder.example.own.cache;

import java.util.Collection;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Timer;
import java.util.TimerTask;
import java.util.concurrent.ConcurrentHashMap;

import org.apache.commons.lang.StringUtils;
import org.apache.log4j.Logger;

/**
 * This is an implementation of CacheManager.
 * This is a simple hash map based cache with LRU cleanup
 * algorithm.
 * 
 * @author Dapinder Singh
 * 
 * @see com.dapinder.example.own.cache.CacheManager
 * @see com.dapinder.example.own.cache.CacheEntry
 */

public class CacheManagerImpl implements CacheManager {
    /** Logger for this class and subclasses */
    private final Logger        logger = Logger.getLogger(this.getClass());

    // The map to hold cached objects
    private Map> cache;

    // the interval (in milliseconds) after which cache refresh task should run.
    private int   refreshTimeInterval;

    // the maximum number of entries in cache
    private int   maxCacheEntries;

    // the maximum time (in milliseconds) of inactivity for which an object will
    // remain in cache
    private int   maxHoldTime;

    // the name of the cache
    private String       cacheName;

 
 @Override
 public void addObjectToCache(final String key, final K objectToCache) {
 if (StringUtils.isEmpty(key)) {
     throw new NullPointerException("Key provided for adding the item to the cache is null.");
 }

 // create Cache entry
 CacheEntry entry = cache.get(key);
 if (null == entry) {
     entry = new CacheEntry();
 }
 entry.setCachedObject(objectToCache);

 // Add entry to the cache
 cache.put(key, entry);
}

 
 @Override
 public K getCachedObject(final String key) {
 if (StringUtils.isEmpty(key)) {
     throw new NullPointerException("Key for fetching the item from cache is null.");
 }
 final CacheEntry cacheEntry = cache.get(key);
 if (null == cacheEntry) {
     return null;
 }

 return cacheEntry.getCachedObject();
}

    /**
     * Sets the interval between the two consecutive refresh tasks for this
     * cache.
     * 
     * @param refreshTimeInterval
     *            the refreshTimeInterval to set
     */
    public void setRefreshTimeInterval(final int refreshTimeInterval) {
 this.refreshTimeInterval = refreshTimeInterval;
    }

    /**
     * Sets the minimum count of objects that will trigger the cache clean up.
     * 
     * @param maxCacheEntries
     *            the maxCacheEntries to set
     */
    public void setMaxCacheEntries(final int maxCacheEntries) {
 this.maxCacheEntries = maxCacheEntries;
    }

    /**
     * Sets the maximum time of inactivity for which an object will remain in
     * cache.
     * 
     * @param maxHoldTime
     *            the maxHoldTime to set
     */
    public void setMaxHoldTime(final int maxHoldTime) {
 this.maxHoldTime = maxHoldTime;
    }

    /**
     * Sets the name of the cache. This is solely from the perspective of
     * logging.
     * 
     * @param cacheName
     *            the cacheName to set
     */
    public void setCacheName(final String cacheName) {
 this.cacheName = cacheName;
    }


@Override
public int hashCode() {
 final int prime = 31;
 int result = 1;
 result = prime * result + ((cache == null) ? 0 : cache.hashCode());
 result = prime * result + ((cacheName == null) ? 0 : cacheName.hashCode());
 result = prime * result + maxCacheEntries;
 result = prime * result + maxHoldTime;
 result = prime * result + refreshTimeInterval;
 return result;
    }


@Override
public boolean equals(final Object obj) {
 if (this == obj) {
     return true;
 }
 if (obj == null) {
     return false;
 }
 if (getClass() != obj.getClass()) {
     return false;
 }
 final CacheManagerImpl other = (CacheManagerImpl) obj;
 if (cache == null) {
     if (other.cache != null) {
  return false;
     }
 }
 else if (!cache.equals(other.cache)) {
     return false;
 }
 if (cacheName == null) {
     if (other.cacheName != null) {
  return false;
     }
 }
 else if (!cacheName.equals(other.cacheName)) {
     return false;
 }
 if (maxCacheEntries != other.maxCacheEntries) {
     return false;
 }
 if (maxHoldTime != other.maxHoldTime) {
     return false;
 }
 if (refreshTimeInterval != other.refreshTimeInterval) {
     return false;
 }
 return true;
}


@Override
public String toString() {
 return "CacheManagerImpl [cache=" + cache + ", cacheName=" + cacheName + ", maxCacheEntries=" + maxCacheEntries
  + ", maxHoldTime=" + maxHoldTime + ", refreshTimeInterval=" + refreshTimeInterval + "]";
}

    /**
     * This method initializes the CacheManager. Specifically, this instantiates
     * the cache and sets up the refresh process for the cache.
     */
    public void initialize() {
     // instantiate the cache
     instantiateCache();
     // setup the refresh Process
     setRefreshProcess();
    }

    /**
     * This instantiate the cache. The cache is a sorted cache based on
     */
    private void instantiateCache() {
      cache = new ConcurrentHashMap>();

    }
    
    /**
     * This method sets the refresh process for the cache.
     */
    private void setRefreshProcess() {
 final TimerTask refreshTask = new RefreshTask();

 final Timer refreshTimer = new Timer();
 refreshTimer.scheduleAtFixedRate(refreshTask, 0, refreshTimeInterval);
    }

    /**
     * This defines the process of refreshing the cache. The cache refreshing
     * policy is simple LRU. However, cache is not cleaned, it it has not
     * attained its optimum size.
     */
    private void cleanCache() {
 // cache must be larger than optimum size to be cleaned.
 if (!isCacheLargerThanOptimumSize()) {
     return;
 }

 // remove all old objects
 removeOldObjects();
    }

    /**
     * It finds all the cacheEntries that are not used for the max hold time and
     * removes those objects.
     */
    private void removeOldObjects() {
 int removedItemCount = 0;
 for (final Entry> mapEntry : cache.entrySet()) {
     if (maxHoldTime <= mapEntry.getValue().getLastAccessTime()) {
  cache.remove(mapEntry.getKey());
  removedItemCount++;
     }
 }

 if (logger.isInfoEnabled()) {
     logger.info(removedItemCount + "items removed from " + cacheName);
 }
}

    /**
     * Checks if the size of the cache is larger than optimum cache size
     * @return
     */
    private boolean isCacheLargerThanOptimumSize() {
      return maxCacheEntries < cache.size();
    }

  /**
  * This defines the cache cleanup task.
  */
  private final class RefreshTask extends TimerTask {

 /**
  * (non-Javadoc)
  * @see java.util.TimerTask#run()
  */
 @Override
 public void run() {
     cleanCache();
 }
}

/**
* (non-Javadoc)
* @com.dapinder.example.own.cache.CacheManager#getAllKeys()
*/
@Override
public Collection getAllKeys() {
 return cache.keySet();
}
}
```