Write a concurrent LRU Cache using ReadWriteLock to allow parallel reads

 

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/cache

This LRUCache is implemented using ReadWriteLock allowing parallel reads where as only a single write can happen at a time. But caches are meant for read with less write and this approach would help in parallel reads for small scale of data.

This approach has a major disadvantage with respect to time taken for searching an entry if the scale of data to be retained is huge. This is because the ConcurrentLinkedQueue needs to be scanned to re-add after picking up the data every time. For large scale data it is better to use the synchronized LinkedHashMap approach.

package com.test.algorithm.cache;

import java.util.Map;
import java.util.Queue;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class LRUCacheWithReadWriteLock<K, V> {

    private final int limit;
    private final Map<K, V> internalCache;
    private final Queue<K> trackingQueue;

    private final ReadWriteLock readWriteLock = new ReentrantReadWriteLock();

    public LRUCacheWithReadWriteLock(int limit){
        internalCache = new ConcurrentHashMap<>();
        trackingQueue = new ConcurrentLinkedQueue<>();
        this.limit = limit;
    }

    public V get(K key) {
        this.readWriteLock.readLock().lock();
        try {
            V value = internalCache.get(key);
            if (value != null) {
                if (trackingQueue.remove(key)) {
                    trackingQueue.add(key);
                }
            }
            return value;
        } finally {
            this.readWriteLock.readLock().unlock();
        }
    }

    public void put(K key, V value) {
        this.readWriteLock.writeLock();
        try {
            if (internalCache.containsKey(key)) {
                trackingQueue.remove(key);
            }
            if (trackingQueue.size() == limit) {
                K expiredKey = trackingQueue.poll();
                internalCache.remove(expiredKey);
            }
            internalCache.put(key, value);
            trackingQueue.add(key);
        } finally {
            this.readWriteLock.writeLock().unlock();
        }
    }

    public static void main(String arg[]){
        LRUCacheWithReadWriteLock<Integer, String> lruCache = new LRUCacheWithReadWriteLock<>(4);

        lruCache.put(1, "Object1");
        lruCache.put(2, "Object2");
        lruCache.put(3, "Object3");
        lruCache.get(1);
        lruCache.put(4, "Object4");
        System.out.println(lruCache);
        lruCache.put(5, "Object5");
        lruCache.get(3);
        lruCache.put(6, "Object6");
        System.out.println(lruCache);
        lruCache.get(4);
        lruCache.put(7, "Object7");
        lruCache.put(8, "Object8");
        System.out.println(lruCache);
    }

    @Override
    public String toString() {
        return "LRUCacheWithReadWriteLock{" +
                "internalCache=" + internalCache +
                '}';
    }
}

Write a concurrent LRU Cache using LinkedHashMap

 

github: https://github.com/prasune/Algorithms/tree/master/src/main/java/com/test/algorithm/cache

For handling concurrency, we will have to synchronize the methods of LinkedHashMap being used as LRU Cache.

For better performance, LRU Cache can be implemented using ReadWriteLock, ConcurrentLinkedQueue and a ConcurrentHashMap - refer the implementation

package com.test.algorithm.cache;

import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCacheWithLinkedHashMap<K, V> {

    private final Map<K, V> internalCache;

    public LRUCacheWithLinkedHashMap(int limit){
        internalCache = Collections.synchronizedMap(new LinkedHashMap<K, V>(limit, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > limit;
            }
        });
    }

    public V get(K key) {
        return internalCache.get(key);
    }

    public void put(K key, V value) {
        internalCache.put(key, value);
    }

    public V remove(K key) {
        return internalCache.remove(key);
    }

    public static void main(String arg[]){
        LRUCacheWithLinkedHashMap<Integer, String> lruCache = new LRUCacheWithLinkedHashMap<>(4);

        lruCache.put(1, "Object1");
        lruCache.put(2, "Object2");
        lruCache.put(3, "Object3");
        lruCache.get(1);
        lruCache.put(4, "Object4");
        System.out.println(lruCache);
        lruCache.put(5, "Object5");
        lruCache.get(3);
        lruCache.put(6, "Object6");
        System.out.println(lruCache);
        lruCache.get(4);
        lruCache.put(7, "Object7");
        lruCache.put(8, "Object8");
        System.out.println(lruCache);
    }

    @Override
    public String toString() {
        return "LRUCacheWithLinkedHashMap{" +
                "internalCache=" + internalCache +
                '}';
    }
}

Java 5 - ReadWriteLock for better performance - ReentrantReadWriteLock and StampedLock

ReadWriteLock was introduced in Java 5 in the form of ReentrantReadWriteLock. A readWriteLock improves performance significantly in a multi-threaded environment when a resource is read more often than it is written.

The concept is simple, multiple threads can do read simultaneously and does not need to be blocked on each other, but if a write operation is going on all the subsequent write/read locks need to wait. A write lock will also wait for already acquired read locks before it gains the exclusive lock on the resource.

A typical use case of ReadWriteLock comes while maintaining a cache that needs to be updated when a new value gets added to the system.

An example cache managed by ReadWriteLock is as follows:

package com.prasune.test.concurrent; import java.util.HashMap; import java.util.Map; import java.util.concurrent.locks.ReentrantReadWriteLock; public class CachedDataManager {     private static Map<String, Object> cachedData = new HashMap<>();     /**      * Read/write lock to manage cache read/write operations.      */     private final ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();     /**      * Singleton instance      */     private static CachedDataManager instance = new CachedDataManager();     /**      * private constructor to make class singleton      */     private CachedDataManager() {     }         public CachedDataManager getInstance() {         return instance;     }     /**      * Fetch cache data using key      * @param key      * @return      */     public Object getCachedData(String key) {         Object data = null;         try {             readWriteLock.readLock().lock();             data = cachedData.get(key);                    } finally {             readWriteLock.readLock().unlock();         }         return data;     }         /**      * Update cache  by adding new entry      * @param key      * @param data      */     public void addToCache(String key, Object data) {         try {             readWriteLock.writeLock().lock();             cachedData.put(key, data);                    } finally {             readWriteLock.writeLock().unlock();         }     } }

ReentrantReadWriteLock performs better than the traditional lock mechanism, but it is not fast enough and is too slow at times. So, Java 8 introduced a new ReadWriteLock in the form of StampedLock which uses new set of algorithms and memory management introduced in Java 8.

StampedLock uses a stamp to identify the lock which helps in better performance in managing the read/write lock.

Let us modify our program to use StampedLock:

package com.prasune.test.concurrent; import java.util.HashMap; import java.util.Map; import java.util.concurrent.locks.StampedLock; public class CachedDataManager {     private static Map<String, Object> cachedData = new HashMap<>();     /**      * Read/write lock to manage cache read/write operations.      */     private final StampedLock readWriteLock = new StampedLock();     /**      * Singleton instance      */     private static CachedDataManager instance = new CachedDataManager();     /**      * private constructor to make class singleton      */     private CachedDataManager() {     }         public CachedDataManager getInstance() {         return instance;     }     /**      * Fetch cache data using key      * @param key      * @return      */     public Object getCachedData(String key) {         Object data = null;         Long stamp = 0L;         try {             stamp = readWriteLock.readLock();             data = cachedData.get(key);                    } finally {             readWriteLock.unlockRead(stamp);         }         return data;     }         /**      * Update cache  by adding new entry      * @param key      * @param data      */     public void addToCache(String key, Object data) {         Long stamp = 0L;         try {             stamp = readWriteLock.writeLock();             cachedData.put(key, data);                    } finally {             readWriteLock.unlockWrite(stamp);         }     } }