会将数据D误认为将来最有可能被访问到的数据。
Redis
作者曾想改进LRU
算法,但发现Redis
的LRU
算法受制于随机采样数maxmemory_samples
,在maxmemory_samples
等于10的情况下已经很接近于理想的LRU
算法性能,也就是说,LRU
算法本身已经很难再进一步了。
于是,将思路回到原点,淘汰算法的本意是保留那些将来最有可能被再次访问的数据,而LRU
算法只是预测最近被访问的数据将来最有可能被访问到。我们可以转变思路,采用一种LFU(Least Frequently Used)
算法,也就是最频繁被访问的数据将来最有可能被访问到。在上面的情况中,根据访问频繁情况,可以确定保留优先级:B>A>C=D。
在LFU
算法中,可以为每个key维护一个计数器。每次key被访问的时候,计数器增大。计数器越大,可以约等于访问越频繁。
上述简单算法存在两个问题:
第一个问题很好解决,可以借鉴LRU
实现的经验,维护一个待淘汰key的pool。第二个问题的解决办法是,记录key最后一个被访问的时间,然后随着时间推移,降低计数器。
Redis
对象的结构如下:
在LRU
算法中,24 bits的lru
是用来记录LRU time
的,在LFU
中也可以使用这个字段,不过是分成16 bits与8 bits使用:
高16 bits用来记录最近一次计数器降低的时间ldt
,单位是分钟,低8 bits记录计数器数值counter
。
Redis
4.0之后为maxmemory_policy
淘汰策略添加了两个LFU
模式:
还有2个配置可以调整LFU
算法:
lfu-log-factor
可以调整计数器counter
的增长速度,lfu-log-factor
越大,counter
增长的越慢。
lfu-decay-time
是一个以分钟为单位的数值,可以调整counter
的减少速度
在lookupKey
中:
当采用LFU
策略时,updateLFU
更新lru
:
首先,LFUDecrAndReturn
对counter
进行减少操作:
函数首先取得高16 bits的最近降低时间ldt
与低8 bits的计数器counter
,然后根据配置的lfu_decay_time
计算应该降低多少。
LFUTimeElapsed
用来计算当前时间与ldt
的差值:
具体是当前时间转化成分钟数后取低16 bits,然后计算与ldt
的差值now-ldt
。当ldt > now
时,默认为过了一个周期(16 bits,最大65535),取值65535-ldt+now
。
然后用差值与配置lfu_decay_time
相除,LFUTimeElapsed(ldt) / server.lfu_decay_time
,已过去n个lfu_decay_time
,则将counter
减少n,counter - num_periods
。
增长函数LFULogIncr
如下:
counter
并不是简单的访问一次就+1,而是采用了一个0-1之间的p因子控制增长。counter
最大值为255。取一个0-1之间的随机数r与p比较,当r<p
时,才增加counter
,这和比特币中控制产出的策略类似。p取决于当前counter
值与lfu_log_factor
因子,counter
值与lfu_log_factor
因子越大,p越小,r<p
的概率也越小,counter
增长的概率也就越小。增长情况如下:
可见counter
增长与访问次数呈现对数增长的趋势,随着访问次数越来越大,counter
增长的越来越慢。
另外一个问题是,当创建新对象的时候,对象的counter
如果为0,很容易就会被淘汰掉,还需要为新生key设置一个初始counter
,createObject
:
counter
会被初始化为LFU_INIT_VAL
,默认5。
pool算法就与LRU
算法一致了:
计算idle
时有所不同:
使用了255-LFUDecrAndReturn(o)
当做排序的依据。