大家好，我是伟伟。本篇带大家来看看LFU的事情。为什么我突然想说这件事，因为前段时间有读者给我发了一个链接：我看到了，好家伙，这不是我亲爱的老朋友吗，达博同学。点进去看看，是关于LFU缓存的BUG：https://github.com/apache/dub...大家知道的，我喜欢查开源项目的BUG，看看有没有机会，还有捡起丢失的东西。在我辉煌的“捡漏”历史中，最出彩的一笔是在Redisson。我发现作者在重构代码的时候，错误地将某个方法的count从默认值0改成了1，这个BUG会直接导致Redission锁失去可重入性。我发现后，源码没有下载，直接在网页上改回来：我以为这可能是巅峰之作。但是直到我遇到了Dubbo的LFUCacheBUG，它的修复方案只是交换两行代码的顺序，就简单多了。怎么回事，我带你去看看。首先，刚刚提到BUG，因为这次针对LFU实现的优化提交：https://github.com/apache/dub...从链接我们知道，这次提交的目的是为了优化LFUCache类，使其可以通过频率获取对应的key，然后删除空缓存。但是有了内存泄露BUG，这个BUG怎么修复呢？直接提交对应的回滚：不过个人觉得回滚的代码有问题，用起来有点别扭。在为大家分析Dubbo的LFU实现问题之前，首先要让大家对LFU的思路有个清晰的认识，这样大家才能顺利入戏。LRUvsLFU在说LFU之前，先简单提一下它的好兄弟：LRU，LeastRecentlyUsed，最近最少使用。LRU算法的思想是：如果一条数据在最近一段时间没有被访问过，那么以后访问它的可能性很小。因此，当指定空间已满数据时，应剔除最长时间未被访问的数据。你从描述中知道，它是一种消除算法。如果LRU是Easy模式，那么把中间的字母从R（Recently）改成F（Frequently），也就是LFU，也就是hard模式。不知道Frequently也没关系，毕竟是英语词汇。我，英语八级半，我可以教你：thisisanadv，副词，指句子中表示行为或状态特征的词，用来修饰动词、形容词、其他副词或整句，表示时间、地点、程度和方法等概念。在LFU中，它的意思是频率，翻译过来就是：最不常用的策略。LRU在淘汰数据的时候，只看数据在缓存中停留了多长时间这个维度。当LFU缓存满了需要淘汰数据时，取决于数据访问的次数。数据被访问的次数越多，被淘汰的可能性就越小。但是，某些数据的访问次数可能相同。如何处理？如果访问次数相同，则考虑数据在缓存中停留多长时间的维度。也就是说LFU算法先看访问次数，如果次数相同，再看缓存时间。让我给你一个具体的例子。假设我们的缓存容量为3，按照如下数据顺序进行访问：如果按照LRU算法进行数据淘汰，那么访问十次后的结果如下：访问十次后，缓存中剩下的三项是b、c和d。元素。仔细再重复一遍，是不是觉得哪里不对？元素a在十次访问中被访问了5次，说明a是一个经常使用的东西。结果按照LRU算法最终淘汰了元素a？根据LFU算法，缓存中最后剩下的三个元素应该是b、c、a。这样LFU比LRU更合理也更舒服。好了，题目描述到此结束。假设我们要实现一个LFUCache：classLFUCache{publicLFUCache(intcapacity){}publicintget(intkey){}publicvoidput(intkey,intvalue){}}那么应该怎么想呢？如果去面试一个双向链表，在我接触LFU算法之前，面试官就问了这样一个问题，让我苦思冥想，唯一能想到的解决办法如下。因为我们前面分析过，这个东西既需要频率顺序，也需要时间顺序。我们可以做一个链表，先按频率排序，频率相同，再按时间排序。因为在这个过程中我们需要删除节点，所以为了效率我们使用了双向链表。还是假设我们的缓存容量为3，还是用刚才的那组数据来演示。我们定义频率为freq，那么在前3次访问之后，也就是3次请求访问之后：每个元素的频率，也就是freq为1。所以链表应该是这样的：由于我们的容量是3，此时已经满了。那我问你一个问题：如果这个时候来了一个不是a的元素，谁会被踢出缓存？在这个问题上，你还想一想，这不是明摆着的事情吗？对于当前三个元素，value=a是频率相同时最长时间没有被访问的元素，所以是头节点的下一个元素，随时等待被淘汰。但是你说下一个请求是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。最低频率？我们怎么知道哪个键的频率最小？前面说了，我们有一个HashMap来存储key和freq的对应关系。我们肯定可以遍历这个HashMap，得到freq最小的key。但是我的朋友们，遍历到了，那么时间复杂度还是O(1)吗？那我们该怎么办呢？注意，高潮来了，一学就没用了，一点点就坏了。我们可以设置一个变量来记录最小频率，叫做minFreq，在缓存运行的过程中一直保持下去，不就可以了吗？现在我们有了最小频率（minFreq），我们需要获取这个最小频率对应的key，时间复杂度必须是O(1)。来吧，朋友，请大声告诉我，你想到了什么数据结构？是不是又想到了HashMap？好了，我们现在有3个HashMap，我给大家介绍一下：一个是存储key和value的HashMap，即HashMap。一个存储key和freq的HashMap，即HashMap。一个存储freq和key的HashMap，即HashMap。他们各司其职，目的是为了达到O(1)的时间复杂度。但是我们可以合并前两个HashMap。让我们创建一个对象，它包含两个属性：value和freq。假设这个对象叫做Node，是这样的，频率默认为1：classNode{intvalue;int频率=1;//constructoromitted}现在我们可以将前面的两个HashMap换成一个，即HashMap。同样的，我们可以给Node添加另外一个key属性：classNode{intkey;整数值；int频率=1;//constructoromitted}因为Node包含key，我们可以把第三个HashMap换成HashMap。当我们有了一个封装了key、value、freq属性的Node对象时，我们的三个HashMap就变成了两个：一个存储key和Node的HashMap，即存储freq的HashMap和存储freq的NodeHashMap，即HashMap，如果你看这个思路，是不是很清楚？有了清晰的思路，是不是写代码更有效？好，我现在告诉你，在这一点上，我们还缺一个逻辑，这个逻辑很重要，现在不要着急往下看，先回顾一下整个推理过程和最后的思路，好好想想有什么不同？……至此，我们还缺少一个非常关键的信息，就是下面的一点。第四点：最小频率相同的key可能有多个。这个时候把这批数据中缓存时间最长的那个元素去掉。在这个需求中，我们需要通过freq找到Node，然后操作哈希表HashMap。上面写着【multiplekeyshavethesameminimumfreq】，也就是说，通过minFreq，可以查询到多个Node。所以哈希表HashMap应该是这样的：HashMap>。你能理解吗？一个坑下面，挂着一串节点。此时的问题就变成了：我们应该用什么集合来保存这个Node对象呢？别着急，我们继续分析。我们先搞清楚这个集合需要满足什么条件。当我们通过minFreq获取到这个集合时，也就是队列满了。当我们要从这个集合中删除数据时，首先，当我们需要删除Node.因为这个集合中包含了访问频率相同的数据，所以希望可以对这批数据进行定时，这样可以快速删除等待时间最长的Node。有序且有时间顺序，可以快速找到删除时间最长的key。LinkedList，一个双向链表，可以满足这个要求吧？另外，在大多数情况下，当一个Node被访问时，它的频率必然会增加一个。所以访问Node时也要考虑。例如下面的例子：假设最小访问频率，minFreq=5，5的坑对应3个Node对象。此时，我想访问value=b的对象，那么这个对象就会从minFreq=5的值中移除。然后将频率加一，即5+1=6。加入到minFreq=6的值集合中，会是这样：也就是说，我们要支持任意节点的快速删除。LinkedList不支持快速删除任意节点，需要遍历。当然你也可以自己做一个满足要求的MySelfLinkedList。但是在Java集合类中，其实有一个集合满足上面说的顺序，并且支持快速删除。那就是LinkedHashSet，它是一个基于LinkedHashMap的有序的、去重的集合列表。底层还是一个Map，删除Map中指定元素的复杂度为O(1)。所以，HashMap就是HashMap。综上所述。我们需要两个HashMap，分别是HashMapHashMap>，然后需要维护一个最小访问频率，minFreq。哦，对了，还有一个参数记录缓存支持的最大容量，capacity。然后，走了。有朋友肯定会问：你给了我一份代码吗？这些分析出来之后，代码就慢慢自己出来了。这段代码应该是大部分面试官在问LFU的时候最想看到的代码。另外，关于LFU出现在面试环节，突然想起一个笑话，觉得有一点道理：面试官要，我就做两个数的和。如果我不要你，我会让你写LFU。这里我主要是引导大家理清思路，思路清晰后再写代码。就算你在面试的时候没有写出没有bug的代码，也基本是一样的。所以这里就不给出具体的代码实现了。网上有很多搜索。关键是理清思路。这东西就像你的作品。关键是把需求梳理清楚，然后想想代码长什么样子。至于具体的写法，到处贴也不是不可以。或者，把设计文档写出来，代码实现的时候让小弟们跟着你的思路走。你应该把工作精力放在更值得花的地方：比如战需求、写文档、写周报、写PPT、舔领导等等……既然Dubbo的LFU来了，你应该明白什么是LFU了吧。下面我给大家介绍下Dubbo中的LFU。它的实现方案并没有采用我们前面分析的方案。它另辟蹊径，想出了一个新花样。它是如何实现的？我会为你设置的。Dubbo在2.7.7版本之后支持LFU，所以如果想在本地测试，需要在这个版本之后导入Maven依赖。这里我直接pull下来dubbo源码，然后看Master分支的代码。首先看它的数据结构：它有一个Map，就是存储的key和Nodes的映射关系。然后是一个freqTable字段，它的数据结构是一个数组，我们没有看到一个叫minFreq的字段。当我的LFUCache定义如下：newLFUCache<>(5,0.2f);表示缓存容量为5，当满了，“优化”5*0.2个对象，即从缓存对象中踢出1个对象。从Debug模式看，它的结构如下：我们先主要关注freqTable字段。下面标①的地方，表示是一个长度为capacity+1的数组，即长度为6，每个位置都有一个新的CacheDeque对象。标出②的地方，一个单向链表的维护动作就完成了：freqTable是干什么用的？以下三行代码为例：cache.put("why",18);缓存.get("为什么");缓存.get("为什么");第一行执行完后，why元素放在freqTable的第一个坑，即数组的index=0：第二行执行完成后，why元素放在freqTable的第二个坑freqTable:第三行执行完成后，为什么这个元素放在freqTable的第三个洞里：有什么感觉吗？在freqTable数组中，每个坑位对应不同的频率，我给大家做个图：比如d和c放在index=3处，表示在缓存中访问d和c的频率是4次。但是谁停留的时间更长，d还是c？不知道，只好看源码删除元素，是删除last还是first，谁被删除了，就停留在这个频率最久。答案就隐藏在它的eviction方法中：org.apache.dubbo.common.utils.LFUCache#proceedEviction从数组的第一个坑开始遍历数组，如果这个坑下有挂链表，则开始遍历连续移动划分头节点，直到驱逐出指定数量的元素。去掉头节点，所以，d是这个频率中最长的时间。基于这张图，假设现在队列已经满了，那么下一步就是“优化”why节点：这就是Dubbo中LFU实现的核心思想。它非常聪明，根据数组的顺序，来表示元素被访问的频率。不过细细品味之后，大家有没有想过这样一个问题，当我访问缓存中元素的次数大于freqTable数组的长度时，会出现什么神奇的现象呢？给大家看一下代码：虽然mx元素的访问次数远高于why元素，但这两个元素最终都在freqTable数组的最后一个坑里。也就是说，会有这样一个场景：好，我问你一个问题：假设，在这种情况下，要淘汰元素，淘汰谁？必须按照头节点即why节点的顺序进行淘汰。接下来关注一下，我再问一个问题：假设为什么这个时候lucky又被访问了，然后又来了一个新元素，触发了淘汰策略，淘汰谁呢？为什么会在这个坑下成为链表的最后一个节点，从而避免下一次淘汰。消除了mx元素。这个东西一下子从LFU变成了LRU。在同一个实现中，同时存在LFU和LRU。这东西的学问很复杂。我就问你6不6？因此，这是Dubbo的LFU算法实现的劣势。这个缺点是由它的设计理念和数据结构决定的。如果要避免这个问题，我觉得有点麻烦，得推翻。所以我只是在这里向你描述这个问题的存在。那么，Dubbo的LFU的实现还有一个神奇的地方。我认为这纯粹是一个BUG。我仍然为您制作一个测试用例：@TestvoidtestPutAndGet(){LFUCachecache=newLFUCache<>(5,0.2f);对于(inti=0;i<5;i++){缓存。放（我+“”，我）;缓存.get(i+"");}cache.put("为什么",18);整数why=cache.get("why");System.out.println("why="+why);}在一个容量为5的LFUCache中，我先往里面放了5个元素，put之后再获取每个元素，这样每个元素的出现频率就变成了2。然后，这时候我在里面放了一个why，拿出来why就没了。你有什么样的缓存？刚放进去的东西马上就要用了，拿到手就没了。这不是BUG吗？问题出在它的put方法上：将标①的地方放入缓存，放好后判断是否会触发淘汰机制，然后删除标②处的元素。前面提到淘汰策略，proceedEviction方法，从freqTable数组的第一个坑开始遍历数组。如果这个坑下面挂着一个链表，那么它会继续移除头结点，直到驱逐出指定的个数。元素。所以，在我刚才的示例代码中，刚刚放入了why元素，它的频率为1，放在了freqTable数组的第0个位置。玩完看一看，淘汰机制被触发了，让proceedEviction方法看看应该淘汰谁。你说，这不是巧合吗，为什么直接被淘汰了，因为它访问频率最低。所以，当你马上去获取“为什么”的时候，你是获取不到的。这里的逻辑是有缺陷的。不应采用“先放新要素，后判断容量，满则触发淘汰机制”的实施方案。而是应该采用“先判断容量，满了触发淘汰机制，最后放新元素”的方案。也就是我需要改变这两行代码的位置：再次执行测试用例，就不会出问题了：咦，你猜这是什么？这不是为开源项目贡献源代码的好机会吗？所以...https://github.com/apache/dub...有个提pr的小细节。我悄悄告诉你：合并不合并无所谓。重要的是用英文提问，就算是中文一键翻译也要贴，框要满，档次要提高……至于完结，不合并的话，说明我没有仔细考虑，而且是新材料。如果合并，可以在简历上写：熟练使用Dubbo，并为其贡献过源码。到时候如果我脸皮再厚点，我也可以这样写：阅读了Apache顶级开源项目的源码，多次为它贡献核心源码，写了一系列博文加深我的理解学习感想……不能说了，剩下的就是自己体会了！最后，本文到此结束。如果对你有帮助，请给我一个免费的点赞，是不是太过分了？
