简单理解Redis的LRU缓存淘汰算法实现
最新回答
理想三旬
2020-12-24 07:53:23
Redis的LRU缓存淘汰算法分为严格LRU和近似LRU两种实现方式，实际生产环境采用近似LRU以平衡性能与资源消耗，其核心原理如下：
1. 严格LRU的局限性
严格LRU通过双向链表维护数据访问顺序：新数据插入链表头部，访问数据移动至头部，链表尾部为最近最少使用数据。当内存不足时淘汰尾部数据。但该实现存在三个问题：
- 需额外内存存储链表结构
- 频繁的链表操作（插入、移动）导致性能下降
- 数据量大时操作耗时显著增加
2. 近似LRU的实现机制
Redis通过三步优化实现近似LRU：
2.1 全局LRU时钟管理
- 时钟精度：使用1秒为单位的UNIX时间戳（通过getLRUClock()函数获取），无法区分1秒内的多次访问
- 更新机制：全局时钟server.lruclock由serverCron周期性更新（默认每100ms执行一次），确保时钟值与系统时间同步
- 数据结构：每个键值对通过redisObject结构体的24位lru字段存储最近访问时间戳
2.2 键值对时间戳更新
- 初始化：创建键值对时（createObject函数），根据maxmemory_policy配置初始化lru值。若非LFU策略，则直接赋值为当前全局时钟值
- 访问更新：任何访问操作通过lookupKey函数触发，若配置为非LFU策略，则更新lru为最新全局时钟值
2.3 淘汰策略执行流程
- 触发条件：处理每个命令时（processCommand）调用performEvictions，当内存使用超过maxmemory且策略为allkeys-lru/volatile-lru时启动
- 候选池管理：
随机采样：从全局哈希表（allkeys-lru）或带TTL的键集合（volatile-lru）中随机选取maxmemory-samples个键（默认5个）
空闲时间计算：通过estimateObjectIdleTime计算键的空闲时间（当前时间戳与lru值的差值）
候选池更新：将采样键按空闲时间插入EvictionPoolLRU数组（固定大小16），替换空闲时间更短的键
- 淘汰决策：从候选池尾部（空闲时间最长）开始遍历，选择第一个非空键进行淘汰，支持同步/异步删除
- 循环淘汰：若释放内存不足，重复采样-淘汰流程直至满足需求
3. 近似LRU的优势
- 内存效率：无需维护链表结构，仅需固定大小的候选池（16个键）
- 性能优化：通过随机采样减少全表扫描开销，时间复杂度从O(n)降至O(1)
- 精度权衡：1秒时钟精度在大多数场景下足够，避免高频更新带来的性能损耗
总结：Redis通过全局时钟+随机采样+空闲时间排序的组合方案，在内存占用和操作效率间取得平衡，既保留了LRU的核心思想，又避免了严格实现的高成本，成为高并发缓存场景下的实用选择。
热门标签
