乐趣区

关于后端:关于我在学习LFU的时候在开源项目捡了个漏这件事

你好呀,我是歪歪。

这篇文章带大家盘一下 LFU 这个玩意。

为什么忽然想起聊聊这个货色呢,因为前段时间有个读者给我扔过去一个链接:

我一看,好家伙,这不是我敬爱的老朋友,Dubbo 同学嘛。

点进去一看,就是一个对于 LFU 缓存的 BUG:

https://github.com/apache/dub…

你晓得的,我就喜爱盘一点开源我的项目的 BUG,看看有没有机会,捡捡漏什么的。在我辉煌的“捡漏”历中,已经最浓墨重彩的一笔是在 Redisson 外面,发现作者在重构代码的时候,误把某个办法的计数,从默认值为 0,改成了为 1。

这个 BUG 会间接导致 Redission 锁失去可重入的性质。我发现后,源码都没下载,间接在网页上就改回去了:

我认为这可能就是巅峰了。

然而直到我遇到了 Dubbo 的这个 LFUCache 的 BUG,它的修复计划,只是须要替换两行代码的程序就完事儿了,更加简略。

到底怎么回事呢,我带你盘一把。

首先,刚刚提到 BUG,因为这一次针对 LFU 实现的优化提交:

https://github.com/apache/dub…

通过链接咱们晓得,这次提交的目标是优化 LFUCache 这个类,使其能通过 frequency 获取到对应的 key,而后删除空缓存。

然而带了个内存泄露的 BUG 下来,那么这个 BUG 是怎么修复的呢?

间接给对应的提交给回滚掉了:

然而,回滚回来的这一份代码,我集体感觉也是有问题的,应用起来,有点不得劲。

在为你解析 Dubbo 的 LFU 实现的问题之前,我必须要先把 LFU 这个货色的思路给你盘明确了,你能力丝滑入戏。

LRU vs LFU

在说 LFU 之前,我先给简略提一句它的好兄弟:LRU,Least Recently Used,最近起码应用。

LRU 这个算法的思维就是:如果一个数据在最近一段时间没有被拜访到,那么在未来它被拜访的可能性也很小。所以,当指定的空间已存满数据时,该当把最久没有被拜访到的数据淘汰。

听形容你也晓得了,它是一种淘汰算法。

如果说 LRU 是 Easy 模式的话,那么把两头的字母从 R(Recently)变成 F(Frequently),即 LFU,那就是 hard 模式了。

如果你不意识 Frequently 没关系,毕竟这是一个英语专八的词汇。

我,英语八级半,我能够教你:

这是一个 adv,副词,是指在句子中示意行为或状态特色的词,用以润饰动词、形容词、其余副词或全句,示意工夫、地点、水平、形式等概念。

在 LFU 外面,示意的就是频率,它翻译过去就是:最不常常应用策略。

LRU 淘汰数据的时候,只看数据在缓存外面待的工夫长短这个维度。

而 LFU 在缓存满了,须要淘汰数据的时候,看的是数据的拜访次数,被拜访次数越多的,就越不容易被淘汰。

然而呢,有的数据的拜访次数可能是雷同的。

怎么解决呢?

如果拜访次数雷同,那么再思考数据在缓存外面待的工夫长短这个维度。

也就是说 LFU 算法,先看拜访次数,如果次数统一,再看缓存工夫。

给你举个具体的例子。

假如咱们的缓存容量为 3,依照下列数据程序进行拜访:

如果依照 LRU 算法进行数据淘汰,那么十次拜访的后果如下:

十次拜访完结后,缓存中剩下的是 b,c,d 这三个元素。

你认真嗦一下,你有没有感觉有一丝丝不对劲?

十次拜访中元素 a 被拜访了 5 次,阐明 a 是一个常常要用到的货色,后果依照 LRU 算法,最初元素 a 被淘汰了?

如果依照 LFU 算法,最初留在缓存中的三个元素应该是 b,c,a。

这样看来,LFU 比 LRU 更加正当,更加巴适。

好的,题目形容结束了。假如,要咱们实现一个 LFUCache:

class LFUCache {public LFUCache(int capacity) { }
    
    public int get(int key) { }
    
    public void put(int key, int value) {}}

那么思路应该是怎么的呢?

一个双向链表

如果是我去面试,在齐全没有接触过 LFU 算法之前,面试官出了这么一道题,让我硬想,我能想到的计划也只能是上面这样的。

