併發版本的LRU緩存

Question

我已經在java中實現了LRU CAche。它完美的作品。我使用了兩種數據結構：用於快速檢索現有元素的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，是不可能找到併發鏈接。在這種情況下只能使用同步版本。目前我做了我算法的新版本，在ConcurrentHashMap中使用WeakReference來存儲節點（@Marko Topolnik - 你確定你想使用AtomicReference嗎？仍然無法自拔）。恕我直言，這使我可以避免在獲取現有元素的同時讀取和寫入同步，因爲從列表中刪除尾部（逐出）將自動從哈希映射中刪除節點。列表方法的課程同步仍然是必需的。這個解決方案唯一的一個弱點是我們沒有對GC的控制，所以它有可能從hashMap中獲得過時的數據......

據我所知，爲了使LRU緩存併發，我們需要改變實現如下（幾種可能性）：

• -locking唯一上榜的某些部分
• - 使用概率方法來找到好的受害者驅逐
• - 提供異步提交前的環緩衝區（獨立閱讀和寫作）和使用狀態機進入生命週期以避免 reord ering of operations