LRU算法—缓存淘汰算法原理

1、LRU

1.1 LRU核心原理
Least recently used(LRU，最近最少使用)算法根据数据的历史访问记录淘汰数据。其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”；

1.2 算法实现
最常见的实现是使用一个链表保存缓存数据，详细算法实现如下：

LRU简化模型算法.png

算法流程：

新数据插入到链表头部；
每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
当链表满的时候，将链表尾部的数据丢弃。

几种实现方案：
1.用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。

2.利用一个链表来实现，每次新插入数据的时候将新数据插到链表的头部；每次缓存命中（即数据被访问），则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据丢弃。

3.利用LinkedHashMap。 LinkedHashMap是用的HashMap加双链表实现的，而且本身已经实现了按照访问顺序的存储，这样可以直接用这个类来保存数据，只需要在移除元素时简单处理就行。

对于第一种方法，需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n)。对于第二种方法，链表在定位数据的时候时间复杂度为O(n)。所以在一般使用第三种方式来是实现LRU算法。

1.3 分析
【命中率】
当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。
【复杂度】
实现简单。
【代价】
命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。
1.4 代码实现

/**
 * 类说明：利用LinkedHashMap实现LRU缓存， 必须实现removeEldestEntry方法
 */
public class LRU<K, V> {
    private static final float LOAD_FACTOR = 0.75f;
    private LinkedHashMap<K, V> map;
    private int capacitySize;

    public LRU(int capacitySize) {
        this.capacitySize = capacitySize;
        map = new LinkedHashMap<K, V>(capacitySize, LOAD_FACTOR, true) {
            @Override
            protected boolean removeEldestEntry(Entry<K, V> eldest) {
                return size() > capacitySize;
            }
        };
    }

    public synchronized V get(K key) {
        return map.get(key);
    }

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

    public synchronized void clear() {
        map.clear();
    }
}

2、LRU-K

2.1 LRU-K核心原理
LRU-K中的K代表最近使用的次数，因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。

2.2 算法实现

LRU-K模型算法.png

算法流程：
1）数据第一次被访问，加入到访问历史记录表（简称记录表）；在记录表中对应的K单元中设置最后访问时间=new()，且设置访问次数为1；
2）如果数据访问次数没有达到K次，则访问次数+1。最后访问时间与当前时间间隔超过预设的值(如30秒)，访问次数清0并加1；
3）当数据访问计数超过(>=)K次后，则访问次数+1。将数据保存到LRU缓存队列中，缓存队列重新按照时间排序；
4）LRU缓存队列中数据被再次访问后，重新排序；
5）LRU缓存队列需要淘汰数据时，淘汰缓存队列中排在末尾的数据，即：淘汰“倒数第K次访问离现在最久”的数据。

2.3 分析
【命中率】
LRU-K降低了“缓存污染”带来的问题，命中率比LRU要高。
【复杂度】
LRU-K队列是一个优先级队列，算法复杂度和代价比较高。
【代价】
由于LRU-K还需要记录那些被访问过、但还没有放入缓存的对象，因此内存消耗会比LRU要多；当数据量很大的时候，内存消耗会比较可观。
LRU-K需要基于时间进行排序（可以在需要淘汰时再排序，也可以即时排序），CPU消耗比LRU要高。

总结：
LRU-K具有LRU的优点，同时能够避免LRU的缺点，实际应用中LRU-2是综合各种因素后最优的选择，LRU-3或者更大的K值命中率会高，但适应性差，需要大量的数据访问才能将历史访问记录清除掉。

参考：
1）缓存淘汰算法--LRU算法
2）基于LRU-K算法设计本地缓存实现流量削峰
3）LRU算法四种实现方式介绍