因为后面咱们剖析了,这个玩意既须要有频次,又须要有工夫程序。

咱们就能够搞个链表,先依照频次排序,频次一样的,再依照工夫排序。

因为这个过程中咱们须要删除节点,所以为了效率,咱们应用双向链表。

还是假如咱们的缓存容量为 3,还是用刚刚那组数据进行演示。

咱们把频次定义为 freq,那么前三次拜访完结后,即这三个申请拜访完结后:

每个元素的频次,即 freq 都是 1。所以链表外面应该是这样的:

因为咱们的容量就是 3,此时曾经满了。

那我问你一个问题:如果此时来任意一个不是 a 的元素,谁会被踢出缓存?

就这问题,你还思考个毛啊,这不是高深莫测的事件吗?

对于目前三个元素来说,value=a 是频次雷同的状况下,最久没有被拜访到的元素,所以它就是 head 节点的下一个元素,随时等着被淘汰。

然而你说巧不巧,

接着过去的申请就是 value=a:

当这个申请过去的时候,链表中的 value=a 的节点的频率(freq)就变成了 2。

此时,它的频率最高,最不应该被淘汰,a 元素实现了自我救赎!

因而,链表变成了上面这个样子,没有任何元素被淘汰了。

链表变动的局部,我用不同于红色的色彩(我色弱不晓得这是个啥色彩,蓝色吗?)标注进去:

接着间断来了三个 value=a 的申请:

此时的链表变动就集中在 value=a 这个节点的频率(freq)上。

为了让你能丝滑跟上,我把每次的 freq 变动都给你画进去。这行为,实锤了,妥妥的暖男作者:

接着,这个 b 申请过去了:

b 节点的 freq 从 1 变成了 2,节点的地位也产生了变动:

而后,c 申请过去:

这个时候就要特地留神了:

你说这个时候会产生什么事件?

链表中的 c 以后的拜访频率是 1,当这个 c 申请过去后,那么链表中的 c 的频率就会变成 2。

你说巧不巧,此时,value=b 节点的频率也是 2。

撞车了,那么你说,这个时候怎么办?

后面说了:频率一样的时候,看工夫。

value=c 的节点是正在被拜访的,所以要淘汰也应该淘汰之前被拜访的 value=b 的节点。

此时的链表,就应该是这样的:

而后,最初一个申请过去了:

d 元素,之前没有在链表外面呈现过,而此时链表的容量也满了。

那么刺激的就來了,该进行淘汰了,谁会被“优化”掉呢?

一看链表,哦,head 的下一个节点是 value=b:

而后把 value=d 的节点插入:

最终,所有申请结束。

留在缓存中的是 d,c,a 这三个元素。

最初,汇个总,整体的流程就是这样的:

当然,这里只是展现了链表的变动。

后面说了,这是缓存淘汰策略,缓存嘛,大家都懂,是一个 key-value 键值对。

所以后面的元素 a,b,c 啥的,其实对应的是咱们放的 key-value 键值对。也就是应该还有一个 HashMap 来存储 key 和链表节点的映射关系。

这个点比较简单,用脚趾头都能想到,我也就不开展来说了。

依照下面这个思路,你缓缓的写代码,应该是能写进去的。

下面这个双链表的计划,就是扣着脑壳硬想,大部分人能间接想到的计划。

然而,面试官如果真的是问这个问题的话,当你给出这个答复之后,他必定会诘问:有没有工夫复杂度为 O(1) 的解决方案呢?

双哈希表

如果咱们要拿出工夫复杂度为 O(1) 的解法,那就得细细的剖析了,不能扣着脑壳硬想了。

咱们先剖析一下需要。

第一点:咱们须要依据 key 查问其对应的 value。

后面说了,这是一个缓存淘汰策略,缓存嘛,用脚趾头都能想到,用 HashMap 存储 key-value 键值对。

查问工夫复杂度为 O(1),满足。

第二点:每当咱们操作一个 key 的时候,不论是查问还是新增,都须要保护这个 key 的频次,记作 freq。

因为咱们须要频繁的操作 key 对应的 freq,频繁地执行把 freq 拿进去进行加一的操作。

获取,加一,再放回去。来,请你大声的通知我,用什么数据结构?

是不是还得再来一个 HashMap 存储 key 和 freq 的对应关系?

第三点:如果缓存外面放不下了,须要淘汰数据的时候,把 freq 最小的 key 删除掉。

留神啊,下面这句话,看黑板,我再强调一下:把 freq 最小的 key 删除掉。

