推荐NovaX · 2016-04
“I recommend reading the TinyLFU paper as I think it is the best match to your ideas.”
推荐读 TinyLFU,认为最契合对方的想法
用近似 LFU 计数器决定新条目是否值得进入缓存
论文提出在访问分布偏斜时,用基于频率的缓存准入策略提升缓存效果:对新访问的条目和缓存中的淘汰候选者,依据近期访问历史判断是否值得以牺牲候选者为代价接纳新条目。实现手段是基于布隆过滤器理论的新型近似 LFU 结构 TinyLFU,紧凑且轻量,维护大量近期访问条目的近似频率。作者用合成负载和多个真实 trace 做模拟,展示了它给多种替换策略带来的命中率提升,并提出组合策略 W-TinyLFU,其命中率与其他先进策略持平或更好,且是唯一在所有 trace 上都取得如此结果的方案。
HN 上的人在讨论缓存设计时推荐它,并提到 Caffeine 等缓存库用了 TinyLFU,以及它如何用计数布隆过滤器做空间高效的频率统计。
“I recommend reading the TinyLFU paper as I think it is the best match to your ideas.”
“Maybe also consider tinylfu.”
“you'd probably also want the window cache to correct the deficiency outlined in the updated paper”
“Counting Bloom Filters are useful as space efficient counters in LFU cache admission/eviction [1].”
“the Caffeine cache (Java) uses TinyLFU”