缓存理论

Question

是否有统一的缓存理论？也就是说，用于构建缓存和/或优化缓存的定理和算法的集合？

这个问题故意宽泛，因为我寻找的结果也是宽泛的。最大可实现加速比的公式，缓存算法的度量标准，诸如此类的东西。一本大学水平的教科书可能是理想的。

Answer 1

现实世界中的绝大多数缓存都涉及到利用"80-20规则“或Pareto distribution。它的外观如下所示

​

​

这在应用程序中表现为：

在同一段代码中花费了大量的运行时(使代码缓存在CPU上effective)

• Often，当访问变量时，它很快就会被再次访问(使数据缓存在CPU上effective)

• When浏览器查找一次网站的主机名，它将在不久的将来频繁地访问它(使
• 有效)

因此，我要说的“缓存理论”是只消耗一些额外的资源，这些资源通常是“稀有”但“快速”的，以补偿你将要做的最活跃、重复的事情。

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

Answer 2

我和我们学校的一位教授谈过，他给我指出了online algorithms，这似乎是我正在寻找的主题。

缓存算法和页面替换算法之间有很多重叠之处。一旦我对这些主题有了更多的了解，我可能会编辑这些主题的WikiPedia页面，以阐明它们之间的联系。

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

当然，这适用于请求数量为无穷大的情况，但您可以看到这将如何通过使用缓存轻松地加速您的系统。