什么是Redis-LFU

这篇文章主要讲解了“什么是Redis-LFU”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“什么是Redis-LFU”吧!

LFU是redis中被使用的一个淘汰策略,当然redis实现的是非常的巧妙,它的全称是Least  Frequently  Used,即用的次数少的被淘汰。它相比于LRU(大家可以自行了解,后续博文会对它进行补充)更精确通过读redis相关源码(version:6.2)发现,每次操作db的时候都会调用 robj *lookupKeyredisDb *db, robj *key, int flags)函数,这个函数是这样实现的

robj *lookupKeyredisDb *db, robj *key, int flags) {
    dictEntry *de = dictFinddb->dict,key->ptr);
    if de) {
        robj *val = dictGetValde);

        /* 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) {
                updateLFUval);
            } else {
                val->lru = LRU_CLOCK);
            }
        }
        return val;
    } else {
        return NULL;
    }
}

当在字典中发现存在这个key的时候&它没有开启一个子线程去做saving操作的时候&配了最大内存策略&MAXMEMORY_FLAG_LFU 它都会updateLFU,让我们看看updateLFU函数是怎么实现的吧,先上代码:

void updateLFUrobj *val) {
    unsigned long counter = LFUDecrAndReturnval);
    counter = LFULogIncrcounter);
    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 LFUDecrAndReturnrobj *o) {
    unsigned long ldt = o->lru >> 8;
    unsigned long counter = o->lru & 255;
    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsedldt) / 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 updateLFUrobj *val) {
    unsigned long counter = LFUDecrAndReturnval);   // 递减操作
    counter = LFULogIncrcounter);  // 递增操作
    val->lru = LFUGetTimeInMinutes)<<8) | counter; // 生成真正的LFU
}
uint8_t LFULogIncruint8_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 *createObjectint type, void *ptr) {
    robj *o = zmallocsizeof*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

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注