(1) LFU源码解读

LFU 算法的启用,是通过设置 Redis 配置文件 redis.conf 中的 maxmemory 和 maxmemory-policy。

LFU 算法的实现能够分成三局部内容,别离是键值对拜访频率记录、键值对拜访频率初始化和更新,以及LFU算法淘汰数据。

(1.1) 键值对拜访频率记录

每个键值对的值都对应了一个 redisObject 构造体,其中有一个 24 bits 的 lru 变量。

LRU 算法和 LFU 算法并不会同时应用。为了节俭内存开销,Redis 源码就复用了 lru 变量来记录 LFU 算法所需的拜访频率信息。

记录LFU算法的所需信息时,它会用24 bits中的低8 bits作为计数器,来记录键值对的拜访次数,同时它会用24 bits中的高16 bits,记录拜访的工夫戳。

      |<---拜访工夫戳--->|< 计数器 >|            16 bits      8 bits      +----------------+--------+      + Last decr time | LOG_C  |      +----------------+--------+            

(1.2) 键值对拜访频率初始化和更新

(1.2.1) 初始化

键值对 lru变量初始化是在 创立redisObject调用 createObject 函数时实现的。

次要分2步:
第一部是 lru 变量的高16位,是以1分钟为精度的 UNIX 工夫戳。(LFUGetTimeInMinutes)
第二部是 lru 变量的低8位,被设置为宏定义 LFU_INIT_VAL,默认值为 5。

源码如下

// file: src/object.c/* * 创立一个redisObject对象 * * @param type redisObject的类型 * @param *ptr 值的指针 */robj *createObject(int type, void *ptr) {    // 为redisObject构造体分配内存空间    robj *o = zmalloc(sizeof(*o));      // 省略局部代码     // 将lru字段设置为以后的 lruclock(分钟分辨率),或者 LFU 计数器。     // 判断内存过期策略    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {        // 对应lfu         // LFU_INIT_VAL=5 对应二进制是 0101         // 或运算  高16位是工夫,低8位是次数, LFU_INIT_VAL = 5        o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;    } else {        // 对应lru         o->lru = LRU_CLOCK();    }    return o;}

counter会被初始化为LFU_INIT_VAL,默认5。

// file: src/evict.c/* ---------------------------------------------------------------------------- * LFU (Least Frequently Used) implementation. *  * 为了实现 LFU(最不罕用)驱赶策略,咱们在每个对象中总共有 24 位空间,因为咱们为此目标从新应用了 LRU 字段。 * * 咱们将 24 位分成两个字段: * *          16 bits      8 bits *     +----------------+--------+ *     + Last decr time | LOG_C  | *     +----------------+--------+ * * LOG_C 是提供拜访频率批示的对数计数器。  * 然而,这个字段也必须递加,否则过来常常拜访的键将永远放弃这样的排名,而咱们心愿算法适应拜访模式的变动。 * * 因而,残余的 16 位用于存储“递加工夫”, * 这是一个精度升高的 Unix 工夫(咱们将 16 位工夫转换为分钟,因为咱们不关怀回绕), * 其中 LOG_C 计数器减半 如果它具备高值,或者如果它具备低值则只是递加。 * * 新key不会从零开始,以便可能在被淘汰之前收集一些拜访,因而它们从 COUNTER_INIT_VAL 开始。 * COUNTER_INIT_VAL = 5 * 因而从5(或具备较小值)开始的键在拜访时递增的可能性十分高。 * * 在递加期间,如果对数计数器的以后值大于5的两倍,则对数计数器的值减半,否则它只减一。 *  * --------------------------------------------------------------------------*//*  * 以分钟为单位返回以后工夫,只取最低无效16位。  * 返回的工夫适宜存储为 LFU 实现的 LDT(最初递加工夫)。 */unsigned long LFUGetTimeInMinutes(void) {    // 65535 = 2^16 - 1 对应二进制是 1111 1111 1111 1111    // (server.unixtime/60) & 1111 1111 1111 1111    return (server.unixtime/60) & 65535;}

(1.2.2) 更新LFU值

当一个键值对被拜访时,Redis 会调用 lookupKey 函数进行查找。lookupKey 函数会调用 updateLFU 函数来更新键值对的拜访频率。

