Redis的LRU缓存淘汰算法怎么实现

34次阅读

共计 5312 个字符，预计需要花费 14 分钟才能阅读完成。

本文丸趣 TV 小编为大家详细介绍“Redis 的 LRU 缓存淘汰算法怎么实现”，内容详细，步骤清晰，细节处理妥当，希望这篇“Redis 的 LRU 缓存淘汰算法怎么实现”文章能帮助大家解决疑惑，下面跟着丸趣 TV 小编的思路慢慢深入，一起来学习新知识吧。

1 标准 LRU 的实现原理

LRU，最近最少使用（Least Recently Used，LRU），经典缓存算法。

LRU 会使用一个链表维护缓存中每个数据的访问情况，并根据数据的实时访问，调整数据在链表中的位置，然后通过数据在链表中的位置，表示数据是最近刚访问的，还是已有段时间未访问。

LRU 会把链头、尾分别设为 MRU 端和 LRU 端：

MRU，Most Recently Used 缩写，表示此处数据刚被访问

LRU 端，此处数据最近最少被访问的数据

LRU 可分成如下情况：

case1：当有新数据插入，LRU 会把该数据插入到链首，同时把原来链表头部的数据及其之后的数据，都向尾部移动一位

case2：当有数据刚被访问一次后，LRU 会把该数据从它在链表中当前位置，移动到链首。把从链表头部到它当前位置的其他数据，都向尾部移动一位

case3：当链表长度无法再容纳更多数据，再有新数据插入，LRU 去除链表尾部的数据，这也相当于将数据从缓存中淘汰掉

case2 图解：链表长度为 5，从链表头部到尾部保存的数据分别是 5，33，9，10，8。假设数据 9 被访问一次，则 9 就会被移动到链表头部，同时，数据 5 和 33 都要向链表尾部移动一位。

所以若严格按 LRU 实现，假设 Redis 保存的数据较多，还要在代码中实现：

为 Redis 使用最大内存时，可容纳的所有数据维护一个链表

需额外内存空间来保存链表

每当有新数据插入或现有数据被再次访问，需执行多次链表操作

在访问数据的过程中，让 Redis 受到数据移动和链表操作的开销影响

最终导致降低 Redis 访问性能。

所以，无论是为节省内存 or 保持 Redis 高性能，Redis 并未严格按 LRU 基本原理实现，而是提供了一个近似 LRU 算法实现。

2 Redis 的近似 LRU 算法实现

Redis 的内存淘汰机制是如何启用近似 LRU 算法的？redis.conf 中的如下配置参数：

maxmemory，设定 Redis server 可使用的最大内存容量，一旦 server 使用实际内存量超出该阈值，server 会根据 maxmemory-policy 配置策略，执行内存淘汰操作

maxmemory-policy，设定 Redis server 内存淘汰策略，包括近似 LRU、LFU、按 TTL 值淘汰和随机淘汰等

所以，一旦设定 maxmemory 选项，且将 maxmemory-policy 配为 allkeys-lru 或 volatile-lru，近似 LRU 就被启用。allkeys-lru 和 volatile-lru 都会使用近似 LRU 淘汰数据，区别在于：

allkeys-lru 是在所有的 KV 对中筛选将被淘汰的数据

volatile-lru 在设置了 TTL 的 KV 对中筛选将被淘汰数据

Redis 如何实现近似 LRU 算法的呢？

全局 LRU 时钟值的计算

如何计算全局 LRU 时钟值的，以用来判断数据访问的时效性

键值对 LRU 时钟值的初始化与更新

哪些函数中对每个键值对对应的 LRU 时钟值，进行初始化与更新

近似 LRU 算法的实际执行

如何执行近似 LRU 算法，即何时触发数据淘汰，以及实际淘汰的机制实现

2.1 全局 LRU 时钟值的计算

近似 LRU 算法仍需区分不同数据的访问时效性，即 Redis 需知道数据的最近一次访问时间。因此，有了 LRU 时钟：记录数据每次访问的时间戳。

