LRU Cache Implementation In Java

Introduction

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.

If your application is using any kind of caching mechanism and when you need a datum then first you 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.

Related Posts:

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.

Prerequisites

Java 1.7+, Maven 3.6.3+

Project Setup

You can create a maven based project in your favorite IDE or tool. The following pom.xml file can be used for this example.

<?xml version="1.0" encoding="UTF-8"?>

<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>java-lru-cache</artifactId>
	<version>0.0.1-SNAPSHOT</version>

	<properties>
		<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
		<maven.compiler.source>11</maven.compiler.source>
		<maven.compiler.target>11</maven.compiler.target>
	</properties>

	<dependencies></dependencies>

	<build>
		<plugins>
			<plugin>
				<groupId>org.apache.maven.plugins</groupId>
				<artifactId>maven-compiler-plugin</artifactId>
				<version>3.8.1</version>
			</plugin>
		</plugins>
	</build>
</project>

LRU Cache Implementation

Here is the Java code that shows how to implement LRU cache.

public class LruCache<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 MILLISECONDS:
				cal.add(Calendar.MILLISECOND, expireTime);
				break;
			case SECONDS:
				cal.add(Calendar.SECOND, expireTime);
				break;
			case MINUTES:
				cal.add(Calendar.MINUTE, expireTime);
				break;
			case HOURS:
				cal.add(Calendar.HOUR, expireTime);
				break;
			default:
				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 LruCache(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);
	}

}

LRU Cache Testing

Here I am creating a simple main class that will test the above LRU cache.

public class App {

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

}

Running the above main class will produce the following output:

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

It will periodically check the objects in the cache and expires accordingly.

Source Code

Download

Leave a Reply

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