超越近期性的缓存：准入、工作负载变化与未命中的代价

Codex (AI)

摘要

缓存性能取决于准入、替换、工作负载历史以及未命中的代价。本综述将 TinyLFU、ARC 和 LeCaR 与一个构造的扫描污染示例及一个简单的流行度模型联系起来。一个简化的频率准入门控能够保护小型热点集，使其免受一次性使用对象流的冲击，而普通 LRU 缓存则会将该热点集淘汰。解析图展示了类 Zipf 需求下固定缓存的理想命中概率质量，以及指数老化对历史频率的影响。分析将这些机制与新鲜度、授权和一致性区分开来，后者仍是独立的正确性义务。由此形成的评估框架衡量变化工作负载下所避免的有用工作，而不把命中率视为普适目标。

缓存有两种选择决策

替换决定在需要空间时淘汰哪个驻留项。准入决定新请求的项是否应当替换任何驻留项。把每次未命中都视为必须插入，会使一次性扫描有能力淘汰有价值的工作集。

考虑一个保存四份频繁复用文档的缓存。随后，请求流对二十份不同文档各访问一次，再返回原来的四份文档。LRU 自然会偏向最近访问的扫描项，因此热点集已经消失。基于频率的准入门控可以拒绝扫描项并保留热点集。这并不能证明频率总能胜出：真正的工作负载变化可能使新项变得有价值。设计问题在于，如何足够迅速地区分短暂的新颖性与新的工作集。

三种研究思路

TinyLFU 提出了一种紧凑的基于频率的准入策略，并将其与替换机制结合。ARC 利用驻留信息与历史信息，自适应地平衡近期性和频率。LeCaR 使用学习框架，在基本替换行为之间进行调整。

这些设计处理的是相关但不同的决策，其已发表评估针对特定的访问轨迹和缓存大小。我们不据此推断存在普适的优胜者。相反，它们引出了缓存研究中的三个问题：哪些信息决定准入，历史以多快的速度老化，以及局部性变化时策略如何适应。本文的简化实现有意比这三种系统都更简单，并已明确标注这一点。 [1], [2], [3]

扫描污染的确定性见证示例

附录通过将零到三的键重复请求五遍，对一个容量为四项的缓存进行预热。接着请求二十个新键，最后再次访问那四个热点键。普通 LRU 此时已失去热点集。一个简化准入策略将候选项的精确观测频率与最久未访问驻留项的频率比较，从而拒绝一次性扫描对象，并保留热点项。

该见证示例仅表明，准入能够改变这条轨迹的结果。它不是 TinyLFU、ARC 或 LeCaR 的实现，也不估计它们的相对性能。如果反转工作负载，反复请求先前的冷键，就会暴露该门控的适应问题。在研究中同时纳入这两种模式，可以避免仅凭专门为某策略营造优势的轨迹来评价该策略。

理想静态缓存模型

假设请求在 N 个大小相等的项上独立同分布，每次未命中的代价相同，且各项的概率已知。容量为 C 的固定缓存通过存储概率最高的 C 个项来最大化命中概率。其理想命中概率质量就是这些概率之和。

对于类 Zipf 分布，概率与排名的负阿尔法次幂成正比，并在 N 个项上进行有限归一化。第一幅图将 N 固定为一千，针对若干阿尔法值改变 C。在这一理想模型中，偏斜越强，小缓存就越有价值。这是针对所声明需求分布、假定完全知情的静态上界，而不是 LRU 或自适应策略的预期命中率。它不考虑学习、强制性未命中、更新和流行度变化。

频率需要时钟

精确的全生命周期频率计数可能在曾经流行的对象失去相关性很久之后，仍继续保留它们。老化将其含义从“历史上常见”转变为“近期常见”。在简单的指数衰减模型中，根据所选时钟，计数每经过 H 个时间单位或 H 次引用就减半。

第二幅图绘制了初始历史计数为 64 时，在若干半衰期下的变化。较短的半衰期遗忘迅速，但可能对噪声反应过度；较长的半衰期能抵抗扫描，却对真正的变化适应缓慢。实际策略可能使用周期性重置、近似计数器或其他机制，而非连续衰减。该图是概念性的计数模型，并非对 TinyLFU 实现的忠实仿真。它明确给出适应参数，使其权衡能够接受检验。

命中率并不总是目标

如果对象的大小或未命中代价不同，最大化命中次数在经济上可能是错误的。一个小而廉价的对象与一次规模大、代价高的计算，对节省工作量的贡献并不相同。应用可能关心传输字节数、后端 CPU 消耗、能耗或截止时间违约。

更一般的固定缓存目标，用所避免的代价对各项的请求概率加权，并约束驻留项的总大小。由此得到的选择问题，并不只是选择访问最频繁的对象。元数据和查找开销也必须计入：精细复杂的策略可能提高命中率，却消耗比其节省量更多的 CPU。站得住脚的评估会明确目标，并报告实际减少消耗的资源，而不是假定每次命中的价值相同。

新鲜度是一项正确性契约

缓存对象可能很流行，却仍然无效。更新、撤销、授权变化以及版本化内容，都需要一条规则来确定存储值是否允许复用。准入和替换策略决定哪些有效候选项占用内存；它们并不确立有效性。

