Threadsafe LRU Cache

Question

Trying to design a threadsafe lru cache using a reentrant lock. Currently I don't like the tryLock in a loop approach. Any inputs on making it more optimal in terms of concurrency?

    import java.util.ArrayDeque;
    import java.util.Deque;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.concurrent.locks.Lock;
    import java.util.concurrent.locks.ReentrantLock;
    
    class LRUNode {
        String key;
        String value;
        LRUNode(String key,String value){
            this.key  = key;
            this.value = value;
        }
    }
    public class LRU {
        Lock lock;
        Map<String,LRUNode> map;
        Deque<LRUNode> deque;
        int capacity;
        int size;
    
        LRU(int capacity) {
            this.size = 0;
            this.capacity = capacity;
            deque = new ArrayDeque<>();
            this.map = new HashMap<>();
            lock = new ReentrantLock();
        }
    
        public String get(String key){
    
            try {
                while (!lock.tryLock()) {
                    Thread.sleep(50);
                }
                if (map.containsKey(key)) {
                    //update deque
                    LRUNode lruNode = map.get(key);
                    System.out.println("Getting " + key + " from cache");
                    deque.remove(lruNode);
                    deque.offer(lruNode);
                    return lruNode.value;
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
            return null;
        }
    
        public void print(){
            System.out.println("----- cache contents -------");
            for(Map.Entry<String,LRUNode> entry : this.map.entrySet()){
                System.out.println(entry.getKey()+ " : "+ entry.getValue().value);
            }
            System.out.println("----------------------------");
        }
        public void put(String key, String value){
            try {
                while (!lock.tryLock()) {
                    Thread.sleep(50);
                }
                if (size == capacity) {
                    LRUNode nodeToBeRemoved = deque.getFirst();
                    System.out.println("Evicting " + nodeToBeRemoved.key + " from cache");
                    map.remove(nodeToBeRemoved.key);
                    deque.removeFirst();
                    size--;
                }
                LRUNode lruNode = new LRUNode(key, value);
                map.put(key, lruNode);
                deque.offer(lruNode);
                System.out.println("Added " + key + " to cache");
                size++;
            }catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
        }
    
        public static void main(String[] args) {
            LRU lru = new LRU(3);
            lru.put("k1","v1");
            lru.put("k2","v2");
            lru.put("k3","v3");
    
            lru.print();
    
            lru.put("k4","v4");
            lru.put("k5","v5");
            lru.put("k6","v6");
            lru.put("k7","v7");
            lru.put("k8","v8");
            lru.put("k9","v9");
            lru.print();
        }
    }

Answer 1

Any inputs on making it more optimal in terms of concurrency?

This is specifically addressed in the Javadoc for LinkedHashMap:

If multiple threads access a linked hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be "wrapped" using the Collections.synchronizedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

I.e. if you do not already have a synchronized object that encloses the Map, they recommend wrapping the Map with Collections.synchronizedMap. Then you don't have to write any concurrent code of your own.

So, replace your

            LRU lru = new LRU(3);

with

Map<String, String> lru = Collections.synchronizedMap(new LinkedHashMap<String, String>(3) {

    protected final int LIMIT;

    public LRUCache(int capacity) {
        super(2 * capacity, .75, true);
        LIMIT = capacity;
    }

    @Override
    protected boolean removeEldestEntry() {
        return size() > LIMIT;
    }

});

You can then modify your print method to take a Map as an argument instead of operating on this.

This version

1. Reduces the amount of code that you have to write.
2. Provides you with all the advantages, including edge case handling and optimizations, of the native LinkedHashMap version of a least-recently-used cache.
3. Provides you with all the advantages, including edge case handling and optimizations, of the native concurrency wrapper for Map.

Now, it is certainly possible that your version is superior to this in some ways. If so, you should explain what your version gives that this version does not. The default should be to use the built-in versions until you find a reason to use something else.

Since you use a Map internally, you are going to get the default map behavior. One example of that is that when the third element is added, your version will exceed the load factor and double the initial capacity. This version goes ahead and does that immediately, so no overhead on the third put.

It is possible to come up with better implementations of a map, given that you don't need to resize. But you don't do that.

An ArrayDeque is a bad solution for a least-recently-used queue. It requires copying blocks of memory each time you remove from the middle. So the LinkedHashMap is probably superior here, as it uses a linked list. And of course, the map gives constant time accesses to any node while the linked list gives constant time removes and adds.

An alternative would be to make an array and maintain the links as indexes in the array. Then you wouldn't have to keep making and destroying the nodes. You'd just keep recycling the nodes in the array. You could even make it so that put would automatically write over the least-recently-used entry. This is a place where your version could be superior to LinkedHashMap.

Because your capacity is so small, you also might find a heap (PriorityQueue) to provide superior performance. Yes, it's logarithmic removes and adds rather than constant. But for a small size, it may be faster to maintain the heap than to manage the linked list (including the memory allocations).

Similarly, for a capacity of three, ditching the hash map and just doing a linear scan is sensible. But of course, you may simply have picked three as a small size so that it's easy to test the logic. Perhaps in practice, this would be much larger.

Answer 2

LRUNode is probably best located as a private static inner class of LRU. An LRU node shouldn't be visible outside the scope of the LRU cache it belongs to. Even better would be to change it to be a record instead of a class.

LRU is an algorithm. A cache which uses an LRU eviction strategy would probably be better named LruCache.

For readability reasons, it's preferable to use CamelCase even for abbreviations. LruNode instead of LRUNode, and Lru instead of LRU.

All the instance variables of LRU should be marked private They shouldn't be accessed directly from outside the LRU class.

size will default to zero, and doesn't need to be explicitly assigned.

dequeue, map, and lock can and should be assigned inline.

Of the instance variables, only size can change. The rest can be marked final to indicate they do not change after being assigned.

size doesn't actually need to be tracked. It will always equal both the size of the map and the size of the duque.

The LRU constructor being package-private scope is an odd choice. I would expect it to be public.

The use of whitespace is inconsistent, which makes the code harder to read.

Looping over lock.tryLock() until it is available is not necessary. Calling lock.lockInterruptibly() will cause the thread to sleep until the lock becomes available.

As mdfst13 notes, a linked list would be preferable to an array-backed list for performance reasons. On a small scale, their performance will be indistinguishable, but it's a better practice to use the "correct" data structure.

It would be preferable to use a logger such as java.util.logging.Logger instead of System.out.println to log messages. If those are debugging messages, they should be removed.

Comments like //update queue don't provide much information. Comments generally provide a "why", not a "what". Otherwise they go stale as the code changes out from underneath them.

Logging an InterruptedException isn't super helpful. That's not a failure, it's an indication that somebody asked the current thread to stop waiting for the cache to become available. Better would be to stop waiting on the lock and to re-trigger the interrupt status in case something else on the thread is blocking.

The print() method is conceptually wrong. A class shouldn't print itself. Instead, implement toString() to return a string representation of the class. The caller can decide what it wants to do with it. Maybe print, maybe log, maybe write to a file ..

Depending on the expected frequency of cache hits vs. misses, separate read and write locks might be more performant. That's probably too much to worry about in a project of this scope.

deque.removeFirst() returns the removed node. There's no need to call getFirst and then removeFirst. Just remove it from the queue before you remove it from the map.

As mdfst13 notes, using a LinkedHashMap instead of a map/list pairing is a reasonable alternative. If you, you'd want to extend LinkedHashMap and override removeEldestEntry.

Even though they're equivalent, for clarity offerLast would be preferable to offer, since this is a duque. Similarly removeFirstOccurrence vs remove.

The code doesn't check if an item being put is already in the cache. This can lead to differences between the map size and cache size. It needs to check and see if the key is already in the cache, and if so replace the value.

If you made all these changes, your code might look more like:

public final class LruCache {
    private final Lock lock = new ReentrantLock();
    private final Map<String,LruNode> map = new HashMap<>();
    private final Deque<LruNode> deque = new LinkedList<>();
    private final int capacity;

    public LruCache(int capacity) {
        this.capacity = capacity;
    }

    public String get(String key) {
        try {
            lock.lockInterruptibly();
            if (map.containsKey(key)) {
                LruNode lruNode = map.get(key);
                deque.removeFirstOccurrence(lruNode);
                deque.offerLast(lruNode);
                return lruNode.value;
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        } finally {
            lock.unlock();
        }
        return null;
    }
    
    public void put(String key, String value) {
        try {
            lock.lockInterruptibly();
            if (map.containsKey(key)) {
                LruNode nodeToRemove = map.remove(key);
                deque.removeFirstOccurrence(nodeToRemove);
            } else if (map.size() == capacity) {
                LruNode nodeToBeRemoved = deque.removeFirst();
                map.remove(nodeToBeRemoved.key);
            }
            LruNode lruNode = new LruNode(key, value);
            map.put(key, lruNode);
            deque.offerLast(lruNode);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        } finally {
            lock.unlock();
        }
    }
    
    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("----- cache contents -------\n");
        for (Map.Entry<String, LruNode> entry : this.map.entrySet()) {
            stringBuilder.append(entry.getKey()+ " : " + entry.getValue().value + "\n");
        }
        stringBuilder.append("----------------------------\n");
        return stringBuilder.toString();
    }
    
    private static record LruNode(String key, String value) {}

    public static void main(String[] args) {
        LruCache lruCache = new LruCache(3);
        lruCache.put("k1","v1");
        lruCache.put("k1","v0");
        lruCache.put("k2","v2");
        lruCache.put("k3","v3");
        lruCache.put("k3","v4");

        System.out.println(lruCache.toString());

        lruCache.put("k4","v4");
        lruCache.put("k4","e4");
        lruCache.put("k5","v5");
        lruCache.put("k6","v6");
        lruCache.put("k7","v7");
        lruCache.put("k8","v8");
        lruCache.put("k9","v9");
        System.out.println(lruCache.toString());
    }
}