Redis缓存淘汰算法：LRU与LFU的实现原理与调优实战
1. 项目概述：为什么我们需要淘汰算法？
缓存，几乎是现代高并发系统设计的标配。无论是电商秒杀、社交信息流，还是实时推荐，背后都离不开缓存的身影。而 Redis，作为内存数据存储的王者，其高性能的核心秘密之一，就在于它巧妙地将数据存放在内存中。但内存是昂贵且有限的，当内存被数据填满时，新的写入请求该如何处理？Redis 不会像传统数据库那样直接报错，而是启动一套精密的“淘汰机制”，像一位经验丰富的仓库管理员，决定哪些“旧货物”需要被移出仓库，为新到的“紧俏商品”腾出空间。这个决策过程所依赖的核心算法，就是 LRU（最近最少使用）和 LFU（最不经常使用）。
这个项目标题“Redis的LRU与LFU算法实现”，看似在探讨两个经典的缓存淘汰算法，但其背后直指一个核心的工程问题：在有限的内存资源下，如何最大化缓存的命中率，从而降低后端数据库的压力，提升整体系统性能？这不仅仅是理论上的算法比较，更是每一个使用 Redis 的开发者、架构师必须深入理解的实战课题。理解它们的实现，能帮助你在面对“缓存穿透”、“缓存雪崩”等复杂场景时，做出更合理的配置选择，甚至能启发你设计更适合自身业务场景的自定义淘汰策略。本文将深入 Redis 源码的简化模型，拆解 LRU 与 LFU 的实现细节、适用场景以及那些官方文档里不会写的调优心得。
2. 核心思路：近似算法与权衡的艺术
在理想的理论模型中，LRU 和 LFU 都需要维护一个全局的、精确的访问顺序链表或频率统计。对于 LRU，每次访问都需要将节点移动到链表头部，这是一个 O(1) 操作，但需要为每个对象维护前后指针，内存开销大。对于 LFU，需要为每个对象维护一个访问计数器，并在淘汰时找到计数最小的对象，这通常需要堆结构，实现更复杂。
然而，Redis 作为一个追求极致性能和简洁性的单线程内存数据库，它无法承受为海量（可能数百万）的 key 维护全局精确数据结构带来的内存和 CPU 开销。因此，Redis 采取了一种“近似算法”的哲学。它不追求 100% 的精确淘汰，而是用一个相对较小的、固定的内存开销，去实现一个在绝大多数生产场景下都“足够好”的淘汰效果。这是一种典型的工程权衡：用微小的精度损失，换取巨大的性能和资源收益。
具体到实现上，Redis 的淘汰算法并非独立存在，而是与它的核心数据结构——redisObject紧密绑定。每个 Redis 对象（无论是 String、Hash 还是 List）的元数据头里，都藏着一个 24 位的字段lru（在 LRU 模式下）或lfu（在 LFU 模式下）。这个字段，就是整个近似算法的基石。所有的魔法，都围绕着如何高效地更新和解读这 24 位信息而展开。
3. LRU 算法实现：时间戳的采样与淘汰
3.1 核心数据结构：精简的 LRU 时钟
Redis 实现 LRU 的关键，在于它如何记录每个 key 的“最近访问时间”。它没有保存一个精确的 Unix 时间戳，那样需要 32 位或 64 位。相反，它维护了一个全局的lruclock，这个时钟通常每秒钟更新多次（在 Redis 源码中，由serverCron函数更新，默认每秒更新 10 次，即精度为 100 毫秒）。
这个lruclock本身也只有 24 位。24 位无符号整数最大值为 2^24 - 1 = 16,777,215。当lruclock递增到这个最大值后，会回绕到 0 重新开始。这意味着这个时钟的周期大约是 194 天（16,777,215 / (24360010) 天，这里按每秒10次更新估算）。对于缓存场景来说，一个 key 如果近 200 天未被访问，那它几乎肯定可以被淘汰了，这个周期是足够的。
当一个 key 被访问（读或写）时，Redis 就会将当前的全局lruclock值，写入这个 key 对应的redisObject.lru字段。所以，redisObject.lru记录的不是一个绝对时间，而是该 key 最后一次被访问时，所处的那个“时钟滴答”时刻。
3.2 淘汰过程：随机采样与比较
当内存不足需要淘汰 key 时，Redis 并不会遍历所有 key 来找出那个“最久远”的。遍历全部 key 是 O(N) 操作，在 key 数量巨大时是不可接受的。Redis 采用的是随机采样（Sampling）淘汰。
它会从所有待淘汰的键空间中（例如所有的volatile-lrukey），随机选取一定数量的 key（默认是 5 个，可通过maxmemory-samples配置），放入一个“候选池”。然后，它比较这 5 个 key 的redisObject.lru字段值。这个值越小，说明它上次被访问的时间点离当前的lruclock可能越“远”（需要考虑时钟回绕问题）。Redis 会淘汰掉这个候选池中lru值最小的那个 key。
注意：由于是随机采样，你淘汰掉的未必是全局最旧的 key，但很大概率是一个比较旧的 key。增加
maxmemory-samples的值可以提高淘汰的精确度，但也会增加淘汰时的 CPU 开销。这又是一个需要根据实际情况权衡的配置点。通常，设置为 10 就能达到很好的效果，再增加收益递减。
3.3 处理时钟回绕（Wrap-around）
由于lruclock只有 24 位，会发生回绕。如何比较两个lru值的先后？Redis 使用了一个巧妙的技巧。它假设在两个 key 的访问时间差之内，时钟回绕最多发生一次。比较函数大致逻辑如下：
// 伪代码，演示比较逻辑 unsigned long estimateObjectIdleTime(redisObject *o) { unsigned long lruclock = getLRUClock(); // 获取当前全局lruclock // 当前时钟减去对象的lru时间，如果结果没有溢出（即当前时钟 >= 对象时钟），直接返回差值 if (lruclock >= o->lru) { return (lruclock - o->lru) * LRU_CLOCK_RESOLUTION; // 转换为毫秒或秒 } else { // 否则发生了回绕，需要加上一个最大周期值 return (lruclock + (LRU_CLOCK_MAX - o->lru)) * LRU_CLOCK_RESOLUTION; } }通过这个函数，可以将一个 key 的“空闲时间”估算出来，从而在候选池中进行比较。这个估算的时间是近似的，但对于淘汰决策来说已经足够。
实操心得：在生产环境中，如果你发现volatile-lru策略下，缓存命中率不理想，感觉该留的 key 被淘汰了，不该留的却还在。除了检查业务访问模式是否真的是“最近最少使用”，另一个排查方向就是maxmemory-samples。对于 key 数量特别大（百万级以上）的场景，适当调大这个值（比如到 10 或 20），让采样更充分，往往能提升淘汰的准确性。
4. LFU 算法实现：频率计数与衰减机制
LFU 的核心思想是淘汰访问频率最低的 key。但直接记录绝对访问次数会遇到两个问题：1) 内存开销，每个 key 需要一个计数器；2) 历史累积效应，一个过去很热但现在冷了的 key，会因为历史高计数而长期无法被淘汰。
Redis 的 LFU 实现同样基于那 24 位的lfu字段，并精巧地解决了上述问题。
4.1 数据结构：分频段计数与访问时间
Redis 将 24 位的lfu字段拆分成两部分：
- 高 16 位：用于记录最近一次访问的时间（分钟精度），用于衰减。
- 低 8 位：用于记录访问频率计数器（counter），这是一个基于概率递增的计数器，最大值是 255。
8 位计数器意味着最大频率记录为 255。这足够吗？由于它是概率递增且会衰减，这个范围对于区分“非常热”、“热”、“温”、“冷”的 key 是完全足够的。它不是一个精确的访问次数，而是一个经过平滑处理的“热度分数”。
4.2 计数器增长：基于概率的对数递增
当一个 key 被访问时，如何增加它的计数器？如果每次访问都counter++，那么一个短时间内被疯狂访问的 key 会迅速达到 255，之后就失去了区分度。Redis 采用了一种概率递增策略，其增长难度随着当前counter值的增大而指数级增加。
增长逻辑的伪代码如下：
uint8_t LFULogIncr(uint8_t counter) { if (counter == 255) return 255; // 已达最大值 // 生成一个0到1之间的随机数 double r = (double)rand()/RAND_MAX; // 计算增长概率的倒数，base是配置参数lfu_log_factor，默认是10 double baseval = counter - LFU_INIT_VAL; // LFU_INIT_VAL是初始值5 if (baseval < 0) baseval = 0; double p = 1.0 / (baseval * server.lfu_log_factor + 1); // 只有当随机数r小于概率p时，计数器才加1 if (r < p) counter++; return counter; }这个公式意味着：
counter值越小，增长概率p越大（接近 1），很容易增长。counter值越大，增长概率p越小。例如，当counter=10，lfu_log_factor=10时，p ≈ 1/(5*10+1) ≈ 0.0196，大约需要 50 次访问才能有一次增长。lfu_log_factor可配置，用于调整计数器增长的难度。因子越大，counter 越难增长，区分度越细。
这种设计使得counter值能够反映 key 的“长期热度和近期热度”的加权，并且天然地将热度映射到一个较小的、可控的范围内。
4.3 频率衰减：模拟时间窗口
为了解决“历史热 key 霸占缓存”的问题，LFU 必须支持衰减。Redis 利用lfu字段的高 16 位记录上次访问时间（单位是分钟，精度足够）。
Redis 有一个后台定时任务，会定期（默认每1分钟）随机检查一批 key，进行衰减计算。衰减算法如下：
// 伪代码：衰减一个key的counter值 unsigned long LFUDecrAndReturn(redisObject *o) { // 取出高16位记录的上次访问时间（分钟） unsigned long ldt = o->lfu >> 8; // 取出低8位的counter值 unsigned long counter = o->lfu & 255; // 计算该key已经空闲了多少分钟（当前时间 - ldt） unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0; if (num_periods) { // 如果空闲周期数大于counter，则减到0，否则减去相应周期数 if (counter > num_periods) { counter -= num_periods; } else { counter = 0; } // 将衰减后的counter和新的访问时间写回lfu字段 o->lfu = (LFUGetTimeInMinutes() << 8) | counter; } return counter; }这里的关键配置是lfu_decay_time（默认是1）。它的含义是：经过多少分钟，counter 值应该减 1。例如，lfu_decay_time=10，意味着一个 key 如果 10 分钟没被访问，它的热度值就衰减 1。这个值越大，衰减越慢，历史热度影响越持久；值越小，衰减越快，算法对近期访问越敏感。
4.4 LFU 淘汰过程
LFU 的淘汰过程与 LRU 类似，也是采用随机采样。从候选池中，它比较的是每个 key 当前的counter值（经过可能衰减后的值）。counter值最小的 key 被淘汰。如果counter值相同，则比较它们的空闲时间（高16位），空闲时间更长的被淘汰。
避坑指南：从 Redis 4.0 开始支持 LFU。如果你从旧版本升级，或者之前一直使用 LRU，切换到 LFU 时需要特别注意lfu_log_factor和lfu_decay_time这两个参数的调整。默认值（10 和 1）是一个通用保守值。对于访问模式变化非常快的业务（如热点新闻），可能需要调小lfu_decay_time（如 0.5，表示30秒衰减1），让算法更快“忘记”过去。对于访问模式稳定、希望长期留住热 key 的场景（如用户基础信息缓存），可以适当调大lfu_log_factor（如 20）和lfu_decay_time（如 10）。
5. 配置选择与实战场景分析
了解了实现原理，我们就能更理性地选择淘汰策略和配置参数。Redis 的maxmemory-policy提供了多种选择：
| 策略 | 含义 | 适用场景 |
|---|---|---|
noeviction | 不淘汰，写操作报错。 | 数据绝对不允许丢失，且有其他监控保障内存不超限。 |
allkeys-lru | 从所有 key 中近似 LRU 淘汰。 | 最常用。业务期望缓存整体访问服从“二八原则”，即部分热点数据支撑大部分请求。 |
volatile-lru | 从设置了过期时间（TTL）的 key 中近似 LRU 淘汰。 | 需要区分“永久数据”和“缓存数据”。只希望对缓存部分进行淘汰。 |
allkeys-lfu | 从所有 key 中近似 LFU 淘汰。 | 访问频率分布相对稳定，希望长期保留最常访问的热点，比如“商品品类列表”、“城市信息”等。 |
volatile-lfu | 从设置了 TTL 的 key 中近似 LFU 淘汰。 | 同 volatile-lru，但希望基于频率淘汰。 |
allkeys-random/volatile-random | 随机淘汰。 | 所有 key 被访问的概率几乎相等，或者你对淘汰没有特殊要求，只追求速度。 |
volatile-ttl | 淘汰剩余存活时间（TTL）最短的 key。 | 你明确知道并希望优先淘汰即将过期的数据，常用于缓存层叠场景。 |
5.1 如何选择 LRU 还是 LFU？
这是一个没有标准答案的问题，取决于你的数据访问模式。
选择 LRU 的场景：
- 访问模式具有明显的时间局部性：最近访问过的数据，在短期内再次被访问的概率很高。例如，社交媒体的时间线、新闻客户端的最新列表。
- 存在“扫描式”或“循环式”访问：如果业务存在全量遍历 key 的操作（虽然不推荐），LRU 会因为最近被遍历过而保护了这些 key，可能导致真正的热点被误伤。这时需要评估影响。
- 实现简单，理解直观：LRU 的概念更容易被团队成员理解和接受。
选择 LFU 的场景：
- 访问频率是价值的核心指标：某些数据被访问的次数直接决定了其重要性。例如，热门商品详情、常用 API 响应缓存、基础资料库（如行政区划）。
- 希望抵御“一次性批量操作”的干扰：例如，一个爬虫脚本一次性读取了大量冷数据。在 LRU 下，这些冷数据会“污染”LRU 链表，挤走真正的热点。而 LFU 因为其概率递增和衰减机制，这些一次性访问的数据很难积累起高
counter值，很快会被淘汰。 - 存在“老而弥热”的数据：有些经典内容（如经典文章、常青商品）长期有稳定但不高频的访问。LRU 可能因为其一段时间没被访问而淘汰它，但 LFU 能凭借其积累的频率计数将其保留。
一个简单的判断方法：观察你的缓存命中率监控。如果使用 LRU 时，命中率波动大，或在特定事件（如爬虫、定时任务）后显著下降，可以尝试切换到 LFU 观察效果。
5.2 关键参数调优实战
maxmemory-samples(LRU/LFU 采样数)：- 默认值：5
- 调优建议：在内存充足、CPU 压力不大的情况下，可以适当增加到 10。通过
INFO stats命令观察evicted_keys趋势，如果淘汰量很大但命中率不高，可以尝试提高采样数以获得更精确的淘汰。增加到 10 以上通常收益很小。
lfu-log-factor(LFU 对数因子)：- 默认值：10
- 调优建议：这个值决定了 counter 增长的难度。值越大，counter 越难增长，不同访问量级 key 的 counter 值区分度越细。如果你希望更精细地区分“超级热”和“普通热”，可以调大（如 20）。如果业务访问量级普遍很大，希望快速区分热度，可以调小（如 5）。调整后，需要观察一段时间内不同热度 key 的 counter 值分布。
lfu-decay-time(LFU 衰减时间，单位：分钟)：- 默认值：1
- 调优建议：这个值决定了历史访问记录的“遗忘速度”。对于热点变化非常快的场景（如秒杀、实时热搜），可以调小（如 0.2，即12秒衰减1），让算法更关注最近几分钟的热度。对于热点稳定、希望长期保留的场景（如基础库），可以调大（如 60，即1小时衰减1）。
配置方法：可以在redis.conf中配置，也可以在运行时通过CONFIG SET命令动态调整，方便进行 A/B 测试。
CONFIG SET maxmemory-policy allkeys-lfu CONFIG SET lfu-log-factor 15 CONFIG SET lfu-decay-time 56. 常见问题与排查技巧
6.1 内存明明没满，为什么触发了淘汰？
这可能是因为 Redis 的maxmemory机制。当已用内存达到maxmemory阈值时，Redis 就会开始执行淘汰策略，而不是等到 100% 才行动。此外，Redis 的内存统计可能因为内存碎片而略高于实际数据大小。可以通过INFO memory命令查看used_memory（总分配内存）、used_memory_rss（进程实际占用的物理内存）以及mem_fragmentation_ratio（碎片率）。如果碎片率很高（比如大于 1.5），可能需要进行清理或重启。
6.2 设置了volatile-lru，但带 TTL 的 key 没被淘汰，反而noeviction报错了？
检查你的 key 是否真的设置了 TTL。使用TTL key命令查看，返回-1表示没有设置过期时间。volatile-*策略只会在设置了过期时间的 key 集合中进行淘汰。如果这类 key 的内存占用总和未达到maxmemory，但所有 key 的总和达到了，而volatile-*策略又找不到可淘汰的带 TTL 的 key，那么对于volatile-lru等策略，Redis 的行为会退化成类似noeviction，导致写操作报错。这是一个常见的配置陷阱。
6.3 LFU 的 counter 值为什么一直很低，上不去？
首先，确认 key 是否被频繁访问。其次，理解 LFU 的 counter 是基于概率递增的，且上限是 255。对于一个新 key，初始 counter 是 5（LFU_INIT_VAL）。如果lfu-log-factor设置得较大（比如默认的10），那么从 5 增长到 10 可能需要数十次甚至上百次访问。你可以通过OBJECT FREQ key命令查看一个 key 当前的 LFU counter 值。如果业务确实访问很频繁但 counter 增长慢，可以考虑适当调小lfu-log-factor。
6.4 如何监控淘汰效果？
INFO stats命令：关注keyspace_hits、keyspace_misses计算命中率，关注evicted_keys观察淘汰数量。一个健康的缓存，命中率应该较高且稳定，淘汰数量平稳缓慢增长。如果evicted_keys暴增，说明内存压力极大或淘汰策略可能不合适。INFO memory命令：关注used_memory、maxmemory以及mem_fragmentation_ratio。- 慢日志：如果淘汰过程（特别是采样过程）影响了性能，可能会在慢日志中体现。
- 自定义监控：可以通过定期采样
OBJECT FREQ或OBJECT IDLETIME（对于 LRU）来观察 key 的热度分布变化。
6.5 除了 LRU/LFU，还有其他优化思路吗？
绝对有。Redis 的淘汰策略是最后一道防线。更优的实践是“主动管理”：
- 合理设置 TTL：为缓存数据设置一个合理的、分散的过期时间，让数据自然过期，避免集中淘汰。
- 缓存维度化与分级：区分热点数据和全量数据。极热数据可以设置更长的 TTL 甚至永不过期，使用独立的 Redis 实例或数据库。
- 使用 Redis 4.0+ 的
MEMORY命令：MEMORY USAGE key可以精确计算一个 key 的内存占用，用于更精细的内存分析。 - 考虑使用 Redis Module：如 RedisBloom 的 Cuckoo Filter 可以用于解决缓存穿透，间接减轻内存压力。
理解 Redis LRU 和 LFU 的实现，最终目的是为了让你在“资源有限”这个永恒的技术约束下，做出更明智的决策。它不是一个“设置完就忘”的配置，而是需要结合业务监控、不断观察和调优的活组件。下次当你面对缓存命中率下降的告警时，希望你能想起这两个 24 位的字段，以及它们背后精巧的权衡艺术。