LRU及LFU学习笔记

时间:2024-03-15 09:19:58

概述

也算巧合,最近在做将数据缓存到本地的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未满时插入元素
LRU及LFU学习笔记
LRU及LFU学习笔记
cache已满时插入元素
LRU及LFU学习笔记
LRU及LFU学习笔记
更新元素
LRU及LFU学习笔记
LRU及LFU学习笔记
访问元素
LRU及LFU学习笔记
LRU及LFU学习笔记
由于使用了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)的时间复杂度
LRU及LFU学习笔记
LRU及LFU学习笔记
LRU及LFU学习笔记
LRU及LFU学习笔记
上图以插入为例,展示了以小顶堆的方式插入元素时的节点移动过程,清楚可见其时间复杂度为O(logn),同理,查询和删除时时间复杂度不变,由于其实现不是本节重点,故这里不再赘述,感兴趣的同学可以自行模拟其调整过程。

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

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

论文中将cache存储在两种数据结构中,将数据node存放在datanode数据结构中,将其频率存放在freqnode数据结构中,具体见下图
LRU及LFU学习笔记
datanode中存放具体的值以及前后datanode的指针,并维护一个指向freqnode的指针,freqnode维护一个int类型的频率值,前后freqnode的指针,以及该频率下的某一个datanode的指针,光这么说很难理解,我们接着结合存储结构来看,下图中以紫色方框代表freqnode,黄色圆形代表datanode(每个datanode指向freqnode的指针没有画,否则比较凌乱)
LRU及LFU学习笔记
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 具体如下图所示
LRU及LFU学习笔记
LRU及LFU学习笔记
LRU及LFU学习笔记
上图以访问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设置过期时间,等等诸如此类,但是无论如何变化,其核心思想还是在本文论述范围内。