性能文章>【全网首发】Redis系列20:LFU内存淘汰算法分析>

【全网首发】Redis系列20:LFU内存淘汰算法分析原创

6月前
251035

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淘汰内存淘汰算法分析

1 介绍

上一期我们介绍了 Redis系列19:LRU淘汰内存淘汰算法分析 ,大致了解了LRU(Least Rencently Used) 的算法原理,即将最近最久未使用的算法进行数据淘汰。
但是这样的算法也有一些比较明显缺陷:

  • 稳定性和性能问题:LRU算法认为最近最少使用的数据是最该被淘汰的,但是这可能导致某些数据被频繁地淘汰和加载,因为它们可能只在某个时间段内被使用一次,而在其他时间段内则不会被使用。这会使得缓存的效率降低,增加了CPU和内存之间的通信开销。
  • 空间问题:LRU算法需要维护一个链表来记录数据的访问顺序,这需要额外的空间。链表可能会占用较大的空间,导致缓存的效率降低。
  • 访问顺序问题:我们的访问顺序并不一定是按照时间来的,而是有一定的规律。例如,我们在处理数据时可能会按照某个频率访问数据,而不是按照时间顺序。这种情况下,LRU算法可能会将某些我们还需要被访问数据淘汰掉。
  • 数据局限性问题:淘汰算法的本意是保留那些将来最有可能被再次访问的数据,而LRU算法只是预测最近被访问的数据将来最有可能被访问到。这样太局限,误伤很多高频被访问但某段时间空窗的数据。

image.png

如上图,Key 1会被优先淘汰掉,但实际上,Key 1的访问频率和可能行高很多,我们并不希望Key 1被淘汰,而是希望淘汰率是 Key 2 > Key 1
为了解决这些问题,一些改进的算法被提出来,例如LFU(Least Frequently Used)算法和FIFO(First In First Out)算法。这些算法在某些情况下比LRU算法更合理更有效。

2 实现原理

LFU(Least Frequently Used)是Redis 4.0 引入的淘汰算法,它通过key的访问频率、访问时间比较来淘汰key,重点突出的是Frequently Used,用于在缓存容量有限时决定哪些缓存块应该被清除。

LFU算法根据缓存块的使用频率来决定哪些块应该被清除。具体来说,它会记录每个缓存块的使用次数,并按照使用次数从低到高排序。当缓存达到容量上限时,LFU算法会选择使用次数最少的缓存块进行清除,也就是最不经常使用的缓存块。

LFU算法的优点是能够有效地防止缓存溢出,并且能够最大限度地减少清除重要数据的概率。但是,由于需要记录每个缓存块的使用次数,因此LFU算法需要较大的内存空间,并且由于需要经常更新使用次数,因此其时间复杂度相对较高。

LFU算法常用于Web缓存、数据库缓存、文件系统缓存等场景,用于提高系统的性能和稳定性。

实现原理如下:

image.png

LFU近似于LRU,使用概率计数器Morris计数器来估计每个对象的访问频率,并结合衰变周期使计数器随时间减少。这样,即使在过去,我们也不再考虑频繁访问的密钥。因此,该算法可以适应访问模式的变化。
Redis4.0之后 maxmemory_policy 淘汰策略 添加了两个LFU模式:

  • allkeys-lfu:对全部key采用LFU淘汰算法进行计算
  • volatile-lfu:对设置了过期时间的key采用LFU淘汰算法

3 算法实现

3.1 从源码理解算法实现过程

在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  |
+----------------+--------+

image.png

  • Last Decrement Time计算的算法源码:
/* 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;
}
  • Redis Logistic Counter增长计算的源码:
/* 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;
}

3.2 在redis.conf中开启配置

可以修改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

4 总结

LFU(Least Frequently Used)是Redis 4.0 引入的淘汰算法,它通过key的访问频率、访问时间比较来淘汰key,重点突出的是Frequently Used,用于在缓存容量有限时决定哪些缓存块应该被清除。它避免了LRU淘汰算法明显缺陷。

点赞收藏
分类:标签:
Pinocao
请先登录,查看3条精彩评论吧
快去登录吧,你将获得
  • 浏览更多精彩评论
  • 和开发者讨论交流,共同进步

为你推荐

得物一面:Redis大key有什么危害?如何排查和处理?

得物一面:Redis大key有什么危害?如何排查和处理?

5
3