效能最佳化：關於快取的一些思考

利用快取做效能最佳化的案例非常多，從基礎的作業系統到資料庫、分散式快取、本地快取等。它們表現形式各異，卻有著共同的樸素的本質：彌補CPU的高算力和IO的慢讀寫之間巨大的鴻溝。

和架構選型類似，每引入一個元件，都會導致複雜度的上升。以快取為例，它帶來效能提升的同時，也帶來一些問題，需要開發者設計和權衡。

本文的思維脈絡如下：

一 快取和多級快取

1 快取的引入

在初期業務量小的時候，資料庫能承擔讀寫壓力，應用可以直接和DB互動，架構簡單且強壯。

經過一段時間發展後，業務量迎來了大規模增長，此時DB查詢壓力和耗時都在增長。此時引入分散式快取，在減少DB壓力的同時，還提供了更高的QPS。

再往後發展，分散式快取也成為了瓶頸，高頻的QPS是一筆負擔；另外快取驅逐以及網路抖動會影響系統的穩定性，此時引入本地快取，可以減輕分散式快取的壓力，並減少網路以及序列化開銷。

2 讀寫的效能提升

快取透過減少IO操作來獲得讀寫的效能提升。有一個表格，可以看見磁碟、網路的IO操作耗時，遠高於記憶體存取。

讀最佳化：當請求命中快取後，可直接返回，從而略過IO讀取，減小讀的成本。

寫最佳化：將寫操作在緩衝中合併，讓IO裝置可以批次處理，減小寫的成本。

快取帶來的QPS、RT提升比較直觀，不補充介紹。

3 快取Miss

快取Miss是必然會面對的問題，快取需保證在有限的容量下，將熱點的資料維護在快取中，從而達到效能、成本的平衡。

快取通常使用LRU演算法淘汰近期不常用的Key。

近似LRU

可以先試想嚴格LRU的實現。假設Redis當前有50W規模的key，先透過Keys 遍歷獲得所有Key，然後比對出空閒時間最長的某個key，最後執行淘汰。這樣的流程下來，是非常昂貴的，Keys命令是一筆不小的開銷，其次大規模執行比對也很昂貴。

當然嚴格LRU實現的最佳化空間還是有的，YY一下，可以透過活躍度分離出活躍Key和待回收Key， 淘汰時只關注待回收key即可；回收演算法引入連結串列或者樹的結構，使Key按空閒時間有序，淘汰時直接獲取。然而這些最佳化不可避免的是，在快取讀寫時，這些輔助的資料結構需要同步更新，帶來的儲存以及計算的成本很高。

在Redis中它採用了近似LRU的實現，它隨機取樣5個Key，淘汰掉其中空閒時間最長的那個。近似LRU實現起來更簡單、成本更低，在效果上接近嚴格LRU。它的缺點是存在一定的機率淘汰掉最近被訪問的Key，即在TTL到期前也可能被淘汰。

避免短期大量失效

在一些場景中，程式是批次載入資料到快取的， 比如透過Excel上傳資料，系統解析後，批次寫入DB和快取。此時若不經設計，這批資料的超時時間往往是一致的。快取到期後，本該快取承擔的流量將打到DB上，從而降低介面甚至系統的效能和穩定性。

可以利用隨機數打散快取失效時間，例如設定TTL=8hr+random（8000）ms。

4 快取一致性

系統應儘量保證DB、快取的資料一致性，較常使用的是cache aside設計模式。

避免使用非常規的快取設計模式： 先更新快取、後更新DB； 先更新DB、後更新快取（cache aside是直接失效快取）。這些模式的不一致風險較高。

快取設計模式

業務系統通常使用cache aside 模式，作業系統、資料庫、分散式快取等會使用write throgh、write back。

cache aside的快取不一致

Cache aside模式大部分時間執行良好，在一些極端場景下，仍可能出現不一致風險。主要來自兩方面：

由於中介軟體或者網路等問題，快取失效失敗。

出現意外的快取失效、讀取的時序。

快取失效失敗很容易理解，不做補充。主要介紹時序引起的不一致問題。

考慮這樣的時間軸，A執行緒發現cache miss後重新載入快取，此時讀的資料還是老的， 另一個執行緒B更新資料並失效快取。若B執行緒失效快取的操作完成時間早於A執行緒，A執行緒會寫入老的資料。

快取不一致有一些緩解方法，例如延遲雙刪、CDC同步。這些方案都提升了系統複雜度，需綜合考慮業務的容忍度，方案的複雜度等。