Redis 对每个 KV 对中的 V，会使用个 redisObject 结构体保存指向 V 的指针。那 redisObject 除记录值的指针，还会使用 24 bits 保存 LRU 时钟信息，对应的是 lru 成员变量。这样，每个 KV 对都会把它最近一次被访问的时间戳，记录在 lru 变量。

redisObject 定义包含 lru 成员变量的定义：

每个 KV 对的 LRU 时钟值是如何计算的？Redis Server 使用一个实例级别的全局 LRU 时钟，每个 KV 对的 LRU time 会根据全局 LRU 时钟进行设置。

这全局 LRU 时钟保存在 Redis 全局变量 server 的成员变量 lruclock

当 Redis Server 启动后，调用 initServerConfig 初始化各项参数时，会调用 getLRUClock 设置 lruclock 的值：

于是，就得注意，** 若一个数据前后两次访问的时间间隔<1s，那这两次访问的时间戳就是一样的！** 因为 LRU 时钟精度就是 1s，它无法区分间隔小于 1 秒的不同时间戳！

getLRUClock 函数将获得的 UNIX 时间戳，除以 LRU_CLOCK_RESOLUTION 后，就得到了以 LRU 时钟精度来计算的 UNIX 时间戳，也就是当前的 LRU 时钟值。

getLRUClock 会把 LRU 时钟值和宏定义 LRU_CLOCK_MAX（LRU 时钟能表示的最大值）做与运算。

所以默认情况下，全局 LRU 时钟值是以 1s 为精度计算得 UNIX 时间戳，且是在 initServerConfig 中进行的初始化。

那 Redis Server 运行过程中，全局 LRU 时钟值是如何更新的？和 Redis Server 在事件驱动框架中，定期运行的时间事件所对应的 serverCron 有关。

serverCron 作为时间事件的回调函数，本身会周期性执行，其频率值由 redis.conf 的 hz 配置项决定，默认值 10，即 serverCron 函数会每 100ms（1s/10 = 100ms）运行一次。serverCron 中，全局 LRU 时钟值就会按该函数执行频率，定期调用 getLRUClock 进行更新：

这样，每个 KV 对就能从全局 LRU 时钟获取最新访问时间戳。

对于每个 KV 对，它对应的 redisObject.lru 在哪些函数进行初始化和更新的呢？

2.2 键值对 LRU 时钟值的初始化与更新

对于一个 KV 对，其 LRU 时钟值最初是在这 KV 对被创建时，进行初始化设置的，这初始化操作在 createObject 函数中调用，当 Redis 要创建一个 KV 对，就会调用该函数。

createObject 除了会给 redisObject 分配内存空间，还会根据 maxmemory_policy 配置，初始化设置 redisObject.lru。

若 maxmemory_policy=LFU，则 lru 变量值会被初始化设置为 LFU 算法的计算值

maxmemory_policy≠LFU，则 createObject 调用 LRU_CLOCK 设置 lru 值，即 KV 对对应的 LRU 时钟值。

LRU_CLOCK 返回当前全局 LRU 时钟值。因为一个 KV 对一旦被创建，就相当于有了次访问，其对应 LRU 时钟值就表示了它的访问时间戳：

那一个 KV 对的 LRU 时钟值又是何时再被更新？

只要一个 KV 对被访问，其 LRU 时钟值就会被更新！而当一个 KV 对被访问时，访问操作最终都会调用 lookupKey。

lookupKey 会从全局哈希表中查找要访问的 KV 对。若该 KV 对存在，则 lookupKey 会根据 maxmemory_policy 的配置值，来更新键值对的 LRU 时钟值，也就是它的访问时间戳。

而当 maxmemory_policy 没有配置为 LFU 策略时，lookupKey 函数就会调用 LRU_CLOCK 函数，来获取当前的全局 LRU 时钟值，并将其赋值给键值对的 redisObject 结构体中的 lru 变量

这样，每个 KV 对一旦被访问，就能获得最新的访问时间戳。但你可能好奇：这些访问时间戳最终是如何被用于近似 LRU 算法进行数据淘汰的？

2.3 近似 LRU 算法的实际执行

