這篇寫一下計算機系統(tǒng)中的緩存Cache應(yīng)用場景和實現(xiàn)方式介紹。

Memory hierarchy

在講緩存之前，首先要了解計算機中的內(nèi)存結(jié)構(gòu)層次Memory hierarchy。也就是下圖金字塔形狀的結(jié)構(gòu)。

從上到下，內(nèi)存層次結(jié)構(gòu)如下：

1. 寄存器：這是計算機中最快速的存儲區(qū)域。它們位于處理器內(nèi)，用于存儲即將被處理器執(zhí)行的指令和數(shù)據(jù)。

2. 高速緩存（Cache）：位于處理器和主內(nèi)存之間，用于存儲最近或頻繁訪問的數(shù)據(jù)和指令。高速緩存有多級（L1、L2、L3），其中L1最接近處理器且速度最快，但也最小。

3. 主內(nèi)存（RAM）：當計算機運行程序時，程序的代碼和數(shù)據(jù)被加載到主內(nèi)存中。

4. 硬盤驅(qū)動器（HDD）或固態(tài)硬盤（SSD）：這些是非易失性的存儲設(shè)備，用于長期存儲數(shù)據(jù)和程序。

5. 網(wǎng)絡(luò)存儲和云存儲：這些存儲設(shè)備位于本地計算機之外，數(shù)據(jù)通常通過網(wǎng)絡(luò)進行訪問。

從上到下離CPU就越來越遠，越往下的部分，容量往往越大，價格也越便宜；而越靠近CPU的部分，速度越快但是價格高且容量小。

Locality

局部性原理 (Locality of Reference) 是設(shè)計內(nèi)存層次結(jié)構(gòu)時需要考慮的重要因素，也是后面緩存為什么能夠起作用的原因。

• 時間局部性（Temporal Locality）：如果一個數(shù)據(jù)或指令在某個時間點被訪問，那么在未來的一段時間內(nèi)，這個數(shù)據(jù)或指令可能會被再次訪問。這是由于程序的執(zhí)行往往具有重復(fù)性，例如循環(huán)和遞歸。高速緩存就是基于時間局部性設(shè)計的，將最近訪問過的數(shù)據(jù)和指令存儲在快速訪問的緩存中。

• 空間局部性（Spatial Locality）：如果一個數(shù)據(jù)或指令被訪問，那么在未來的一段時間內(nèi)，其附近的數(shù)據(jù)或指令也可能會被訪問。這是由于程序的執(zhí)行通常具有連續(xù)性，例如順序執(zhí)行的指令和數(shù)組的元素。內(nèi)存管理系統(tǒng)會將整個塊（包含了訪問數(shù)據(jù)或指令的附近地址）加載到高速緩存或主內(nèi)存中，以利用空間局部性。

緩存Cache

如果我們把用過地址放在CPU里的存儲單元，或者說一個更接近CPU、更能快速獲取的地方，就有了我們廣義概念上的“Cache”了。雖然這個地方很小，但基于locality的原理，程序傾向于使用之前的地址或者之前地址附近地址，每次CPU像訪問數(shù)據(jù)，它都會優(yōu)先從cache里查找（因為離得更近），如果是那種多次反復(fù)需要的數(shù)據(jù)，就可以直接讓cache來提前處理了，提高數(shù)據(jù)獲取速度。

當然，畢竟cache的位置有限，如果請求的數(shù)據(jù)沒有在cache里（這叫做cache miss），就只能把cache中的數(shù)據(jù)刪掉（比如最久沒用的那個），然后把新數(shù)據(jù)從下面更慢的內(nèi)存結(jié)構(gòu)中獲取后替換上去。

幾種Cache miss

Cache miss主要有以下三種：

1. 冷（強制）未命中（Cold or Compulsory Miss）
   冷未命中是因為緩存開始時是空的，而這是對該塊的第一次引用。換句話說，這是無法避免的未命中，因為當你第一次訪問一個數(shù)據(jù)塊時，它不可能已經(jīng)在緩存中。

