W-TinyLFU

10 December 2025   580 words   ~2 mins
#缓存 #算法 #后端开发

W-TinyLFU

前置理解

SLRU 分段最久未使用

分段的意思是将原来只有一段的队列分成两段，一段为 保护段 另一段为 试用段，其内部逻辑与 LRU 相同。 核心流程：

  1. 新数据会进入试用段
  2. 试用段中的数据再次被访问进入保护段
  3. 保护段中被淘汰的数据会回到试用段 SLRU 相比 LRU 的优势 在 LRU 场景下 如果短时有大量新的 散列的非热点数据访问可能导致缓存中的热点数据被移除替换导致 缓存污染，SLRU 的多级淘汰制可以减少这种情况的发送。

CountMinSketch 近似计数器器

原理与布隆过滤器类似，将输入的元素通过散列函数映射到不同的数组位置，每个位置每被映射一次该处的计数器就加一。当请求结果时就返回散列结果中计数最小的值作为计数结果，所以会导致类似布隆过滤器“假阳性”的问题，也就是返回计数比实际计数偏大。

W-TinyLFU

LRU 窗口缓存 + CountMinSketch + SLRU 核心流程：

  1. 新加入的缓存进入 LRU 窗口缓存
  2. 被窗口淘汰的缓存如果 SLRU 段未满则直接进入
  3. 否则从 SLRU 尾部选出将被淘汰的缓存 PK 最少使用的会被淘汰，胜利的会进入 SLRU

Reference

title: "W-TinyLFU缓存淘汰策略W-TinyLFU是一种非常优秀的缓存淘汰策略，它综合的考虑了现实场景中可能会遇到的各种问 - 掘金"
image: "https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/9cb71ed5731e4cddb4c664381140c6f7~tplv-k3u1fbpfcp-zoom-in-crop-mark:1512:0:0:0.awebp?"
description: "W-TinyLFU是一种非常优秀的缓存淘汰策略，它综合的考虑了现实场景中可能会遇到的各种问题，具有能够提高缓存命中率的准入策略，带有LFU的基于频率的优点，还具备元素保鲜机制，同时还能保证低空间消耗。"
url: "https://juejin.cn/post/7144327955353698334#heading-6"
favicon: ""
aspectRatio: "22.90249433106576"
← prev next →