// file: src/db.c/*  * 拜访对象时更新 LFU。 * 首先,如果达到递加工夫,则递加计数器。 * 而后以对数形式递增计数器,并更新拜访工夫。 */void updateLFU(robj *val) {    // 获取计数器    unsigned long counter = LFUDecrAndReturn(val);    // 更新计数器    counter = LFULogIncr(counter);    val->lru = (LFUGetTimeInMinutes()<<8) | counter;}
(1.2.2.1) 递加计数器-LFUDecrAndReturn
/* * 如果达到对象递加工夫,则 递加LFU计数器 但 不更新对象的LFU字段, * 咱们在真正拜访对象时以显式形式更新拜访工夫和计数器。 *  * 并且咱们将依据 通过的工夫/server.lfu_decay_time 将计数器减半。 * 返回对象频率计数器。 * redis.conf配置文件里 lfu-decay-time 默认是 1 * And we will times halve the counter according to the times of * elapsed time than server.lfu_decay_time. *  * 此函数用于扫描数据集以获得最佳对象 *  适宜:当咱们查看候选对象时,如果须要,咱们会递加扫描对象的计数器。 */unsigned long LFUDecrAndReturn(robj *o) {    // 高16位存的是 上次访问工夫(分钟级的) Last decr time     unsigned long ldt = o->lru >> 8;    // 255 对应二进制 1111 1111     // o->lru & 1111 1111 相当于取低8位的值    // 获取计数器    unsigned long counter = o->lru & 255;    // 0 <= LFUTimeElapsed(ldt) <  65535    // 过了的分钟数 / server.lfu_decay_time    // num_periods 是过了 n轮 衰减工夫(lfu_decay_time)    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;    // 如果通过的轮数不为0 (超过1分钟了)    if (num_periods)         // 如果 n轮衰减 > 拜访次数,counter设置为0,相当于从新开始计算        // 否则,n轮衰减 <= 拜访次数,counter设置为 counter - num_periods,相当于每过1轮衰减工夫(lfu_decay_time),减1        counter = (num_periods > counter) ? 0 : counter - num_periods;    // 如果没有超过1分钟,num_periods=0,间接返回counter    // 如果超过1分钟,num_periods!=0,至多过了1轮衰减工夫(lfu_decay_time)了,更新counter后返回    return counter;}

LFUDecrAndReturn 失去的计数后果

  1. 如果在以后分钟工夫戳内,counter不变
  2. 如果不在以后分钟工夫戳内,每过1轮衰减工夫(lfu_decay_time),counter减1 (代码里是过了num_periods轮,减num_periods)
/*  * 计算过了多少分钟 *  * 给定对象的上次访问工夫,计算自上次访问以来通过的最小分钟数。  * 解决溢出(ldt 大于以后 16 位分钟工夫),将工夫视为正好回绕一次。 *  * @param ldt 上一次拜访的工夫(分钟级) */unsigned long LFUTimeElapsed(unsigned long ldt) {    // 获取分钟级工夫戳    unsigned long now = LFUGetTimeInMinutes();    // 计算过了多少分钟    if (now >= ldt) return now-ldt;    // 实际上now永远是在ldt(上一次拜访工夫之后)    // 然而当初 now < ldt,不合乎预期     // ldt是 (server.unixtime/60) & 1111 1111 1111 1111 失去的,相当于取余,也就是至多过了1轮了     // 假如 ldt = 65534  now = 1,其实过了2分钟    return 65535-ldt+now;}
(1.2.2.2) 更新LFU计数器-LFULogIncr
/*  * 以对数形式递增计数器。 以后计数器值越大,它真正实现的可能性就越小。 在255时饱和。 * * Logarithmically increment a counter.  * The greater is the current counter value * the less likely is that it gets really implemented.  * Saturate it at 255.  */uint8_t LFULogIncr(uint8_t counter) {    // 最大255    if (counter == 255) return 255;    // 获取一个随机数    double r = (double)rand()/RAND_MAX;    // 根底值 = counter - 5    double baseval = counter - LFU_INIT_VAL;    // 最小=0    if (baseval < 0) baseval = 0;    // 取对数     double p = 1.0/(baseval*server.lfu_log_factor+1);    // 随机数 < 对数时,计数器+1    if (r < p) counter++;    return counter;}

counter并不是简略的拜访一次就+1,而是采纳了一个0-1之间的p因子管制增长。

取一个0-1之间的随机数r与p比拟,当r < p时,才减少counter
p取决于以后counter值与lfu_log_factor因子,counter值与lfu_log_factor因子越大,p越小,r<p的概率也越小,counter增长的概率也就越小。

增长状况如下

+--------+------------+------------+------------+------------+------------+| factor | 100 hits   | 1000 hits  | 100K hits  | 1M hits    | 10M hits   |+--------+------------+------------+------------+------------+------------+| 0      | 104        | 255        | 255        | 255        | 255        |+--------+------------+------------+------------+------------+------------+| 1      | 18         | 49         | 255        | 255        | 255        |+--------+------------+------------+------------+------------+------------+| 10     | 10         | 18         | 142        | 255        | 255        |+--------+------------+------------+------------+------------+------------+| 100    | 8          | 11         | 49         | 143        | 255        |+--------+------------+------------+------------+------------+------------+

(1.3) LFU算法淘汰数据

次要有三步
第一步,调用 getMaxmemoryState 函数计算待开释的内存空间;
第二步,调用 evictionPoolPopulate 函数随机采样键值对,并插入到待淘汰汇合 EvictionPoolLRU 中;
第三步,遍历待淘汰汇合 EvictionPoolLRU,抉择理论被淘汰数据,并删除。

参考资料

https://weikeqin.com/tags/redis/

Redis源码分析与实战 学习笔记 Day16 16 | LFU算法和其余算法相比有劣势吗?
https://time.geekbang.org/col...