2. 容量未命中（Capacity Miss）
   當活動的緩存塊集合（工作集）大于緩存的容量時，就會發(fā)生容量未命中。即使數(shù)據(jù)塊之前已在緩存中，但由于緩存空間有限，可能已經(jīng)被其他更近期訪問的數(shù)據(jù)塊替換出去。

3. 沖突未命中（Conflict Miss）
   前兩個都比較好理解，這個沖突未命中比較復(fù)雜，我用通俗的語言講大概是這樣：比如我們教室有三排學生，每排都有一個椅子當作cache，那么我們cache一共有3個，學生有3排。這個時候如果規(guī)定每排學生只能用對應(yīng)的一把椅子，就會發(fā)生conflict miss。比如第一排第一個同學有了一個行為，他被存儲在了第一個椅子上；這個時候第一排第二個同學又有一個行為，我們只會用第二個同學去換下第一個同學——即使這個時候還有兩把椅子是空的。當最后再次訪問第一個同學時，你會發(fā)現(xiàn)明明第一個同學之前訪問過，明明cache里有空位，但就是在cache里找不到他，這種情況下的miss就叫做conflict miss。

Cache的參數(shù)和大小表示

高速緩存（Cache）的總大小可以由以下三個參數(shù)描述：

• S：緩存的集數(shù)（Set）。
• E：每個集中的線數(shù)（Line），也就是每個集中的緩存塊數(shù)量（Cache blocks per set）。
• B：每個緩存塊的大小（Size of each block）。

而Cache set就等于 S × E × B。

?Cache的結(jié)構(gòu)看起來這么麻煩，如何存儲數(shù)據(jù)呢？對于一個數(shù)據(jù)，如cache會根據(jù)它的地址來劃分和存儲。

如上圖所示，通常地址會被劃分成3部分：塊偏移量（block offset）、集索引（set index）和標簽（tag）。

• 塊偏移量（Block Offset）：這部分的位數(shù)取決于每個cache塊（或行）的大小。例如，如果一個塊的大小是16字節(jié)，那么塊偏移量就需要4位（因為2^4 = 16），用于確定一個字節(jié)在其塊中的位置。

• 集索引（Set Index）：這部分的位數(shù)取決于cache的集數(shù)。例如，如果有64個集，集索引就需要6位（因為2^6 = 64），用于確定一個塊應(yīng)該存儲在哪個集中。

• 標簽（Tag）：地址中剩下的位被用作標簽，用于在cache查找過程中區(qū)分不同的內(nèi)存塊。

所以對于一個地址，大致的查找流程是這樣的：首先進行地址分割，就像上面說的那樣分成三部分；其次拿著集索引去cache中找到對應(yīng)的集，拿到了這個集（可以理解成圖里的一整行藍色背景，包含很多l(xiāng)ine），我們查找所有l(wèi)ine（通常會并行查找來提高速度），找到那個line，which有效位（valid bit）是1以及tag標簽和地址劃分出來的tag部分一樣，如果找到了，則使用塊偏移量從這個集中取出所需的數(shù)據(jù)。

再舉個例子，在上面這個圖中，?block塊大小是8，因此我們需要3個位作為block offset，這里offset是100也就是4，那么數(shù)據(jù)到時候會從第4位開始，也就是圖中綠色塊部分；集的個數(shù)不知道，集索引的位數(shù)也不確定，但這里0...01不管中間幾個0，都是1，表示對應(yīng)第一個集。在剩下的部分就是兩個紅色部分的tag比較了。

用這句話來檢查一下你是否理解：這里雖然得到的塊偏移量是4，但是你可以發(fā)現(xiàn)我們把4往后的部分也都放在cache里了（綠色部分）。因為這樣的話如果下次訪問這個同樣的地址+1，按找那套流程算下來其實直接就對應(yīng)塊偏移量為5的部分，直接就在cache里了！這就是cache對Spatial Locality也友好的地方——不止是之前訪問過的我有，之前訪問過的鄰居我也有！

Cache的寫操作

當我們討論寫操作（write operations）在緩存系統(tǒng)中的行為時，我們需要考慮兩種基本的情況：寫命中（write hit）和寫未命中（write miss）。在處理這兩種情況時，有幾種常見的策略：

