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

一、前言

在上一章我们已经讲过《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。

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 的源码：

通过上面的源码， 我们可以得出一个结论，当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-lfu 或 maxmemory-policy allkeys-lfu