延遲雙刪：主執行緒失效快取後，將失效指令放入延時佇列，另一個執行緒輪詢佇列獲取指令並執行。

CDC同步：透過canal訂閱MySQL binlog的變更，上報給Kafka，系統監聽Kafka訊息觸發快取失效。

二 從堆記憶體到直接記憶體

1 直接記憶體的引入

Java本地快取分兩類，基於堆記憶體的、基於直接記憶體的。

採用堆記憶體做快取的主要問題是GC，由於快取物件的生命週期往往較長，需要透過Major GC進行回收。若快取的規模很大，那麼GC會非常耗時。

採用直接記憶體做快取的主要問題是記憶體管理。程式需自主控制記憶體的分配和回收，存在OOM或者Memory Leak的風險。另外直接記憶體不能存取物件，在操作時需進行序列化。

直接記憶體能減少GC壓力，因為它只需要儲存直接記憶體的引用，而物件本身是儲存在直接記憶體中。引用晉升到老年代後佔用的空間很小，對GC的負擔可忽略。

直接記憶體的回收依賴System。gc的呼叫，但這個呼叫JVM不保證執行、也不保證何時執行，它的行為是不可控的。程式一般需要自行管理，成對去呼叫malloc、free，依託於這種“手工、類C”的記憶體管理，可以增加記憶體回收的可控性和靈活性。

2 直接記憶體管理

由於直接記憶體的分配和回收比較昂貴，需要透過核心操作物理記憶體。申請的時候一般是申請大的記憶體快，然後再根據需求分配小塊給執行緒。回收的時候不直接釋放，而是放入記憶體池來重用。

如何快速找到一個空閒塊、如何減少記憶體碎片、如何快速回收等等，它是一個系統性的問題，也有很多專門的演算法。

Jemalloc是綜合能力較好的演算法，free BSD、Redis預設採用了該演算法，OHC快取也建議伺服器配置該演算法。Netty的作者實現了Java版本，感興趣的可以閱讀。

三 CPU快取

利用上分散式快取、本地快取之後，還可以繼續提升的就是CPU快取了。它雖不易察覺，但在高併發下對效能存在一定的影響。

CPU快取分為L1、L2、L3 三級，越靠近CPU的，容量越小，命中率越高。當L3等級的快取都取不到資料的時候，需從主存中獲取。

1 CPU cache line

CPU快取由cache line組成，每一個cache line為64位元組，能容納8個long值。在CPU從主存獲取資料時，以cache line為單位載入，於是相鄰的資料會一併載入到快取中。很容易想到，陣列的順序遍歷、相鄰資料的計算是非常高效的。

2 偽共享 false sharing

CPU快取也存在一致性問題，它透過MESI協議、MESIF協議來保證。

偽共享來源於高併發時cache line出現了快取不一致。同一個cache line中的資料會被不同執行緒修改，它們相互影響，導致處理效能降低。

上圖模擬一個偽共享場景，NoPadding是執行緒共享物件，thread0 會修改no0、thread1 會修改no1。當thread0修改時，除了修改自身的cache line，依據CPU快取協議還會導致thread1對應的cache line失效，這時thread1 發現cache miss後從主存載入，修改後又導致thread0 的cache line 失效。

NoPadding {long no0；long no1；}

3 偽共享解決方案

padding

透過填充，讓no0、no1落在不同的cache line中：

Padding {long p1， p2， p3， p4， p5， p6， p7；volatile long no0 = 0L；long p9， p10， p11， p12， p13， p14；volatile long no1 = 0L；}

案例：jctools

Contended 註解

委託JVM填充cache line：

@sun。misc。Contended static final class CounterCell { volatile long value； CounterCell（long x） { value = x； } }

案例：JDK原始碼中LongAdder中的Cell、ConcurrentHashMap的CounterCell。

無鎖併發

無鎖併發可以從本質上解決偽共享問題，它無需填充cache line，並且執行效率是最高的。

案例：disruptor

四 總結

近來由於業務對介面RT提出了更高的要求，在效能最佳化的過程中，快取的使用是非常多的。藉此機會記錄下在這段時間的思考。私以為，在引入某一項技術的時候，需整體的去看，瞭解其概念、原理、適用場景、注意事項，這樣可以在設計之初就規避掉一些風險。

分散式快取、本地快取、CPU快取涵蓋的內容非常多，本文做了一些歸納。對細節感興趣的同學可以閱讀《Redis 設計與實現》、disruptor 設計文件及程式碼。

作者 | 燭衡