这两年做Redis调优和面试准备绕不开的一个话题就是内存淘汰策略尤其是LRU和LFU这两个算法。你可以把它们理解成Redis内存遇到压力时的“清退机制”直接决定了当maxmemory被耗尽时哪些key会被优先踢掉、哪些key会被留下来继续提供热点数据。很多人背过配置名会写allkeys-lru和allkeys-lfu但真到需要回答“为什么选LFU而不是LRU”、“LFU的实现细节是什么”时往往就只能聊个表面。这篇文章我会结合Redis源码和实际生产调优经验把LRU与LFU的原理、区别、Redis中近似实现的方式以及到底该怎么选型完整拆解一遍最后也会聊一些我在线上踩过的坑和排查经验。适合正在做缓存治理的同学也适合准备Redis面试的工程师尤其是那些不想停留在“会用命令”层面、想真正理解内在逻辑的人。1. 为什么Redis必须面对LRU和LFU1.1 内存满了会发生什么先理解maxmemoryRedis是一个内存型数据库所有key-value都放在内存里。你会给它设一个内存上限也就是maxmemory比如maxmemory 4gb或者maxmemory 1gb。当数据量超过这个上限时Redis并不会自动给你扩容或者扩容磁盘它必须决定接下来怎么办。默认行为是拒绝写入直接返回OOM错误比如OOM command not allowed when used memory maxmemory。这在生产环境里是不能接受的因为缓存场景的Redis通常只是加速层一旦拒绝写入后面的业务就会报错或者直接打到数据库。所以更好的做法是设置maxmemory-policy也就是当内存达到上限时Redis主动淘汰一部分key腾出空间给新数据。淘汰策略的核心就是“怎么选key”而LRU和LFU是其中最常考的两种选择逻辑。1.2 淘汰策略全景从LRU到LFU再到其他Redis支持的淘汰策略细分下来有这么几类noeviction默认策略不淘汰内存满了直接拒绝写命令。allkeys-lru从所有key中按LRU最近最少使用淘汰。volatile-lru只在设置了过期时间的key中按LRU淘汰。allkeys-random从所有key中随机淘汰。volatile-random只在设置过期的key中随机淘汰。volatile-ttl按剩余TTL排序淘汰最早过期的key。allkeys-lfu从所有key中按LFU最不经常使用淘汰。volatile-lfu只在设置过期的key中按LFU淘汰。从这里面你能看到LRU和LFU是唯二的“基于访问模式”的淘汰策略它们更聪明能最大化保留热数据。随机和TTL策略都有明显的局限随机淘汰无法判断热度TTL只适合那些明确设置了过期时间的临时数据。所以如果你连expire都没设置volatile-*策略实际上一个都不会淘汰等于白配这个坑我后面会再提。2. LRU与LFU的核心原理与本质区别2.1 LRU按“时间”淘汰看最近有没有被访问LRU全称是Least Recently Used最近最少使用。核心逻辑是假设如果一个key刚刚被访问过那么它在未来被再次访问的概率也比较高因此优先淘汰的是“最长没有被访问过”的key。类比现实场景就像你的衣柜你最近经常穿的那几件外套一定放在伸手就能拿到的位置而那些几个月没穿的衣服被你塞在衣柜深处。当你衣柜装满时你会先把角落里那些长期不穿的拿出来丢掉这就是LRU的思路。实现上一个标准的LRU需要记录每个元素最后被访问的时间。新元素插入时记录当前时间访问已有元素时更新时间淘汰时找到时间戳最老的key。2.2 LFU按“频率”淘汰看谁被访问的次数少LFU全称是Least Frequently Used最不经常使用。核心逻辑是一个key在很长一段时间内被访问的频率越高说明它越是长期热数据应该尽量保留。淘汰时优先踢掉访问频次最低的那个key。还是衣柜的例子LRU看的是“最后一次穿是什么时候”而LFU看的是“一年里穿了多少次”。有些衣服你可能昨天刚穿过一次但一年只穿那一次LFU就会觉得这衣服整体价值不高反而是那种每周都穿、但昨天碰巧没穿的衣服LFU认为值得保留。2.3 LRU与LFU对比表时间维度 vs 频率维度维度LRU最近最少使用LFU最不经常使用判断依据最后访问时间访问频率适合的访问模式有突发性、短期热点长期稳定热点缺点偶发性访问可能把热key冲掉老热点可能永远占据内存不被淘汰内存开销每条记录存一个时间戳每条记录存时间和计数Redis实现24bit近似时钟16bit计数器衰减机制举个真实场景你的缓存里有一个商品详情页平时访问量不大但某天它被KOL推荐了之后短时间流量暴涨。LRU会因为它“最近被大量访问”而保留它LFU却因为它在之前的统计周期里访问基数低即使被突击访问一次也只算一次低频数据反而可能被淘汰掉。所以两种算法没有绝对的好坏完全取决于你的业务访问模式。3. Redis中LRU的实现近似LRU与采样淘汰3.1 为什么Redis不用精确LRU标准的精确LRU需要维护一个双向链表每次访问都要把节点移动到链表头部这需要额外的指针和内存还要处理并发和锁。对于Redis这种追求高性能的KV存储所有主操作都拿CPU时间内存结构越简单越好。Redis采用了一种近似LRU的实现。在每个Redis对象robj里使用lru字段存放一个24bit的时钟值这个值记录的是该对象最近一次被访问的时间相对时间。因为只有24bit时钟会周期性回绕但配合Redis时钟机制可以判断相对新旧。淘汰时它不会扫描所有key而是随机抽取一部分key按lru值排序淘汰最旧的。默认抽样数量是5通过maxmemory-samples配置调整。3.2 抽样采样与淘汰池优化Redis的近似LRU第一版是全量抽样也就是每次从某个方向取出maxmemory-samples个key比较它们的lru值把最旧的那个淘汰掉。这个办法的问题在于如果抽样数量太小最终淘汰的key可能并不是全局最旧的。为了解决这个问题Redis引入了淘汰池eviction pool机制。每一次淘汰时会从待淘汰集合中随机抽样多次每次抽maxmemory-samples个把“较旧”的key加入到淘汰池中。淘汰池本身也是一个按idle排序的数组当池子满时只保留最旧的若干个。最终在池子里选择最旧的那个key进行淘汰。这个过程可以重复多轮可以理解为真实LRU是全局精确搜索Redis的近似LRU是“多轮随机抽样 池子排序”在CPU开销和淘汰质量之间取得了一个平衡。3.3 配置项maxmemory-policy与maxmemory-samples[plaintext] maxmemory 4gb maxmemory-policy allkeys-lru maxmemory-samples 5 ]maxmemory-policy指定淘汰策略这里是全局LRU。maxmemory-samples每次抽样数量默认5。调大这个值会让淘汰更接近精确LRU但会消耗更多CPU。我一般推荐生产环境调到10左右因为Redis是一个单进程处理命令淘汰时如果耗时太长会阻塞后续命令。注意maxmemory-samples只是近似LRU中“抽样数量”的替代不代表一次最多淘汰多少个keyRedis在每个事件循环里会循环处理多次直到内存降到maxmemory以下。体验是如果你把maxmemory-samples调得特别大比如20、30内存淘汰会更精准但在高并发写入时Redis的CPU占用会明显上升有可能会影响其他正常命令的延迟。所以这个值要克制。4. Redis中LFU的实现概率计数与衰减机制4.1 16bit计数器如何记录访问频率LFU很难在有限内存下精确实现因为每个key的“访问计数”理论上可能无限增长。Redis用了一个很巧妙的办法在robj的lru字段里24bit的空间被拆成了两部分。高位16bit保存一个last decr time格式是“分钟级时间戳”记录上一次衰减计算的时间。低位8bit保存一个访问频率计数器counter。也就是说LFU的计数器最大只有255访问频率超过255也不会继续拉大。但是问题来了如果一个key被频繁访问它的计数器会很快冲到255然后所有高频key都是255没法区分谁更热点。所以Redis不是简单地进行加1操作而是采用“对数递增”的方式。4.2 对数递增的本质让计数增长越来越慢Redis的LFU计数器更新规则是每次访问key时一个随机数会被用来决定计数值是否增加。判断原则是计数越高增加的概率越低。核心代码逻辑类似#define LFU_INIT_VAL 5 uint8_t LFUDecrAndReturn(robj *o, long now) { ... }更直接一点new值 old值 1的概率是1/(old * lfu_log_factor 1)。所以计数是1时几乎100%递增计数是255时增长概率已经非常低。这种设计保证了高频key不会全部饱和在255低频key又能快速积累计数。这里有个隐含配置lfu-log-factor默认是10。调大这个值会使得“计数值增加更慢”也就是更难从低频变为高频调小则相反。从实际调优效果看如果你的热点key被频繁访问但很快又会被淘汰可能是lfu-log-factor太小导致计数迅速满了然后又因为时间衰减导致计数被周期清掉。4.3 衰减机制为什么要衰减LFU如果只统计绝对访问次数会出现一个尴尬局面一个冷门key曾经在历史上火过一次比如去年双十一的高流量商品之后再也不访问了但它的计数可能还是很高。由于它一直占着内存LFU算法会认为它是热点永远不淘汰它这显然不对。Redis通过lfu-decay-time参数控制计数衰减。它的单位是分钟默认是1。每次访问key的时候计算出上次衰减到现在经过了多少个lfu-decay-time的周期如果超过周期就把计数器按差值递减。uint8_t LFUTimeElapsed(unsigned long now, unsigned long last) { // 计算相差了多少个decay time周期每周期计数值减一 }举个例子如果lfu-decay-time1表示每分钟访问不到一次的话计数就会逐步减少。如果lfu-decay-time60表示每小时才做一次衰减更迟钝。我在生产环境里配置LFU时会把这个值调成1分钟配合lfu-log-factor10对一些中长期热点比如会员信息、配置信息的命中率有明显提升。4.4 LFU配置示例[plaintext] maxmemory-policy allkeys-lfu lfu-log-factor 10 lfu-decay-time 1 ]注意volatile-lfu同样是只对设置了过期时间的key生效。如果你的业务里所有key都有过期时间那就用volatile-lfu也可以但最通用的还是allkeys-lfu。5. 选型指南该用LRU还是LFU别光看名字5.1 业务访问模式决定一切选LRU还是LFU核心看你的访问模式。如果你的缓存访问具有明显的短期突发性比如新闻热点、秒杀活动、被推荐的帖子这些key只会在一小段时间内被大量访问之后很快沉寂那LRU其实更合适。因为LRU只认“最近是否访问过”能快速识别出当前正在火的数据也会在热度过去之后因为长时间没人访问而被自然淘汰。如果你的业务访问模式是长期均衡型比如用户体系里的个人资料、权限配置、商品基础信息这类key的访问频率总体稳定还偶尔会有人扫一遍这时候LFU更有优势。LFU能识别出“每天都有人访问但不够爆发”的key从而不会因为某一次偶发访问就错误地把它当热点也不会因为某个key刚好不在最近访问窗口里就被误删。反过来看LFU的劣势也很明显如果某个key曾经是热点访问次数很高即使现在不火了只要后续没有太多低频key来竞争淘汰它可能长时间占用内存。这种时候就需要配合lfu-decay-time否则容易内存被历史热点占满新的热点进不来。5.2 结合缓存治理场景穿透、击穿与雪崩选型不是孤立拍脑袋要结合你的缓存治理策略。如果你的系统容易出现“缓存穿透”也就是查询一个不存在的数据导致请求直接打到数据库那你更关心的是如何保护数据库。穿透通常和淘汰策略关系不大更侧重于布隆过滤器或空值缓存因为不存在的key本身无所谓淘汰不淘汰。如果系统容易出现“缓存击穿”也就是一个热点key在过期的一瞬间有大量请求去重建缓存那选LFU会更友好。因为LFU能更准确地把高频key识别出来在淘汰时尽量不动它们。我在一个物流查询服务里就是这样做的把运单状态的缓存位点配置为volatile-lfu配合稍长的过期时间击穿率下降很明显。如果系统整体对缓存命中率要求很高所有key都希望能尽量长时间保留那你可能还要考虑键本身是否存在命中的随机性。比如有些key只是被偶尔读一次但它们体积很大一次性就占掉大量内存这时候LRU反而不友好因为每次被访问都会刷新它的时间。LFU则会让大体积低频key快速淘汰给高频小key腾地方。5.3 一份选型参考矩阵业务场景推荐策略理由热点秒杀LRU短期突发流量需要快速保留当前热点会员资料、配置LFU长期稳定访问需要抵抗偶发访问数据预热型缓存LRU一次性批量载入访问时间集中低频大key多高频小key多LFU频率优先避免大key长期占内存所有key都设置了过期时间volatile-lru/lfu没有过期时间时volatile策略失效完全混沌无法预测模式allkeys-random兜底策略最差但不是不能用一个更稳妥的做法是先用LRU跑一段时间观察evicted_keys和命中率再切到LFU对比用数据说话。我自己在好几个项目里都是这样做的不要迷信配置名要相信监控指标。6. 实操调优与常见问题排查6.1 用INFO命令直观查看淘汰情况无论你选LRU还是LFU都要能监控淘汰是否如你预期。Redis提供了INFO stats信息其中evicted_keys字段会告诉你累计淘汰了多少个key。你可以每隔一段时间采样这个指标如果它增长很快说明你的内存上限和淘汰策略正在频繁工作。同样值得关注的是keyspace_hits和keyspace_misses它们分别代表key被命中和未命中的次数。命中率公式大概是hits / (hits misses)。如果你的命中率持续走低即使淘汰策略是LFU也可能是采样数量不够或者热点key本身生命周期太短。在INFO memory里你还能看到maxmemory_human和used_memory_human结合这两个值判断当前内存水位。如果内存一直顶在maxmemory附近说明你的容量规划本身偏紧不要全指望淘汰策略应该考虑扩容或换用更省内存的数据结构。6.2 常见坑配置了却没用或者用错了第一个常见坑是配置了volatile-lru或者volatile-lfu但业务里有一大批key没有设置expire那么这些key永远不会被淘汰。因为volatile-*策略的淘汰范围只包含设置了过期时间的key没设置的key会像“铁公鸡”一样始终占用内存。第二个坑是大家都以为maxmemory-samples调越大越好其实要结合Redis的模型。Redis是单线程处理淘汰时每次抽样都要排序、池化这个过程如果太重会拖慢主线程影响所有命令。建议先保持默认的5线上通过压测证明需要更精确时再慢慢调大到10-15同时关注Redis的CPU使用率。第三个坑是LFU的lfu-decay-time设置得太小。我见过有人配置lfu-decay-time 1结果所有key的计数都在快速衰减最终LFU退化成近似LRU甚至因为计数一直减不到0而导致冷门key无法淘汰。这个参数的设计是“分钟”为单位如果你业务里访问间隔本身就很大可以设置成5或者10。第四个坑和淘汰无关但影响很大很多人在做缓存时误以为maxmemory-policy只决定淘汰就觉得设置成LRU/LFU之后一定不会有OOM。实际上如果maxmemory设置得非常大或者内存中单key体积特别大导致一次写入就超过上限在这种极端情况下Redis也可能无法一次性淘汰足够空间仍然会拒绝写入。所以淘汰策略不是银弹容量规划更重要。6.3 面试角度这些点必须能讲清楚先回答“LRU和LFU的区别”不要只答一句话“一个是最近最少使用一个是最不经常使用”。要展开说LRU基于时间维度适合突发性访问LFU基于频率维度适合长期稳定热点。而且要点出Redis中的实现是近似的LRU用采样淘汰池LFU用16bit计数器衰减。再回答“Redis的LRU为什么是近似实现”说清楚为了省内存、避免维护双向链表采样5个key用淘汰池提升准确率。如果面试官追问“还有什么改进空间”可以说可以结合业务的访问模式去调整maxmemory-samples和淘汰池轮数。关于LFU可以聊“计数器为什么最大255”因为它用了8bit来存频率。再聊“为什么叫对数递增”因为递增概率随着计数器值增大而减小这样能区分高热度key和超高热度key。还有一个高频问题是“自己设计一个LRU怎么做”。这个通常有两种答案一种是利用Java的LinkedHashMap设置accessOrdertrue重写removeEldestEntry就能实现一个简单的LRU另一种是哈希表双向链表get时把节点移到头部put时如果超过容量就删除尾部节点。LFU实现复杂度更高比较常见的方案是双哈希表最小堆或者三条双向链表这个如果实在讲不清楚至少说出“用计数器排序”这一层。6.4 真实线上落地经验我之前负责过一个广告投放平台的Redis缓存原先用的allkeys-lru线上内存一直顶在4GB但命中率大概只有85%左右。后来我分析了业务请求分布发现大部分访问集中在少量的某几个广告位配置对象上属于典型的长尾低频头部长热。于是我把策略切成allkeys-lfulfu-decay-time设为5lfu-log-factor设为10然后又跑了三天命中率提升到了95%左右。但这并不意味着LFU永远比LRU好。另一个项目做的是活动日历缓存每个活动只在活动期内被高频访问过了活动期就彻底变冷。在这里LFU反而成了拖累因为历史热门活动计数很高很难被淘汰。后来切成allkeys-lru活动结束后很快会被自然淘汰内存利用率高了不少。所以我个人的核心体会是不要只看理论一定要结合监控数据去调。而且切换策略前最好先把maxmemory-samples的配置预留好因为近似LRU和近似LFU在Redis里的抽样机制是共用的你调优maxmemory-samples的效果在两种策略里都能体现。另外如果你用Redis做缓存时还涉及到主从或哨兵一定记得主库和从库的maxmemory-policy要保持一致否则主从切换后缓存淘汰行为可能出现差异。这个看似细节的小坑我曾经在排查线上问题时花了不少时间才定位到。