聊聊本地缓存 · 造舟野渡

概述

本文介绍一些常见的缓存设计算法和思路。比如缓存淘汰的算法：LRU，SLRU，LFU，W-TinyLFU。实现入guava cache和caffeine。

LRU

LRU的全称是Least Recently Used，最近最少使用。如果缓存满了，把最近没有被使用到的数据移出。它的思想是：如果数据最近被访问过，将来被访问的概率也更高。

最简单的方式就是使用LinkedHashMap，几行代码就能实现。

public class LruCacheLinkedHashMapLazy<K, V> implements LruCache<K,V> {
    private LinkedHashMap<K, V> map;
    private final int CAPACITY;

    public LruCacheLinkedHashMapLazy(int capacity) {
        CAPACITY = capacity;
        map = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > CAPACITY;
            }
        };
    }
    @Override
    public V get(K key) {
        return map.getOrDefault(key, null);
    }
    @Override
    public void put(K key, V value) {
        map.put(key, value);
    }
}

LinkedHashMap通过hash表和双向链表维护数据，如果初始化时accessOrder=true，新加入或者访问的数据都会放到链表头部，这样，一直没被访问的node就会被顶到尾部，如果超出缓存大小，把链表尾部的数据删除即可。

也可以通过HashMap和Doubley-Linked实现，这样更清晰看出怎么通过双向链表实现：

public class LRUCacheHashMapAndDoublyLinked<K, V> implements LruCache<K, V> {
    private class Node {
        K key;
        V value;
        Node prev, next;

        Node(K k, V v) {
            this.key = k;
            this.value = v;
        }
    }

    private int capacity, count;
    private Map<K, Node> map;
    private Node head, tail;

    public LRUCacheHashMapAndDoublyLinked(int capacity) {
        this.capacity = capacity;
        this.count = 0;
        map = new HashMap<>();
        head = new Node(null, null);
        tail = new Node(null, null);
        head.next = tail;
        tail.prev = head;
    }

    private void update(Node node) {
        remove(node);
        add(node);
    }

    private void add(Node node) {
        Node after = head.next;
        head.next = node;
        node.prev = head;
        node.next = after;
        after.prev = node;
    }

    private void remove(Node node) {
        Node before = node.prev, after = node.next;
        before.next = after;
        after.prev = before;
    }

    @Override
    public V get(K k) {
        Node n = map.get(k);
        if (null == n) {
            return null;
        }
        update(n);
        return n.value;
    }

    @Override
    public void put(K key, V value) {
        Node n = map.get(key);
        if (null == n) {
            n = new Node(key, value);
            map.put(key, n);
            add(n);
            ++count;
        } else {
            n.value = value;
            update(n);
        }
        if (count > capacity) {
            Node toDel = tail.prev;
            remove(toDel);
            map.remove(toDel.key);
            --count;
        }
    }
}

但是，上面两个示例都不是并发安全的，需要加锁，加锁后怎么提升性能呢，后面详细说明。

LFU

LFU(Least Frequently Used)即最近最不常用，它的核心思想是只缓存那些经常使用的。这个算法必须要维护数据的访问频次，按照频次排序，淘汰频次最低的数据。

比如上图，至少有4个数据结构才能实现了LFU。 LFU缺点:

数据年龄问题。比如某网站首页数据展示，当天访问量大，但是之后可能再也不会被访问到了。所以，访问频率并不是绝对完美的判断标准。对于过时数据，需要降低他的访问频次，即“动态衰老最经常使用"。
内存开销：就是已经从cache中移除，也要保存访问频次的记录。我们可以设置一个最大值，但是这个最大值应该是多少，也不好评估。

Guava cache 实现SLRU

对上面的示例，要并发安全，只能加锁。为了改善加锁后开销，可以像ConcurrentHashMap一样，把table分到一个个segment下，每个segment对应一个锁，来分散全局锁带来的性能损失，GuavaCache就是这样的实现，如下图。 guava cache还维护两个队列，accesQueue和writeQueue，用来实现segement的局部LRU和过期时间。另外还有一个recencyQueue，它用来提高accessQueue更新锁消耗。如果每次访问都加锁更新accessQueue，影响性能，guava把访问的数据更新到recencyQueue，recencyQueue通过ConcurrentLinkedQueue实现，并发安全。等写入数据时，再加锁从recencyQueue更新到accesQueue。

另外，对于过期数据的清理，guava并不是另起一个线程，而是每次有访问的时候才清理。

W-TinyLFU

不管是LFU还是LRU，都是希望在缓存填满后，淘汰掉那些在短期内可能不会使用的数据，从而提升缓存的命中率。LRU和LFU都有他的局限性。因为LFU的问题，LRU是一个比较流行的算法，它什么问题？

它不是抗扫描的。比如cache的大小是N，缓存N+1个item(第一个会被淘汰)，如果顺序发起N个请求。将导致没有一个命中缓存。

W-TinyLFU 是一个综合LRU和LFU优点的实现方式：其中TinyLFU维护了近期访问记录的频率信息，作为一个过滤器，当新记录来时，只有满足TinyLFU要求的记录才可以被插入缓存。其中实现算法采用ount-Min Sketch算法。以LRU作为淘汰方式，TinyLFU作为许入过滤器。

CountMin Sketch 通过矩阵和多个hash函数实现：一个key，通过不同的hash定位到数组index，值加1，最后取min(8,6,7,6)=6作为此key的访问次数记录。因为hash冲突的原因，值不一定准确，但对于LFU的实现，这个误差可以忽略。下面我们看它是怎么解决LFU缺点的。

因为使用矩阵，跟数据量大小没关系，很好地解决了LFU的内存开销问题。对于数据年龄，可以添加一个计数上线，一旦到达上线，所有记录的Sketch数据都除2，从而实现衰减效果，对于短暂热点数据，如果之后一直没有访问，count/2不断衰减，直至淘汰。

下图是另一种表达方式： sketch 作为过滤器（filter）。当新来的数据比要驱逐的数据高频时，这个数据才会被缓存接纳。基于java8的库caffeine就是这样的实现。缓存命中表现：

参考文档: [1]. A LRU Cache in 10 Lines of Java [2]. TinyLFU: A Highly Efficient Cache Admission Policy [3]. Approximating Data with the Count-Min Data Structure [4]. On Window TinyLFU [5]. Design Of A Modern Cache [6]. go-tinylfu

Menu

概述

LRU

LFU

Guava cache 实现SLRU

W-TinyLFU