LFU算法和其他算法相比有优势吗

(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...

作者:wkq2786130原文地址:https://segmentfault.com/a/1190000043370998

%s 个评论

要回复文章请先登录注册