java Thread-safe LRUCache implementation

Question

What is best way to implement thread-safe LRUCache in java? Please review this one. Is there any better approach which can be taken here?

package cache;

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class  LRUCache<K,V> {

    private  ConcurrentLinkedQueue<K> concurrentLinkedQueue = new ConcurrentLinkedQueue<K>();

    private  ConcurrentHashMap<K,V> concurrentHashMap = new ConcurrentHashMap<K, V>();

    private ReadWriteLock readWriteLock = new ReentrantReadWriteLock();

    private Lock readLock = readWriteLock.readLock();

    private Lock writeLock = readWriteLock.writeLock();

    int maxSize=0;

    public LRUCache(final int MAX_SIZE){
        this.maxSize=MAX_SIZE;
    }

    public V getElement(K key){

        readLock.lock();
        try {
        V v=null;
          if(concurrentHashMap.contains(key)){
              concurrentLinkedQueue.remove(key);
              v= concurrentHashMap.get(key);
                concurrentLinkedQueue.add(key);
          }


        return v;
        }finally{
            readLock.unlock();
        }
    }

    public V removeElement(K key){
         writeLock.lock();
         try {
        V v=null;
        if(concurrentHashMap.contains(key)){
        v=concurrentHashMap.remove(key);
            concurrentLinkedQueue.remove(key);
        }

        return v;
         } finally {
             writeLock.unlock();
         }
    }

    public V addElement(K key,V value){
        writeLock.lock();
        try {
        if(concurrentHashMap.contains(key)){
             concurrentLinkedQueue.remove(key);
        }
        while(concurrentLinkedQueue.size() >=maxSize){
             K queueKey=concurrentLinkedQueue.poll();
             concurrentHashMap.remove(queueKey);
        }
        concurrentLinkedQueue.add(key);
        concurrentHashMap.put(key, value);

        return value;
        } finally{
            writeLock.unlock();
        }
    }
}

lauthu · Accepted Answer · 2019-03-11 11:48:49Z

4

Advice 1

This implementation is not thread safe. For example, if two threads invoked getElement(key1) simultaneously, they may runs to concurrentLinkedQueue.add(key) at same times(they both performed delete and get, but delete will fail the second time or just do nothing), then two same keys will be added.

Advice 2

Maybe capacity is more suitable than maxSize.

Advice 3

LinkedHashMap is often used as LRU cache.

edited Mar 11, 2019 at 11:48

answered Mar 11, 2019 at 4:10

lauthu

1414 bronze badges

\$\begingroup\$ Why does the number 1 happen? Doesn't the key get removed and added? Isn't concurrent containers thread safe. \$\endgroup\$

JaDogg
– JaDogg

2019-03-11 09:02:48 +00:00
Commented Mar 11, 2019 at 9:02
\$\begingroup\$ @422_unprocessable_entity the three operations inside if block is not atomic. If two threads running to concurrentLinkedQueue.add(key); at same times(they both performed delete and get, but delete will fail the second time or just do nothing), two same keys will be added. \$\endgroup\$

lauthu
– lauthu

2019-03-11 09:33:41 +00:00
Commented Mar 11, 2019 at 9:33
\$\begingroup\$ Yes you are correct. Well done on catching it. :) Can you insert the explanation in the answer as well. \$\endgroup\$

JaDogg
– JaDogg

2019-03-11 09:50:16 +00:00
Commented Mar 11, 2019 at 9:50

Add a comment |

coderodde · Accepted Answer · 2019-03-09 07:37:47Z

Advice 1

public class  LRUCache<K,V>

You have two spaces between class and LRUCache.

Advice 2

v=null

In professional Java programming, it is customary to have a single space before and after each binary operator.

Advice 3

public V getElement(K key){

    readLock.lock();
    try { ... } ...

Looks strange to me. Why not have instead the following:

public V getElement(K key){
    readLock.lock();

    try { ... } ...

Advice 4

int maxSize=0;

First of all, I suggest you make it private. Also, there is no need to initialize member ints with zero, that is done by Java by default. Other fundamental types are initialized to zero too.

Advice 5

public LRUCache(final int MAX_SIZE)

It is idiomatic to name only constants with UPPER CASE. Constructor (and method) parameters are advised to be in camelCase.

Advice 6

private  ConcurrentHashMap<K,V> concurrentHashMap = new ConcurrentHashMap<K, V>();

You could omit type parameters in new ConcurrentHashMap<K, V> thanks to diamond inference. Also, you could declare all the members instead of maxSize to final:

private final ConcurrentHashMap<K,V> concurrentHashMap = new ConcurrentHashMap<>();

Advice 7

ConcurrentHashMap<K,V>

It is also customary to have a single space after each comma character: <K,_V>.

Advice 8

concurrentLinkedQueue and concurrentHashMap. These are not the best possible names for the two data structures. Instead of naming them according to their type I instead suggest to name them according to what they do.

prasune · Accepted Answer · 2020-11-29 15:53:02Z

Advice 1

Rename concurrentHashMap to internalCache

Advice 2

Rename concurrentLinkedQueue to trackingQueue

Advice 3

Declare using Queue Interface:

Queue<K> trackingQueue = new ConcurrentLinkedQueue<>();

Advice 4

Your get API implementation is not thread safe as pointed out in one of the comments above. You can do the getElement implementation as follows to make sure that a simultaneaous remove from queue for same element does not result in adding back duplicate element to queue:

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

Stack Exchange Network

java Thread-safe LRUCache implementation

3 Answers 3

Advice 1

Advice 2

Advice 3

Advice 4

You must log in to answer this question.

Hot Network Questions

java Thread-safe LRUCache implementation

3 Answers 3

Advice 1

Advice 2

Advice 3

Advice 4

You must log in to answer this question.

Related

Hot Network Questions