Redis 的 LFU（Least Frequently Used，最不经常使用）淘汰算法主要用于

1. maxmemory-policy

复制代码

设置为

1. allkeys-lfu

复制代码

或

1. volatile-lfu

复制代码

时，以最少使用频率的键进行淘汰。其核心实现涉及到 访问频率计数 和 时间衰减机制，源码主要集中在

1. src/server.c

复制代码

和

1. src/evict.c

复制代码

文件中。

1. LFU 计数存储

Redis 采用 8-bit 的

1. LRU

复制代码

字段 来存储访问频率计数，存储在

1. robj

复制代码

结构体的

1. lru

复制代码

字段中：

1. struct redisObject {
   
2.     unsigned type:4;
   
3.     unsigned encoding:4;
   
4.     unsigned lru:LRU_BITS; // 用于 LRU/LFU 计算
   
5.     int refcount;
   
6.     void *ptr;
   
7. };

复制代码

其中

1. lru

复制代码

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

• 前 6-bit（
  1. counter

  复制代码
  ）：用于存储访问计数，最大值 63。
  
• 后 2-bit（
  1. clock

  复制代码
  ）：用于时间衰减计算。
  

2. 访问计数的计算

LFU 计数在每次访问键时都会递增，但递增方式不是简单

1. +1

复制代码

，而是使用 对数增长 方式，避免某些键因高访问量而垄断：

1. unsigned long LFUDecrAndReturn(robj *o) {
   
2.     unsigned long counter = LFUGetCounter(o);
   
3.     if (counter == 0) return 0;
   
4.     if (rand() % (counter + 1) == 0) counter--;
   
5.     LFUSetCounter(o, counter);
   
6.     return counter;
   
7. }

复制代码

计数增长时：

1. int LFUIncrAndReturn(robj *o) {
   
2.     unsigned long counter = LFUGetCounter(o);
   
3.     if (counter < 63) {
   
4.         if (rand() % (counter + 1) == 0) counter++;
   
5.     }
   
6.     LFUSetCounter(o, counter);
   
7.     return counter;
   
8. }

复制代码

这意味着：

• 初始时计数增长较快 (
  1. 1 → 2 → 3

  复制代码
  …)
  
• 计数越高，增长概率越低（符合 对数曲线）
  
• 这样可以防止某些高访问量键长期存活。
  

3. LFU 访问频率的衰减

由于有些数据可能短期内访问频繁，但长期不再被访问，因此 Redis 采用了 时间衰减机制：
每 1 分钟 递减一次访问计数。
使用 2-bit 记录最近访问的时间

1. lfu_clock

复制代码

，每隔 60s 触发 衰减：

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

复制代码

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

4. 淘汰策略

当

1. maxmemory

复制代码

超出时，Redis 需要淘汰一部分数据，LFU 主要执行：
遍历数据，找到访问计数最小的键。
采用

1. volatile-lfu

复制代码

或

1. allkeys-lfu

复制代码

进行数据删除：

1. evictionPoolPopulate(dict *sample_dict) {
   
2.     // 从字典中随机采样 N 个键
   
3.     for (i = 0; i < EVPOOL_SIZE; i++) {
   
4.         lfu = LFUGetCounter(entry);
   
5.         if (lfu < min_lfu) {
   
6.             min_lfu = lfu;
   
7.             min_entry = entry;
   
8.         }
   
9.     }
   
10.     // 淘汰访问次数最少的
    
11.     dictDelete(sample_dict, min_entry);
    
12. }

复制代码

采用 近似随机采样，而不是遍历所有键，提高效率。

5. 关键总结

• 存储方式：使用
  1. robj.lru

  复制代码
  变量的 8-bit 空间存储访问计数和时间信息。
  
• 访问计数增长：采用对数增长策略，防止单个键因访问量过大而占用内存。
  
• 时间衰减：每分钟对访问频率计数进行衰减，确保长期未访问的键被淘汰。
  
• 淘汰策略：采样多个键，找到访问计数最少的键进行删除。
  

Redis 的 LFU 机制相比 LRU 更适用于热点数据访问场景，避免了某些短期流行的键占用大量缓存，同时也能让真正的 高频访问数据 存活更久。
到此这篇关于浅谈Redis中LFU算法源码解析的文章就介绍到这了,更多相关Redis LFU算法内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！

来源：https://www.jb51.net/database/339346yv7.htm
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！