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：

1. dictGetSomeKeys采样的哈希表，由maxmemory_policy配置项决定：
   • 若maxmemory_policy=allkeys_lru，则待采样哈希表是Redis Server的全域哈希表，即在所有KV对中采样
   • 否则，待采样哈希表就是保存着设定了TTL的K的哈希表，

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

于是，dictGetSomeKeys回传采样的KV对集合，evictionPoolPopulate根据实际采样到的KV对数量count，执行回圈：呼叫estimateObjectIdleTime计算在采样集合中的每一个KV对的空闲时间：

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

1. 能在阵列中找到一个尚未插入KV对的空位
2. 能在阵列中找到一个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对，组成待淘汰候选集合，并根据它们的访问时间戳，选出最旧资料淘汰

一个算法的基本原理和算法的实际执行，在系统开发中会有一定折中，需综合考虑所开发的系统，在资源和性能方面的要求，以避免严格按照算法实作带来的资源和性能开销，