江苏龙网

  1. 主页 > 生活百科 > >

深入解析Redis的LRU与LFU算法实现( 二 )

Redis


2.3 LRU算法缺陷LRU算法仅关注数据的访问时间或访问顺序 ， 忽略了访问次数的价值 ， 在淘汰数据过程中可能会淘汰掉热点数据 。

深入解析Redis的LRU与LFU算法实现

文章插图
如上图所示 ， 时间轴自左向右 ， 数据A/B/C在同一段时间内被分别访问的数次 。数据C是最近一次访问的数据 ， 按照LRU算法排列数据的热度是C>B>A ， 而数据的真实热度是B>A>C 。
这个是LRU算法的原理性问题 ， 自然也会在Redis 近似LRU算法中呈现 ， 为了解决这个问题衍生出来LFU算法 。
三、Redis的LFU实现3.1 LFU算法原理LFU（Least frequently used）即最不频繁访问 ， 其原理是：如果一个数据在近期被高频率地访问 ， 那么在将来它被再访问的概率也会很高 ， 而访问频率较低的数据将来很大概率不会再使用 。
【深入解析Redis的LRU与LFU算法实现】很多人看到上面的描述 ， 会认为LFU算法主要是比较数据的访问次数 ， 毕竟访问次数多了自然访问频率就高啊 。实际上 ， 访问频率不能等同于访问次数 ， 抛开访问时间谈访问次数就是在“耍流氓” 。
深入解析Redis的LRU与LFU算法实现

文章插图
在这段时间片内数据A被访问了5次 ， 数据B与C各被访问了4次 ， 如果按照访问次数判断数据热度值 ， 必然是A>B=C；如果考虑到时效性 ， 距离当前时间越近的访问越有价值 ， 那么数据热度值就应该是C>B>A 。因此 ， LFU算法一般都会有一个时间衰减函数参与热度值的计算 ， 兼顾了访问时间的影响 。
LFU算法实现的数据结构与LRU一样 ， 也采用Hash表 + 双向链表的结构 ， 数据在双向链表内按照热度值排序 。如果某个数据被访问 ， 更新热度值之重新插入到链表合适的位置 ， 这个比LRU算法处理的流程复杂一些 。
3.2 Redis LFU算法实现Redis 4.0版本开始增加了LFU缓存淘汰策略 ， 也采用数据随机筛选规则 ， 然后依据数据的热度值排序 ， 淘汰掉热度值较低的数据 。
3.2.1 LFU算法代码实现
LFU算法的实现没有使用额外的数据结构 ， 复用了redisObject数据结构的lru字段 ， 把这24bit空间拆分成两部分去使用 。
深入解析Redis的LRU与LFU算法实现

文章插图
  • 由于记录时间戳在空间被压缩到16bit ， 所以LFU改成以分钟为单位 ， 大概45.5天会出现数值折返 ， 比LRU时钟周期还短 。
     
  • 低位的8bit用来记录热度值（counter） ， 8bit空间最大值为255 ， 无法记录数据在访问总次数 。
LFU热度值（counter）的算法实现：
#define LFU_INIT_VAL 5/* 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) {if (counter == 255) return 255;double r = (double)rand()/RAND_MAX;double baseval = counter - LFU_INIT_VAL;if (baseval < 0) baseval = 0;double p = 1.0/(baseval*server.lfu_log_factor+1);if (r < p) counter++;return counter;}
  • counter 小于或等于 LFU_INIT_VAL 时候 ， 数据一旦被访问命中 ，  counter接近100%概率递增1；
  • counter 大于 LFU_INIT_VAL 时候 ， 需要先计算两者差值 ， 然后作为分母的一部分参与递增概率的计算；
  • 随着counter 数值的增大 ， 递增的概率逐步衰减 ， 可能数次的访问都不能使其数值加1；
  • 当counter 数值达到255 ， 就不再进行数值递增的计算过程 。
LFU counter的计算也并非“一尘不变” ， 为了适配各种业务数据的特性 ， Redis在LFU算法实现过程中引入了两个可调参数：
深入解析Redis的LRU与LFU算法实现

文章插图
热度值counter的时间衰减函数：unsigned long LFUDecrAndReturn(robj *o) {unsigned long ldt = o->lru >> 8;unsigned long counter = o->lru & 255;unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;if (num_periods)counter = (num_periods > counter) ? 0 : counter - num_periods;return counter;}


推荐阅读


上一篇：字节跳动开源 Kelemetry：面向 Kubernetes 控制面的全局追踪系统

下一篇：聊聊Excel解析：如何处理百万行EXCEL文件？