redis lru和lfu算法的区别,redis算法详解

redis lru和lfu算法的区别,redis算法详解,Redis中LFU算法的深入分析

本文主要介绍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缓存

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我们的支持。

redis lru和lfu算法的区别,redis算法详解