freq 最小?

咱们怎么晓得哪个 key 的 freq 最小呢?

后面说了,咱们有一个 HashMap 存储 key 和 freq 的对应关系。咱们必定是能够遍历这个 HashMap,来获取到 freq 最小的 key。

然而啊,敌人们,遍历呈现了,那么工夫复杂度还会是 O(1) 吗?

那怎么办呢?

留神啊,低潮来了,一学就废,一点就破。

咱们能够搞个变量来记录这个最小的 freq 啊,记为 minFreq,在对缓存操作的过程中继续的对其进行保护,不就行了?

当初咱们有最小频次(minFreq)了,须要获取到这个最小频次对应的 key,工夫复杂度得为 O(1)。

来,敌人,请你大声的通知我,你又想起了什么数据结构?

是不是又想到了 HashMap?

好了,咱们当初有三个 HashMap 了,给大家介绍一下:

一个存储 key 和 value 的 HashMap,即 HashMap<key,value>。
一个存储 key 和 freq 的 HashMap,即 HashMap<key,freq>。
一个存储 freq 和 key 的 HashMap,即 HashMap<freq,key>。

它们每个都是各司其职,目标都是为了工夫复杂度为 O(1)。

然而咱们能够把前两个 HashMap 合并一下。

咱们弄一个对象,对象外面蕴含两个属性别离是 value、freq。

假如这个对象叫做 Node,它就是这样的,频次默认为 1:

class Node {
    int value;
    int freq = 1;
    // 构造函数省略
}

那么当初咱们就能够把后面两个 HashMap,替换为一个了,即 HashMap<key,Node>。

同理,咱们能够在 Node 外面再退出一个 key 属性:

class Node {
    int key;
    int value;
    int freq = 1;
    // 构造函数省略
}

因为 Node 外面蕴含了 key,所以能够把第三个 HashMap<freq,key> 替换为 HashMap<freq,Node>。

当咱们有了封装了 key、value、freq 属性的 Node 对象之后,咱们的三个 HashMap 就变成了两个:

一个存储 key 和 Node 的 HashMap,即 HashMap<key,Node>
一个存储 freq 和 Node 的 HashMap,即 HashMap<freq,Node>

你捋一捋这个思路,是不是十分的清晰,有了清晰的思路,去写代码是不是就事倍功半了。

好,当初我通知你,到这一步,咱们还差一个逻辑,而且这个逻辑十分的重要,你当初先别着急往下看,先再回顾一下目前整个推理的过程和最初的思路,想一想到底还差啥?

到这一步,咱们还差了一个十分要害的信息没有补全,就是上面这一个点。

第四点:可能有多个 key 具备雷同的最小的 freq,此时移除这一批数据在缓存中待的工夫最长的那个元素。

在这个需要外面,咱们须要通过 freq 查找 Node,那么操作的就是 HashMap<freq,Node> 这个哈希表。

下面说 [多个 key 具备雷同的最小的 freq],也就是说通过 minFreq,是能够查问到多个 Node 的。

所以 HashMap<freq,Node> 这个哈希表,应该是这样的:HashMap<freq, 汇合 <Node>>。

这个能想明确吧?

一个坑位下,挂了一串节点。

此时的问题就变成了: 咱们应该用什么汇合来装这个 Node 对象呢?

不慌,咱们又接着剖析嘛。

先理一下这个汇合须要满足什么条件。

咱们通过 minFreq 获取这个汇合的时候,也就是队列满了,要从这个汇合中删除数据的时候

首先,须要删除 Node 的时候。

因为这个汇合外面装的是拜访频次一样的数据,那么心愿这批数据能有时序,这样能够疾速的删除待的工夫最久的 Node。

有序,有时序,能疾速查找删除待的工夫最久的 key。

LinkedList,双向链表,能够满足这个需要吧?

另外还有一种大多数状况是一个 Node 被拜访的时候,它的频次必然就会加一。

所以还要思考拜访 Node 的时候。

比方上面这个例子:

假如最小拜访频次,minFreq=5,而 5 这个坑位对应了 3 个 Node 对象。

此时,我要拜访 value=b 的对象,那么该对象就会从 minFreq=5 的 value 中移走。

而后频次加一,即 5+1=6。

退出到 minFreq=6 的 value 汇合中,变成上面这个样子:

也就是说咱们得反对任意 node 的疾速删除。

LinkedList 不反对任意 node 的疾速删除,这玩意须要遍历啊。