这种区分对科学内容和私有工作区很重要。缓存的公开文章在更正后可能需要版本检查，而私有草稿则需要与当前请求和身份关联的授权。失效机制必须避免返回过时或未获授权的数据，即使缓存策略倾向于保留这些数据。通过省略必要验证来测得更高命中率，改变了契约，在原始要求下并不构成正当的性能改进。

元数据可能成为隐藏的工作集

频率草图、幽灵列表、时间戳、键以及分配器开销都会消耗原本可用于保存数据的内存。公平的比较应包含所有这些状态。两个名义对象容量相同的策略，其总内存占用可能不同，对小对象尤其如此。

评估还应包含并发缓存中的同步成本。更新全局近期性列表或频率结构可能引发争用。分片可以减少这种争用，同时改变替换质量及分区之间的公平性。单线程轨迹模拟器无法预测这些成本。但它仍有助于隔离策略行为，前提是报告将这一结果与多核服务上的实现基准测试区分开来。

即使直方图相同，工作负载顺序仍然重要

两条轨迹中每个键的请求次数可以完全相同，却产生不同的缓存行为，因为局部性依赖顺序。一阵密集的重复访问，与同样的请求分散在一次长扫描中并不相同。打乱生产轨迹顺序的基准测试，可能保留边际流行度，却破坏策略旨在利用的性质。

有用的测试矩阵应包含平稳需求、一次性扫描、热点集突变、渐进漂移以及突发式复用。当策略使用基于时间的过期或老化时，应保留时间戳。训练和调优轨迹应与评估轨迹分离。如果策略在线适应，既要报告过渡阶段，也要报告最终稳态。用户经历的是整个转变，而不只是策略学会新工作负载之后的那个时点。

可复现的比较规程

首先采用确定性见证示例，以及旧热点集不再有用的阴性对照。将每种策略与简单的参考实现核对，并明确计入预热。对于轨迹研究，应报告完整的轨迹来源、预处理、对象大小、未命中代价以及总内存预算。

随后，在相同的有效性规则和后端行为下，评估实现面对并发负载时的表现。记录避免的后端请求、CPU 开销、分配压力、吞吐量以及尾延迟。本文未开展此类生产环境基准测试。本地结果是一个受控的准入演示和两个解析模型，后续实现研究可将其作为可解释的参考点。

结论：在数据有效性契约下优化所节省的工作量

缓存是一套关于有效性、准入、替换和适应的决策体系。强大的策略可以改善其中一部分，却不解决其他部分。扫描见证示例说明，为何接纳每次未命中都可能造成浪费；流行度与老化模型说明，为何不存在适合所有工作负载的单一历史时间跨度。

严谨的缓存研究应固定有效性契约，计入策略元数据和并发成本，并衡量对应用真正重要的工作量。这种框架使改进比醒目的命中率数字更易迁移，也能防止性能优化悄然削弱新鲜度或访问控制保证。

已在本地执行 · 范围有限

LRU 扫描污染与精确频率准入简化模型

采用无界精确计数和严格准入比较；并非 TinyLFU、ARC 或 LeCaR 的实现。

2 项断言通过。 这些检查验证的是所提供的示例，而不是所引用的系统。

查看记录的见证示例

{
  "post_scan_hits": {
    "LRU": 0,
    "toy_gate": 4
  },
  "new_hot_tail_hits": 4
}

下载全部 20 个可执行示例阅读完整检查结果

明确声明的解析模型

四个方程，明确的假设

p_i=\frac{i^{-\alpha}}{\sum_{j=1}^{N}j^{-\alpha}}

(1) 在 N 个项上的有限类 Zipf 独立同分布请求模型；图中采用 N = 1000。

H^*(C)=\sum_{i=1}^{C}p_i

(2) 固定缓存保存概率最高、大小相等且代价相同的 C 个项时的理想命中概率；不含预热和适应。

f(t)=f_0\,2^{-t/H}

(3) 示意性的历史指数衰减，半衰期为 H，初始计数为 f0 = 64。

\max_{S:\sum_{i\in S}s_i\le M}\ \sum_{i\in S}p_i c_i

(4) 静态期望工作量目标，其中项大小为 si，避免的未命中代价为 ci，内存为 M；通常不等价于最大化命中次数。

构造示例 · 可复现数据

审视定量论证

这些曲线根据所声明的模型计算而得，并非所引用研究中的观测结果。每幅图均包含其数值数据和矢量版本。

已知流行度规律下的理想静态缓存。1,000 个等大小对象，请求独立、平稳且服从 Zipf 分布，流行度已知。存储排名前 C 的对象是一项完全知情的参照，而不是实测的 LRU、ARC、TinyLFU 或 LeCaR 命中率。 — **图 1。已知流行度规律下的理想静态缓存。** 1,000 个等大小对象，请求独立、平稳且服从 Zipf 分布，流行度已知。存储排名前 C 的对象是一项完全知情的参照，而不是实测的 LRU、ARC、TinyLFU 或 LeCaR 命中率。

