Redis中LRU算法的实现（介绍了整体设计思路和LRU时钟概述、对象的空闲时间的计算、LRU执行的时机、执行过程）

﹏ヽ暗。殇╰゛Y 2024-04-01 16:26 10阅读 0赞

**整体思路：**

首先定义一个淘汰池，这个淘汰池是一个数组（大小为16），然后触发淘汰时会根据配置的淘汰策略，先从符合条件
    的key中随机采样选出5（可在配置文件中配置）个key，计算其空闲时间，如果Pool还没有满或者比Pool中的最小空
    闲时间Key大的话，就将空闲时间小的Key从Pool中移除，将Key加入到Pool中。每次采样之后更新这个淘汰池，让
    这个淘汰池里保留的总是那些随机采样出的key中空闲时间最长的那部分key。需要删除key时，只需将淘汰池中空闲
    时间最长的key删掉即可。

**LRU时钟概述：**

Redis 在实现上引入了一个 LRU 全局时钟来代替 unix 时间戳，其基本单位是1000ms，LRU时钟在1000ms
    内的时间戳都是一样的，LRU全局时钟的更新通过serverCron时间事件回调函数周期性更新（默认每100ms
    执行一次）来实现。

**对象的空闲时间的计算：**  
每个对象的在创建或每次被访问都会记录下当前服务器的 LRU 时钟（由键值对数据结构 RedisObject 中的24 bits的 lru 字段记录），然后用服务器的 LRU 时钟减去对象本身的时钟，得到的就是这个对象没有被访问的时间间隔（也称空闲时间），空闲时间最大的就是需要淘汰的对象。

**LRU执行的时机：**  
每一次处理客户端命令的时候

**执行过程：**

服务器维护一个大小为16的淘汰池（数组实现），按照空闲时间从小到大排序。
    
    首先评估当前内存的使用情况，使用的内存容量是否超过maxmemory配置的值。
    
    如果没有超过，返回
    
    如果超过阈值，那么调用函数循环淘汰数据释放内存。
    
    选取待淘汰的键值对：
    
    如果淘汰策略是allkeys_lru，就从全部键值对中采样
    
    如果淘汰策略是volitile_lru，就从设置了TTL的键值对中采样
    
    随机选出maxmemory-samples（默认是5）个键值对
    
    更新淘汰池
    
    对于上一步采样的每一个待淘汰键值对，如果可以满足以下条件之一，就可以插入到淘汰池当中：
    
    淘汰池没有满
    
    淘汰池中存在键值对的空闲时间小于采样的待淘汰键值对
    
    选择被淘汰的键值对并删除
    
    淘汰池里面的数据都是按照空闲时间从小到大来排序的，所以从淘汰池数组的末尾开始遍历，然后找到第一个非空的数据，然后根据Redis server的惰性删除配置，执行同步删除或异步删除，终止遍历。
    
    判断是否再次循环
    
    至此淘汰了一个key，若此时没有达到待释放空间，则再次采样、更新、删除。