Redis 中的 LFU 算法源码解析

2025/4/7 21:17:03 来源：https://blog.csdn.net/qq_41893505/article/details/146581708 浏览: 次关键词：Redis 中的 LFU 算法源码解析

Redis 的 LFU（Least Frequently Used，最不经常使用）淘汰算法主要用于 maxmemory-policy 设置为 allkeys-lfu 或 volatile-lfu 时，以最少使用频率的键进行淘汰。其核心实现涉及到 访问频率计数 和 时间衰减机制，源码主要集中在 src/server.c 和 src/evict.c 文件中。

1. LFU 计数存储

Redis 采用 8-bit 的 LRU 字段 来存储访问频率计数，存储在 robj 结构体的 lru 字段中：

struct redisObject {unsigned type:4;unsigned encoding:4;unsigned lru:LRU_BITS; // 用于 LRU/LFU 计算int refcount;void *ptr;
};

其中 lru 变量的 8-bit 空间被拆分：

前 6-bit（counter）：用于存储访问计数，最大值 63。
后 2-bit（clock）：用于时间衰减计算。

2. 访问计数的计算

LFU 计数在每次访问键时都会递增，但递增方式不是简单 +1，而是使用 对数增长 方式，避免某些键因高访问量而垄断：

unsigned long LFUDecrAndReturn(robj *o) {unsigned long counter = LFUGetCounter(o);if (counter == 0) return 0;if (rand() % (counter + 1) == 0) counter--;LFUSetCounter(o, counter);return counter;
}

计数增长时：

int LFUIncrAndReturn(robj *o) {unsigned long counter = LFUGetCounter(o);if (counter < 63) {if (rand() % (counter + 1) == 0) counter++;}LFUSetCounter(o, counter);return counter;
}

这意味着：

初始时计数增长较快 (1 → 2 → 3…)
计数越高，增长概率越低（符合 对数曲线）
这样可以防止某些高访问量键长期存活。

3. LFU 访问频率的衰减

由于有些数据可能短期内访问频繁，但长期不再被访问，因此 Redis 采用了 时间衰减机制：

每 1 分钟 递减一次访问计数。

使用 2-bit 记录最近访问的时间 lfu_clock，每隔 60s 触发衰减：

#define LFU_INIT_VAL 5 // 初始访问计数
unsigned long LFUDecrAndReturn(robj *o) {unsigned long counter = LFUGetCounter(o);if (counter == 0) return 0;if (rand() % (counter + 1) == 0) counter--;LFUSetCounter(o, counter);return counter;
}

该方法会按照一定概率减少计数，确保 近期访问过的键不会轻易被淘汰，而 长时间未访问的键会逐步淘汰。

4. 淘汰策略

当 maxmemory 超出时，Redis 需要淘汰一部分数据，LFU 主要执行：

遍历数据，找到访问计数最小的键。

采用 volatile-lfu 或 allkeys-lfu 进行数据删除：

evictionPoolPopulate(dict *sample_dict) {// 从字典中随机采样 N 个键for (i = 0; i < EVPOOL_SIZE; i++) {lfu = LFUGetCounter(entry);if (lfu < min_lfu) {min_lfu = lfu;min_entry = entry;}}// 淘汰访问次数最少的dictDelete(sample_dict, min_entry);
}