关于redis:深入解析Redis的LRU与LFU算法实现

作者：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 算法