缓存理论

Question

有没有关于缓存的统一理论？ 也就是说，构建缓存和/或针对缓存进行优化的定理和算法的集合？

这个问题故意很宽泛，因为我想要的结果也很广泛。 最大可实现加速比的公式，缓存算法的度量标准等等。 大学级教材可能是理想的选择。

- Jørgen Fogh

Answer 1

我和学校的一位教授交谈过，他向我指出了在线算法，这似乎是我正在寻找的主题。

缓存算法和页面替换算法之间有很大的重叠。一旦我对这个主题有更多的了解，我可能会编辑维基百科上这些主题的页面，以澄清它们之间的关系。

- Jørgen Fogh

Answer 2

绝大多数实际缓存应用都利用了“二八定律”或Pareto distribution。如下图所示。

这在应用程序中表现为：

• 大部分运行时间都花费在同一段代码上（使CPU上的代码缓存有效）
• 经常情况下，当一个变量被访问时，它很快会再次被访问（使CPU上的数据缓存有效）
• 当浏览器查找网站的主机名时，它会频繁地访问它（使DNS缓存有效）

因此，我认为“缓存理论”的目的是使用一些额外的资源来弥补你将要重复执行的最活跃的事情，这些资源通常是“稀缺”但“快速”的。

你这样做的原因是尝试根据上面高度倾斜的图表“平衡”执行“慢”操作的次数。

- Chris Harris

Answer 3

如果你能假设缓存命中比缓存未命中快得多，你会发现随着时间的推移，即使你只有缓存未命中，使用缓存仍然比不使用缓存更快或相同。

以下是数学计算：

Number of hits = NumRequests - #CacheMisses

AverageTime = ((NumRequests-#CacheMisses) * TimePerHit + #CacheMisses * TimePerMiss)/NumRequests

如果我们假设NumRequests是无限大的（这是一个极限问题，不要害怕微积分），那么我们可以看到：

AverageTime = Infinity*TimePerHit/Infinity - #CacheMisses*TimePerHit/Infinity + #CacheMisses*TimePerMiss/Infinity

#CacheMisses这两个术语都变为零，但整个方程式的解析结果是：

AverageTime = TimePerHit

虽然这仅适用于请求数量为无限大的情况，但您可以看到使用缓存将轻松加速系统。

- samoz

---

你的计算看起来非常好。不幸的是，它暗示了缓存未命中数是恒定的假设，这似乎极不可能。正确的数量应该是：命中概率 * 命中时间 + (1 - 命中概率) * 未命中时间 - Jørgen Fogh

我知道这个数学有点靠不住；这是我去年秋季上课时必须学习的证明，我只是试图从那里回忆起来。不过针对你的观点，既然我有CacheHits与CacheMisses，这是一个比率，那么使用命中概率不就是同样的事情了吗？ - samoz

不完全正确。假设缓存未命中的概率是一个非零常数，那么如果进行无限次试验，就会出现无限次未命中。 如果缓存足够大，可以容纳将来请求的所有数据，则您的公式是正确的。然后，未命中次数有一个恒定的上限。 - Jørgen Fogh

是的，我同意Fogh的观点。一开始听起来就不太对。 - Khue Vu

我基本上是在说使用缓存对系统的开销可以忽略不计。随着请求数量趋近于无限，开销基本上变为零。 - samoz