Redis 之所以实现近似 LRU，是为减少内存资源和操作时间上的开销。

2.3.1 何时触发算法执行？

近似 LRU 主要逻辑在 performEvictions。

performEvictions 被 evictionTimeProc 调用，而 evictionTimeProc 函数又是被 processCommand 调用。

processCommand，Redis 处理每个命令时都会调用：

然后，isSafeToPerformEvictions 还会再次根据如下条件判断是否继续执行 performEvictions：

一旦 performEvictions 被调用，且 maxmemory-policy 被设置为 allkeys-lru 或 volatile-lru，近似 LRU 就被触发执行了。

2.3.2 近似 LRU 具体执行过程

执行可分成如下步骤：

2.3.2.1 判断当前内存使用情况

调用 getMaxmemoryState 评估当前内存使用情况，判断当前 Redis Server 使用内存容量是否超过 maxmemory 配置值。

若未超过 maxmemory，则返回 C_OK，performEvictions 也会直接返回。

getMaxmemoryState 评估当前内存使用情况的时候，若发现已用内存超出 maxmemory，会计算需释放的内存量。这个释放内存大小 = 已使用内存量 -maxmemory。

但已使用内存量并不包括用于主从复制的复制缓冲区大小，这是 getMaxmemoryState 通过调用 freeMemoryGetNotCountedMemory 计算的。

而若当前 Server 使用的内存量超出 maxmemory 上限，则 performEvictions 会执行 while 循环淘汰数据释放内存。

为淘汰数据，Redis 定义数组 EvictionPoolLRU，保存待淘汰的候选 KV 对，元素类型是 evictionPoolEntry 结构体，保存了待淘汰 KV 对的空闲时间 idle、对应 K 等信息：

这样，Redis Server 在执行 initSever 进行初始化时，会调用 evictionPoolAlloc 为 EvictionPoolLRU 数组分配内存空间，该数组大小由 EVPOOL_SIZE 决定，默认可保存 16 个待淘汰的候选 KV 对。

performEvictions 在淘汰数据的循环流程中，就会更新这个待淘汰的候选 KV 对集合，即 EvictionPoolLRU 数组。

2.3.2.2 更新待淘汰的候选 KV 对集合

performEvictions 调用 evictionPoolPopulate，其会先调用 dictGetSomeKeys，从待采样哈希表随机获取一定数量 K：

dictGetSomeKeys 采样的哈希表，由 maxmemory_policy 配置项决定：

若 maxmemory_policy=allkeys_lru，则待采样哈希表是 Redis Server 的全局哈希表，即在所有 KV 对中采样

否则，待采样哈希表就是保存着设置了 TTL 的 K 的哈希表。

dictGetSomeKeys 采样的 K 的数量由配置项 maxmemory-samples 决定，默认 5：

于是，dictGetSomeKeys 返回采样的 KV 对集合。evictionPoolPopulate 根据实际采样到的 KV 对数量 count，执行循环：调用 estimateObjectIdleTime 计算在采样集合中的每一个 KV 对的空闲时间：

接着，evictionPoolPopulate 遍历待淘汰的候选 KV 对集合，即 EvictionPoolLRU 数组，尝试把采样的每个 KV 对插入 EvictionPoolLRU 数组，取决于如下条件之一：

能在数组中找到一个尚未插入 KV 对的空位

能在数组中找到一个 KV 对的空闲时间<采样 KV 对的空闲时间

有一成立，evictionPoolPopulate 就能把采样 KV 对插入 EvictionPoolLRU 数组。等所有采样键值对都处理完后，evictionPoolPopulate 函数就完成对待淘汰候选键值对集合的更新了。

接下来，performEvictions 开始选择最终被淘汰的 KV 对。

2.3.2.3 选择被淘汰的 KV 对并删除

因 evictionPoolPopulate 已更新 EvictionPoolLRU 数组，且该数组里的 K，是按空闲时间从小到大排好序了。所以，performEvictions 遍历一次 EvictionPoolLRU 数组，从数组的最后一个 K 开始选择，若选到的 K 非空，就把它作为最终淘汰的 K。

该过程执行逻辑：