4. LRU 近似实现：Redis LRU 实现原理、采样与淘汰、对命中率的权衡

4.1 系统边界与分层职责

Redis 并未实现标准的、全序的 LRU（最近最少使用）链表。标准 LRU 需要 O(1) 移动操作和双向链表维护，在 Redis 千万级 key、单线程模型下会导致性能瓶颈和内存碎片。因此 Redis 采用近似 LRU 算法：在系统边界上，它将淘汰决策从“全局有序”降级为“采样最优”，用少量随机样本近似淘汰最久未访问的 key。

4.2 数据流与控制流：近似 LRU 的完整路径

1. 访问触发：每次 get/set 操作，Redis 更新对应 robj->lru 字段为当前 unix 时间戳（秒）。
2. 内存超限检查：执行命令前调用 freeMemoryIfNeeded()，若已用内存 > maxmemory 则进入淘汰流程。
3. 策略分支：根据淘汰策略（如 allkeys-lru）选择全局 dict 或过期 dict。
4. 采样淘汰：从 dict 中随机选取 N 个 key（默认 N=5），放入淘汰池。池内按 lru 时间戳升序排列，取最旧的 key 驱逐。
5. 池退化与提升：淘汰后，池中的剩余候选 key 保留，供后续淘汰复用。此机制减少重复采样开销。
6. 逐出完成：释放对象，更新内存计数器，循环直至满足 maxmemory 约束。

4.3 策略选型权衡：命中率、CPU 与内存碎片

4.4 风险点与应对

• 采样抖动导致缓存击穿：近似 LRU 可能错误淘汰热点 key，引发缓存雪崩。应对：叠加 min-eviction-ttl 限制或使用多级缓存（本地 + Redis）。
• 时钟精度回绕：Redis lru 字段使用 24 位存储秒级时间戳，约 194 天回绕一次。回绕期间旧 key 可能被误认为最新访问。应对：Redis 5.0+ 已对该场景做隐式处理，升级版本即可。
• 淘汰池无限膨胀：极端写入压力下淘汰池可能持续增大。应对：Redis 源码限制池大小为 16 个 key（硬编码），防止内存泄漏。
• 慢查询与阻塞：单次淘汰若采样过多（N>50），可能阻塞其他命令。应对：监控 evicted_keys 指标，N 值不宜超过 20。

4.5 落地步骤与验收标准

落地步骤

1. 评估业务 QPS 与内存配额，确认选用 volatile-lru 或 allkeys-lru。
2. 配置 maxmemory 为物理内存 60%-70%，预留系统开销。
3. 设置 maxmemory-samples 10，部署灰度验证。
4. 启用慢查询日志，监控 evicted_keys、expired_keys 变化斜率。
5. 压测热点 key 访问，观察 p99 延迟和命中率，微调 samples 参数。
6. 写入配置至 redis.conf，全量重启集群确保配置生效。

验收标准

• 淘汰过程中 p99 延迟上升不超过 2ms。
• 缓存命中率维持在 90% 以上（对比标准 LRU 降幅低于 5%）。
• 无异常 key 频繁进入/离开淘汰池（可通过监控 evicted_keys/time 判断）。
• 单次淘汰平均 CPU 耗时低于 50μs（通过 Redis 内部统计 eviction-time）。