当然,你能够本人去手撸一个符合要求的 MySelfLinkedList。

然而,在 Java 汇合类中,其实有一个满足下面说的有序的、反对疾速删除的汇合。

那就是 LinkedHashSet,它是一个基于 LinkedHashMap 实现的有序的、去重汇合列表。

底层还是一个 Map,Map 针对指定元素的删除,O(1)。

所以,HashMap<freq, 汇合 >,就是 HashMap<freq,LinkedHashSet>。

总结一下。

咱们须要两个 HashMap,别离是

  • HashMap<key,Node>
  • HashMap<freq,LinkedHashSet<Node>>

而后还须要保护一个最小拜访频次,minFreq。

哦,对了,还得来一个参数记录缓存反对的最大容量,capacity。

而后,没了。

有的小伙伴必定要问了:你倒是给我一份代码啊?

这些剖析进去了,代码本人缓缓就撸进去了,这一份代码应该就是绝大部分面试官问 LFU 的时候,想要看到的代码了。

另外,对于 LFU 呈现在面试环节,我忽然想起一个段子,我感觉还有一丝情理:

面试官想要,我会出个两数之和,如果我不想要你,我就让你写 LFU。

我这里次要带大家梳理思路,思路清晰后再去写代码,就算面试的时候没有写出 bug free 的代码,也基本上八九不离十了。

所以具体的代码实现,我这里就不提供了,网上一搜多的很,要害是把思路弄清楚。

这玩意就像是你工作,要害的是把需要梳理明确,而后想想代码大略是怎么样的。

至于具体去写的时候,到处粘一粘,也不是不能够。再或者,把设计文档写进去了,代码落地就让小弟们照着你的思路去干就行了。

应该把工作精力放在更值得破费的中央:比方 battle 需要、写文档、写周报、写 PPT、舔领导啥的 …

Dubbo 的 LFU

到这里,你应该是懂了 LFU 到底是个啥玩意了。

当初我带你看看 Dubbo 外面的这个 LFU,它的实现计划并没有采取咱们后面剖析进去的计划。

它另辟蹊径,搞了一个新花样进去。它是怎么实现的呢?我给你盘一下。

Dubbo 是在 2.7.7 版本之后反对的 LFU,所以如果你要在本地测试一把的话,须要引入这个版本之后的 Maven 依赖。

我这里间接是把 Dubbo 源码拉下来,而后看的是 Master 分支的代码。

首先看一下它的数据结构:

它有一个 Map,是寄存的 key 和 Node 之间的映射关系。而后还有一个 freqTable 字段,它的数据结构是数组,咱们并没有看到一个叫做 minFreq 的字段。

当我的 LFUCache 这样定义的时候:

new LFUCache<>(5, 0.2f);

含意是这个缓存容量是 5,当满了之后,“优化”5*0.2 个对象,即从缓存中踢出 1 个对象。

通过 Debug 模式看,它的构造是这样的:

咱们先次要关注 freqTable 字段。

在上面标号为 ① 的中央,示意它是一个长度为 capacity+1 的数组,即长度为 6,且每个地位都 new 了一个 CacheDeque 对象。

标号为 ② 的中央,实现了一个单向链表的保护动作:

freqTable 具体拿来是干啥用的呢?

用上面这三行代码举个例子:

cache.put("why", 18);
cache.get("why");
cache.get("why");

当第一行执行实现之后,why 这个元素被放到了 freqTable 的第一个坑位,即数组的 index=0 外面:

当第二行执行实现之后,why 这个元素被放到了 freqTable 的第二个坑位外面:

当第三行执行实现之后,why 这个元素被放到了 freqTable 的第三个坑位外面:

有没有点感觉了?

freqTable 这个数组,每个坑位就是对应不同的频次,所以,我给你搞个图:

比方 index=3 地位放的 d 和 c,含意就是 d 和 c 在缓存外面被拜访的频次是 4 次。

然而,d 和 c 谁待的工夫更长呢?

我也不晓得,所以得看看源码外面删除元素的时候,是移走 last 还是 first,移走谁,谁就在这个频率下待的工夫最长。

答案就藏在它的驱赶办法外面:

org.apache.dubbo.common.utils.LFUCache#proceedEviction

从数组的第一个坑位开始遍历数组,如果这个坑位下挂的有链表,而后开始一直的移除头结点,直到驱赶指定个数的元素。

移除头结点,所以,d 是在这个频次中待的工夫最长的。

