知识卡片

普通读书笔记卡 · 2277.k.16

W-TinyLFU改进LFU

理解等级:未标注

LFU 有两个短板:精确计数开销大,旧热点难以褪去。TinyLFU 用 Count-Min Sketch 以少量空间近似估计访问频率,并用滑动时间窗定期把计数减半,让旧热点自然衰减。代价是一天只跑一次的突发访问难以快速积累频率而被误杀,这恰是 LRU 的强项。W-TinyLFU 把两者结合:新数据先进走 LRU 的窗口缓存攒热度,通过 TinyLFU 过滤后再晋升到分段 LRU 的主缓存,命中率更好。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《凤凰架构:构建可靠的大型分布式系统》第4章"透明多级分流系统" 4.6.1节"缓存属性"(源文件:_epub-src/OEBPS/Text/chapter54.xhtml) - 结论依据:原文说明TinyLFU用Count-Min Sketch近似估计频率、用滑动时间窗 衰减计数器解决LFU两大缺陷,又指出TinyLFU难以应对稀疏突发访问,W-TinyLFU 用前端LRU的Window Cache结合后端分段LFU的Main Cache弥补这一短板,直接 支撑本卡片结论。 - 原始内容:TinyLFU可以用相对小得多的记录频率和空间来近似地找出缓存中 的低价值数据……W-TinyLFU结合了LRU和LFU的优点,从整体上看它是LFU策略, 从局部实现上看它又是LRU策略。