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

总结

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