共计 5318 个字符，预计需要花费 14 分钟才能阅读完成。
(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 失去的计数后果
- 如果在以后分钟工夫戳内，counter 不变
- 如果不在以后分钟工夫戳内，每过 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 时，才减少 counterp取决于以后 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…
正文完
