緩存與置換：速度的背包

記憶的物理學

想像妳是一名在工作台前工作的木匠。妳的腰間繫著一個 工具帶 (緩存/Cache)，而後院裡有一個巨大的 工具棚 (硬碟/Hard Drive)。

• 工具帶： 它很小，只能掛 5 件工具。但妳只需 1 秒鐘就能拿到錘子。
• 工具棚： 它無限大，裝著妳擁有的所有東西。但走過去拿個電鑽需要 10 分鐘。

緩存的目標很簡單：把妳此刻需要的工具留在腰帶上。 但腰帶容量有限。當妳需要第 6 件工具時，妳必須做出一個艱難的決定：我該把腰帶上的哪件工具拿下來，給新工具騰出位置？

這個決定——即「置換策略 (Eviction Policy)」——正是區分快系統與慢系統的關鍵。

生存的策略

在本章中，我們將探索關於「誰有資格留下」的不同哲學：

緩存的三大法則

1. 局部性原理 (Locality)： 程式（和人類）是可以預測的。如果妳存取了數據 X，妳很可能很快再次存取 X（時間局部性），或者存取 X 的鄰居（空間局部性）。
2. 命中率 (Hit Rate)： 這是唯一重要的指標。如果妳的緩存能響應 90% 的請求，系統就是快的。如果只有 10%，那無論妳的代碼優化得再好，系統也是慢的。
3. 一致性 (Coherence)： 電腦科學中只有兩件難事：緩存失效 (Cache Invalidation) 和命名。當「工具棚」裡的東西變了，如何保持「工具帶」上的東西同步，是終極的頭痛難題。

小結

在本章中，我們將學習如何構建「雖然小但比誰都聰明」的儲存系統。我們將發現，所謂的「智慧」，往往只是基於過去預測未來的能力。

讓我們從最著名的演算法開始：LRU。