作者:vivo 互联网服务器团队 - Luo Jianxin

重点介绍了Redis的LRU与LFU算法实现,并剖析总结了两种算法的实现成果以及存在的问题。

一、前言

Redis是一款基于内存的高性能NoSQL数据库,数据都缓存在内存里, 这使得Redis能够每秒轻松地解决数万的读写申请。

绝对于磁盘的容量,内存的空间个别都是无限的,为了防止Redis耗尽宿主机的内存空间,Redis外部实现了一套简单的缓存淘汰策略来管控内存使用量。

Redis 4.0版本开始就提供了8种内存淘汰策略,其中4种都是基于LRU或LFU算法实现的,本文就这两种算法的Redis实现进行了具体的介绍,并论述其优劣个性。

二、Redis的LRU实现

在介绍Redis LRU算法实现之前,咱们先简略介绍一下原生的LRU算法。

2.1 LRU算法原理

LRU(The Least Recently Used)是最经典的一款缓存淘汰算法,其原理是 :如果一个数据在最近一段时间没有被拜访到,那么在未来它被拜访的可能性也很低,当数据所占据的空间达到肯定阈值时,这个起码被拜访的数据将被淘汰掉。

现在,LRU算法广泛应用在诸多零碎内,例如Linux内核页表替换,MySQL Buffer Pool缓存页替换,以及Redis数据淘汰策略。

以下是一个LRU算法示意图:

  1. 向一个缓存空间顺次插入三个数据A/B/C,填满了缓存空间;
  2. 读取数据A一次,依照拜访工夫排序,数据A被挪动到缓存头部;
  3. 插入数据D的时候,因为缓存空间已满,触发了LRU的淘汰策略,数据B被移出,缓存空间只保留了D/A/C。

一般而言,LRU算法的数据结构不会如示意图那样,仅应用简略的队列或链表去缓存数据,而是会采纳Hash表 + 双向链表的构造,利用Hash表确保数据查找的工夫复杂度是O(1),双向链表又能够使数据插入/删除等操作也是O(1)。

如果你很相熟Redis的数据类型,你会发现这个LRU的数据结构与ZSET类型OBJ\_ENCODING\_SKIPLIST编码构造类似,只是LRU数据排序形式更简略一些。

2.2 Redis LRU算法实现

依照官网文档的介绍,Redis所实现的是一种近似的LRU算法,每次随机选取一批数据进行LRU淘汰,而不是针对所有的数据,通过就义局部准确率来进步LRU算法的执行效率。

Redis外部只应用Hash表缓存了数据,并没有创立一个专门针对LRU算法的双向链表,之所以这样解决也是因为以下几个起因:

  • 筛选规定,Redis是随机抽取一批数据去依照淘汰策略排序,不再须要对所有数据排序;
  • 性能问题,每次数据拜访都可能波及数据移位,性能会有少许损失;
  • 内存问题,Redis对内存的应用一贯很“抠门”,数据结构都很精简,尽量不应用简单的数据结构治理数据;
  • 策略配置,如果线上Redis实例动静批改淘汰策略会触发全副数据的结构性扭转,这个Redis零碎无奈接受的。

redisObject是Redis外围的底层数据结构,成员变量lru字段用于记录了此key最近一次被拜访的LRU时钟(server.lruclock),每次Key被拜访或批改都会引起lru字段的更新。

#define LRU_BITS 24 typedef struct redisObject {    unsigned type:4;    unsigned encoding:4;    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or                            * LFU data (least significant 8 bits frequency                            * and most significant 16 bits access time). */    int refcount;    void *ptr;} robj;

默认的LRU时钟单位是秒,能够批改LRU\_CLOCK\_RESOLUTION宏来扭转单位,LRU时钟更新的频率也和server.hz参数无关。

unsigned int LRU_CLOCK(void) {    unsigned int lruclock;    if (1000/server.hz <= LRU_CLOCK_RESOLUTION) {        atomicGet(server.lruclock,lruclock);    } else {        lruclock = getLRUClock();    }    return lruclock;}

