LRUキャッシュの同時バージョン

Question

私はLRU CAcheをjavaで実装しました。それは完全に動作します。私は、既存の要素を高速に取得するためのhashMapとノードの順序を保持するためのDoubleLinkedListという2つのデータ構造を使用しました。しかし、実装に効率的な同時実行メカニズムを提供する方法が混乱していますか？私はコンセプションをロックすることから始めましたが、執筆との同期なしで速い読みを保証したいと思います。私はこれをすることができないように見えるので、私はここにこだわっています。

私はLRU実装のために同時キャッシュを使用して、キャッシュ全体で気まぐれなロックを避ける方法を教えてください。私たちはHashMapのとDoubleLinkedListを使用する場合、実装キャッシュの古典的なアプローチで、同時実行と一致することは不可能であることがわかり@BenManesからのリンクによると

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

：以下は私のコードです。そのような場合には同期バージョンのみが可能です。現在、アルゴリズムの新しいバージョンを作成しました。ノードを格納するためにConcurrentHashMapのWeakReferenceを使用しています（@Marko Topolnik - あなたはAtomicReferenceを使用しますか？あなたの方法はまだありません）。 IMHOを使うと、リストからテールを削除すると、自動的にノードをハッシュマップから削除するので、既存の要素を取得しながら、読み込みと書き込みを同期させないようにできます。リスト方法のオフコース同期はまだ必要です。このソリューションの唯一の弱点は、GCを制御できないためです。ハッシュマップから失効したデータを取得する可能性があります...

私が理解したように、LRUキャッシュを同時に実行するには、 （いくつかの可能性）を次のようにリストの一部だけを-locking

• 確率論的方法を-using
• は、非同期の読み取りと書き込みのために別々のリングバッファを（事前にコミット-providing立ち退き
• のための良好な被害者を見つけるために）と避けるためにエントリのライフサイクルのためのステートマシンを使用 reord操作の誤り