基于这个图片,假如当初队列满了,那么接下来,必定是要把 why 这个节点给“优化”了:

这就是 Dubbo 外面 LFU 实现的最外围的思维,很奇妙啊,基于数组的程序,来示意元素被拜访的频次。

然而,细细的嗦一下滋味之后,你有没有想过这样一个问题,当我拜访缓存中的元素的次数大于 freqTable 数组的长度的时候,会呈现什么神奇的景象?

我还是给你用代码示意:

尽管 mx 元素的拜访次数比 why 元素的次数多得多,然而这两个元素最初都落在了 freqTable 数组的最初一个坑位中。

也就是会呈现这样的场景:

好,我问你一个问题:假如,在这样的状况下,要淘汰元素了,谁会被淘汰?

必定是依照头结点的程序开始淘汰,也就是 why 这个节点。

接下来留神了,我再问一个问题:假如此时 why 有幸再次被拜访了一下,而后才来一个新的元素,触发了淘汰策略,谁会被淘汰?

why 会变成这个坑位下的链表中的 last 节点,从而规避过下一次淘汰。mx 元素被淘汰了。

这玩意忽然就从 LFU,变成了一个 LRU。在同一个实现外面,既有 LFU 又有 LRU,这玩意,常识都学杂了啊。

我就问你 6 不 6?

所以,这就是 Dubbo 的 LFU 算法实现的一个弊病,这个弊病是因为它的设计理念和数据结构决定的,如果想要防止这个问题,我感觉有点麻烦,得颠覆素来。

所以我这里也只是给你形容一下有这个问题的存在。

而后,对于 Dubbo 的 LFU 的实现,还有另外一个神奇的货色,我感觉这纯纯的就是 BUG 了。

我还是给你搞一个测试用例:

@Test
void testPutAndGet() {LFUCache<String, Integer> cache = new LFUCache<>(5, 0.2f);
    for (int i = 0; i < 5; i++) {cache.put(i + "", i);
        cache.get(i + "");
    }
    cache.put("why", 18);
    Integer why = cache.get("why");
    System.out.println("why =" + why);
}

一个容量为 5 的 LFUCache,我先放五个元素进去,每个元素 put 之后再 get 一下,所以每个元素的频率变成了 2。

而后,此时我放了一个 why 进去,而后在取出来的时候,why 没了。

你这啥缓存啊,我刚刚放进去的货色,等着马上就要用呢,后果获取的时候没了,这不是 BUG 是啥?

问题就出在它的 put 办法中:

标号为 ① 的中央往缓存外面放,搁置结束之后,判断是否会触发淘汰机制,而后在标号 ② 的中央删除元素。

后面说了,淘汰策略,proceedEviction 办法,是从 freqTable 数组的第一个坑位开始遍历数组,如果这个坑位下挂的有链表,而后开始一直的移除头结点,直到驱赶指定个数的元素。

所以,在刚刚我的示例代码中,why 元素刚刚放进去,它的频率是 1,放在了 freqTable 数组的第 0 个地位。

放完之后,一看,触发淘汰机制了,让 proceedEviction 办法看看是谁应该被淘汰了。

你说,这不是赶巧了嘛,间接又把 why 给淘汰了,因为它的拜访频率最低。

所以,立马去获取“why”的时候,获取不到。

这个中央的逻辑就是有问题的。

不应该采取“先放新元素,再判断容量,如果满了,触发淘汰机制”的实现计划。

而应该采取“先判断容量,如果满了,再触发淘汰机制,最初再放新元素的”计划。

也就是我须要把这两行代码换个地位:

再次执行测试案例,就没有问题了:

诶,你说这是什么?

这不就是为开源我的项目奉献源码的好机会吗?

于是 …

https://github.com/apache/dub…

对于提 pr,有一个小细节,我悄悄的通知你:合不合并什么的不重要,重要的是全英文发问,哪怕是中文一键翻译过去的,也要贴上去,逼格要拉满,品位要下来 …

至于最初,如果没合并,阐明我考虑不周,又是新的素材。

如果合并了,简历上又能够写:纯熟应用 Dubbo,并为其奉献过源码。

到时候,我脸皮再厚一点,还能够写成:浏览过 Apache 顶级开源我的项目源码,屡次为其奉献过外围源码,并写过系列博文,加深学习印象 …

不能再说了,剩下的就靠本人悟了!

最初,文章就到这里了,如果对你有一丝丝的帮忙, 帮我点个收费的赞 ,不过分吧?

退出移动版