共计 5644 个字符，预计需要花费 15 分钟才能阅读完成。
丸趣 TV 小编给大家分享一下 Redis 如何实现 LRU 缓存淘汰算法，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！
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。
该过程执行逻辑：
一旦选到被淘汰的 K，performEvictions 就会根据 Redis server 的惰性删除配置，执行同步删除或异步删除：
至此，performEvictions 就淘汰了一个 K。若此时释放的内存空间还不够，即没有达到待释放空间，则 performEvictions 还会重复执行前面所说的更新待淘汰候选 KV 对集合、选择最终淘汰 K 的过程，直到满足待释放空间的大小要求。
performEvictions 流程：
近似 LRU 算法并未使用耗时且耗空间的链表，而使用固定大小的待淘汰数据集合，每次随机选择一些 K 加入待淘汰数据集合。
最后，按待淘汰集合中 K 的空闲时间长度，删除空闲时间最长的 K。
总结
根据 LRU 算法的基本原理，发现若严格按基本原理实现 LRU 算法，则开发的系统就需要额外内存空间保存 LRU 链表，系统运行时也会受到 LRU 链表操作的开销影响。
而 Redis 的内存资源和性能都很重要，所以 Redis 实现近似 LRU 算法：
首先是设置了全局 LRU 时钟，并在 KV 对创建时获取全局 LRU 时钟值作为访问时间戳，及在每次访问时获取全局 LRU 时钟值，更新访问时间戳
然后，当 Redis 每处理一个命令，都调用 performEvictions 判断是否需释放内存。若已使用内存超出 maxmemory，则随机选择一些 KV 对，组成待淘汰候选集合，并根据它们的访问时间戳，选出最旧数据淘汰
一个算法的基本原理和算法的实际执行，在系统开发中会有一定折中，需综合考虑所开发的系统，在资源和性能方面的要求，以避免严格按照算法实现带来的资源和性能开销。
以上是“Redis 如何实现 LRU 缓存淘汰算法”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注丸趣 TV 行业资讯频道！
