閑話緩存：概述

每當我們讨論緩存時，總是會對如下幾個詞比較熟悉，

Write-back,  write-through, write-around

似乎，緩存主要是為“寫”設計的，其實這是錯誤的了解，寫從緩存中獲得的好處是非常有限的，緩存主要是為“讀”服務的。

之是以我們要順帶提一下，在一個緩存系統中，如何處理寫的順序，是因為，在寫的過程中，需要動态的更新緩存（否則就會産生資料不一緻性的問題），以及後端主存。這三個詞都是用來表示如何處理寫更新的。就是用什麼方式來處理寫。

在一個有緩存的層次結構中，如何了解緩存是為“讀”服務的？這涉及到讀請求的處理序列。對于每一個讀請求，我們都會用如下的操作序列去處理它：

1.      在緩存中查找請求對應的資料

a.      如果找到，則直接傳回給客戶

b.      如果沒找到，則把請求的資料讀入緩存（更新緩存），然後把資料傳回給客戶

既然緩存主要是為讀服務的（後面的文章，我們會讨論，用什麼方式來改善寫的性能），那麼為了提高讀的性能，或者說減少讀的響應時間，我們就要提高緩存的命中率，減少緩存的miss 率。這也是我們緩存算法設計的目标。

那麼我們來想想，在設計緩存時，我們應該從哪幾方面考慮來達到這個緩存的設計目标呢？根據我們上面提到的讀請求的操作序列，我們可以從如下幾個方面來思考：

1.      我們應該盡量多的用有用的資料填滿緩存。也就是說，我們要充分利用緩存。

a.      這是緩存子產品和其它子產品不同的地方，并不是說緩存中的資料越少越好，而是有用的資料越多越好。

b.      這裡有個非常好的列子，就是Windows的記憶體占用率總是非常高，很多人都表示過不滿。其實這是一個非常好的設計。Windows總是試圖盡量利用那些空閑的記憶體，用來緩存磁盤上的資料，以此來提高系統的整體性能。否則你那麼大的記憶體，就為了拿來好看？

2.      如何擷取“有用”的資料。這裡，“有用”的資料的定義就是可能在不久的将來會被client用到的資料。為了得到有用的資料，我們需要預估用戶端應用的I/O 模式，比如順序讀寫，随機讀寫等等。這裡就涉及到了“pre-fetch”算法。

a.      Pre-fetch（預取算法）：是一種預測用戶端應用下次讀寫的資料在哪裡的算法，并且把客戶要用的資料提前放入緩存中，以此來提高讀的響應速度。

3.      問題來了，如果緩存已經滿了，那麼如何存放新的需要緩存的單元呢？這就牽涉到緩存設計的另一端：淘汰算法。

a.      相比于pre-fetch，淘汰算法（replacement policy）更加重要。因為對于随機的I/O， 預取算法是無能為力的。

b.      淘汰算法的關鍵是如何判斷一個單元的資料比另一個單元的資料更加重要。但需要淘汰一個資料單元時，丢棄掉最不重要的那個資料單元，并且用它來存放新的資料。

4.      緩存算法設計的另外一個重要的考慮因素是算法的複雜度。或者說是實作或運作算法帶來的額外開銷。我們希望算法容易實作，并且額外開銷不随着緩存大小的改變而改變。包括容量的額外開銷和計算的額外開銷。

接下來的文章，我們會詳細讨論預取算法和淘汰算法。