Redis中LFU算法的深入分析
前言
在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(LeastFrequentlyUsed)算法，也就是最频繁被访问的数据将来最有可能被访问到。在上面的情况中，根据访问频繁情况，可以确定保留优先级：B>A>C=D。
Redis中的LFU思路
在LFU算法中，可以为每个key维护一个计数器。每次key被访问的时候，计数器增大。计数器越大，可以约等于访问越频繁。
上述简单算法存在两个问题：
- 在LRU算法中可以维护一个双向链表，然后简单的把被访问的节点移至链表开头，但在LFU中是不可行的，节点要严格按照计数器进行排序，新增节点或者更新节点位置时，时间复杂度可能达到O(N)。
- 只是简单的增加计数器的方法并不完美。访问模式是会频繁变化的，一段时间内频繁访问的key一段时间之后可能会很少被访问到，只增加计数器并不能体现这种趋势。
第一个问题很好解决，可以借鉴LRU实现的经验，维护一个待淘汰key的pool。第二个问题的解决办法是，记录key最后一个被访问的时间，然后随着时间推移，降低计数器。
Redis对象的结构如下：
typedefstructredisObject{
unsignedtype:4;
unsignedencoding:4;
unsignedlru:LRU_BITS;/*LRUtime(relativetogloballru_clock)or
*LFUdata(leastsignificant8bitsfrequency
*andmostsignificant16bitsaccesstime).*/
intrefcount;
void*ptr;
}robj;
在LRU算法中，24bits的lru是用来记录LRUtime的，在LFU中也可以使用这个字段，不过是分成16bits与8bits使用：
16bits8bits +----------------+--------+ +Lastdecrtime|LOG_C| +----------------+--------+
高16bits用来记录最近一次计数器降低的时间ldt，单位是分钟，低8bits记录计数器数值counter。
LFU配置
Redis4.0之后为maxmemory_policy淘汰策略添加了两个LFU模式：
- volatile-lfu：对有过期时间的key采用LFU淘汰算法
- allkeys-lfu：对全部key采用LFU淘汰算法
还有2个配置可以调整LFU算法：
lfu-log-factor10 lfu-decay-time1
lfu-log-factor可以调整计数器counter的增长速度，lfu-log-factor越大，counter增长的越慢。
lfu-decay-time是一个以分钟为单位的数值，可以调整counter的减少速度
源码实现
在lookupKey中:
robj*lookupKey(redisDb*db,robj*key,intflags){
dictEntry*de=dictFind(db->dict,key->ptr);
if(de){
robj*val=dictGetVal(de);
/*Updatetheaccesstimefortheageingalgorithm.
*Don'tdoitifwehaveasavingchild,asthiswilltrigger
*acopyonwritemadness.*/
if(server.rdb_child_pid==-1&&
server.aof_child_pid==-1&&
!(flags&LOOKUP_NOTOUCH))
{
if(server.maxmemory_policy&MAXMEMORY_FLAG_LFU){
updateLFU(val);
}else{
val->lru=LRU_CLOCK();
}
}
returnval;
}else{
returnNULL;
}
}
当采用LFU策略时，updateLFU更新lru：
/*UpdateLFUwhenanobjectisaccessed.
*Firstly,decrementthecounterifthedecrementtimeisreached.
*Thenlogarithmicallyincrementthecounter,andupdatetheaccesstime.*/
voidupdateLFU(robj*val){
unsignedlongcounter=LFUDecrAndReturn(val);
counter=LFULogIncr(counter);
val->lru=(LFUGetTimeInMinutes()<<8)|counter;
}
降低LFUDecrAndReturn
首先，LFUDecrAndReturn对counter进行减少操作：
/*IftheobjectdecrementtimeisreacheddecrementtheLFUcounterbut
*donotupdateLFUfieldsoftheobject,weupdatetheaccesstime
*andcounterinanexplicitwaywhentheobjectisreallyaccessed.
*Andwewilltimeshalvethecounteraccordingtothetimesof
*elapsedtimethanserver.lfu_decay_time.
*Returntheobjectfrequencycounter.
*
*Thisfunctionisusedinordertoscanthedatasetforthebestobject
*tofit:aswecheckforthecandidate,weincrementallydecrementthe
*counterofthescannedobjectsifneeded.*/
unsignedlongLFUDecrAndReturn(robj*o){
unsignedlongldt=o->lru>>8;
unsignedlongcounter=o->lru&255;
unsignedlongnum_periods=server.lfu_decay_time?LFUTimeElapsed(ldt)/server.lfu_decay_time:0;
if(num_periods)
counter=(num_periods>counter)?0:counter-num_periods;
returncounter;
}
函数首先取得高16bits的最近降低时间ldt与低8bits的计数器counter，然后根据配置的lfu_decay_time计算应该降低多少。
LFUTimeElapsed用来计算当前时间与ldt的差值：
/*Returnthecurrenttimeinminutes,justtakingtheleastsignificant
*16bits.ThereturnedtimeissuitabletobestoredasLDT(lastdecrement
*time)fortheLFUimplementation.*/
unsignedlongLFUGetTimeInMinutes(void){
return(server.unixtime/60)&65535;
}
/*Givenanobjectlastaccesstime,computetheminimumnumberofminutes
*thatelapsedsincethelastaccess.Handleoverflow(ldtgreaterthan
*thecurrent16bitsminutestime)consideringthetimeaswrapping
*exactlyonce.*/
unsignedlongLFUTimeElapsed(unsignedlongldt){
unsignedlongnow=LFUGetTimeInMinutes();
if(now>=ldt)returnnow-ldt;
return65535-ldt+now;
}
具体是当前时间转化成分钟数后取低16bits，然后计算与ldt的差值now-ldt。当ldt>now时，默认为过了一个周期(16bits，最大65535)，取值65535-ldt+now。
然后用差值与配置lfu_decay_time相除，LFUTimeElapsed(ldt)/server.lfu_decay_time，已过去n个lfu_decay_time，则将counter减少n，counter-num_periods。
增长LFULogIncr
增长函数LFULogIncr如下：
/*Logarithmicallyincrementacounter.Thegreateristhecurrentcountervalue
*thelesslikelyisthatitgetsreallyimplemented.Saturateitat255.*/
uint8_tLFULogIncr(uint8_tcounter){
if(counter==255)return255;
doubler=(double)rand()/RAND_MAX;
doublebaseval=counter-LFU_INIT_VAL;
if(baseval<0)baseval=0;
doublep=1.0/(baseval*server.lfu_log_factor+1);
if(r
counter并不是简单的访问一次就+1，而是采用了一个0-1之间的p因子控制增长。counter最大值为255。取一个0-1之间的随机数r与p比较，当r
+--------+------------+------------+------------+------------+------------+
|factor|100hits |1000hits |100Khits |1Mhits |10Mhits |
+--------+------------+------------+------------+------------+------------+
|0 |104 |255 |255 |255 |255 |
+--------+------------+------------+------------+------------+------------+
|1 |18 |49 |255 |255 |255 |
+--------+------------+------------+------------+------------+------------+
|10 |10 |18 |142 |255 |255 |
+--------+------------+------------+------------+------------+------------+
|100 |8 |11 |49 |143 |255 |
+--------+------------+------------+------------+------------+------------+
可见counter增长与访问次数呈现对数增长的趋势，随着访问次数越来越大，counter增长的越来越慢。
新生key策略
另外一个问题是，当创建新对象的时候，对象的counter如果为0，很容易就会被淘汰掉，还需要为新生key设置一个初始counter，createObject:
robj*createObject(inttype,void*ptr){
robj*o=zmalloc(sizeof(*o));
o->type=type;
o->encoding=OBJ_ENCODING_RAW;
o->ptr=ptr;
o->refcount=1;
/*SettheLRUtothecurrentlruclock(minutesresolution),or
*alternativelytheLFUcounter.*/
if(server.maxmemory_policy&MAXMEMORY_FLAG_LFU){
o->lru=(LFUGetTimeInMinutes()<<8)|LFU_INIT_VAL;
}else{
o->lru=LRU_CLOCK();
}
returno;
}
counter会被初始化为LFU_INIT_VAL，默认5。
pool
pool算法就与LRU算法一致了：
if(server.maxmemory_policy&(MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_LFU)||
server.maxmemory_policy==MAXMEMORY_VOLATILE_TTL)
计算idle时有所不同：
}elseif(server.maxmemory_policy&MAXMEMORY_FLAG_LFU){
/*WhenweuseanLRUpolicy,wesortthekeysbyidletime
*sothatweexpirekeysstartingfromgreateridletime.
*HoweverwhenthepolicyisanLFUone,wehaveafrequency
*estimation,andwewanttoevictkeyswithlowerfrequency
*first.Soinsidethepoolweputobjectsusingtheinverted
*frequencysubtractingtheactualfrequencytothemaximum
*frequencyof255.*/
idle=255-LFUDecrAndReturn(o);
使用了255-LFUDecrAndReturn(o)当做排序的依据。
参考链接
- RandomnotesonimprovingtheRedisLRUalgorithm
- UsingRedisasanLRUcache
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对毛票票的支持。