完全掌握Redis的LRU缓存淘汰算法实现
2024-03-29 00:42:56
Redis的近似LRU算法实现是通过对全局LRU时钟和键值对LRU时钟的管理，结合随机采样和空闲时间排序来完成的。
一、全局LRU时钟值的计算
Redis使用一个全局LRU时钟来记录数据的访问时间戳。这个时钟在Redis启动时通过initServerConfig函数初始化，并在serverCron函数中定期更新。serverCron的频率由redis.conf中的hz配置项决定，默认每100毫秒执行一次。全局LRU时钟值的计算通过getLRUClock函数实现，该函数将UNIX时间戳除以LRU_CLOCK_RESOLUTION（默认1秒），得到以秒为精度的LRU时钟值。由于精度限制，若两次访问时间间隔小于1秒，则时间戳相同。
二、键值对LRU时钟值的初始化与更新
每个键值对（KV对）的LRU时钟值存储在redisObject结构体的lru成员变量中。KV对创建时，createObject函数根据maxmemory_policy配置初始化lru值：若配置为LFU，则初始化为LFU计算值；否则初始化为当前全局LRU时钟值。当KV对被访问时，lookupKey函数会更新其lru值为当前全局LRU时钟值，确保记录最新访问时间戳。
三、近似LRU算法的实际执行
近似LRU算法的核心逻辑在performEvictions函数中，该函数由processCommand触发，并在满足条件时执行内存淘汰：
触发条件：Redis处理每个命令时，若当前内存使用量超过maxmemory配置值，且maxmemory-policy设置为allkeys-lru或volatile-lru，则触发近似LRU算法。
评估内存使用情况：getMaxmemoryState函数评估当前内存使用情况，计算需释放的内存量（已用内存量减去maxmemory）。若未超限，则直接返回；否则进入淘汰流程。
更新待淘汰候选集合：evictionPoolPopulate函数从全局哈希表（allkeys-lru时）或设置了TTL的键哈希表（volatile-lru时）中随机采样一定数量的键（数量由maxmemory-samples配置，默认5个）。对每个采样键，计算其空闲时间（当前时间戳减去最后一次访问时间戳），并尝试将其插入待淘汰候选集合EvictionPoolLRU（大小为EVPOOL_SIZE，默认16）。插入条件为：找到空位或找到空闲时间更小的键。
选择并淘汰键：performEvictions遍历EvictionPoolLRU数组，从空闲时间最长的键开始选择，执行同步或异步删除操作。若释放的内存量不足，则重复上述过程，直到满足内存释放要求。
四、近似LRU算法的优势
近似LRU算法通过固定大小的待淘汰集合和随机采样，避免了严格LRU算法中链表操作带来的内存和性能开销。虽然牺牲了部分精确性，但在Redis的内存和性能敏感场景下，实现了更好的折中。
热门标签
