缓存与置换：概览
| , 1 minutes reading.
缓存与置换：速度的背包
记忆的物理学
想象你是一名在工作台前工作的木匠。你的腰间系着一个 工具带 (缓存/Cache)，而后院里有一个巨大的 工具棚 (硬盘/Hard Drive)。
- 工具带： 它很小，只能挂 5 件工具。但你只需 1 秒钟就能拿到锤子。
- 工具棚： 它无限大，装着你拥有的所有东西。但走过去拿个电钻需要 10 分钟。
缓存的目标很简单：把你此刻需要的工具留在腰带上。 但腰带容量有限。当你需要第 6 件工具时，你必须做出一个艰难的决定：我该把腰带上的哪件工具拿下来，给新工具腾出位置？
这个决定——即“置换策略 (Eviction Policy)”——正是区分快系统与慢系统的关键。
生存的策略
在本章中，我们将探索关于“谁有资格留下”的不同哲学：
| 策略 | 灵魂 / 隐喻 | 代表算法 | 最佳应用场景 |
|---|---|---|---|
| 近况 (Recency) | 实用主义者 “如果你最近没派上用场，你就出局。” | LRU (最近最少使用) | 通用场景 大多数现实访问模式（如浏览历史）。 |
| 频率 (Frequency) | 历史学家 “我不关心最近；我只在乎忠诚度。” | LFU (最不经常使用) | 静态热度 那些总是很热门的东西（如 Google Logo）。 |
| 公平 (Fairness) | 官僚主义者 “先来后到，概无例外。” | FIFO (先进先出) | 简单场景 缓冲区和消息队列。 |
| 平衡 (Balance) | 大战略家 动态平衡“近况”与“频率”。 | ARC (自适应置换缓存) | 复杂负载 数据库与文件系统 (ZFS)。 |
缓存的三大法则
- 局部性原理 (Locality)： 程序（和人类）是可以预测的。如果你访问了数据 X，你很可能很快再次访问 X（时间局部性），或者访问 X 的邻居（空间局部性）。
- 命中率 (Hit Rate)： 这是唯一重要的指标。如果你的缓存能响应 90% 的请求，系统就是快的。如果只有 10%，那无论你的代码优化得再好，系统也是慢的。
- 一致性 (Coherence)： 计算机科学中只有两件难事：缓存失效 (Cache Invalidation) 和命名。当“工具棚”里的东西变了，如何保持“工具带”上的东西同步，是终极的头痛难题。
小结
在本章中，我们将学习如何构建“虽然小但比谁都聪明”的存储系统。我们将发现，所谓的“智能”，往往只是基于过去预测未来的能力。
让我们从最著名的算法开始：LRU。