LRU淘汰算法优化本文链接这个项目中为了提高缓存命中率我需要一个算法这个算法的触发时机当缓存超出阈值后进行淘汰淘汰时脏数据先刷盘落盘,干净数据直接清缓存(假设磁盘已有副本)在数据集中热门数据会被经常访问应当长期存放于内存中不应该被淘汰而冷门数据由于长期未被访问所以在淘汰过程中应该被放进磁盘清理缓存中的这个数据这时候我们就可以用LRU最近最少使用算法根据最近访问次序在链表中有序排列然后再淘汰的时候淘汰掉前n个最近未访问的数据最久没用的先淘汰具体实现方式可以参考力扣题目LRU缓存局限性这个算法根据次序进行排列然后删除最近未访问的数据但如果考虑每个数据的数据大小和缓存容量那就会体现这个算法的局限性大对象只要保持不是最久没用,就永远不被淘汰这会导致在多轮淘汰后缓存的数据可能会被大数据占满数据量少导致淘汰频繁命中率低假设用户访问一个大数据未在缓存会在磁盘中读取出来然后这个数据导致缓存超出阈值了使得其他很多热门小对象被淘汰而此后这个大数据就没被访问了造成浪费举个例子一个 1MB 的数据 2 小时没用,而 100 个 1KB 的 1 天没用,LRU 会先淘汰那 100 个小数据(腾 100KB),1MB 的继续占着(占 1000 倍内存)大对象写入缓存后造成了污染如果那100个小数据全是热门数据如1分钟内访问由于大对象是最新访问就丢失了100个小数据如果再访问这些数据就要进行大量的磁盘IO且由于大对象会占用比较多的缓存空间导致比较频繁的淘汰策略从而导致大量的淘汰和磁盘IO而如果对象的大小比较均衡这个算法还是可以的如果运行一段时间这个缓存中间件的缓存中主要以热门大数据为缓存导致了缓存的数据量很少而其他众多的热门小数据可能会进行大量的淘汰和磁盘IO分析需求因此我需要同时考虑数据大小和使用频率这两个维度但仔细思考会发现使用频率在某些场合似乎依旧不合适热门数据是有时效性的假设一个数据A在某一个小时内被访问了100w次如某些秒杀场景而在之后的一周内数据A均未被访问过但是它的访问频率依旧非常高造成缓存污染而正常情况下热点数据过了就应该被清掉而不是留在缓存中因此当时在分析的时候我还是决定用数据大小和最近时间间隔这两个维度但是我们需要做一些处理使得结果尽可能拟合实际且时间间隔已经在一定程度上包含了频率这个信息因为高频的数据时间间隔也会比较小低频数据时间间隔就长而且我用的是最近使用间隔避免了刚刚的秒杀造成的缓存污染使用数据大小和频率其实也可以不过也要进行一些处理这里我用时间间隔并进行一些处理这个存储引擎还需要存储自定义数据类型这可能会导致存储的数据大小差异会比较大因此要考虑数据大小总结一下淘汰中我们需要考以下因素缓存阈值数据大小最近时间间隔淘汰设计现在我们需要借助这几个因素想办法如何淘汰淘汰性价比最高的数据这里我用分数去表示性价比而分数需要由数据大小和最近时间间隔这两个维度考虑分数越大越需要被淘汰原因如下如果淘汰比较大的数据那么能更快处理淘汰缓存更快的低于阈值且保证缓存中的热点数据比较多如果淘汰最近时间间隔比较长的数据目的和LRU一样我们需要设计一个二元函数去通过这个两个维度计算分数先看下这个分数怎么用为了尽快处理淘汰少影响性能我参考了Redis的思路随机采样淘汰并结合LRU做了个新的使用方法和标准的LRU一样力扣语义维护一个最近最少使用链表头是最近使用尾是最久未使用淘汰时从尾部往回采样n个数据最久未用区域然后逐个算分数淘汰分数最大的看起来这个淘汰策略还是比较直观的链表的尾部区域就是冷门数据比例比较多的地方比Redis的全局随机采样淘汰理论上会好点然后我们看看分数怎么计算分数 f(数据大小) g(最近间隔) 数据大小dataSize 最近时间间隔interval时间模块在C中用std::chrono::time_point一般转换后数值比较大数据大小也是大对象可能会有几百MB转换为B后数值也很大而小对象却很小这会造成量纲失衡我们需要压缩量纲适当减少数量级的差异这里我对dataSize和interval取ln这样大数据在取对数后就很小了分数 ln(interval) ln(dataSize)但这又有个问题log(时间间隔)把量级都压缩了(一天和一小时的差距太小)场景如果有一个很大的数据经常被访问(时间间隔接近0)而其他数据一天都没被访问就会把这个大的数据给淘汰因为时间差距太小了导致这时候以数据大小为评判标准把热门数据踢出了于是我又想到在ln取对数后在前面加上系数来平衡经过AI的帮忙进行一顿计算最后发现interval和dataSize取对数后系数比为3:1比较合适以时间为主数据大小微调这个比例能够解决上述场景了但如果我们换一个场景这里我用了AI造的一组数据3:1 下时间为主是软性的(权重 3 倍),不是硬隔离。时间差 e 倍 3 分,大小差 e³ 20 倍 3 分 ——大 20 倍可以抵消老 2.7 倍。举个实际例子(score 3·ln(interval) ln(size)):100KB,3 小时没用:3×23.1 11.5 80.81MB,2.7 小时没用:3×23.0 13.8 82.81MB 的只新了 20 分钟,就因为大 10 倍反超,先被淘汰。最初担心的大数据侵蚀时间排序只是被压住,没有消除 —— 大小差异越大,这个反超越频繁。**问题**这个比例是静态的如果我们换一个场景可能这个系数比例就不合适了甚至淘汰策略会很烂更不用说一些在动态变化的业务场景我们还需要让这个公式具备一定的动态性可能会问那么把系数弄成动态的不就行了根据实际场景动态创造系数然后执行函数计算分数比如我们根据当前缓存数据量缓存大小来决定系数比但实际上由于每次CRUD都需要对访问的数据进行更新每次都要计算分数但到了淘汰的时候由于每个分数的值都是由不同的临时创造的函数计算得来这导致每个分数的依据也不一样(缓存数据量缓存大小不一样)因为刚刚的实际场景是动态变化的那么这个函数也会动态变化分数的依据也会动态变化这导致淘汰没有一个统一的标准淘汰没有意义那么还能怎么解决最终公式设计我最终想到了根据interval进行分段硬处理计算公式score 时间档位 * 档距 ln(dataSize) 时间档位(建议静态常量表):1min / 1h / 1d / 7d / ≥7d 五档,也可以根据具体业务调整通过interval进行量级选择 档距取 30ln(dataSize) 最大约 ln(memoSize) ≈ 20~25(10GB 经计算也就 23)档距30 保证跨档绝对无法依靠dataSize翻盘也就是说依靠LRU随机采样后优先删除挡位靠后的相同挡位的话比较dataSize这样也减少了一个ln计算这个公式既兼顾了interval也兼顾了dataSize且不需要调参档位边界是自然时间锚点(1min/1h/1d/7d)任何业务都直观极端场景(数据集中在档位临界)也只需调整档位表这个算法还有一点小问题经过资料的查阅说是QPS在百万以上的话log计算可能会成为性能消耗不过一般情况下也不会出现这类问题如果确实需要我们可以把ln更换为近似计算减少性能消耗算法总结LRU算法优化缓存数据淘汰策略维度有两个数据大小dataSize和最近使用间隔interval动态维护一个哈希链表LRU和力扣的最近最少使用算法一样分数计算公式score 时间档位 * 档距 ln(dataSize) log:ln 档位(建议静态常量表):1min / 1h / 1d / 7d / ≥7d 五档,也可以根据具体业务调整 档距取 30:ln(dataSize) 最大约 ln(memoSize) ≈ 20~25(10GB 也就 23),30 保证跨档绝对无法翻盘 由于log会导致量纲过度压缩一些数量级的差异不明显(比如一天未使用的小数据未被淘汰而把经常使用的大数据淘汰了这是非常影响性能的) 而如果对ln(dataSize),ln(dataSize)两个分别设置系数的话由于是静态的系数很难取到一个很好的值来满足大部分业务 分档加档距去做能符合大部分业务场景极端情况就是很多数据都集中在挡位临界上但这种情况非常少。但即使出现这种情况也只需重新分档调档距即可然后进行尾部采样比如15个为一组然后算分数值淘汰掉分数最大的淘汰n次直到缓存大小低于阈值先删除过期数据再进行淘汰淘汰的瓶颈不在计算log上所以dataSize的处理暂时先用ln如果后续测试发现确实在log上再重新设计dataSize的处理比如可以用近似计算ln换一种量纲压缩工具由于该项目需要存储自定义数据类型对象大小差异一般比较大所以考虑了数据大小这个维度比较借助AI辅助总结了一下对比项标准 LRU力扣精确版Redis 近似 LRU本算法淘汰依据单维最久未使用单维最久未使用近似双维时间间隔分档 数据大小淘汰对象选择精确直接删链表尾全局随机采样n 个默认 5删最久未用的链表尾部最久未用区域采样 15 个算分数删最大容量管理按条数按字节maxmemory按字节curSize vs memoSize数据大小不区分每条等权不区分每条等权ln(dataSize) 加权同档先淘汰大的时间区分连续精确连续采样近似档位硬隔离1min/1h/1d/7d跨档绝对优先时间复杂度O(1)O(samples)O(15) O(1)淘汰精度精确近似采样 5~10越调大越接近精确近似采样 15且采样区集中于高分区域理论上优于全局随机参数无maxmemory-samples 可调档位表自然时间锚点通常不用调核心弱点大对象占满缓存、单次访问大对象污染缓存不感知大小大对象同样污染档位临界处近似极少见调档位表即可一句话对比标准 LRU:精确、O(1)、无参数,但只看时间不看大小,大对象污染缓存Redis 近似 LRU:用随机采样换掉精确排序(O(samples)),按字节管容量,但仍然不看数据大小—— 大对象和小对象等权,大对象污染问题没解决本算法:保留 Redis 的采样思路,但把采样区从全局随机改为链表尾部(更聚焦高分区域),并加上大小维度 时间档位硬隔离—— 解决大对象污染,同时刚使用的大数据受档位保护不被误淘汰本质:标准 LRU 管谁最久没用,Redis 管谁大概率最久没用,本算法管谁最该走——久不用的大对象先走,刚用的多大都留下。