一、引言

在日常开发使用中，我们经?；崾褂胟ey-value，也就是hash的数据结构，在java中我们用的HashMap通常是没有淘汰策略的，大小在超过我们设定的值之后会自动扩容。而我们在使用缓存的场景下，其大小通常是有限制的，在容量有限的情况下，怎么合理的淘汰没有价值的内存，提高缓存的命中率是一门优雅的艺术。

二、常见的淘汰策略算法

首先要定义怎样的数据才算是“低价值”？由于缓存的通用性，这个问题的答案必须是与具体业务逻辑是无关的。我们从何种维度、如何定义数据的价值高低，其实也就决定了我们要使用什么样的缓存淘汰策略。我们最常见的缓存淘汰策略有:FIFO(First In First Out)、LRU(Least Recent Used),LFU（Least Frequently Used）下面我们依次讲解这几种淘汰策略的实现原理及其实现。

FIFO:

先淘汰最早进入被缓存的数据。FIFO 实现十分简单，但一般来说它并不是优秀的淘汰策略，越是频繁被用到的数据，往往会越早被存入缓存之中。如果采用这种淘汰策略，很可能会大幅降低缓存的命中率。

LRU（The Least Recently Used）:

优先淘汰最近最久未被使用访问过的数据。在计算机科学中，通常认为越是最近经常访问的数据，越是将要被访问到，从这个角度看，那么越久没有被访问到的数据，越是应该被优先淘汰掉。下面我来看看一下具体的实现。
首先具体的操作大致有两个，一个是put操作储存元素，另一个是get操作获取元素值。
为了使获取数据的时间复杂度尽可能低，我们优先使用的是hash的数据结构，但是想要实现优先淘汰最近最久没有被访问的数据，那么我们首先想到可以存数据的访问时间，在容量到达阈值时，根据根据访问时间来判断，但是这显然不是最优解。另一种办法是我们维护一个链表，最久没有访问过的数据放在尾部，最近访问过的数据放在头部，这样我们淘汰数据时，就可以直接删除链表尾部的数据，其时间复杂度是O（1）。而且插入数据时，我们需要维护链表元素的顺序性时，移动元素的时间复杂也可以达到O(1)。这样我们基本就确定了要使用 hash 和 链表的数据结构，具体两种数据结构定义，我们可以从思考两种操作如何实现上来得到答案。

实现逻辑

首先put操作：存储元素时，需要判断元素是否已经存在，
1、如果元素已经存在，则更新map中key对应的value值，并且将链表中的这个元素的节点移动到链表的头部。
2、 如果不存在则map和链表中直接新增元素。在map中新增元素时，需要判断容量是否已满，如果容量已满，我们需要先淘汰元素，然后需要在map和List中都新增一个元素；如果容量未满，则直接在map和链表中新增。
get操作：
如果元素不存在，直接返回null，如果元素存在，则需要移动链表中的节点至头部，然后返回key对应的value值。

根据以上操作，我们定义一个LRUCache类，这个LURCache中肯定有一个 cacheMap，map中的value存的肯定不能是key对应的value值，而应该是一个链表中的一个节点Node。因为我们在put和get操作中都需要移动链表节点，这个节点是从map中取出来的。那Node节点应该包含哪些属性呢，首先value值肯定有，因为get操作我们需要返回value值。其次还需要 prev 和 next属性，也就是这个链表是一个双向链表，因为在删除和移动节点的过程中需要访问节点的前置和后置。Node中key也需要，因为删除节点时，map中是根据key删除的。为了方便操作双向链表，使得删除（删除尾节点）和插入（插入头结点）操作时间复杂度尾O(1),LRUCache 中还需要 head 节点 和 tail 尾节点。 最后还需要有个 capital容量的属性，判断map中元素是否达到阈值。那么至此，LRUCache类的数据结构就出来了

class LRUCache {
     private ListNode head ;
    private ListNode tail ;
    private Map<Integer,ListNode> lruMap ;
    private int capacity = 65535;

    public LRUCache(int capacity){
        this.capacity = capacity;
        head = new ListNode(null,0,0,null);
        tail = new ListNode(head,0,0,null);
        head.next = tail;
        lruMap = new HashMap<>();
    }
    
    public void put(Integer key,Integer value){
     ...
    }

    public Integer get(Integer key){
     ...
    }


