关于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 算法实现之前，咱们先简略介绍一下原生的 LRU 算法。

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

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

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

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

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

如果你很相熟 Redis 的数据类型，你会发现这个 LRU 的数据结构与 ZSET 类型 OBJ\_ENCODING\_SKIPLIST 编码构造类似，只是 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 淘汰策略部分生效。

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

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

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

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

很多人看到下面的形容，会认为 LFU 算法次要是 比拟数据的拜访次数 ，毕竟拜访次数多了天然拜访频率就高啊。实际上， 拜访频率不能等同于拜访次数，抛开拜访工夫谈拜访次数就是在“耍流氓”。

在这段时间片内数据 A 被拜访了 5 次，数据 B 与 C 各被拜访了 4 次，如果依照拜访次数判断数据热度值，必然是 A >B=C；如果思考到时效性，间隔以后工夫越近的拜访越有价值，那么数据热度值就应该是 C >B>A。因而，LFU 算法个别都会有一个工夫衰减函数参加热度值的计算，兼顾了拜访工夫的影响。

LFU 算法实现的数据结构与 LRU 一样，也采纳 Hash 表 + 双向链表的构造，数据在双向链表内依照热度值排序。如果某个数据被拜访，更新热度值之从新插入到链表适合的地位，这个比 LRU 算法解决的流程简单一些。

Redis 4.0 版本开始减少了 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]。

仅从代码层面剖析钻研 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 算法无奈展现出较大的劣势，也可能会淘汰掉比拟热的数据。

参考文献：

Key eviction。
Redis 的 LRU 缓存淘汰算法实现（上）
Redis 缓存淘汰策略以及 LRU、LFU 算法

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

一、前言

二、Redis 的 LRU 实现

2.1 LRU 算法原理

2.2 Redis LRU 算法实现

2.3 LRU 算法缺点

三、Redis 的 LFU 实现

3.1 LFU 算法原理

3.2 Redis LFU 算法实现

3.2.1 LFU 算法代码实现

3.3.2 LFU Counter 剖析

四、总结

Just My Socks（注册教程内含优惠码）

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

一、前言

二、Redis 的 LRU 实现

2.1 LRU 算法原理

2.2 Redis LRU 算法实现

2.3 LRU 算法缺点

三、Redis 的 LFU 实现

3.1 LFU 算法原理

3.2 Redis LFU 算法实现

3.2.1 LFU 算法代码实现

3.3.2 LFU Counter 剖析

四、总结

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）