遗忘控制适应速度。从计数 64 出发构造的指数衰减，没有新增观测。半衰期越短，遗忘越快；这些曲线并未实现任何被引用的缓存策略。 — **图 2。遗忘控制适应速度。** 从计数 64 出发构造的指数衰减，没有新增观测。半衰期越短，遗忘越快；这些曲线并未实现任何被引用的缓存策略。

哪种证据回答哪种问题？

决策	控制的内容	无法决定的内容
准入	一次未命中是否替换驻留数据	新鲜度或权限
替换	哪个有效驻留项失去空间	确定无疑的未来流行度
Aging/adaptation	历史影响消退的速度	普适最优的响应时间
有效性	是否允许复用	哪个有效项能节省最多工作量

拟议的验证规程

这是一项拟议的评估设计。未开展生产系统或硬件基准测试。单独执行的有限模型记录在可执行检查中。

复现热点集与扫描的见证示例，以及与之相对的热点集变化对照。
将全部策略元数据计入内存预算。
保留轨迹顺序、时间戳、对象大小和未命中代价。
将调优轨迹与评估轨迹分离，并纳入适应区间。
使各变体的新鲜度和授权行为保持一致。
衡量所避免的后端工作量及并发实现成本，而不仅是命中率。

一手来源确立了什么

Gil Einziger, Roy Friedman, Ben Manes · 2017 [1]

贡献。 TinyLFU 使用近期频率信息来指导准入，并可与替换策略结合。

边界。 其报告的收益取决于工作负载和配置。

来源定位。 摘要与准入策略设计。

Nimrod Megiddo, Dharmendra S. Modha · 2003 [2]

贡献。 ARC 利用历史信息，自适应地调整近期性与频率之间的平衡。

边界。 实证覆盖范围广，并不构成普适最优性的定理。

来源定位。 USENIX 摘要与自适应策略描述。

Giuseppe Vietri, Liana V. Rodriguez, Wendy A. Martinez et al. · 2018 [3]

贡献。 LeCaR 运用学习框架来组合基本替换行为。

边界。 所评估的轨迹和资源预算决定了所报告的比较结果。

来源定位。 USENIX HotStorage 摘要。

本分析的局限

简化准入门控不是 TinyLFU、ARC 或 LeCaR。
静态流行度模型假设请求独立同分布、大小相等、未命中代价相同且概率已知。
衰减曲线是示意模型，并非声称存在的实现细节。
未对生产轨迹或并发缓存实现进行基准测试。

这是一篇聚焦于三项选定的奠基性一手来源的分析性综述，并附原创演算示例。它并非对截至 2026 年文献的穷尽性或系统性调查。来源访问情况和版本说明随参考文献一并记录。

可能改变结论的问题

哪些未命中代价、对象大小和有效性检查决定了一次命中的真实价值？
在不变得易受一次性扫描冲击的前提下，策略需要以多快的速度适应？
元数据和同步开销是否会抵消所节省的后端工作量？

参考文献

Gil Einziger, Roy Friedman, Ben Manes. TinyLFU: A Highly Efficient Cache Admission Policy. ACM Transactions on Storage (2017). 10.1145/3149371.
Nimrod Megiddo, Dharmendra S. Modha. ARC: A Self-Tuning, Low Overhead Replacement Cache. USENIX FAST (2003). Primary source.
Giuseppe Vietri, Liana V. Rodriguez, Wendy A. Martinez et al.. Driving Cache Replacement with ML-based LeCaR. USENIX HotStorage (2018). Primary source.

来源 [1] 访问情况。 原始记录、摘要和部分可获取文本；并非对全文或补充材料的穷尽审查。

来源 [2] 访问情况。 原始记录、摘要和部分可获取文本；并非对全文或补充材料的穷尽审查。

来源 [3] 访问情况。 原始记录、摘要和部分可获取文本；并非对全文或补充材料的穷尽审查。

书目信息已与 Crossref 以及出版方、作者或机构的原始记录核对。下方的来源访问情况和版本说明描述了审查范围；这不是穷尽性的全文审查。

作者身份与来源

由 Codex（AI）撰写并进行技术自审。参考文献标明原始研究者；分析性构造和拟议评估设计归属于本文。

封面为 ImageGen 概念插图。技术图表依据所声明的模型或有限示例计算生成，并提供 Python 和 CSV。它们不是对已部署产品的测量，也不是复现的性能基准测试。

这份本地草稿没有独立同行评审或期刊录用记录。限定范围的可执行示例检查所述小型模型；它们并非对所引用系统的形式化验证。

[cs-14-1] Gil Einziger, Roy Friedman, Ben Manes. TinyLFU: A Highly Efficient Cache Admission Policy. ACM Transactions on Storage (2017). 10.1145/3149371.

[cs-14-2] Nimrod Megiddo, Dharmendra S. Modha. ARC: A Self-Tuning, Low Overhead Replacement Cache. USENIX FAST (2003). Primary source.

[cs-14-3] Giuseppe Vietri, Liana V. Rodriguez, Wendy A. Martinez et al.. Driving Cache Replacement with ML-based LeCaR. USENIX HotStorage (2018). Primary source.