Параллельная версия кэша LRU

Question

Я реализовал LRU CAche в java. Он работает отлично. Я использовал две структуры данных: hashMap для быстрого извлечения существующих элементов и DoubleLinkedList для поддержания порядка узлов. Однако я смущен тем, как я могу обеспечить эффективный механизм параллелизма для моей реализации? Я начал с концепции блокировки, но хотел бы обеспечить быстрое чтение без синхронизации с письмом, и я застрял здесь, потому что похоже, что я не могу этого сделать.

Не могли бы вы посоветовать мне, как я могу доказать параллелизм для моей реализации LRU, избегая неэлегантной блокировки всего кеша? Ниже мой код:

public class LRUCacheImpl implements LRUCache { 
    private final Map<Integer, Node> cacheMap = new ConcurrentHashMap<>(); 
    private final DoubleLinkedList nodeList; 
    private final int allowedCapacity; 

    public LRUCacheImpl(int allowedCapacity) { 
     this.allowedCapacity = allowedCapacity; 
     nodeList = new DoubleLinkedListImpl(allowedCapacity); 
    } 

    @Override 
    public Node getElement(int value) { 
     Node toReturn = cacheMap.get(value); 
     if(toReturn != null){ 
      nodeList.moveExistingToHead(toReturn); 
      toReturn = new Node(toReturn.getValue()); 
     } 
     else{ 
      synchronized (this) { 
       if (allowedCapacity == nodeList.getCurrentSize()) { 
        cacheMap.remove(nodeList.getTail().getValue()); 
       } 
       toReturn = new Node(value); 
       nodeList.addNewAsHead(toReturn); 
       cacheMap.put(value, toReturn); 
      } 
     } 
     return new Node(toReturn.getValue()); 
    } 

    List<Node> getCacheState() { 
     return nodeList.getAllElements(); 
    } 
} 

public class DoubleLinkedListImpl implements DoubleLinkedList { 
    private Node head; 
    private Node tail; 
    private int currentSize; 
    private final int allowedCapacity; 

    public DoubleLinkedListImpl(int allowedCapacity) { 
     this.currentSize = 0; 
     this.allowedCapacity = allowedCapacity; 
    } 

    @Override 
    public synchronized int getCurrentSize() { 
     return currentSize; 
    } 

    @Override 
    public synchronized Node getTail() { 
     return tail; 
    } 

    @Override 
    public void moveExistingToHead(Node element) { 
     if(element != null && element != head) { 
      synchronized (this) { 
       if(element != null && element != head) { 
        Node prev = element.getPrev(); 
        Node next = element.getNext(); 
        prev.setNext(next); 
        if (next != null) { 
         next.setPrev(prev); 
        } else { 
         tail = prev; 
        } 
        attachAsHead(element); 
       } 
      } 
     } 
    } 

    @Override 
    public synchronized void addNewAsHead(Node element) { 
     if(currentSize == 0){ 
      head = tail = element; 
      currentSize = 1; 
     } 
     else if(currentSize < allowedCapacity){ 
      currentSize++; 
      attachAsHead(element); 
     } 
     else{ 
      evictTail(); 
      attachAsHead(element); 
     } 
    } 

    private synchronized void attachAsHead(Node element) { 
     element.setPrev(null); 
     element.setNext(head); 
     head.setPrev(element); 
     head = element; 
    } 

    @Override 
    public synchronized List<Node> getAllElements() { 
     List<Node> nodes = new LinkedList<>(); 
     Node tmp = head; 
     while(tmp != null){ 
      nodes.add(new Node(tmp.getValue())); 
      tmp = tmp.getNext(); 
     } 
     return nodes; 
    } 

    private synchronized void evictTail(){ 
     tail = tail.getPrev(); 
     tail.setNext(null); 
     currentSize--; 
    } 
} 

public class Node { 
    private int value; 
    private Node prev; 
    private Node next; 
    // getters and setters ommited 
} 

Answer 1

По ссылкам из @BenManes я вижу, что в классическом подходе кэшем реализации, когда мы используем HashMap и DoubleLinkedList, невозможно соответствовать параллельности. В этом случае возможна только синхронизированная версия. В настоящее время я сделал новую версию своего алгоритма, используя WeakReference в ConcurrentHashMap для хранения узлов (@Marko Topolnik - вы уверены, что хотите использовать AtomicReference? Все еще не можете получить свой путь). IMHO позволяет мне избежать синхронизации чтения с записью при получении существующего элемента, поскольку удаление хвоста из списка (выселение) автоматически удалит узел из хэш-карты. Синхронизация курсов по методам списка по-прежнему требуется. Единственной слабой точкой этого решения является то, что мы не имеем контроля над GC, поэтому возможно получить устаревшие данные из hashMap ...

Как я понял, для одновременного использования кеша LRU нам необходимо изменить реализацию следующим образом (несколько вариантов):

• -locking только некоторые части списка
• -при вероятностных методов, чтобы найти хорошую жертву выселения
• -предоставляющего асинхронные предварительную фиксацию кольцевых буферов (отдельно для чтения и записей) и использование конечного автомата для жизненного цикла входа во избежание ошибок