   class ListNode{
        Integer key;
        Integer val;
        ListNode pre;
        ListNode next;

        public ListNode(ListNode pre,Integer key,Integer val,ListNode next){
            this.key = key;
            this.val = val;
            this.pre = pre;
            this.next = next;
        }
    }
}

LRU算法相比FIFO虽然已经能够显著提高缓存的命中率，但是从另外一个角度来看，还是存在一些问题，比如一些热点数据在系统中经常被频繁访问，但最近一段时间因为某种原因未被访问过（周期性热点数据），此时这些热点数据依然要面临淘汰的命运，LRU 依然可能错误淘汰价值更高的数据。

LFU（The Least Frequently Used）:

优先淘汰最不经常使用的数据。如果定义一个数据会不会经常被使用呢，可能就需要给这个元素定义一个访问计数器， 根据访问计数器的大小来判断，访问得越少，就优先淘汰。下面我们来思考怎么实现。
淘汰数据时要根据元素访问计数器的大小，怎么判断访问计数器大小有两种方式，一种是在元素淘汰时，先把所有元素取出来对比一下，找到最小的淘汰，这种时间复杂度要O(N)，通常不采用。另外一种是在元素插入时，就按照其大小排列好，可以采用红黑树的数据结构，时间复杂度可以达到logN，这种显然要更优。
基于上面所说，基本数据结构就出来了，采用Map 和 TreeSet的数据结构。

public class LFUCache<K,V> {

    /**
     * 存对象key，Node
     */
    private Map<K,LFUNode<K,V>> cacheMap = new HashMap<K,LFUNode<K,V>>();

    /**
     * 排序的set，根据活跃数
     */
    private TreeSet<LFUNode> activeSet;

    private Integer capital = 65535;

    public LFUCache(Integer capital) {
        this.capital = capital;
    }

    public V get(K key) {
       ...
    }

    public void put(K key,V value) {
     ...
    }

    class LFUNode<K,V> implements Comparable<LFUNode>{
        private K key;

        private V value;

        private Integer activeCount;

        public LFUNode(K key,V value,Integer activeCount) {
            this.key = key;
            this.value = value;
            this.activeCount = activeCount;
        }

        @Override
        public int compareTo(LFUNode o) {
            return activeCount - o.activeCount;
        }
    }
}

实现逻辑

首先put操作：存储元素时，需要判断元素是否已经存在，
1、如果元素已经存在，则更新map中key对应元素的value值，并且元素访问计数器+1，treeSet中删除此key对应的元素，并将更新后的元素添加到treeSet。
2、 如果不存在则map和set中直接新增元素。在map中新增元素时，需要判断容量是否已满，如果容量已满，我们需要先淘汰treeSet中的第一个元素（默认访问计数器升序排列），然后再在map和TreeSet中新增一个元素；如果容量未满，则直接在map和TreeSet中新增一个元素。
get操作：
如果元素不存在，直接返回null，如果元素存在，从map中取出key对应元素，元素访问计数器+1，treeSet中删除此key对应的元素，并将更新后的元素添加到treeSet，最后返回元素的valuie值

优化升级版的LFU

以上的实现我们上文提到我们在像treeSet中添加元素或者删除元素时的时间复杂度都是logn，那有没有更优解呢，比如把时间复杂度降低为O(1)呢。在计算机科学中，还有一种常见的做法，当我们要追求时间上的极致性能时，往往要牺牲空间上的性能，也就是以空间换时间。
使用的数据结构：

比如我们可以建一个freqMap，key用来存访问次数，value则使用LinkedHashSet来存储Node节点，之所以使用LinkedHashSet，而不用List，是因为首先删除元素操作是常数阶的时间复杂度，另外， 同一个访问次数可能对应多个元素，需要保证这些元素是有序的，这样我们就可以在同一个访问次数的情况下，先删除set中的第一个元素（也就是最久未使用的元素）。另外，我们还需要维护一个min，用来表示当前最小访问次数。这样在容量超过阈值时，我们就可以直接删除这个访问次数的节点元素。

min的维护

