java - 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 中使用 Wea​​kReference 来存储节点(@Marko Topolnik - 您确定要使用 AtomicReference 吗？仍然无法如愿)。恕我直言，这使我能够避免在获取现有元素时同步读取和写入，因为从列表中删除尾部(逐出)将自动从 HashMap 中删除节点。当然，列表方法上的同步仍然是必需的。该解决方案唯一的弱点是我们无法控制 GC，因此有可能从 hashMap 获取过时的数据...

据我了解，为了使 LRU 缓存并发，我们需要按如下方式更改实现(可能性很小):

• -仅锁定列表的某些部分
• -使用概率方法寻找适合驱逐的受害者
• -提供异步预提交环形缓冲区(读写分离)并使用状态机进行条目生命周期以避免重新排序操作