本文主要介绍Redis中LFU算法的相关信息,并通过示例代码进行了详细介绍。对大家学习或使用Redis有一定的参考价值。有需要的话一起学吧。
前言
在Redis的LRU算法中,据说LRU在以下情况下有缺陷:
~ ~ ~ ~ ~ A ~ ~ ~ ~ ~ A ~ ~ ~ ~ ~ A ~ ~ ~ ~ ~ A ~ ~ ~ ~ A ~ ~ ~ ~ ~ A ~ ~ ~ ~ ~ A ~ ~ ~ ~ ~ A ~ ~ ~
~ ~ B ~ ~ B ~ ~ B ~ ~ B ~ ~ B ~ ~ B ~ ~ B ~ ~ B ~ ~ B ~ ~ B ~ ~ B ~ ~ B ~ ~ B ~ ~ B ~ |
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ C ~ ~ ~ ~ ~ ~ ~ C ~ ~ ~ ~ ~ ~ ~ ~ ~ C ~ ~ ~ ~ ~ ~ ~ C ~ ~ ~ ~ ~ ~ |
~ ~ ~ ~ ~ D ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ D ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ D ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ D |
把社交数据D误认为未来最有可能被访问的数据。
Redis的作者想改进LRU算法,但发现Redis的LRU算法受制于随机采样数maxmemory_samples,当maxmemory_samples等于10时,非常接近理想的LRU算法性能。也就是说,LRU算法本身很难再往前走了。
所以,回想一下原点,淘汰算法的初衷是保留那些未来最有可能再次被访问的数据,而LRU算法只是预测最近被访问的数据未来最有可能被访问。我们可以换个思路,采用一种LFU(最少使用)算法,即最频繁访问的数据最有可能在未来被访问。上述情况下,根据访问的频繁程度,可以确定保留优先级:BAC=D。
Redis中的LFU思路
在LFU算法中,可以为每个密钥维护一个计数器。每次访问密钥时,计数器都会递增。计数器越大,访问越频繁。
上面的简单算法有两个问题:
在LRU算法中,可以维护一个双向链表,然后简单地将访问过的节点移到链表的开头,但在LFU是不可行的。节点要严格按照计数器排序,添加新节点或更新节点位置时时间复杂度可能达到O(N)。
简单的增加计数器的方法并不完美。访问模式会经常改变。在一段时间内频繁访问的键在一段时间后可能很少被访问。仅仅增加计数器并不能反映这个趋势。
第一个问题很容易解决。我们可以借鉴LRU实施的经验,保持一个有待消除的关键点库。第二个问题的解决方案是记录最后一次访问键的时间,然后随着时间的推移减少计数器。
Redis对象的结构如下:
typedef结构redisObject {
无符号类型:4;
无符号编码:4;
无符号LRU:LRU _比特;/* LRU时间(相对于全球lru_clock)或
* LFU数据(最低有效8位频率
*和最高有效的16位访问时间)。*/
int refcount
void * ptr
} robj
在lru算法中,24位的LRU用于记录LRU时间,该字段在LFU也可以使用,但分为16位和8位:
16位8位
- -
上次解密时间| LOG_C |
- -
高16位用于记录最后一次计数器减少的时间ldt(分钟),低8位用于记录计数器值counter。
LFU配置
在Redis4.0之后,为maxmemory_policy消除策略添加了两种LFU模式:
Volatile-lfu:对过期的密钥采用lfu消除算法。
Allkeys-lfu:所有键都采用lfu消去算法。
还有两种配置来调整LFU算法:
lfu-log-因子10
lfu-衰变时间1
lfu-log-factor可以调整计数器的增长率。lfu对数因子越大,计数器增长越慢。
Lfu-decay-time是一个以分钟为单位的值,可以调整计数器的递减速度。
源码实现
在lookupKey中:
robj *lookupKey(redisDb *db,robj *key,int flags) {
dictEntry *de=dictFind(db-dict,key-ptr);
if (de) {
robj * val=dictGetVal(de);
/*更新老化算法的访问时间。
*如果我们有一个节约的孩子,不要这样做,因为这会触发
*一份关于写作的疯狂。*/
if (server.rdb_child_pid==-1
server.aof_child_pid==-1
!(标志LOOKUP_NOTOUCH))
{
if(server . MAXMEMORY _ policy MAXMEMORY _ FLAG _ LFU){
update lfu(val);
}否则{
val-LRU=LRU _时钟();
}
}
返回英国压力单位
}否则{
返回空
}
}
当采用LFU策略时,更新LFU更新lru:
/*当对象被访问时更新LFU .
*首先,如果到达递减时间,则递减计数器。
*然后对数递增计数器,并更新访问时间。*/
void updateLFU(robj *val) {
无符号长整型计数器=LFUDecrAndReturn(val);
counter=LFULogIncr(计数器);
瓦尔-LRU=(lfuggettimeinminutes()8)|计数器;
}
降低LFUDecrAndReturn
首先,LFUDecrAndReturn对计数器进行减少操作:
/*如果达到了对象递减时间,则递减LFU计数器,但是
*不更新对象的LFU字段,我们更新访问时间
*并在对象真正被访问时以显式的方式计数器。
*我们将根据的次数将计数器减半
*运行时间超过server.lfu_decay_time .
*返回对象频率计数器。
*
*使用此函数是为了扫描数据集中的最佳对象
*适合:当我们检查候选人时,我们递增递减
*扫描对象的计数器(如果需要)。*/
无符号长整型LFUDecrAndReturn(robj *o) {
无符号长ldt=o-LRU 8;
无符号长计数器=o-LRU 255;
无符号long num _ periods=服务器。lfu _ decay _ time?LFUTimeElapsed(ldt)/server。lfu _ decay _ time:0;
if (num_periods)
计数器=(周期数计数器)?0:计数器-数量_周期;
返回计数器;
}
函数首先取得高16位的最近降低时间激光放电管(激光放电管)与低8位的计数器计数器,然后根据配置的lfu_decay_time计算应该降低多少。
LFUTimeElapsed用来计算当前时间与激光放电管(激光放电管)的差值:
/*返回以分钟为单位的当前时间,只取最不重要的时间
* 16位。返回的时间适合存储为LDT(最后一次减量
*时间)用于LFU实施。*/
无符号长整型lfuggettimeinminutes(void){
回程(server . UNIX time/60)65535;
}
/*给定对象的上次访问时间,计算最小分钟数
*自上次访问以来经过的时间。句柄溢出(ldt大于
*当前16位分钟时间)将时间视为回绕
*恰好一次。*/
无符号长整型LFUTimeElapsed(无符号长整型ldt) {
unsigned long now=lfuggettimeinminutes();
if (now=ldt)返回now-ldt;
现在返回65535-ldt;
}
具体是当前时间转化成分钟数后取低16位,然后计算与激光放电管(激光放电管)的差值现在-ldt。当ldt now时,默认为过了一个周期(16位,最大65535),取值65535-ldt现在。
然后用差值与配置lfu_decay_time相除,LFUTimeElapsed(ldt)/server。lfu _ decay _ time,已过去n个lfu_decay_time,则将计数器减少n,计数器的周期数。
增长LFULogIncr
增长函数LFULogIncr如下:
/*对数递增计数器。当前计数器值越大
*它被真正实施的可能性越小。在255度饱和。*/
uint 8 _ t lflogincr(uint 8 _ t计数器){
如果(计数器==255)返回255;
double r=(double)RAND()/RAND _ MAX;
双基数VAL=反LFU _初始化_ VAL
if(基值0)基值=0;
double p=1.0/(base val * server。lfu _ log _ factor 1);
中频计数器;
返回计数器;
}
计数器并不是简单的访问一次就1,而是采用了一个0-1之间的p因子控制增长柜台。最大值为255。取一个0-1之间的随机数r与p比较,当菲律宾共和国时,才增加计数器,这和比特币中控制产出的策略类似100便士取决于当前计数器值与lfu _ log _因子因子,计数器值与lfu _ log _因子因子越大,p越小,rp的概率也越小,计数器增长的概率也就越小。增长情况如下:
- - - - - -
|因子| 100点击量| 1000点击量| 10万点击量| 1M点击量| 10米点击量|
- - - - - -
| 0 | 104 | 255 | 255 | 255 | 255 |
- - - - - -
| 1 | 18 | 49 | 255 | 255 | 255 |
- - - - - -
| 10 | 10 | 18 | 142 | 255 | 255 |
- - - - - -
| 100 | 8 | 11 | 49 | 143 | 255 |
- - - - - -
可见计数器增长与访问次数呈现对数增长的趋势,随着访问次数越来越大,计数器增长的越来越慢。
新生key策略
另外一个问题是,当创建新对象的时候,对象的计数器如果为0,很容易就会被淘汰掉,还需要为新生键设置一个初始计数器,创建对象:
robj *createObject(int类型,void *ptr) {
robj * o=zmalloc(sizeof(* o));
o型=类型;
o编码=OBJ _编码_原始;
o-ptr=ptr;
o-ref计数=1;
/*将LRU设置为当前lruclock(分钟分辨率),或
*或者LFU柜台。*/
如果(服务器。MAXMEMORY _ policy MAXMEMORY _ FLAG _ LFU){
LRU=(lfuggettimeinminutes()8)| LFU _初始化_瓦尔;
}否则{
LRU=LRU _时钟();
}
返回o;
}
计数器会被初始化为LFU初始化值,默认5。
pool
泳池算法就与LRU算法一致了:
如果(服务器。最大内存策略(最大内存标志LRU |最大内存标志LFU)| |
服务器。MAXMEMORY _ policy==MAXMEMORY _ VOLATILE _ TTL)
计算闲置的时有所不同:
} else if(服务器。MAXMEMORY _ policy MAXMEMORY _ FLAG _ LFU){
/*当我们使用LRU策略时,我们按照空闲时间对键进行排序
*以便我们从更长的空闲时间开始使密钥过期。
*但是,当策略是LFU策略时,我们有一个频率
*估计,我们想驱逐频率较低的键
*首先。所以在池子里,我们用倒置的
*最大频率减去实际频率
*频率为255。*/
idle=255-LFUDecrAndReturn(o);
使用了255-LFUDecrAndReturn(o)当做排序的依据。
参考链接
关于改进雷迪斯LRU算法的随笔
使用雷迪斯作为LRU缓存
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我们的支持。
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。