产品中心
前言
在Redis中的LRU算法文中说到，LRU有一个缺陷，在如下情况下：
~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~|
~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~|
~~~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~|
~~~~~D~~~~~~~~~~D~~~~~~~~~D~~~~~~~~~D|
会将数据D误认为将来最有可能被访问到的数据。
Redis作者曾想改进LRU算法，但发现Redis的LRU算法受制于随机采样数maxmemory_samples，在maxmemory_samples等于10的情况下已经很接近于理想的LRU算法性能，也就是说，LRU算法本身已经很难再进一步了。
于是，将思路回到原点，淘汰算法的本意是保留那些将来最有可能被再次访问的数据，而LRU算法只是预测最近被访问的数据将来最有可能被访问到。我们可以转变思路，采用一种LFU(Least Frequently Used)算法，也就是最频繁被访问的数据将来最有可能被访问到。在上面的情况中，根据访问频繁情况，可以确定保留优先级：B>A>C=D。
Redis中的LFU思路
在LFU算法中，可以为每个key维护一个计数器。每次key被访问的时候，计数器增大。计数器越大，可以约等于访问越频繁。
上述简单算法存在两个问题：
第一个问题很好解决，可以借鉴LRU实现的经验，维护一个待淘汰key的pool。第二个问题的解决办法是，记录key最后一个被访问的时间，然后随着时间推移，降低计数器。
Redis对象的结构如下：
LFU配置Redis4.0之后为maxmemory_policy淘汰策略添加了两个LFU模式：
还有2个配置可以调整LFU算法：
源码实现在lookupKey中:
降低LFUDecrAndReturn首先，LFUDecrAndReturn对counter进行减少操作：
增长LFULogIncr增长函数LFULogIncr如下：
新生key策略另外一个问题是，当创建新对象的时候，对象的counter如果为0，很容易就会被淘汰掉，还需要为新生key设置一个初始counter，createObject:
poolpool算法就与LRU算法一致了：
Random notes on improving the Redis LRU algorithm本篇文章到此结束，如果您有相关技术方面疑问可以联系我们技术人员远程解决，感谢大家支持本站！
