缓存条目替换算法

Question

我有一个软件项目，可以从不同大小的对象中创建一系列指纹（哈希）值。当然，对象越大，哈希计算就越昂贵。这些哈希用于比较目的。

现在我希望缓存哈希值以提高后续比较的性能。对于缓存中的任何给定条目，我有以下可用指标：

- 命中次数 - 最后修改日期/时间 - 哈希的对象大小

那么，我的问题是：考虑到需要限制缓存的大小（将其限制为特定数量的条目），什么是平衡的替换缓存条目的方法？

显然，较大的对象更昂贵，因此需要尽可能长时间地保留它们。但是，我不想出现这样的情况，即填充缓存与大量大型对象将阻止未来（较小的）项目被缓存。

因此，基于上述可用指标，我正在寻找一个好的通用“公式”，用于在缓存变满时过期（删除）缓存条目。

欢迎提出您的想法和评论。

- MER

---

你有没有获取条目最后访问时间戳的功能？ - Erik

是的，“最后修改时间”在访问条目时也会更新。 - MER

Answer 1

假设能够记录最后访问条目的时间，我会为每个条目设置一个“成本”，您可以随时删除成本最低的条目。

Cost = Size * N - TimeSinceLastUse * M 

假设您完全从缓存中删除条目（并且不保留旧的命中计数数据），我建议避免使用命中计数作为指标，因为您最终会得到一个具有高命中计数的条目，这是因为它存在了很长时间，并且由于其高命中计数而将继续存在更长时间。

- Erik

---

谢谢您的反馈。不好意思，如果我有些愚蠢，但是您上面的方程中的变量N和M代表什么？ - MER

你需要调整的常数因素 - Erik

Answer 2

你需要考虑对象的本质。思考对象被再次调用的概率，然后移除最不可能被调用的对象。

这非常具体取决于你使用的软件和对象的本质。
如果它们在程序中持续使用，它们可能会遵守引用局部性原则。因此，您应该使用LRU（最近最少使用）算法。

如果具有更高命中次数的对象更有可能被再次调用，则使用该对象（并删除最低对象）。

看一下缓存算法

原则上，您需要计算：

min(p*cost)

p = 再次调用的概率。
cost = 再次缓存该对象的成本。

- Yochai Timmer

---

我同意。然而，如果具有更高命中次数的对象更有可能再次使用，则无需使用命中次数，因为它们也是最可能最近未使用的对象。正如Erik所回复的那样，命中次数是一个自我实现的预言。 - Tom Macdonald

Answer 3

通常我使用严格的最近最少使用（LRU）方案来清理缓存中的内容，除非重构某些项目的成本非常高。 LRU的好处是实现非常简单，并且对于各种应用程序都能很好地工作。 它还将最经常使用的项目保留在缓存中。

基本上，我创建了一个同时由字典索引的链表。 当客户端需要一个项目时，我在字典中查找。 如果找到了，我将节点从链表中取消链接并移动到列表的头部。 如果该项目不在缓存中，我会构建它（从磁盘加载或其他方式），将其放在列表的头部，插入到字典中，然后删除列表尾部的项目。

- Jim Mischel

Answer 4

可能想尝试一种多级缓存风格。将缓存的一定比例专用于创建昂贵的项目，另一部分专用于易于创建但访问更频繁的项目。然后，您可以使用不同的策略来维护昂贵的缓存和较便宜的缓存。

- apaq11

Answer 5

算法可以考虑再现缺失元素的成本。这样，您就可以在缓存中保留最有价值的项目。

- Bo Persson