并发版本的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