具体min 怎么维护呢，我们新增元素时，min = 1。另外删除元素时，有两个场景，一个是cache中已经存在此元素，这个时候，freqMap中需要删除这个元素访问次数中set对应的元素节点，删除完了之后，需要判断一下当前set中是否还有元素，如果没有元素，说明当前访问次数中的元素访问次数全部升级了。那么如果当前访问次数 = min，那么min就需要+1； 还有一个场景是cache中元素已经满了的情况下，需要删除min对应set中的第一个元素，删除之后，如果set中没有数据，同样需要对 min进行+1；
具体的put操作和get操作的实现逻辑此处不再赘述，下面只列出相关的数据结构。

class LFUCache {
    Map<Integer, Node> cache;  // 存储缓存的内容
    Map<Integer, LinkedHashSet<Node>> freqMap;
    int size;
    int capacity;
    int min; // 存储当前最小频次

    public LFUCache(int capacity) {
        cache = new HashMap<> (capacity);
        freqMap = new HashMap<>();
        this.capacity = capacity;
    }
    
    public int get(int key) {
     ...
    }
    
    public void put(int key, int value) {
        .....
    }
}

class Node {
    int key;
    int value;
    int freq = 1;

    public Node() {}
    
    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

LFU可以解决LRU周期性的热点数据问题，但是同样也存在以下几个问题：一是我们需要维护好每个元素的访问计数器，这个维护带来的成本是高昂的。另一个是有些数据曾经被频繁访问过，但是最近不需要了，这些数据就很难被清除。比如对突发性的局部热点数据/稀疏流量无法被淘汰，就会导致算法中缓存的命中率急剧下降，这个是它最大弊端。

TinyLFU

这么看来，其实LRU和LFU各有优缺点，LRU使用于突发性流量的场景，而LFU使用于局部周期性流量。那么，有没有一种缓存淘汰算法，能够兼容他们两个的优点呢？TinyLFU算法出现了，顾名思义，TinyLFU是一种LFU算法，只不过在LFU算法的基础上，它又对LFU面临的两个问题给予了解决。
首先，在第一个问题上，对每个元素的维护上带来的时间和空间上的开销，首先对于每个元素的维护时间上的开销，采用了异步的方式，而不是在put或者get的时候直接取维护，而是采用了类似数据库的基于日志提交再去处理的方式。此外，对于在维护每个元素的访问计数所占用的空间问题上，采用了 Count–Min Sketch算法（类似布隆过滤器的原理去降低存储的空间开销）。最后在局部热点数据无法被淘汰的问题上，TinyLFU采用了热度衰减机制，就是当整体的统计计数（当前所有记录的频率统计之和，这个数值内部维护）达到某一个值时，那么所有记录的统计计数除以 2。
下面我们详细说一下Count–Min Sketch算法的具体原理

Count–Min Sketch

W-TinyLFU

W-TinyLFU 又是 TinyLFU 的改进版本。TinyLFU 在实现减少计数器维护频率的同时，也带来了无法很好地应对稀疏突发访问的问题，所谓稀疏突发访问是指有一些绝对频率较小，但突发访问频率很高的数据，譬如某些运维性质的任务，也许一天、一周只会在特定时间运行一次，其余时间都不会用到，此时 TinyLFU 就很难让这类元素通过 Sketch 的过滤，因为它们无法在运行期间积累到足够高的频率。应对短时间的突发访问是 LRU 的强项，W-TinyLFU 就结合了 LRU 和 LFU 两者的优点，从整体上看是它是 LFU 策略，从局部实现上看又是 LRU 策略。具体做法是将新记录暂时放入一个名为 Window Cache 的前端 LRU 缓存里面，让这些对象可以在 Window Cache 中累积热度，如果能通过 TinyLFU 的过滤器，再进入名为 Main Cache 的主缓存中存储，主缓存根据数据的访问频繁程度分为不同的段（LFU 策略，实际上 W-TinyLFU 只分了两段），但单独某一段局部来看又是基于 LRU 策略去实现的（称为 Segmented LRU）。每当前一段缓存满了之后，会将低价值数据淘汰到后一段中去存储，直至最后一段也满了之后，该数据就彻底清理出缓存。
仅靠以上简单的、有限的介绍，你不一定能完全理解 TinyLFU 和 W-TinyLFU 的工作原理，但肯定能看出这些改进算法比起原来基础版本的 LFU 要复杂了许多。有时候为了取得理想的效果，采用较为复杂的淘汰策略是不得已的选择。如果对具体的实现原理感兴趣，可以看一下这篇 caffeine的缓存设计，里面有详细的原理解析。