缓存与置换：速度的背包

记忆的物理学

想象你是一名在工作台前工作的木匠。你的腰间系着一个 工具带 (缓存/Cache)，而后院里有一个巨大的 工具棚 (硬盘/Hard Drive)。

• 工具带： 它很小，只能挂 5 件工具。但你只需 1 秒钟就能拿到锤子。
• 工具棚： 它无限大，装着你拥有的所有东西。但走过去拿个电钻需要 10 分钟。

缓存的目标很简单：把你此刻需要的工具留在腰带上。 但腰带容量有限。当你需要第 6 件工具时，你必须做出一个艰难的决定：我该把腰带上的哪件工具拿下来，给新工具腾出位置？

这个决定——即“置换策略 (Eviction Policy)”——正是区分快系统与慢系统的关键。

生存的策略

在本章中，我们将探索关于“谁有资格留下”的不同哲学：

缓存的三大法则

1. 局部性原理 (Locality)： 程序（和人类）是可以预测的。如果你访问了数据 X，你很可能很快再次访问 X（时间局部性），或者访问 X 的邻居（空间局部性）。
2. 命中率 (Hit Rate)： 这是唯一重要的指标。如果你的缓存能响应 90% 的请求，系统就是快的。如果只有 10%，那无论你的代码优化得再好，系统也是慢的。
3. 一致性 (Coherence)： 计算机科学中只有两件难事：缓存失效 (Cache Invalidation) 和命名。当“工具棚”里的东西变了，如何保持“工具带”上的东西同步，是终极的头痛难题。

小结

在本章中，我们将学习如何构建“虽然小但比谁都聪明”的存储系统。我们将发现，所谓的“智能”，往往只是基于过去预测未来的能力。

让我们从最著名的算法开始：LRU。