因为lru字段仅占用了24bit的空间,按秒为单位也只能存储194天,所以可能会呈现一个意想不到的后果,即距离194天拜访Key后标记的工夫戳一样,Redis LRU淘汰策略部分生效。

2.3 LRU算法缺点

LRU算法仅关注数据的拜访工夫或拜访程序,疏忽了拜访次数的价值,在淘汰数据过程中可能会淘汰掉热点数据。

如上图所示,时间轴自左向右,数据A/B/C在同一段时间内被别离拜访的数次。数据C是最近一次拜访的数据,依照LRU算法排列数据的热度是C>B>A,而数据的实在热度是B>A>C。

这个是LRU算法的原理性问题,天然也会在Redis 近似LRU算法中出现,为了解决这个问题衍生进去LFU算法。

三、Redis的LFU实现

3.1 LFU算法原理

LFU(Least frequently used)即最不频繁拜访,其原理是:如果一个数据在近期被高频率地拜访,那么在未来它被再拜访的概率也会很高,而拜访频率较低的数据未来很大概率不会再应用。

很多人看到下面的形容,会认为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空间拆分成两局部去应用。

  • 因为记录时间戳在空间被压缩到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算法实现过程中引入了两个可调参数:

热度值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;}

浏览完以上的内容,是否感觉似曾类似?实际上LFU counter计算过程就是对拜访次数进行了数值归一化,将数据拜访次数映射成热度值(counter),数值的范畴也从[0,+∞)映射到另一个维度的[0,255]。

3.3.2 LFU Counter剖析

仅从代码层面剖析钻研Redis LFU算法实现会比拟形象且干燥,无奈直观的出现counter递增概率的算法成果,以及counter数值与拜访次数的关系。

在lfu_log_factor为默认值10的场景下,利用Python实现Redis LFU算法流程,绘制出LFU counter递增概率曲线图:

能够清晰的察看到,当LFU counter数值超过LFU_INIT_VAL之后,曲线呈现了垂直降落,递增概率陡降到0.2%左右,随后在底部造成一个较为迟缓的衰减曲线,直至counter数值达到255则递增概率归于0,贴合3.3.1章节剖析的实践。

放弃Redis系统配置默认值的状况下,对同一个数据继续的拜访,并采集此数据的LFU counter数值,绘制出LFU counter数值曲线图:

随着拜访次数的一直减少,LFU counter数值曲线呈现出爬坡式的递增,状态趋近于根号曲线,由此揣测出以下观点:

  • 在拜访次数雷同的状况下,counter数值不是固定的,大概率在一个范畴内稳定;
  • 在同一个时间段内,数据之间拜访次数相差上千次,才能够通过counter数值辨别出哪些数据更热,而“温”数据之间可能很难辨别热度。

四、总结

通过对Redis LRU与LFU算法实现的介绍,咱们能够大体理解两种算法策略的优缺点,在Redis运维过程中,能够根据业务数据的个性去抉择相应的算法。

如果业务数据的拜访较为平均,OPS或CPU利用率个别不会呈现周期性的陡升或陡降,数据没有体现出绝对的“冷热”个性,即倡议采纳LRU算法,能够满足个别的运维需要。

相同,业务具备很强时效性,在流动推广或大促期间,业务某些数据会忽然成为热点数据,监控上呈现出OPS或CPU利用率的大幅稳定,为了能抓取热点数据便于前期的剖析或优化,倡议肯定要配置成LFU算法。

在Used_memory靠近Maxmemory的状况下,Redis始终都采纳随机的形式筛选数据,且筛选的个数极其无限,所以,LFU算法无奈展现出较大的劣势,也可能会淘汰掉比拟热的数据。

参考文献:

  1. Key eviction。
  2. Redis的LRU缓存淘汰算法实现(上)
  3. Redis 缓存淘汰策略以及 LRU、LFU 算法