LRU及LFU学习笔记

概述

也算巧合，最近在做将数据缓存到本地的cache中提升访问效率的项目，正好用到了LFU的开源实现，就顺着这条线索往下看了看与之相关的LRU算法和LFU算法的原理及其应用，本文主要篇幅记录其原理，应用方面只做一些优缺点的阐述。总的来说LRU和LFU算是比较相似的算法，其核心问题是解决在cache空间有限的前提下，选择合适的退出策略来保证cache命中率始终维持在较高水平。通俗来说，即通过cache过去的访问历史来预测未来的访问密度。LRU和LFU在解决此问题时选择了相似却又不同的退出策略。

LRU

LRU(least recently used)顾名思义，即选择最近最久未使用的entry退出cache的策略。

其原理是

插入操作:

1.当cache未满时，每有一个新的entry出现，则直接插入到cache中，并将该entry标记为刚刚使用
2.当cache已满时，每有一个新的entry出现，则首先删除最近最久未使用的entry，然后执行步骤1
查询操作

1.当命中cache时，不仅要返回entry本身，还需要将命中的entry标记为刚刚使用
2.未命中cache时直接返回失败即可
基本来说，LRU的退出策略认为，在最近的一段时间内没有被访问的entry在将来被访问的概率也不高。

import java.util.HashMap;
import java.util.Map;
 
public class LRUCache {
 
    Map<Integer, Node> map;
    Node head, tail;
    int capacity;
 
    public LRUCache(int capacity) {
        map = new HashMap<>(capacity);
        head = new Node(-1, -1, null, null);
        tail = new Node(-1, -1, head, null);
        head.next = tail;
        this.capacity = capacity;
    }
 
    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            touchNode(node);
            return node.value;
        }
        return -1;
    }
 
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            touchNode(node);
        } else {
            Node node = new Node(key, value);
            if (map.size() >= capacity) {
                map.remove(delNode());
            }
            addNode(node);
            map.put(key, node);
        }
    }
 
    private int delNode() {
        Node node = tail.pre;
        node.pre.next = tail;
        tail.pre = node.pre;
        return node.key;
    }
 
    private void addNode (Node node) {
        head.next.pre = node;
        node.next = head.next;
        node.pre = head;
        head.next = node;
    }
 
    private void touchNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        head.next.pre = node;
        node.next = head.next;
        node.pre = head;
        head.next = node;
    }
 
    class Node{
        Node pre, next;
        int key, value;
 
        public Node(int key, int value, Node pre, Node next) {
            this.key = key;
            this.value = value;
            this.pre = pre;
            this.next = next;
        }
 
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
 
    }
}

借助一个hashmap帮助实现，另外维护一个带头尾节点的双向链表来维护访问顺序，靠近头节点的节点是最近被访问的节点，同理，越靠近尾节点的节点则说明越久未被访问过。结合源码，图解如下:

cache未满时插入元素


cache已满时插入元素


更新元素


访问元素


由于使用了HashMap和双向链表，故其时间复杂度为O(1), 空间复杂度为O(n)

LFU

LRU的在特定场景下的缺点也算比较明显，思考这样的两个例子
假如某个缓存长时间访问量极低，但是每当其快要被淘汰的时候，都恰好被访问了一次，此时会导致低频cache总是无法退出，导致内存空耗
假如cache访问的请求有很高的规律性，比如每次以a,b,c,d,e的方式来访问，然而cache缓存却只有4个slot，导致每次访问都无法命中cache，从而缓存完全无法发挥作用还导致了额外的性能和网络开销
总的来说，1问题需要考虑到被访问对象的访问频率，2问题在现实生活中比较罕见，如果真有这样的case，也可以为这样规律的访问做精确的cache策略，所以主要问题还是集中在1上

自然而然的，就有了LFU((Least Frequently Used)算法的诞生，LFU比LRU改进的一点在于额外存储了cache块实际被访问的频次，那么在淘汰时，并不是淘汰最近最久未使用的slot，而是淘汰最少使用的slot

显然，LRU中使用的双向链表虽然可以在链表node中记录访问频次来达到目的，但是分析其时间复杂度，在插入和查询元素时，都需要对元素的访问频次进行排序计算，并最终更新node节点的位置，对链表来说，每次重新排序都涉及到大量的指针移动，当然，在数据结构上可以进行一定的优化，比如将链表换成小顶堆的方式，但是无论如何，其插入，查询和删除操作均至少需要O(logn)的时间复杂度




上图以插入为例，展示了以小顶堆的方式插入元素时的节点移动过程，清楚可见其时间复杂度为O(logn)，同理，查询和删除时时间复杂度不变，由于其实现不是本节重点，故这里不再赘述，感兴趣的同学可以自行模拟其调整过程。

O(logn)的时间复杂度显然无法满足生产环境对于cache高效的访问速度的需求，在实践中，需要提供一种O(1)时间复杂度的实现来替代O(1)时间复杂度的LRU，否则LFU所弥补LRU缺点带来的益处会很快湮灭在其付出的效率成本之中。

这里看到一篇论文lfu.pdf，其实现了一种O(1)时间复杂度的LFU算法，和LRU一样，我们先来看一下其实现LFU的原理

论文中将cache存储在两种数据结构中，将数据node存放在datanode数据结构中，将其频率存放在freqnode数据结构中，具体见下图

datanode中存放具体的值以及前后datanode的指针，并维护一个指向freqnode的指针，freqnode维护一个int类型的频率值，前后freqnode的指针，以及该频率下的某一个datanode的指针，光这么说很难理解，我们接着结合存储结构来看，下图中以紫色方框代表freqnode，黄色圆形代表datanode（每个datanode指向freqnode的指针没有画，否则比较凌乱）

freqnode是严格有序的，其freq值即为其下所有datanode被访问的频次，每当有一个datanode被访问时，直接通过其指向freqnode的指针找到其访问频率，之后将其加1，若发现没有freq+1的freqnode，则new一个freqnode对象，并将该datanode从之前的freqnode节点摘下，重新放入到这个新的freqnode中，如果freq+1的freqnode已经存在，则一样将datanode摘下后放入到freq+1的freqnode中。如果被某个freqnode下的所有datanode都被摘下，则删除该freqnode并链接该freqnode前后的freqnode 具体如下图所示



上图以访问cache为例讲解了LFU算法的操作过程，同理，删除以及插入时遵循同样的置换规则，所要注意的时，插入时，固定插入到freq为1的freqnode中，删除时固定删除head.next中的datanode，这里不再以图的形式说明

我们甚至可以和LRU结合，对于相同freq的datanode，删除时选择删除最近最久未使用的，当然这些都是一些之后的思考，可以作为优化的手段进行考虑

分析时间复杂度，不难发现由于双向链表的特性，我们无论是添加，删除还是访问元素时需要移动的指针均可以在O(1)时间内获得，以访问操作为例，首先通过hashtable拿到datanode节点，通过datanode节点获取freqnode节点，那么在移动datanode节点时，只需要修改datanode的pre，next，f指针即可，整个过程时间复杂度为O(1)，以此类推，不难证明我们的结论

源码实现，由于时间紧急，本人并没有亲自实现该算法，这里有一篇github的实现，比较经典的还原了前文所述的方法，详情请戳这里

总结

至此，LRU和LFU的学习笔记就告一段落啦，当然其算法本身都有不少优化空间，比如LFU中的get方法可以指定一个频率阈值，如若小于该阈值，可以当作为命中来处理，又或者可以为cache的key设置过期时间，等等诸如此类，但是无论如何变化，其核心思想还是在本文论述范围内。