Redis系列1：深刻理解高性能Redis的本质
Redis系列2：数据持久化提高可用性
Redis系列3：高可用之主从架构
Redis系列4：高可用之Sentinel(哨兵模式）
Redis系列5：深入分析Cluster 集群模式
追求性能极致：Redis6.0的多线程模型
追求性能极致：客户端缓存带来的革命
Redis系列8：Bitmap实现亿万级数据计算
Redis系列9：Geo 类型赋能亿级地图位置计算
Redis系列10：HyperLogLog实现海量数据基数统计
Redis系列11：内存淘汰策略
Redis系列12：Redis 的事务机制
Redis系列13：分布式锁实现
Redis系列14：使用List实现消息队列
Redis系列15：使用Stream实现消息队列
Redis系列16：聊聊布隆过滤器（原理篇）
Redis系列17：聊聊布隆过滤器（实践篇）
Redis系列18：过期数据的删除策略
Redis系列19：LRU内存淘汰算法分析
上一期我们介绍了 Redis系列19：LRU淘汰内存淘汰算法分析 ，大致了解了LRU(Least Rencently Used) 的算法原理，即将最近最久未使用的算法进行数据淘汰。
但是这样的算法也有一些比较明显缺陷：
如上图，Key 1会被优先淘汰掉，但实际上，Key 1的访问频率和可能行高很多，我们并不希望Key 1被淘汰，而是希望淘汰率是 Key 2 > Key 1
为了解决这些问题，一些改进的算法被提出来，例如LFU（Least Frequently Used）算法和FIFO（First In First Out）算法。这些算法在某些情况下比LRU算法更合理更有效。
LFU(Least Frequently Used)是Redis 4.0 引入的淘汰算法，它通过key的访问频率、访问时间比较来淘汰key，重点突出的是Frequently Used，用于在缓存容量有限时决定哪些缓存块应该被清除。
LFU算法根据缓存块的使用频率来决定哪些块应该被清除。具体来说，它会记录每个缓存块的使用次数，并按照使用次数从低到高排序。当缓存达到容量上限时，LFU算法会选择使用次数最少的缓存块进行清除，也就是最不经常使用的缓存块。
LFU算法的优点是能够有效地防止缓存溢出，并且能够最大限度地减少清除重要数据的概率。但是，由于需要记录每个缓存块的使用次数，因此LFU算法需要较大的内存空间，并且由于需要经常更新使用次数，因此其时间复杂度相对较高。
LFU算法常用于Web缓存、数据库缓存、文件系统缓存等场景，用于提高系统的性能和稳定性。
实现原理如下：
LFU近似于LRU，使用概率计数器Morris计数器来估计每个对象的访问频率，并结合衰变周期使计数器随时间减少。这样，即使在过去，我们也不再考虑频繁访问的密钥。因此，该算法可以适应访问模式的变化。
Redis4.0之后 maxmemory_policy 淘汰策略 添加了两个LFU模式：
在LFU模式下，Redis对象头的24bit lru字段被分成两段来存储。其中，高16bit用于存储最后一次计数器降低的时间（ldt），低8bit用于存储访问次数的对数值（logc）。
高16bit的ldt字段用于记录最近一次计数器降低的时间。由于只有16bit，它可以表示的最大值为65535（2^16-1）。由于时间以1秒为单位进行计数，因此大约每45.5天（65535/24/60）时间戳会折返重新从0开始。
低8bit的logc字段用于记录访问次数的对数值。由于只有8bit，它可以表示的最大值为255。实际上，logc无法记录真实的Redis key的访问次数，因为每个新加入的key的logc初始值为5（LFU_INITI_VAL），这样可以保证新加入的值不会被首先选中淘汰。每次访问key时，logc都会更新。
16 bits 8 bits
+----------------+--------+
+ Last decr time | LOG_C |
+----------------+--------+
/* Return the current time in minutes, just taking the least significant
* 16 bits. The returned time is suitable to be stored as LDT (last decrement
* time) for the LFU implementation. */
// server.unixtime为Redis缓存的Unix时间戳
// 使用的Unix的分钟时间戳，取模2^16
unsigned long LFUGetTimeInMinutes(void) {
return (server.unixtime/60) & 65535;
}
/* Given an object last access time, compute the minimum number of minutes
* that elapsed since the last access. Handle overflow (ldt greater than
* the current 16 bits minutes time) considering the time as wrapping
* exactly once. */
unsigned long LFUTimeElapsed(unsigned long ldt) {
// 获取系统当前的LFU time
unsigned long now = LFUGetTimeInMinutes();
// 如果now >= ldt 直接取差值
if (now >= ldt) return now-ldt;
// 如果now < ldt 增加上65535
return 65535-ldt+now;
}
/* 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) {
// Logistic Counter最大值为255 （8位的最大值）, 如果已经是最大值了，直接返回
if (counter == 255) return 255;
// 取一个0~1之间的随机数数
double r = (double)rand()/RAND_MAX;
// counter减去LFU_INIT_VAL （LFU_INIT_VAL为每个key的Logistic Counter基数值，默认为5）
double baseval = counter - LFU_INIT_VAL;
// 如果衰减之后counter已经小于基数（如5），那么得出的结果 < 0，也取0
if (baseval < 0) baseval = 0;
// 可以看出如果lfu_log_factor的值越大，分母越大，得到的p越小
double p = 1.0/(baseval*server.lfu_log_factor+1);
// p 越小，r < p的可能性就越小，Logistic Counter增加的概率就越小
// 综上，lfu_log_factor越大增长越缓慢，缓解255空间紧张的问题
if (r < p) counter++;
return counter;
}
可以修改redis.conf配置文件，设置maxmemory-policy volatile-lfu / allkeys-lfu 来进行开启
# MAXMEMORY POLICY: how Redis will select what to remove when maxmemory
# is reached. You can select one from the following behaviors:
#
# volatile-lru -> Evict using approximated LRU, only keys with an expire set.
# allkeys-lru -> Evict any key using approximated LRU.
# volatile-lfu -> Evict using approximated LFU, only keys with an expire set.
# allkeys-lfu -> Evict any key using approximated LFU.
# volatile-random -> Remove a random key having an expire set.
# allkeys-random -> Remove a random key, any key.
# volatile-ttl -> Remove the key with the nearest expire time (minor TTL)
# noeviction -> Don't evict anything, just return an error on write operations.
#
# LRU means Least Recently Used
# LFU means Least Frequently Used
#
# Both LRU, LFU and volatile-ttl are implemented using approximated
# randomized algorithms.
#
# Note: with any of the above policies, when there are no suitable keys for
# eviction, Redis will return an error on write operations that require
# more memory. These are usually commands that create new keys, add data or
# modify existing keys. A few examples are: SET, INCR, HSET, LPUSH, SUNIONSTORE,
# SORT (due to the STORE argument), and EXEC (if the transaction includes any
# command that requires memory).
#
# The default is:
#
# maxmemory-policy noeviction
#
#
# 备注1：对设置了过期时间的key启用LFU淘汰算法
# maxmemory-policy volatile-lfu
# 备注2：对全部key启用LFU淘汰算法进行计算
# maxmemory-policy allkeys-lfu
LFU(Least Frequently Used)是Redis 4.0 引入的淘汰算法，它通过key的访问频率、访问时间比较来淘汰key，重点突出的是Frequently Used，用于在缓存容量有限时决定哪些缓存块应该被清除。它避免了LRU淘汰算法明显缺陷。