按年被提到
20152016 · 2 次2026
系统、数据库与网络›分布式数据与 CRDT·arXiv:1512.00727 · cs.OS

TinyLFU: A Highly Efficient Cache Admission Policy

TinyLFU:高效的缓存准入策略
Gil Einziger, Roy Friedman, Ben Manes · 2015

用近似 LFU 计数器决定新条目是否值得进入缓存

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 6 人首次 2016-01-29 · 最近 2022-10-01
6不同的人
7活跃月份
7讨论串
93被引(OpenAlex)

论文提出在访问分布偏斜时,用基于频率的缓存准入策略提升缓存效果:对新访问的条目和缓存中的淘汰候选者,依据近期访问历史判断是否值得以牺牲候选者为代价接纳新条目。实现手段是基于布隆过滤器理论的新型近似 LFU 结构 TinyLFU,紧凑且轻量,维护大量近期访问条目的近似频率。作者用合成负载和多个真实 trace 做模拟,展示了它给多种替换策略带来的命中率提升,并提出组合策略 W-TinyLFU,其命中率与其他先进策略持平或更好,且是唯一在所有 trace 上都取得如此结果的方案。

HN 为什么提它

HN 上的人在讨论缓存设计时推荐它,并提到 Caffeine 等缓存库用了 TinyLFU,以及它如何用计数布隆过滤器做空间高效的频率统计。

方法难度 3 / 5约 35 分钟经得起时间
读之前最好知道
1缓存替换策略(LRU、LFU)
2布隆过滤器(Bloom filter)
3计数布隆过滤器
4命中率与访问分布(偏斜分布)

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐NovaX · 2016-04

“I recommend reading the TinyLFU paper as I think it is the best match to your ideas.”

推荐读 TinyLFU,认为最契合对方的想法
Ask HN: Cache Hit Ratio原评论 ↗
推荐T0pH4t · 2020-08

“Maybe also consider tinylfu.”

建议也考虑 TinyLFU 缓存准入策略
Constant Time LFU原评论 ↗
引用NovaX · 2016-01

“you'd probably also want the window cache to correct the deficiency outlined in the updated paper”

指出更新版论文提到的缺陷需要用 window cache 来修正
Apache Traffic Server原评论 ↗
引用karlmcguire · 2019-06

“Counting Bloom Filters are useful as space efficient counters in LFU cache admission/eviction [1].”

拿它说明计数 Bloom filter 可作为 LFU 缓存准入的节省空间计数器
The Bloom Clock原评论 ↗
引用thomasmg · 2021-08

“the Caffeine cache (Java) uses TinyLFU”

指出 Java 的 Caffeine 缓存使用了 TinyLFU
Bloom Filters: More than a space-efficient hashmap原评论 ↗
被提交为 story · 2 次