1. 项目概述从缓存淘汰到算法抉择在构建任何依赖缓存来提升性能的系统时我们迟早会面对一个核心问题当缓存空间耗尽时应该“牺牲”谁这个看似简单的抉择背后是缓存系统效率和资源利用率的关键。Redis作为内存数据存储的标杆其内置的多种内存淘汰策略尤其是基于LRU最近最少使用和LFU最不经常使用算法的实现是每一位后端开发者、架构师乃至运维同学必须深入理解的“内功”。我处理过不少线上性能问题很多都直接或间接地与缓存淘汰策略配置不当有关。比如一个热门活动导致缓存Key激增错误的淘汰策略让最热的数据被意外清出瞬间拖垮数据库又或者某些具有周期性访问模式的数据因为策略不匹配无法在缓存中稳定驻留。理解Redis如何实现LRU和LFU远不止于知道几个配置参数。它关乎你能否根据业务的数据访问模型做出最合理的战术决策从而让每一分宝贵的内存都用在刀刃上。本文将彻底拆解Redis中LRU和LFU算法的实现机制。我不会停留在概念复述而是会深入到Redis源码设计层面结合我实际调优的经验讲清楚它们是如何工作的、各有什么优缺点、以及在不同业务场景下该如何选择和调优。无论你是正在为缓存策略头疼的工程师还是希望深化对Redis理解的技术爱好者这篇内容都将提供可直接用于实战的参考。2. 核心思路Redis淘汰策略全景与算法定位在深入LRU和LFU之前我们必须先站在全局视角看看Redis提供了哪些“武器”。通过CONFIG GET maxmemory-policy命令我们可以看到一系列选项它们大致分为三类不淘汰noeviction默认策略。当内存使用达到上限时所有会申请更多内存的命令如SET,LPUSH等直接返回错误读命令不受影响。这适用于数据绝对不允许丢失且你有其他独立机制如监控告警来处理内存压力的场景。对全体Key进行淘汰allkeys-lru从所有Key中根据LRU算法淘汰最近最少使用的。allkeys-lfu从所有Key中根据LFU算法淘汰最不经常使用的。allkeys-random从所有Key中随机淘汰。这通常只在没有明显热点数据或者数据访问完全随机时考虑实践中用得较少。仅对设置了过期时间的Key进行淘汰volatile-lru仅从设置了过期时间TTL的Key中根据LRU算法淘汰。volatile-lfu仅从设置了过期时间TTL的Key中根据LFU算法淘汰。volatile-random仅从设置了过期时间的Key中随机淘汰。volatile-ttl优先淘汰过期时间更近TTL越小的Key。选择allkeys-*还是volatile-*是策略设计的第一个关键决策。如果你的业务中所有数据都可以被缓存且缓存空间不足时淘汰旧数据是可接受的那么allkeys-lru/lfu是更直接的选择它能最大化利用内存来缓存热点。如果你的业务中有一部分数据是持久性存储未设TTL必须常驻内存而另一部分是可过期的缓存数据那么volatile-*系列策略可以保护你的持久数据不被淘汰只在缓存数据中做文章。而LRU和LFU的抉择则是第二个也是更复杂的决策。它取决于你的数据访问模式。LRU的核心思想是“时间局部性”它认为一个数据如果最近被访问过那么它在不久的将来也很可能被再次访问。因此它淘汰的是“最久未被访问”的数据。这非常适合有明显“最近热点”的场景比如新闻网站的头条新闻、社交媒体的最新动态流。LFU的核心思想是“频率局部性”它认为一个数据被访问的次数越多说明它越重要未来被访问的概率也越高。因此它淘汰的是“访问频率最低”的数据。这非常适合有长期稳定热点的场景比如电商网站的商品详情页爆款商品、经典教程文章、用户基本信息等。Redis的聪明之处在于它并没有实现一个“标准”的、教科书式的LRU或LFU而是基于内存和性能的权衡做了一系列精妙的近似实现。理解这些近似实现的细节正是我们合理使用和调优它们的前提。3. Redis的近似LRU实现基于采样的智慧如果让你实现一个标准的LRU你会怎么做一个典型的方案是维护一个所有缓存Key的链表每次访问一个Key就将其移动到链表头部MRU端链表尾部LRU端的就是候选淘汰对象。这个方案的时间复杂度是O(1)但它需要为每一个Key维护额外的链表指针在Redis这种存储海量Key、对内存极度敏感的系统里这种空间开销是不可接受的。Redis选择了一条不同的路近似LRUApproximated LRU。它通过在现有的数据结构上附加一个有限大小的“时间戳”字段并在淘汰时进行随机采样来以极小的额外开销实现接近真实LRU的效果。3.1 核心数据结构redisObject与lru字段Redis中每个值对象无论是String、List还是Hash都由一个redisObject结构体表示。这个结构体里有一个lru字段在LFU启用时它与LFU复用同一存储空间其长度是24位bit。typedef struct redisObject { unsigned type:4; // 对象类型 unsigned encoding:4; // 编码方式 unsigned lru:LRU_BITS; // LRU时间戳或LFU计数24位 int refcount; // 引用计数 void *ptr; // 指向实际数据的指针 } robj;在LRU模式下这24位用来存储一个以秒为精度的Unix时间戳低24位。这个时间戳会在对象被访问读或写时更新。由于只有24位它记录的不是一个完整的时间戳而是对当前全局LRU时钟server.lruclock一个每秒更新一次的全局变量取模后的值。这意味着这个“时间”是一个在约194天内循环的相对时间。对于缓存淘汰来说这完全足够了因为我们只需要比较哪个Key更“旧”。3.2 淘汰过程随机采样与淘汰池当内存不足需要触发淘汰时Redis不会遍历所有Key去找那个最旧的而是采用了一个“随机采样淘汰池”的算法。以allkeys-lru为例其过程如下初始化淘汰池Redis会维护一个固定大小默认为16可通过maxmemory-samples配置的“淘汰候选池”eviction pool。这个池子是一个数组每个元素可以存放一个候选Key及其对应的空闲时间idle time即当前时间减去该Key的lru时间。随机采样Redis从键空间中随机抽取maxmemory-samples个Key默认16个。计算空闲时间并填充池子对于每个采样到的Key计算其空闲时间idle time。然后尝试将这个Key插入到淘汰池中。淘汰池始终按照空闲时间从大到小即最旧到最新排序。淘汰采样和填充完成后淘汰池中空闲时间最大的那个Key即池子里的第一个元素将被选中并删除。这个算法的精妙之处在于空间开销极小每个Key只需24位的额外存储无需链表指针。时间复杂度可控淘汰动作的时间复杂度取决于采样数量maxmemory-samples而与总Key数无关是O(N)的其中N是采样数。你可以通过增大maxmemory-samples来提高近似的精度更接近真实LRU但也会增加淘汰时的CPU开销。Redis官方建议的平衡值是5到10。实操心得不要盲目增大maxmemory-samples。在Key数量巨大百万级以上时将其从默认的5提高到10通常就能获得非常好的近似效果而对性能的影响微乎其微。只有在缓存命中率异常低且你高度怀疑是LRU近似不准导致时才需要考虑继续调高并密切监控CPU使用率。3.3 LRU模式的局限性尽管近似LRU在大多数情况下工作良好但它有几个固有的局限性对“周期性访问”模式不友好想象一个场景有一批数据每天只被访问一次比如每日报表。在LRU看来每天它们被访问后就成了“最新”的会保护起来。而那些每秒钟都被访问的热点数据如果在一次采样中没被选中其“空闲时间”可能会意外地比每日访问的数据更长从而有被淘汰的风险。虽然概率低但在极端情况下会发生。无法区分热点程度一个被连续访问100次的热门Key和一个刚刚被访问1次的Key在LRU的视野里它们都是“最新的”地位相同。LRU无法积累历史访问频率信息。正是这些局限性催生了Redis对LFU算法的支持。4. Redis的近似LFU实现概率计数与衰减机制从Redis 4.0版本开始LFU算法被引入。LFU的实现更为复杂因为它需要记录访问频率。同样出于内存效率的考虑Redis设计了一个极其紧凑且智能的“概率计数器”来实现近似LFU。4.1 核心数据结构复用lru字段作为频率计数器在LFU模式下redisObject的lru字段24位被重新诠释。它不再存储时间戳而是被分为两部分高16位存储一个以分钟为精度的“衰减时间戳”last decrement time。用于配合衰减机制。低8位存储一个“访问频率计数器”logistic counter简称logc。这是频率的核心表示。是的只有8位最大值255来存储频率这显然无法直接记录一个Key被访问了成千上万次。Redis的解决方案是这是一个基于概率递增的对数计数器。4.2 概率递增算法Morris Counterlogc值的增长并非每次访问就1。它的递增是一个概率性事件值越大递增所需的“运气”就越好。具体规则如下计算一个概率因子p 1.0 / (counter当前值 * lfu_log_factor 1)。其中lfu_log_factor是一个可配置参数默认10。生成一个0到1之间的随机数r。如果r p那么counter就加1。这个算法的效果是当counter值很小时比如小于10p很大几乎每次访问都会增加。当counter值变大后p急剧减小增加会变得越来越困难。通过调整lfu_log_factor你可以控制频率计数的增长速度和上限。下表展示了在不同lfu_log_factor下counter值达到特定数值所需的近似访问次数目标counter值lfu_log_factor0 (线性)lfu_log_factor10 (默认)lfu_log_factor1001010访问约 100 次访问约 10万 次2020访问约 10,000 次访问约 2400万 次3030访问约 150万 次访问约 5.6亿 次255255访问约 1000万 次无法达到你可以看到默认因子10下一个Key需要被访问约1000万次其counter值才能达到饱和255。这足以区分出绝大多数业务场景下的热点等级。配置技巧如果你的业务中热点数据与冷数据的访问量级差距巨大比如相差百万倍可以适当调低lfu_log_factor如设为5让计数器增长更快更容易区分出中等热度的数据。反之如果访问模式比较平均可以调高它以获得更精细的区分度。4.3 衰减机制应对热点转移如果一个Key曾经很热但后来再也不被访问了它的高counter值会一直占着茅坑不拉屎导致它永远不被淘汰。这显然不合理。因此Redis引入了衰减机制。还记得lru字段的高16位吗它记录的是上一次衰减发生的时间单位分钟。Redis有一个全局的“LFU衰减时间”每过一分钟自增一次。当一个Key被访问时Redis会检查当前时间与Key记录的上次衰减时间的差值单位分钟。如果这个差值N大于0就会对counter值进行衰减将counter值右移N位相当于除以2^N。如果衰减后counter值小于5则直接设为5提供一个基础热度避免立即被淘汰。更新Key的衰减时间为当前时间。此外Redis还提供了一个配置参数lfu_decay_time默认1单位分钟。它的含义是经过多少分钟counter值应该减半。例如设置lfu_decay_time为10意味着如果某个Key在10分钟内没有被访问其counter值就会衰减一次右移1位。这个参数让你可以控制热点数据的“遗忘”速度。避坑指南lfu_decay_time的配置需要谨慎。设置得太小如1热点数据会很快“冷却”可能无法形成稳定的缓存。设置得太大如10080即一周又可能导致过时的热点长期霸占缓存。一个常见的起始建议值是601小时或14401天你需要根据业务访问模式的变化速度来调整。4.4 LFU的淘汰过程LFU的淘汰过程与LRU类似也采用随机采样和淘汰池。唯一的区别在于排序依据LRU依据的是“空闲时间”idle time而LFU依据的是“访问频率”即counter值。在淘汰池中counter值最小的Key即访问频率最低的排在前面优先被淘汰。5. LRU vs LFU场景化选型与配置实战理解了原理我们最终要落到选择上。下面这个表格从多个维度对比了两种算法特性维度LRU (最近最少使用)LFU (最不经常使用)核心思想淘汰最久未访问的数据淘汰访问频率最低的数据数据访问模式适配访问模式随时间快速变化有强烈的“最近”热点。如新闻Feed、最新评论、实时排行榜。访问模式相对稳定有长期、稳定的热点。如热门商品详情、经典文章、用户基础信息、头部视频。对“周期性访问”的处理不友好。周期访问的数据会保护自己挤占真正持续热点的空间。友好。通过衰减机制旧的周期性热点会逐渐冷却。对“突发流量”的处理敏感。一次突发访问能让一个冷数据变成“最新”保护它一段时间可能挤出其他数据。不敏感。单次或少数几次访问对频率计数影响很小不会立刻改变其淘汰优先级。实现复杂度与开销简单仅需时间戳开销极小。复杂需要概率计数器和衰减逻辑CPU开销略高于LRU。配置参数maxmemory-samples(采样数)lfu_log_factor(计数增长因子)、lfu_decay_time(衰减时间)选择建议业务热点随时间快速轮动或你无法清晰预知访问模式时的安全默认选择。业务有明确、稳定的头部热点且希望缓存能“记住”这些热点抵御突发流量的干扰。5.1 配置实战步骤假设我们有一个电商应用商品详情页是主要负载。我们知道有一些“爆款”商品常年畅销同时也有大量长尾商品。我们希望缓存能牢牢抓住爆款同时也能为近期被查看的长尾商品提供加速。这是一个LFU可能更优的场景。设置最大内存与策略# 在redis.conf中配置或通过CONFIG SET命令动态调整 maxmemory 4gb # 根据你的实例大小设置 maxmemory-policy allkeys-lfu # 我们决定使用LFU并允许淘汰所有Key调整LFU参数# 首先使用默认值观察 # 通过redis-cli用OBJECT FREQ key命令可以查看某个Key的counter值需Redis 4.0 # 如果发现爆款商品和普通商品的counter值拉不开差距比如都在20-30说明计数器增长太慢 CONFIG SET lfu-log-factor 8 # 调低因子让计数器更容易增长 # 如果发现一些过季的爆款商品仍然长期占据缓存counter值很高说明衰减太慢 CONFIG SET lfu-decay-time 360 # 设置为6小时让超过6小时未访问的热点冷却速度加快监控与验证使用INFO stats命令查看keyspace_hits和keyspace_misses计算缓存命中率。使用redis-rdb-tools等第三方工具分析RDB文件查看Key的频率分布。在业务低峰期进行A/B测试对比切换策略前后的缓存命中率和数据库负载。重要提醒修改lfu_log_factor和lfu_decay_time是全局性的会影响所有Key。务必在测试环境充分验证后再在生产环境灰度调整。调整后需要观察一段时间至少一个完整的业务周期因为LFU的效果是滞后的。6. 常见问题与排查技巧实录在实际运维中关于内存淘汰会遇到各种各样的问题。这里记录几个典型场景和我的排查思路。6.1 问题缓存命中率突然下降可能原因与排查步骤检查淘汰策略是否生效执行CONFIG GET maxmemory和CONFIG GET maxmemory-policy确认内存上限设置合理且策略已按预期配置。有时配置未加载或动态修改后未持久化导致重启后失效。确认数据访问模式是否突变排查业务侧是否有新功能上线、推广活动或爬虫导致访问模式从“稳定热点”变成了“随机扫描”或“周期批量访问”。这种模式下LFU可能不如LRU甚至Random。检查LFU计数器饱和如果使用LFU且lfu_log_factor设置过低可能导致热门Key的计数器很快达到255饱和。一旦饱和所有饱和的Key在LFU看来热度相同淘汰就会退化为类似LRU或随机行为。使用OBJECT FREQ抽查热门Key的counter值。采样数不足如果使用LRU且maxmemory-samples设置过小比如默认的5在Key总量很大时随机采样的近似效果可能很差导致误淘汰热点。可以适当调大到10并观察。6.2 问题使用volatile-*策略但内存依然写满导致OOM可能原因volatile-*策略只会在设置了过期时间TTL的Key中淘汰。如果你的大量内存被没有设置TTL的Key占用那么即使触发了淘汰也没有候选对象可以删除最终会触发noeviction类似的行为取决于版本和配置导致写命令失败。解决方案审查你的数据设计。确保所有预期可作为缓存被淘汰的数据都设置了合理的TTL。可以使用SCAN命令扫描并统计无TTL的Key的数量和内存占用。6.3 问题如何观测和调试淘汰过程Redis本身提供的淘汰过程信息有限。但我们可以通过一些间接手段监控evicted_keys通过INFO stats命令观察evicted_keys计数器。这个数字的增长直接反映了淘汰发生的频率。突然的飙升是内存压力的明确信号。使用慢日志淘汰操作DEL可能会被记录到慢日志中如果它执行得慢。可以通过SLOWLOG GET来查看。模拟测试在测试环境可以用DEBUG POPULATE命令快速填充大量测试数据然后强制设置一个很小的maxmemory观察淘汰行为是否符合预期。6.4 关于allkeys-lfu的一个“坑”在Redis中一个新创建的Key其LFU计数器初始值是多少是0吗不是。出于保护目的新创建的Key的logc初始值被设置为LFU_INIT_VAL其值是5。这意味着一个新Key不会因为刚开始访问频率低而被立即淘汰它有一个基本的“生存权”。但是这引入了一个细微的问题假设缓存已满且所有现有Key的频率计数都大于5。此时写入一个全新的Key这个新Key的计数是5。如果紧接着触发淘汰并且这个新Key不幸被采样到那么它就会因为计数最小而被淘汰掉尽管它刚刚被创建。这在理论上可能导致缓存污染永远存不进新的热点。在实践中由于淘汰是随机采样且新Key被创建后通常会被立即访问从而增加计数这个情况发生的概率不高但需要了解。如果你的业务有大量“一次性写入、随后立即访问”的缓存模式可以稍微调高lfu_log_factor让老Key的计数增长变慢从而相对提升新Key的生存机会。选择LRU还是LFU从来不是一道单选题。我个人的经验是对于大多数综合性业务可以从allkeys-lru开始它简单可靠。当你通过监控发现业务有明显的、稳定的头部热点并且希望缓存能更“智能”地记住这些热点时再考虑切换到allkeys-lfu并花时间仔细调整lfu_log_factor和lfu_decay_time这两个参数。记住没有最好的算法只有最适合你业务数据访问模式的算法。最好的调优依据永远是来自你生产环境的真实监控数据。