• 1 寫命中（Write Hit）：當我們試圖寫入的數(shù)據(jù)已在緩存中時，我們有兩種基本策略：

  • 寫直達（Write-Through）：這種策略立即將更改寫入到主存儲器和緩存中。這種策略的優(yōu)點是它保持了主存儲器和緩存中的數(shù)據(jù)一致性，但缺點是每次寫操作都需要訪問主存儲器，這可能會帶來較大的性能開銷。

  • 寫回（Write-Back）：這種策略僅將更改寫入到緩存中，并將緩存行標記為"dirty"（通過設(shè)置一個"dirty bit"）。只有當緩存行被替換出緩存時，更改才會被寫回到主存儲器。這里的dirty bit就是替換時用來判斷的，如果是1，那么就需要把整個緩存行（包含2^b字節(jié)的數(shù)據(jù)塊）寫回（write-back）到主內(nèi)存。這種策略的優(yōu)點是減少了對主存儲器的訪問次數(shù)，從而提高了性能。但是，這也可能會導(dǎo)致主存儲器與緩存之間的數(shù)據(jù)不一致。

• 2 寫未命中（Write Miss）：當我們試圖寫入的數(shù)據(jù)不在緩存中時，我們有兩種基本策略：

  • 不寫分配（No-Write-Allocate）：這種策略直接將數(shù)據(jù)寫入主存儲器，而不將其加載到緩存中。這種策略適用于不希望單次寫操作污染緩存的情況。

  • 寫分配（Write-Allocate）：這種策略在寫入數(shù)據(jù)之前，先將相關(guān)的緩存行加載到緩存中，再將新的寫操作應(yīng)用到這個緩存行。如果預(yù)計將來會有更多對同一位置的寫操作，這種策略可能會很有用。

在實際的系統(tǒng)中，可能會組合使用這些策略。比如，一種常見的組合是使用寫直達和不寫分配策略，這種組合可以保持數(shù)據(jù)的一致性，而且適合處理散列的、非連續(xù)的寫操作。另一種常見的組合是使用寫回和寫分配策略，這種組合可以減少對主存儲器的訪問次數(shù)，從而提高性能，尤其是在處理連續(xù)的、集中的寫操作時。

小結(jié)

這篇文章寫了下cache的概念以及讀寫過程中的讀取策略。cache的緩存命中是非常有用和關(guān)鍵的，可以為程序或許數(shù)據(jù)節(jié)省下非常多時間。一個有趣的觀點是，99%的命中率可能比97%的命中率好兩倍。比如假設(shè)緩存命中的時間為1個周期，未命中的懲罰為100個周期。那么：

• 對于97%的命中率，平均訪問時間為：1個周期（命中時間） + 0.03（未命中率） * 100個周期（未命中懲罰） = 4個周期。
• 對于99%的命中率，平均訪問時間為：1個周期（命中時間） + 0.01（未命中率） * 100個周期（未命中懲罰） = 2個周期。

因此，盡管兩者的命中率只相差2%，但是平均訪問時間卻差了一倍。

所以對于程序員來說，盡量寫出“緩存友好”的代碼也是能很好提升程序的效率。通過理解緩存的工作方式，我們可以編寫出更有效地利用緩存的代碼，一些常見方式有：

• 重復(fù)引用變量：這是好的（利用時間局部性Temporal Locality）：如果一個變量被反復(fù)引用，它可能會留在緩存中，這樣每次引用都會命中緩存，從而提高性能。

• 使用跨度為1的引用模式：這是好的（利用空間局部性Spatial Locality）。如果你的代碼按順序訪問數(shù)據(jù)（例如，遍歷數(shù)組），那么緩存系統(tǒng)可能會預(yù)先加載你即將訪問的數(shù)據(jù)，從而提高緩存命中率。這就是為什么我們一行一行地遍歷二維數(shù)組要比一列一列地遍歷快很多，因為數(shù)組在內(nèi)存中是按行存儲，緩存可以幫助我們提前加載到接下來的數(shù)據(jù)。

結(jié)束！