线程安全LRU缓存

Question

尝试使用可重入锁设计threadsafe缓存。目前，我不喜欢循环方法中的tryLock。对于使它在并发性方面更加优化，有什么投入吗？

    import java.util.ArrayDeque;
    import java.util.Deque;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.concurrent.locks.Lock;
    import java.util.concurrent.locks.ReentrantLock;
    
    class LRUNode {
        String key;
        String value;
        LRUNode(String key,String value){
            this.key  = key;
            this.value = value;
        }
    }
    public class LRU {
        Lock lock;
        Map<String,LRUNode> map;
        Deque<LRUNode> deque;
        int capacity;
        int size;
    
        LRU(int capacity) {
            this.size = 0;
            this.capacity = capacity;
            deque = new ArrayDeque<>();
            this.map = new HashMap<>();
            lock = new ReentrantLock();
        }
    
        public String get(String key){
    
            try {
                while (!lock.tryLock()) {
                    Thread.sleep(50);
                }
                if (map.containsKey(key)) {
                    //update deque
                    LRUNode lruNode = map.get(key);
                    System.out.println("Getting " + key + " from cache");
                    deque.remove(lruNode);
                    deque.offer(lruNode);
                    return lruNode.value;
                }
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
            return null;
        }
    
        public void print(){
            System.out.println("----- cache contents -------");
            for(Map.Entry<String,LRUNode> entry : this.map.entrySet()){
                System.out.println(entry.getKey()+ " : "+ entry.getValue().value);
            }
            System.out.println("----------------------------");
        }
        public void put(String key, String value){
            try {
                while (!lock.tryLock()) {
                    Thread.sleep(50);
                }
                if (size == capacity) {
                    LRUNode nodeToBeRemoved = deque.getFirst();
                    System.out.println("Evicting " + nodeToBeRemoved.key + " from cache");
                    map.remove(nodeToBeRemoved.key);
                    deque.removeFirst();
                    size--;
                }
                LRUNode lruNode = new LRUNode(key, value);
                map.put(key, lruNode);
                deque.offer(lruNode);
                System.out.println("Added " + key + " to cache");
                size++;
            }catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
        }
    
        public static void main(String[] args) {
            LRU lru = new LRU(3);
            lru.put("k1","v1");
            lru.put("k2","v2");
            lru.put("k3","v3");
    
            lru.print();
    
            lru.put("k4","v4");
            lru.put("k5","v5");
            lru.put("k6","v6");
            lru.put("k7","v7");
            lru.put("k8","v8");
            lru.put("k9","v9");
            lru.print();
        }
    }

Answer 1

对于使它在并发性方面更加优化，有什么投入吗？

这一点在JavadocLinkedHashMap中得到了特别的解决：

如果多个线程同时访问链接的散列映射，并且至少有一个线程在结构上修改映射，则必须在外部同步它。这通常是通过对一些自然封装映射的对象进行同步来实现的。如果不存在这样的对象，则应该使用Collections.synchronizedMap方法“包装”映射。这最好在创建时完成，以防止意外地不同步地访问映射: Map m=Collections.synchronizedMap(新的LinkedHashMap(.))；

也就是说，如果您还没有包含Map的同步对象，那么他们建议用Collections.synchronizedMap包装Map。那么您就不必自己编写任何并发代码了。

所以，把你的

LRU lru = new LRU(3);

使用

Map<String, String> lru = Collections.synchronizedMap(new LinkedHashMap<String, String>(3) {

    protected final int LIMIT;

    public LRUCache(int capacity) {
        super(2 * capacity, .75, true);
        LIMIT = capacity;
    }

    @Override
    protected boolean removeEldestEntry() {
        return size() > LIMIT;
    }

});

然后，您可以修改print方法，将Map作为参数，而不是在this上操作。

这个版本

1. 减少您必须编写的代码数量。
2. 为您提供了本机LinkedHashMap版本的最新使用的缓存的所有优点，包括边缘案例处理和优化。
3. 为您提供Map本机并发包装器的所有优点，包括边缘案例处理和优化。

现在，在某些方面，您的版本当然有可能优于这一点。如果是这样的话，您应该解释您的版本给出了什么，而这个版本没有。默认情况下，应该使用内置版本，直到找到使用其他内容的理由为止。

由于您在内部使用Map，所以您将得到默认的映射行为。这方面的一个例子是，当添加第三个元素时，您的版本将超过加载因子并将初始容量增加一倍。这个版本可以立即完成，因此在第三个put上没有开销。

考虑到不需要调整大小，可以提供更好的映射实现。但你不会那么做的。

对于最近使用最少的队列，ArrayDeque是一个糟糕的解决方案。它需要复制内存块，每次从中间删除。因此，LinkedHashMap在这里可能更优越，因为它使用了一个链接列表。当然，映射提供对任何节点的恒定时间访问，而链接列表提供恒定时间删除和添加。

另一种方法是创建一个数组，并将链接作为数组中的索引来维护。这样你就不用继续制造和破坏节点了。您可以继续循环数组中的节点。您甚至可以做到这样，put就可以自动写入最近使用最少的条目。这是一个您的版本可以优于LinkedHashMap的地方。

由于您的容量太小，您可能还会找到一个堆(PriorityQueue)来提供更好的性能。是的，它是对数移除和添加，而不是常量。但是对于较小的大小，维护堆可能比管理链接列表(包括内存分配)更快。

同样，对于容量为3的人来说，放弃哈希映射，只做一次线性扫描是明智的。但是当然，您可能只是选择了三个作为一个小的大小，这样就可以很容易地测试逻辑。也许在实践中，这会大得多。