1. Cache的歷史
在科研領域，C. J. Conti等人于1968年在描述360/85和360/91系統性能差異時最早引入了高速緩存（cache）一詞。Alan Jay Smith于1982年的一篇論文中引入了空間局部性和時間局部性的概念。
Mark Hill在1987年發明了3C（Compulsory, Capacity, Conflict）沖突分類。
最早介紹非阻塞緩存的論文之一來自David Kroft（1981年）。
1990年Norman Paul Jouppi在一篇論文中介紹了受害者緩存并研究了使用流緩沖器進行預取的性能。
在工業領域，最早的有記載的緩存出現在IBM的360/85系統上。
Intel的x86架構CPU從386開始引入使用SRAM技術的主板緩存，大小從16KB到64KB不等。486引入兩級緩存。其中8KBL1緩存和CPU同片，而L2緩存仍然位于主板上，大小可達268KB。將二級緩存置于主板上在此后十余年間一直設計主流。但是由于SDRAM技術的引入，以及CPU主頻和主板總線頻率的差異不斷拉大，主板緩存在速度上的對內存優勢不斷縮水。因此，從Pentium Pro起，二級緩存開始和處理器一起封裝，頻率亦與CPU相同（稱為全速二級緩存）或為CPU主頻的一半（稱為半速二級緩存）。
AMD則從K6-III開始引入三級緩存。基于Socket 7接口的K6-III擁有64KB和256KB的同片封裝兩級緩存，以及可達2MB的三級主板緩存。
今天的CPU將三級緩存全部集成到CPU芯片上。
多核CPU通常為每個核配有獨享的一級和二級緩存，以及各核之間共享的三級緩存。
2. 什么是Cache?
在wikipedia上對cache的解釋：
In computing, a cache is a hardware or software component that stores data so future requests for that data can be served faster; the data stored in a cache might be the result of an earlier computation, or the duplicate of data stored elsewhere. A cache hit occurs when the requested data can be found in a cache, while a cache miss occurs when it cannot. Cache hits are served by reading data from the cache, which is faster than recomputing a result or reading from a slower data store; thus, the more requests can be served from the cache, the faster the system performs.
字面上理解就是，cache是一個硬件或軟件的組件用來存儲將來會請求到的數據，而且能讓數據獲取更快。因為如今緩存的概念已被擴充，不僅在CPU和主內存之間有Cache，而且在內存和硬盤之間也有Cache（磁盤緩存），乃至在硬盤與網絡之間也有某種意義上的Cache──稱為Internet臨時文件夾或網絡內容緩存等。凡是位于速度相差較大的兩種硬件之間，用于協調兩者數據傳輸速度差異的結構，均可稱之為Cache。
- 硬件的cache：CPU cache，GPU cache，DSP；
- 軟件的cache：Disk Cache，Web Cache等。
這里我們著重討論傳統的cache緩存：CPU的cache。不同的存儲技術有著不同的價格和性能的折中。不同存儲器訪問時間差異很大，速度較快的技術每字節的成本要比速度較慢的技術高，而且容量小。金字塔存儲器層次結構如下圖
一般而言，高速緩存（cache）是一個小而快的存儲設備，它作為存儲在更大也更慢的設備中的數據對象的緩沖區域。使用高速緩存的過程成為緩存（caching）。cache的效率由命中率來衡量，一個好的cache效率通常在80%-95%的命中率。
3. 緩存命中和不命中
- 緩存命中
在存儲器層次結構中，假設層次從上到下是增序排列，假設一個k值，當程序需要第k+1層的某個數據對象d時，它首先在第k層的一塊中查找d，如果d剛好緩存在k層中，就是緩存命中(cache hit).
2. 緩存不命中
當在k層找不到數據d時，我們就稱k層緩存不命中(cache miss)。當發生緩存不命中的時候，第k層緩存從第k+1層緩存中取出包含d的那個塊，如果k層緩存滿了，就會覆蓋現有的塊。
覆蓋一個現存的塊的過程稱為替換(replacing)或驅逐(evicting)這個塊。被驅逐的塊稱為犧牲(victim)塊。關于替換哪個具體的塊是由替換策略來控制的。比如隨機替換策略，或最少最近被使用策略(LRU)。
緩存不命中的種類
- 強制不命中或冷不命中：這種不命中是由于緩存是空的，它通常是短暫的，不會在反復訪問存儲器的過程中出現。
- 沖突不命中：這種緩存是由于放置策略引起的。如下圖所示，如果程序請求0，然后8，然后0，然后8，就會出現每次都不命中
- 容量不命中：當工作集的大小超過了緩存的大小的時候，不能處理這個工作集，就會發生容量不命中。
高速緩存存儲器(SRAM)層級
- L1（一級緩存）：一般與處理器同片封裝，訪問速度幾乎和寄存器一樣快，通常是2-4個時鐘周期，大小為8KB-128KB
- L2（二級緩存）：可以在chip中也可以在外部，訪問速度大約是是10個時鐘周期，大小為64KB-8MB
- L3（三級緩存）：在chip外部被多核處理器共享，訪問速度大約是30～40個時鐘周期，大小為4MB-128MB
- L4（四級緩存）：cc-NUMA集群系統的遠程cache，大小比L3緩存大（大于512MB).
4. 高速緩存結構
一般而言，高速緩存的結構可以用元組(S, E, B, m)來表示，緩存大小C=B×E×S。如下圖所示，每個存儲器有m位，一個機器的高速緩存是一個有S個高速緩存組（cache set）的數組，每個組包含E行高速緩存行（cache line），每個行由一個B字節的數據塊，一個有效位（valid bit）表示這個行是否有有意義的信息，t個（t=m-(b+s)）標志位（用于標識存儲在這個高速緩存塊中的位置）組成。
高速緩存確定一個請求是否命中，然后取出被請求的字的過程分為3步：
- 組選擇
- 行匹配
- 字抽取
人們根據E(每個組的行數)的不同把高速緩存分成不同類，主要有
1. 直接映射高速緩存(Direct Mapped cache)
每個組只有一行的高速緩存為直接映射高速緩存。
直接映射緩存的操作：
1）組選擇：根據s位組索引位選擇出組；2）行匹配：確定是否有字w的拷貝存儲在組的高速緩存行中，當設置了有效位，并且行中的標記與w的地址中的標記相匹配的時候，我們認為這一行包含w的一個拷貝。因為每個組只有一行，所以很快就可以完成。如果找到了就是命中，反之不命中。 3）如果不命中要進行行替換 4）取出數據塊
2. 組相聯高速緩存(Set Associative cache)
我們知道，直接映射高速緩存會造成沖突不命中，原因是每個組織有一行。那么組相聯高速緩存則是1圖6
3. 全相聯高速緩存(Fully Associative cache)
全相聯高速緩存的條件是E=C/B，也就是緩存只有一組，組中包含E行。這樣的相聯完全免去了索引的使用
5. 緩存策略
在緩存的讀寫操作中，有不同的策略來指導操作的順序以及位置。
1. 替換策略
上文提到，覆蓋一個現存的塊的時候會使用替換策略，替換策略有很多種，主要有：
- LRU - Least Recently Used
通常用于組相聯高速緩存，會有一個age counter（替換index）與每個數組S相關。這個counter最大值就是S，當一個set被訪問到，那么比它低的counter就被置為0，其他set自增1。舉個例子，有4個set的緩存，原本的counter值是0-3-2-1，如果第三個被訪問到了，那么counter的值是1-3-0-2。 - FIFO - First-In First-Out
先進先出策略，通常用于組相聯高速緩存。 - LFU – Least Frequently Used
很高效的算法，但很耗資源，通常不用。 - Round-robin
用于全相聯高速緩存。有一個指針指向將要被替換的行，當行被替換，指針就會自增1，指針是環形的。 - Random
隨機策略，用于全相聯高速緩存。每個時序Round-robin就要更新，而不是每個替換操作。
2. 回寫策略
cache的回寫策略決定怎么把cache的數據寫到內存的位置中去。有兩種基本的策略：
- 寫回（write back）
寫回是指，僅當一個緩存塊需要被替換回內存時，才將其內容寫入內存。如果緩存命中，則總是不用更新內存。為了減少內存寫操作，緩存塊通常還設有一個臟位（dirty bit），用以標識該塊在被載入之后是否發生過更新。如果一個緩存塊在被置換回內存之前從未被寫入過，則可以免去回寫操作。寫回的優點是節省了大量的寫操作。這主要是因為，對一個數據塊內不同單元的更新僅需一次寫操作即可完成。這種內存帶寬上的節省進一步降低了能耗，因此頗適用于嵌入式系統。 - 寫通（write through）
寫通是指，每當緩存接收到寫數據指令，都直接將數據寫回到內存。如果此數據地址也在緩存中，則必須同時更新緩存。由于這種設計會引發造成大量寫內存操作，有必要設置一個緩沖來減少硬件沖突。這個緩沖稱作寫緩沖器（Write buffer），通常不超過4個緩存塊大小。不過，出于同樣的目的，寫緩沖器也可以用于寫回型緩存。
寫通較寫回易于實現，并且能更簡單地維持數據一致性。
6. 如何編寫高速緩存友好的代碼
當明白了高速緩存的原理后，我們在編程的過程中應該試著去編寫高速緩存友好的代碼。什么樣的代碼算是高速緩存友好的代碼？局部性比較好的程序往往有更高的緩存命中率，而緩存命中率更高，代碼運行的速度就更快。確保代碼高速緩存友好的方法有：
- 讓最常見的情況運行得快。
程序通常大部分時間都在少量的核心函數上，而核心函數大部分時間都花在循環上面，讓這些循環執行得快一點是我們需要關注的地方。 - 在每個循環內部緩存不命中率數量小。
舉個經典的二維數據相加求和的例子：
int colsarray(int a[M][N])
{
int i,j,sum=0;
for(j = 0; j<N; j++)
for(i = 0; i<M; i++)
sum += a[i][j];
return sum;
}上面這個例子，是按列循環相加，如下圖的紅色箭頭方向，每次取的數據都是不同行的，如果a[0][0]失效，不命中，下次取的是a[1][0]，又會不命中，效率很低。
如果只是做下小修改，代碼如下，按上如綠色箭頭，而由于緩存從內存中抓取的幾乎都是同行不同列的數據，這樣如果a[i][0]失效，從內存中抓取的數據實際上包括了a[i][0]-a[i][7](假定使用32字節大小的緩存塊，每個整型值占四字節),這樣后面7次循環緩存都可以命中。大大提高了緩存命中率。那么可以得到大概3/4的命中率。
int colsarray(int a[M][N])
{
int i,j,sum=0;
for(i = 0; i<M; i++)
for(j = 0; j<N; j++)
sum += a[i][j];
return sum;
}在實際的運行過程中，第二種的程序比第一種快2倍。
7. 緩存隔離方法
同一臺服務器上的CPU數量在近幾年一直在增加，32核->48核->72核，為了提高資源使用率，同一臺機器上會同時運行很多應用，在同一個物理CPU的不同邏輯CPU上或者某個CPU package上不同物理CPU運行的應用會共享LLC(Last level cache)，這樣一個batch應用如果需要大量的讀寫LLC，會占據大部分LLC，導致LS(Latency Sensitive)應用在讀取數據時產生cache miss,對于LS應用來說，batch應用會是一個noisy neighbor。
Intel在CPU微架構Haswell開始引入RDT（Resource Director Technology）技術,其中有一個功能是Cache Allocation Technology (CAT)，可以通過設置給不同的core分配不同的cache way，做到cache資源隔離。可以認為CAT使得LLC變成了一種支持QoS（Quality of Service）的資源，操作系統或者容器軟件可以限制應用只能使用為其劃分的部分cache區域，為不同應用劃分的cache區域可以重疊。該功能在分配cache line時起作用，比如讀取數據到cache的時候。不同的cache區域是通過CLOS（Class of Service）標記來區分的，每個CLOS有一個CBM（Cache Bit Mask）。CBM是一個連續的bits，定義了每個cache區域可用的cache大小。
CAT可以在cloud和container環境下，更好的分配管理具有大LLC的高性能服務器。比如具有72個core的服務器上，需要同時運行web服務器，數據庫和Map Reduce任務等。可以通過cache的分區隔離，使不同應用同時達到更好的資源共享效果。
因為CAT支持在應用運行時動態修改cache的分區，可以配合上層監控系統更好的優化LS的性能同時最小化對batch應用的影響。
一個典型的例子就是解決之前提到的noisy neighbor。在container環境下，一個運行在container里面的streaming應用不停的讀寫數據導致大量的LLC占用，會導致同機器上另外一個container里運行的LS需要的數據被evict出LLC，從而導致LS應用性能下降。
