这篇文章主要讲解了“什么是Redis-LFU”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“什么是Redis-LFU”吧！
LFU是redis中被使用的一个淘汰策略，当然redis实现的是非常的巧妙，它的全称是Least Frequently Used，即用的次数少的被淘汰。它相比于LRU（大家可以自行了解，后续博文会对它进行补充）更精确通过读redis相关源码（version：6.2）发现，每次操作db的时候都会调用 robj *lookupKey(redisDb *db, robj *key, int flags)函数，这个函数是这样实现的
robj *lookupKey(redisDb *db, robj *key, int flags) {
dictEntry *de = dictFind(db->dict,key->ptr);
if (de) {
robj *val = dictGetVal(de);
/* Update the access time for the ageing algorithm.
* Don't do it if we have a saving child, as this will trigger
* a copy on write madness. */
if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
updateLFU(val);
} else {
val->lru = LRU_CLOCK();
}
}
return val;
} else {
return NULL;
}
}
当在字典中发现存在这个key的时候&它没有开启一个子线程去做saving操作的时候&配了最大内存策略&MAXMEMORY_FLAG_LFU 它都会updateLFU，让我们看看updateLFU函数是怎么实现的吧，先上代码：
void updateLFU(robj *val) {
unsigned long counter = LFUDecrAndReturn(val);
counter = LFULogIncr(counter);
val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}
先讲下LFU的结构，这样对理解代码有一定的帮助。LFU像LRU一样都用了24bit去表示，不同的是，LFU用前16bit表示时间，剩余的8bit表示被访问次数，即counter，而LRU用全部的24bit表示时间。表象是结构的区别，其实是内在算法实现上的区别。LRU仅根据时间去判断这个key是否该删除，而LFU是根据时间和访问次数两个因子去确定该key是否被删，从概率上来判断，LFU是更准确的。updateLFU中，最后会算出val的真正的lru，time<<8位是为了给counter留出8bit的位置，然后｜counter，得出正确的var的lfu。这个时候你会问了，那明明是lru，其实在源码中它既可以表示lru，又可以表示lfu，其实它就是24bit的int类型字段。它的定义是这样的
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
int refcount;
void *ptr;
} robj;
下面我们介绍LFU中的几个重要的概念
1.LFU的counter（访问次数）不是一直递增的，它有一个递减策略，它的实现，上源码：
unsigned long LFUDecrAndReturn(robj *o) {
unsigned long ldt = o->lru >> 8;
unsigned long counter = o->lru & 255;
unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
if (num_periods)
counter = (num_periods > counter) ? 0 : counter - num_periods;
return counter;
}
方法中的第1行，
unsigned
long
ldt
=
o
->
lru
>>
8
;
这个是算出最近一次的访问时间，可能这里有人会问，为什么会右移8bit，是因为右边的8位是counter，必须被移出去，才能得到时间。如果你现在左右移都弄不清的话，那么就先复习复习左右移。
第2行
unsigned long counter = o -> lru & 255 ;
这个会算出counter，&255正好把前边的16bit都变成0，同样的话，如果你现在不懂&，请复习复习&。
第3行
unsigned
long
num_periods
=
server
.
lfu_decay_time
?
LFUTimeElapsed
(
ldt
)
/
server
.
lfu_decay_time
:
0
;
它的作用是算出递减num，lfu_decay_time表示lfu递减因子，LFUTimeElaspsed这个函数的作用是算出，当前now和最近一次访问的差，即算出多久没有访问了。然后/递减因子，算出需要counter递减的多少。
最后
if ( num_periods )
counter = ( num_periods > counter ) ? 0 : counter – num_periods ;
return counter ;
算出counter。
2.counter先做递减，然后再做递增，上代码，具体讲解，就看我的注释吧
void updateLFU(robj *val) {
unsigned long counter = LFUDecrAndReturn(val); // 递减操作
counter = LFULogIncr(counter); // 递增操作
val->lru = (LFUGetTimeInMinutes()<<8) | counter; // 生成真正的LFU
}
uint8_t LFULogIncr(uint8_t counter) {
if (counter == 255) return 255; // counter的最大值是255
double r = (double)rand()/RAND_MAX;
double baseval = counter - LFU_INIT_VAL;
if (baseval < 0) baseval = 0;
double p = 1.0/(baseval*server.lfu_log_factor+1);
if (r < p) counter++; // 经过算法运算，r < p才做counter++
return counter;
}
3.redis每次创建obj的时候都会设置LFU或者LRU，当然默认是LRU
robj *createObject(int type, void *ptr) {
robj *o = zmalloc(sizeof(*o));
o->type = type;
o->encoding = OBJ_ENCODING_RAW;
o->ptr = ptr;
o->refcount = 1;
/* Set the LRU to the current lruclock (minutes resolution), or
* alternatively the LFU counter. */
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { // 当设置了最大内存策略和LFU的时候走LFU
o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
} else {
o->lru = LRU_CLOCK();
}
return o;
}
当设置了最大内存策略和LFU的时候走LFU，else走LRU