Redis LFU算法详述(Least Frequently Used - 最不常用)

返回主页

一、前言

在上一章我们已经讲过《LRU(Least Recently Used)》的算法, 这个算法有一个缺陷,这里我们回顾下,情况如下:

Redis系列教程入门基础_Redis LRU算法详述(Least Recently Used - 最近最少使用)

当系统内存达到限制, 触发 LRU 算法的时候,会对数据库中的Key 进行筛选淘汰, 如果按照LRU 算法的逻辑(最近最少使用),那么被淘汰的概率将是 Key A > Key B > Key C 。然而在现实中,我们并不希望Key A被淘汰,而是希望淘汰率是 Key C > Key B > Key A,所以在这种情况下, 使用LRU 算法显然不太合适。淘汰算法的本意是保留那些将来最有可能被再次访问的数据,而LRU算法只是预测最近被访问的数据将来最有可能被访问到。 那么有没有更好的的内存淘汰机制呢?当然有,那就是LFU(Least Frequently Used - 最不常用)。

LFU(Least Frequently Used)是Redis 4.0 引入的淘汰算法,它通过key的访问频率、访问时间比较来淘汰key,重点突出的是Frequently Used。

Redis LFU算法详述(Least Frequently Used - 最不常用)
Redis LFU算法详述(Least Frequently Used - 最不常用)

LFU近似于LRU:它使用一个概率计数器,称为Morris计数器,以估计每个对象只使用几比特的对象访问频率,结合衰变周期,使得计数器随着时间的推移而减少,在某个时刻,即使在过去,我们也不再想考虑频繁访问的密钥,因此,该算法可以适应访问模式的变化。

Redis4.0之后为maxmemory_policy淘汰策略添加了两个LFU模式:

  • volatile-lfu:对有过期时间的key采用LFU淘汰算法
  • allkeys-lfu:对全部key采用LFU淘汰算法

二、LFU 算法的实现

在LFU模式下,Redis对象头的24bit lru字段被分成两段来存储,高16bit存储ldt(Last Decrement Time),低8bit存储logc(Logistic Counter)。

     16 bits      8 bits
+----------------+--------+
+ Last decr time | LOG_C  |
+----------------+--------+
  • 高16bit用来记录最近一次计数器降低的时间,由于只有16bit,存储的是Unix分钟时间戳取模2^16,16bit能表示的最大值为65535(65535/60/24≈45.5),大概45.5天会折返(折返指的是取模后的值重新从0开始)。
  • 低8位用来记录访问频次,8bit能表示的最大值为255,logc肯定无法记录真实的访问次数,其实从名字可以看出存储的是访问次数的对数值,每个新加入的key的logc初始值为5(LFU_INITI_VAL),这样可以保证新加入的值不会被首先选中淘汰;logc每次key被访问时都会更新;此外,logc会随着时间衰减。

那么大家就有疑问了, 使用8bit 来记录访问评率, 然而8bit的最大值只有255, 这个不会被记录满吗?答案是会的, 但是确是非常难,接下来看一段rendis 的源码:

Redis LFU算法详述(Least Frequently Used - 最不常用)

通过上面的源码, 我们可以得出一个结论,当counter < 5,每次访问, counter 百分百会 +1, 随着 counter 的变大,counter +1 的概率越来越小。counter并不是简单的访问一次就+1,而是采用了一个0-1之间的p因子控制增长。counter最大值为255。取一个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      |
+--------+------------+------------+------------+------------+------------+

三、配置文件开启LFU算法

修改redis.conf配置文件,设置maxmemory-policy volatile-lfumaxmemory-policy allkeys-lfu

Redis LFU算法详述(Least Frequently Used - 最不常用)

68 预览数量 2024-03-26 17:49:37 发布 时间
目录
赞数量
评论数量
返回顶部
暂无评论

暂无评论