/

传统的LFU算法

传统的LFU算法，被称为最不频繁使用，根据数据被访问的次数决策是否淘汰。

注意：这种淘汰策略的问题比较明显，比如，某些数据很久未被访问，却不会被淘汰，因为它们之前被访问很多次。

Redis的LFU算法

与传统LFU不同，Redis即统计数据被访问次数，也考虑数据被访问的时间。

//使用16bit作为访问时间、使用8bit作为访问频率
    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). */

void updateLFU(robj *val) {
    unsigned long counter = LFUDecrAndReturn(val);  //增长算法
    counter = LFULogIncr(counter);                  //衰退算法
    val->lru = (LFUGetTimeInMinutes()<<8) | counter;//更新为当前时间
}

unsigned long LFUGetTimeInMinutes(void) {
    return (server.unixtime/60) & 65535;     //获取当前时间/60，转为16bit
}

访问次数衰退算法

unsigned long LFUDecrAndReturn(robj *o) {
    unsigned long ldt = o->lru >> 8;            //取出时间（前16bit）
    unsigned long counter = o->lru & 255;       //取出计数器（后8bit）
    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0; //存活时间/衰退周期，表示衰退数
    if (num_periods)                                                     //如果衰退数=0，即1个周期，counter保持不变。如果衰退数>0，即1个周期，counter下降。
        counter = (num_periods > counter) ? 0 : counter - num_periods;   //衰退数>counter，counter归零。衰退数<=counter，counter=counter-衰退数。
    return counter;
}

unsigned long LFUTimeElapsed(unsigned long ldt) {
    unsigned long now = LFUGetTimeInMinutes(); //获取当前时间
    if (now >= ldt) return now-ldt;     //如果当前时间>ldt，取出存活时间
    return 65535-ldt+now;               //如果ldt>当前时间，取出存活时间（now+65535-ldt）
}

访问次数增长算法

#define LFU_INIT_VAL 5
uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;                //如果counter=255，保持不变。
    double r = (double)rand()/RAND_MAX;            //生成小于1的随机数r
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;                  //如果counter<5，p=1。如果counter>5，p<1。
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    if (r < p) counter++;                          //如果p大于r，counter+1。（即counter值越大增长越慢。）
    return counter;
}

执行驱逐

int performEvictions(void) {
..
        if (server.maxmemory_policy & (MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_LFU) ||
            server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL)                   //LRU、LFU、TTL的驱逐逻辑
        {
            struct evictionPoolEntry *pool = EvictionPoolLRU;

            while(bestkey == NULL) {
                unsigned long total_keys = 0, keys;

                for (i = 0; i < server.dbnum; i++) {
                    db = server.db+i;
                    dict = (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) ?
                            db->dict : db->expires;
                    if ((keys = dictSize(dict)) != 0) {
                        evictionPoolPopulate(i, dict, db->dict, pool);        //驱逐池填充
                        total_keys += keys;
                    }
                }
                if (!total_keys) break; /* No keys to evict. */

                /* Go backward from best to worst element to evict. */
                for (k = EVPOOL_SIZE-1; k >= 0; k--) {
                    if (pool[k].key == NULL) continue;
                    bestdbid = pool[k].dbid;

                    if (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) {
                        de = dictFind(server.db[pool[k].dbid].dict,           //从驱逐池中寻找目标
                            pool[k].key);
                    } else {
                        de = dictFind(server.db[pool[k].dbid].expires,
                            pool[k].key);
                    }

                    /* Remove the entry from the pool. */
                    if (pool[k].key != pool[k].cached)
                        sdsfree(pool[k].key);
                    pool[k].key = NULL;                                       //释放
                    pool[k].idle = 0;

                    if (de) {
                        bestkey = dictGetKey(de);
                        break;
                    } else {
                        /* Ghost... Iterate again. */
                    }
                }
            }
        }
..
}

驱逐池填充

驱逐的基本思路：是随机采样，再根据idle排序，再驱逐。

注意：并不是全库排序，并不是驱逐最古老的数据。

# maxmemory-samples 5      //采样池大小
#define EVPOOL_SIZE 16     //驱逐池大小

struct evictionPoolEntry {
    unsigned long long idle;    /* Object idle time (inverse frequency for LFU) */
    sds key;                    /* Key name. */
    sds cached;                 /* Cached SDS object for key name. */
    int dbid;                   /* Key DB number. */
};

void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {
    int j, k, count;
    dictEntry *samples[server.maxmemory_samples];//采样池

    count = dictGetSomeKeys(sampledict,samples,server.maxmemory_samples); //随机采样
    for (j = 0; j < count; j++) {
        unsigned long long idle;
        sds key;
        robj *o;
        dictEntry *de;

        de = samples[j];         //采样
        key = dictGetKey(de);    //采样

        if (server.maxmemory_policy != MAXMEMORY_VOLATILE_TTL) {
            if (sampledict != keydict) de = dictFind(keydict, key);
            o = dictGetVal(de);  //采样
        }

        if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) {
            idle = estimateObjectIdleTime(o);                            //LRU的idle算法
        } else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
            idle = 255-LFUDecrAndReturn(o);                              //LFU的idle算法
        } else if (server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) {
            idle = ULLONG_MAX - (long)dictGetVal(de);                    //TTL的idle算法
        } else {
            serverPanic("Unknown eviction policy in evictionPoolPopulate()");
        }

        k = 0;
        while (k < EVPOOL_SIZE &&
               pool[k].key &&
               pool[k].idle < idle) k++;   //遍历pool，通过idle确定k。
..

//填充k
        int klen = sdslen(key);
        if (klen > EVPOOL_CACHED_SDS_SIZE) {
            pool[k].key = sdsdup(key);
        } else {
            memcpy(pool[k].cached,key,klen+1);
            sdssetlen(pool[k].cached,klen);
            pool[k].key = pool[k].cached;
        }
        pool[k].idle = idle;
        pool[k].dbid = dbid;
    }
}