Java架構師聯盟

在計算機領域，緩存在程序設計過程中扮演著重要角色。瀏覽器的資源緩存策略是影響web網站性能的一個關鍵因素；mysql的Buffer Pool極大的提高了數據庫的查詢效率；redis作為被廣泛應用的緩存數據庫，提供了豐富的數據結構和緩存策略來滿足開發者的需求。緩存在現代計算機系統中無處不在，是一個非常深入、廣泛的話題，本文的目的是從眾多已有的系統設計中，提取出有關系統緩存設計的精要，主要從三個方面展開：

• 多級緩存
• 緩存淘汰策略
• 緩存安全

在討論這些話題的同時，筆者會結合很多實際的例子闡述，其中會涉及到PHP源碼、redis源碼、瀏覽器的緩存策略、mysql數據存儲設計、緩存淘汰算法等偏底層的內容，如果你是一個比較資深的開發工程師，對這些內容都比較了解，本文將非常適合您。為了照顧初學者，涉及到難懂重要的知識點筆者也將會盡可能的描述清楚。本文篇幅有點長，請讀者做好心理預期！

1.多級緩存

1.1 存儲器層次結構

計算機使用不同的存儲技術對數據進行訪問，時間差異很大。速度較快的技術每個字節的成本要比速度較慢的技術高，而且容量較小。CPU和主存(內存)之間的速度差距在增大?；谶@種特性，所有的現代計算機系統都使用了金字塔式的存儲器層次結構。如下圖所示：

從高層往低層走，存儲設備變得更慢、更便宜、容量更大。最高層(L0)是少量快速的CPU寄存器，CPU可以在一個時鐘周期內訪問它們 (一個時鐘周期通常小于1ns)；接下來是一個或多個中小型SRAM高速緩存存儲器，可以在幾個CPU時鐘周期內訪問它們；然后是一個大的基于DRAM的主存，可以在幾十到幾百個CPU時鐘周期內訪問它們；接下來是慢速但是容量很大的本地磁盤(通常是SSD)；最后有些系統甚至包括了一層附加的網絡文件系統(Network File System,NFS)，比如說騰訊云提供的CFS服務就可以通過掛載到多個服務器實現分布式的數據共享。

下面我們從 CPU 的角度以具體的數據來量化對比CPU、磁盤、網絡的速度，對計算機各個組件不同的速度差異有個更直觀的認識。

類型

緩存內容

緩存位置

讀取數據需要時長

對比基本單位時長

CPU寄存器

4字節 & 8字節

芯片上的CPU寄存器

0.38ns

1s

L1高速緩存

64字節塊

芯片上的L1高速緩存

0.5ns

1.3s

L2高速緩存

64字節塊

芯片上的L2高速緩存

7ns

18.2s

L3高速緩存

64字節塊

芯片上的L3高速緩存

35ns

91s

內存

4KB頁

主存

100ns

4分鐘

固態硬盤SSD

磁盤扇區

磁盤控制器

150us

4.5天

網絡磁盤(NFS本地掛載)

部分文件

本地磁盤

1.5ms

一個半月

CPU 和內存之間的瓶頸被稱為馮諾依曼瓶頸, 它們之間至少有著幾百倍的速差，可以想象成天上人間，天上一天，地下一年。普通的磁盤讀取數據就更慢了，尋址時間10ms，對比CPU的基本單位時長是10個月，可以生一次孩子了！所以說IO 設備是計算機系統的瓶頸。以此想到我們網絡中的API請求，動不動就是一百多毫秒，對比CPU的基本單位就是十幾年！

相信通過以上描述，讀者對計算機組件之間數據處理速度有了深入的印象。

1.2 局部性原理

一個編寫良好的計算機程序通常具有良好的局部性(locality)。也就是，它們傾向于引用鄰近于其他最近引用過的數據項的數據項，或者最近引用過的數據項本身。這種傾向性，被稱為局部性原理(principle of locality)，是一個持久的概念，對硬件和軟件系統的設計和性能都有著極大的影響。

局部性通常有兩種不同的形式: 時間局部性(temporal locality) 和 空間局部性(spatial locality)。

• 時間局部性：被引用過一次的內存位置很可能在不遠的將來再被多次引用。
• 空間局部性：如果一個內存位置被引用了一次，那么程序很可能在不遠的將來引用附近的一個內存位置。

Mysql數據庫Innodb引擎的設計就很好的考慮了局部性原理。

Innodb引擎以頁的形式組織數據，頁的默認大小是16KB,存放用戶數據記錄的頁叫“數據頁”，為了實現數據更快的查找，InnoDB使用B+樹的結構組織存放數據，最下層的葉子節點存放“數據頁”，在“數據頁”的上層抽出相應的“目錄頁”，最終形成的基本結構如下圖所示：

數據頁中記錄是連續存放的，當需要訪問某個頁的數據時，就會把完整的頁的數據全部加載到內存中，也就是說即使我們只需要訪問一個頁的一條記錄，那也需要先把整個頁的數據加載到內存中。這就利用了局部性原理中的“空間局部性”。將整個頁加載到內存中后就可以進行讀寫訪問了，在進行完讀寫訪問之后并不著急把該頁對應的內存空間釋放掉，而是將其緩存到Buffer Pool中，這樣將來有請求再次訪問該頁面時，就可以省去磁盤IO的開銷了，這又利用了局部性原理中的“時間局部性”。

局部性原理是系統緩存設計中非常重要的理論基石，下文還會多次提到。

1.3 Cpu 高速緩存

本節我們來聊一聊Cpu 高速緩存，Cpu 高速緩存是影響程序性能的一個關鍵因素。

1.3.1 什么是Cpu 高速緩存?

筆者直接引用維基百科中對Cpu 高速緩存的描述：

在計算機系統中，CPU高速緩存（英語：CPU Cache，在本文中簡稱緩存）是用于減少處理器訪問內存所需平均時間的部件。在金字塔式存儲體系中它位于自頂向下的第二層，僅次于CPU寄存器。其容量遠小于內存，但速度卻可以接近處理器的頻率。 當處理器發出內存訪問請求時，會先查看緩存內是否有請求數據。如果存在（命中），則不經訪問內存直接返回該數據；如果不存在（失效），則要先把內存中的相應數據載入緩存，再將其返回處理器。 緩存之所以有效，主要是因為程序運行時對內存的訪問呈現局部性（Locality）特征。這種局部性既包括空間局部性（Spatial Locality），也包括時間局部性（Temporal Locality）。有效利用這種局部性，緩存可以達到極高的命中率。 在處理器看來，緩存是一個透明部件。因此，程序員通常無法直接干預對緩存的操作。但是，確實可以根據緩存的特點對程序代碼實施特定優化，從而更好地利用緩存。

1.3.2 為什么需要有Cpu 高速緩存?

上文中我們提到馮諾依曼瓶頸。隨著工藝的提升，最近幾十年CPU的頻率不斷提升，而受制于制造工藝和成本限制，目前計算機的內存在訪問速度上沒有質的突破。因此，CPU的處理速度和內存的訪問速度差距越來越大，這種情況下傳統的 CPU 直連內存的方式顯然就會因為內存訪問的等待，導致計算資源大量閑置，降低 CPU 整體吞吐量。同時又由于內存數據訪問的熱點集中性，在 CPU 和內存之間用較為快速而成本較高（相對于內存）的介質做一層緩存，就顯得性價比極高了。

1.3.3 Cpu 高速緩存架構

早期計算機系統的存儲器層次結構只有三層：CPU寄存器、DRAM主存儲器和磁盤存儲。由于CPU和主存之間逐漸增大的差距，系統設計者被迫在CPU寄存器文件和主存之間插入了一個小的SRAM高速緩存存儲器，稱為L1高速緩存(一級緩存),如下圖所示。L1高速緩存的訪問速度幾乎和寄存器相差無幾。

隨著CPU和主存之間的性能差距不斷增大，系統設計者在L1高速緩存和主存之間又插入了一個更大的高速緩存，稱為L2高速緩存，可以在大約10個時鐘周期內訪問到它。現代的操作系統還包括一個更大的高速緩存，稱為L3高速緩存,在存儲器的層次結構中，它位于L2高速緩存和主存之間，可以在大約50個周期內訪問到它。下圖是簡單的高速緩存架構：

數據的讀取和存儲都經過高速緩存，CPU 核心與高速緩存有一條特殊的快速通道；主存與高速緩存都連在系統總線上（BUS），這條總線還用于其他組件的通信。

1.3.4 PHP7數組的設計

關于Cpu 高速緩存的應用，PHP7數組的設計是一個非常經典的案例。在PHP中數組是最常用的一種數據類型，提升數組的性能會使程序整體性能得到提升。我們通過對比PHP7和PHP5 數組的設計，來學習一下PHP 設計者為了提升PHP數組的性能，都進行了哪些思考。

我們先來總結一下PHP數組的特性：

• php中的數組是一個字典dict，存儲著key-value對，通過key可以快速的找到value,其中key可以是整形，也可以是字符串（hash array 和 packed array）。
• 數組是有序的：插入有序、遍歷有序。

PHP中數組使用hashTable實現，我們先來了解一下什么是hashTable。

hashTable是一種通過某種hash函數將特定的key映射到特定value的一種數據結構，它維護著鍵和值的一一對應關系，并且可以快速的根據鍵找到值(o(1)). 一般HashTable的示意圖如下:

1) key: 通過key可以快速找到value。一般可以為數字或者字符串。2) value: 值可以為復雜結構3) bucket: 桶，HashTable存儲數據的單元，用來存儲key/value以及其他輔助信息的容器4) slot:槽，HashTable有多少個槽，一個bucket必須屬于具體的某一個slot，一個slot可以有多個 bucket5) 哈希函數:一般都是自己實現（time33），在存儲的時候，會將key通過hash函數確定所在的slot6) 哈希沖突: 當多個key經過哈希計算后，得到的slot位置是同一個，那么就會沖突，一般這個時候會有 2種解決辦法:鏈地址法和開放地址法。其中php采用的是鏈地址法，即將同一個slot中的bucket通過 鏈表連接起來復制代碼

為了實現數組的插入有序和遍歷有序，PHP5使用hashTable + 雙鏈表實現數組，如下圖是將key分別為：“a”,"b","c","d",值為“1”,"2","3","4" 插入到數組中后的效果：

上圖中b,c,d所在的bucket被存分配到了同一個slot，為了解決hash沖突，slot中多個bucket通過雙向鏈表關聯，稱為局部雙向鏈表；為了實現有序，slot之間也通過雙向鏈表關聯，稱為全局雙向鏈表。

了解php5數組的實現原理之后，我們發現其中影響性能的兩個關鍵點：

1. 頻繁的內存分配！每向數組中添加一個元素，都需要申請分配一個bucket大小的內存，然后維護多個指針。雖然php是基于內存池的管理方式(預先申請大塊內存進行按需分配)，但是內存分配帶來的性能損耗是不可忽略的。
2. Cpu 高速緩存命中率低！因為bucket與bucket之間是通過鏈表指針連接的，bucket隨機分配，內存基本不連續，導致Cpu cache降低，不能給遍歷數組帶來性能提升。

針對以上兩點，php7對hashTable的設計進行了改造。既然是字典，還是要使用hashTable,但php7數組的實現去掉了slot，bucket的分配使用了連續內存；bucket間不再使用真實存在的指針進行維護，bucket只維護一個在數組中的索引，bucket與bucket之間通過內存地址進行關聯，如下圖所示:

PHP7中數組是如何解決hash沖突的？

PHP7對zval進行了改造，zval中有一個u2的union聯合體，占用4字節大小，存放一些輔助信息。PHP7數組中的value也是一個個的zval指針，當發生hash沖突時，zval中u2部分存放的next指針存放指向下一個bucket數組中的索引，通過這樣一種邏輯上的鏈表就巧妙解決hash沖突。關于PHP7中zval的設計，推薦大家閱讀鳥哥的文章：深入理解PHP7內核之zval

可以看到，php7中hashTable對性能提升最重要的改動是bucket的分配使用了連續內存。這樣不僅省去了數組元素插入時頻繁的內存分配開銷；遍歷數組也只需要一個bucket一個bucket的訪問就好了，Cpu 高速緩存命中率非常高，極大的提升了數組性能；符合局部性原理。

更多關于PHP5和PHP7數組的設計細節，推薦大家研究這篇文章：【PHP7源碼學習】系列之數組實現

1.4 瀏覽器的多級緩存機制

舉一個多級緩存的應用案例：瀏覽器對我們生活的影響是不言而喻的，現代的瀏覽器已經不同往昔了，快速的信息加載，順暢的用戶交互，這一切都得益于網絡技術的普及、H5標準特性的推廣應用，當然還有一個重要因素，那就是瀏覽器的緩存策略。本節我們就來簡單介紹一下瀏覽器的多級緩存機制。

對于一個數據請求來說，可以分為發起網絡請求、后端處理、瀏覽器響應三個步驟。瀏覽器緩存可以幫助我們在第一和第三步驟中優化性能。比如說直接使用緩存而不發起請求，或者發起了請求但后端存儲的數據和前端一致，那么就沒有必要再將數據回傳回來，這樣就減少了響應數據。

瀏覽器有四種緩存級別，它們各自都有優先級。

• Service Worker
• Memory Cache
• Disk Cache
• Push Cache

當依次查找緩存且都沒有命中的時候，才會去請求網絡。

1.4.1 Service Worker

Service Worker 是運行在瀏覽器背后的獨立線程，一般可以用來實現緩存功能。使用 Service Worker的話，傳輸協議必須為 HTTPS。因為 Service Worker 中涉及到請求攔截，所以必須使用 HTTPS 協議來保障安全。Service Worker 的緩存與瀏覽器其他內建的緩存機制不同，它可以讓我們自由控制緩存哪些文件、如何匹配緩存、如何讀取緩存，并且緩存是持續性的。

Service Worker 實現緩存功能一般分為三個步驟：首先需要先注冊 Service Worker，然后監聽到 install 事件以后就可以緩存需要的文件，那么在下次用戶訪問的時候就可以通過攔截請求的方式查詢是否存在緩存，存在緩存的話就可以直接讀取緩存文件，否則就去請求數據。

當 Service Worker 沒有命中緩存的時候，我們需要去調用 fetch 函數獲取數據。也就是說，如果我們沒有在 Service Worker 命中緩存的話，會根據緩存查找優先級去查找數據。但是不管我們是從 Memory Cache 中還是從網絡請求中獲取的數據，瀏覽器都會顯示我們是從 Service Worker 中獲取的內容。

1.4.2 Memory Cache

Memory Cache 也就是內存中的緩存，主要包含的是當前頁面中已經抓取到的資源,例如頁面上已經下載的樣式、腳本、圖片等。讀取內存中的數據肯定比磁盤快，內存緩存雖然讀取高效，可是緩存持續性很短，會隨著進程的釋放而釋放。 一旦我們關閉 Tab 頁面，內存中的緩存也就被釋放了。

當我們訪問過頁面以后，再次刷新頁面，可以發現很多數據都來自于內存緩存

內存緩存中有一塊重要的緩存資源是preloader相關指令（例如）下載的資源。眾所周知preloader的相關指令已經是頁面優化的常見手段之一，它可以一邊解析js/css文件，一邊網絡請求下一個資源。

需要注意的事情是，內存緩存在緩存資源時并不關心返回資源的HTTP緩存頭Cache-Control是什么值，同時資源的匹配也并非僅僅是對URL做匹配，還可能會對Content-Type，CORS等其他特征做校驗。

為什么瀏覽器數據不都存放在內存中？

這個問題就算我不回答，讀者肯定也都想明白了，計算機中的內存一定比硬盤容量小得多，操作系統需要精打細算內存的使用，所以能讓我們使用的內存必然不多。谷歌瀏覽器是公認的性能出眾的，但是它占用的內存也是很大的。

1.4.3 Disk Cache

Disk Cache 也就是存儲在硬盤中的緩存，讀取速度慢點，但是什么都能存儲到磁盤中，比之 Memory Cache 勝在容量和存儲時效性上。

在所有瀏覽器緩存中，Disk Cache 覆蓋面基本是最大的。它會根據 HTTP Herder 中的字段判斷哪些資源需要緩存，哪些資源可以不請求直接使用，哪些資源已經過期需要重新請求。并且即使在跨站點的情況下，相同地址的資源一旦被硬盤緩存下來，就不會再次去請求數據。絕大部分的緩存都來自 Disk Cache。

瀏覽器會把哪些文件丟進內存中？哪些丟進硬盤中？

關于這點，網上說法不一，不過有些觀點比較靠得?。簩τ诖笪募碚f，大概率是不存儲在內存中的，另外如果當前系統內存使用率高的話，文件優先存儲進硬盤。

1.4.4 Push Cache

Push Cache（推送緩存）是 HTTP/2 中的內容，當以上三種緩存都沒有命中時，它才會被使用。它只在會話（Session）中存在，一旦會話結束就被釋放，并且緩存時間也很短暫，在Chrome瀏覽器中只有5分鐘左右，同時它也并非嚴格執行HTTP頭中的緩存指令。

Push Cache 在國內能夠查到的資料很少，也是因為 HTTP/2 在國內不夠普及。這里推薦閱讀Jake Archibald的 HTTP/2 push is tougher than I thought 這篇文章，文章中的幾個結論是：

• 所有的資源都能被推送，并且能夠被緩存,但是 Edge 和 Safari 瀏覽器支持相對比較差
• 可以推送 no-cache 和 no-store 的資源
• 一旦連接被關閉，Push Cache 就被釋放
• 多個頁面可以使用同一個HTTP/2的連接，也就可以使用同一個Push Cache。這主要還是依賴瀏覽器的實現而定，出于對性能的考慮，有的瀏覽器會對相同域名但不同的tab標簽使用同一個HTTP連接。
• Push Cache 中的緩存只能被使用一次
• 瀏覽器可以拒絕接受已經存在的資源推送
• 你可以給其他域名推送資源

如果以上四種緩存都沒有命中的話，那么只能發起請求來獲取資源了。

瀏覽器的多級緩存機制到這里就介紹完了，大家可以看到，瀏覽器多級緩存機制的實現思路，和我們前邊說到的計算機系統多級緩存的知識是相呼應的，并且也滿足局部性原理。瀏覽器緩存還有更多值得我們深入學習的內容，感興趣的讀者可以研究一下這篇文章：深入理解瀏覽器的緩存機制

2. 緩存淘汰策略

根據金字塔存儲器層次模型我們知道：CPU訪問速度越快的存儲組件容量越小。在業務場景中，最常用的存儲組件是內存和磁盤，我們往往將常用的數據緩存到內存中加快數據的讀取速度，redis作為內存緩存數據庫的設計也是基于這點考慮的。但是服務器的內存有限，不可能不斷的將數據存入內存中而不淘汰。況且內存占用過大，也會影響服務器其它的任務，所以我們要做到通過淘汰算法讓內存中的緩存數據發揮最大的價值。

本節將介紹業務中最常用的三種緩存淘汰算法:

• Least Recently Used（LRU）淘汰最長時間未被使用的頁面，以時間作為參考
• Least Frequently Used(LFU)淘汰一定時期內被訪問次數最少的頁面，以次數作為參考
• 先進先出算法（FIFO）

筆者會結合Redis、Mysql中緩存淘汰的具體實現機制來幫助讀者學習到，Mysql和Redis的開發者是怎樣結合各自的業務場景，對已有的緩存算法進行改進來滿足業務需求的。

2.1 Least Recently Used（LRU）

LRU是Least Recently Used的縮寫，這種算法認為最近使用的數據是熱門數據，下一次很大概率將會再次被使用。而最近很少被使用的數據，很大概率下一次不再用到。該思想非常契合業務場景 ，并且可以解決很多實際開發中的問題，所以我們經常通過LRU的思想來作緩存，一般也將其稱為LRU緩存機制。

2.1.1 LRU緩存淘汰算法實現

本節筆者以leetcode上的一道算法題為例，使用代碼(Go語言)實現LRU算法，幫助讀者更深入的理解LRU算法的思想。

leetcode 146: LRU緩存機制

運用你所掌握的數據結構，設計和實現一個 LRU (最近最少使用) 緩存機制。它應該支持以下操作： 獲取數據 get 和 寫入數據 put 。

獲取數據 get(key) - 如果密鑰 (key) 存在于緩存中，則獲取密鑰的值（總是正數），否則返回 -1。 寫入數據 put(key, value) - 如果密鑰已經存在，則變更其數據值；如果密鑰不存在，則插入該組「密鑰/數據值」。當緩存容量達到上限時，它應該在寫入新數據之前刪除最久未使用的數據值，從而為新的數據值留出空間。

示例：

LRUCache cache = new LRUCache( 2 /* 緩存容量 */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 該操作會使得密鑰 2 作廢 cache.get(2); // 返回 -1 (未找到) cache.put(4, 4); // 該操作會使得密鑰 1 作廢 cache.get(1); // 返回 -1 (未找到) cache.get(3); // 返回 3 cache.get(4); // 返回 4 復制代碼

我們采用hashmap+雙向鏈表的方式進行實現。可以在 O(1)時間內完成 put 和 get 操作，同時也支持 O(1) 刪除第一個添加的節點。

使用雙向鏈表的一個好處是不需要額外信息刪除一個節點，同時可以在常數時間內從頭部或尾部插入刪除節點。

一個需要注意的是，在雙向鏈表實現中，這里使用一個偽頭部和偽尾部標記界限，這樣在更新的時候就不需要檢查是否是 null 節點。

代碼如下：

type LinkNode struct { key, val int pre, next *LinkNode}type LRUCache struct { m map[int]*LinkNode cap int head, tail *LinkNode}func Constructor(capacity int) LRUCache { head := &LinkNode{0, 0, nil, nil} tail := &LinkNode{0, 0, nil, nil} head.next = tail tail.pre = head return LRUCache{make(map[int]*LinkNode), capacity, head, tail}}復制代碼

這樣就初始化了一個基本的數據結構,大概是這樣：

接下來我們為Node節點添加一些必要的操作方法，用于完成接下來的Get和Put操作：

func (this *LRUCache) RemoveNode(node *LinkNode) { node.pre.next = node.next node.next.pre = node.pre}func (this *LRUCache) AddNode(node *LinkNode) { head := this.head node.next = head.next head.next.pre = node node.pre = head head.next = node}func (this *LRUCache) MoveToHead(node *LinkNode) { this.RemoveNode(node) this.AddNode(node)}復制代碼

因為Get比較簡單，我們先完成Get方法。這里分兩種情況考慮：

• 如果沒有找到元素，我們返回-1。
• 如果元素存在，我們需要把這個元素移動到首位置上去。

func (this *LRUCache) Get(key int) int { cache := this.m if v, exist := cache[key]; exist { this.MoveToHead(v) return v.val } else { return -1 }}復制代碼

現在我們開始完成Put。實現Put時，有兩種情況需要考慮。

• 假若元素存在，其實相當于做一個Get操作，也是移動到最前面（但是需要注意的是，這里多了一個更新值的步驟）。
• 假若元素不存在，我們將其插入到元素首，并把該元素值放入到map中。如果恰好此時Cache中元素滿了，需要刪掉最后的元素。

處理完畢，附上Put函數完整代碼。

func (this *LRUCache) Put(key int, value int) { tail := this.tail cache := this.m if v, exist := cache[key]; exist { v.val = value this.MoveToHead(v) } else { v := &LinkNode{key, value, nil, nil} if len(cache) == this.cap { delete(cache, tail.pre.key) this.RemoveNode(tail.pre) } this.AddNode(v) cache[key] = v }}復制代碼

至此，我們就完成了一個LRU算法，附上完整的代碼：

type LinkNode struct { key, val int pre, next *LinkNode}type LRUCache struct { m map[int]*LinkNode cap int head, tail *LinkNode}func Constructor(capacity int) LRUCache { head := &LinkNode{0, 0, nil, nil} tail := &LinkNode{0, 0, nil, nil} head.next = tail tail.pre = head return LRUCache{make(map[int]*LinkNode), capacity, head, tail}}func (this *LRUCache) Get(key int) int { cache := this.m if v, exist := cache[key]; exist { this.MoveToHead(v) return v.val } else { return -1 }}func (this *LRUCache) RemoveNode(node *LinkNode) { node.pre.next = node.next node.next.pre = node.pre}func (this *LRUCache) AddNode(node *LinkNode) { head := this.head node.next = head.next head.next.pre = node node.pre = head head.next = node}func (this *LRUCache) MoveToHead(node *LinkNode) { this.RemoveNode(node) this.AddNode(node)}func (this *LRUCache) Put(key int, value int) { tail := this.tail cache := this.m if v, exist := cache[key]; exist { v.val = value this.MoveToHead(v) } else { v := &LinkNode{key, value, nil, nil} if len(cache) == this.cap { delete(cache, tail.pre.key) this.RemoveNode(tail.pre) } this.AddNode(v) cache[key] = v }}復制代碼

2.1.2 Mysql緩沖池LRU算法

在使用Mysql的業務場景中，如果使用上述我們描述的LRU算法來淘汰策略，會有一個問題。例如執行下面一條查詢語句：

select * from table_a;復制代碼

如果 table_a 中有大量數據并且讀取之后不會繼續使用,則LRU頭部會被大量的 table_a 中的數據占據,這樣會造成熱點數據被逐出緩存從而導致大量的磁盤IO。所以Mysql緩沖池采用the least recently used（LRU）算法的變體，將緩沖池作為列表進行管理。

Mysql的緩沖池

緩沖池（Buffer Pool）是主緩存器的一個區域，用于緩存索引、行的數據、自適應哈希索引、插入緩存（Insert Buffer）、鎖 還有其他的內部數據結構。Buffer Pool的大小是可以根據我們實際的需求進行更改，那么Buffer Pool的size取多少比較合適?MySQL官網上是這么介紹，在專用服務器上（也就是服務器只承載一個MySQL實例），會將80%的物理內存給到Buffer Pool。Buffer Pool允許直接從內存中讀常用數據去處理，會加快很多的速度。為了提高大容量讀取操作的效率，Buffer Pool被分成可以容納多行的頁面。為了提高緩存管理的效率，Buffer Pool被實現為頁面對應的鏈接的列表（a linked list of pages）。

Mysql數據庫Buffer Pool結構：

當需要空間將新頁面緩存到緩沖池的時候，最近最少使用的頁面將被釋放出去，并將新的頁面加入列表的中間。這個中間點插入的策略將列表分為兩個子列表：

• 頭部是存放最近訪問過的新頁面的子列表
• 尾部是存放那些最近訪問較少的舊頁面的子列表

該算法將保留 new sublist（也就是結構圖中頭部）中大量被查詢使用的頁面。而old sublist 里面較少被使用的頁面作為被釋放的候選項。

理解以下幾個關鍵點是比較重要的：

• 3/8的緩沖池專用于old sublist（也就是3/8來保存舊的頁面，其余部分用來存儲熱數據，存儲熱數據的部分相對大一些，當然這個值可以自己去調整，通過innodb_old_blocks_pct，其默認值是37，也就是3/8*100，上限100，可調整 5-95，可以改小一些，但是調整后盡量保證這個比例內的數據也就是old sublist中的數據只會被讀取一次，若不是了解非常業務數據負載建議不要去修改。）
• 列表的中點是新子列表的尾部與舊子列表的頭部相交的邊界。
• 當InnoDB將頁面讀入緩沖池時，它最初將其插入中點（舊子列表的頭部）。一個頁面會被讀取是因為它是用戶指定的操作（如SQL查詢）所需，或者是由InnoDB自動執行的預讀操作的一部分 。
• 訪問舊子列表中的頁面使其 “ 年輕 ”，將其移動到緩沖池的頭部（新子列表的頭部）。如果頁面是被需要比如（SQL）讀取的，它會馬上訪問舊列表并將頁面推入新列表頭部。如果預讀需要讀取的頁面，則不會發生對舊列表的first access。
• 隨著數據庫的運行，在緩沖池的頁面沒有被訪問則向列表的尾部移動。新舊子列表中的頁面隨著其他頁面的變化而變舊。舊子列表中的頁面也會隨著頁面插入中點而老化。最終，仍未使用的頁面到達舊子列表的尾部并被釋放。默認情況下，頁面被查詢讀取將被立即移入新列表中，在Buffer Pool中存在更長的時間。

通過對LRU算法的改進，InnoDB引擎解決了查詢數據量大時，熱點數據被逐出緩存從而導致大量的磁盤IO的問題。

2.1.3 Redis近似LRU實現

由于真實LRU需要過多的內存（在數據量比較大時）；并且Redis以高性能著稱，真實的LRU需要每次訪問數據時都做相關的調整，勢必會影響Redis的性能發揮；這些都是Redis開發者所不能接受的，所以Redis使用一種隨機抽樣的方式，來實現一個近似LRU的效果。

在Redis中有一個參數，叫做 “maxmemory-samples”，是干嘛用的呢？

1 # LRU and minimal TTL algorithms are not precise algorithms but approximated 2 # algorithms (in order to save memory), so you can tune it for speed or 3 # accuracy. For default Redis will check five keys and pick the one that was 4 # used less recently, you can change the sample size using the following 5 # configuration directive. 6 # 7 # The default of 5 produces good enough results. 10 Approximates very closely 8 # true LRU but costs a bit more CPU. 3 is very fast but not very accurate. 9 # 10 maxmemory-samples 5復制代碼

上面我們說過了，近似LRU是用隨機抽樣的方式來實現一個近似的LRU效果。這個參數其實就是作者提供了一種方式，可以讓我們人為干預樣本數大小，將其設的越大，就越接近真實LRU的效果，當然也就意味著越耗內存。（初始值為5是作者默認的最佳）

左上圖為理想中的LRU算法,新增加的key和最近被訪問的key都不應該被逐出?？梢钥吹?Redis2.8當每次隨機采樣5個key時，新增加的key和最近訪問的key都有一定概率被逐出；Redis3.0增加了pool后效果好一些(右下角的圖)。當Redis3.0增加了pool并且將采樣key增加到10個后，基本等同于理想中的LRU(雖然還是有一點差距)。

Redis中對LRU代碼實現也比較簡單。Redis維護了一個24位時鐘，可以簡單理解為當前系統的時間戳，每隔一定時間會更新這個時鐘。每個key對象內部同樣維護了一個24位的時鐘，當新增key對象的時候會把系統的時鐘賦值到這個內部對象時鐘。比如我現在要進行LRU，那么首先拿到當前的全局時鐘，然后再找到內部時鐘與全局時鐘距離時間最久的（差最大）進行淘汰，這里值得注意的是全局時鐘只有24位，按秒為單位來表示才能存儲194天，所以可能會出現key的時鐘大于全局時鐘的情況，如果這種情況出現那么就兩個相加而不是相減來求最久的key。

struct redisServer { pid_t pid; char *configfile; //全局時鐘 unsigned lruclock:LRU_BITS; ...};復制代碼

typedef struct redisObject { unsigned type:4; unsigned encoding:4; /* key對象內部時鐘 */ unsigned lru:LRU_BITS; int refcount; void *ptr;} robj;復制代碼

總結一下：Redis中的LRU與常規的LRU實現并不相同，常規LRU會準確的淘汰掉隊頭的元素，但是Redis的LRU并不維護隊列，只是根據配置的策略要么從所有的key中隨機選擇N個（N可以配置）,要么從所有的設置了過期時間的key中選出N個鍵，然后再從這N個鍵中選出最久沒有使用的一個key進行淘汰。

2.2 Least Frequently Used(LFU)

LFU（Least Frequently Used）算法根據數據的歷史訪問頻率來淘汰數據，其核心思想是“如果數據過去被訪問多次，那么將來被訪問的頻率也更高”。LFU的每個數據塊都有一個引用計數，所有數據塊按照引用計數排序，具有相同引用計數的數據塊則按照時間排序。LFU需要記錄所有數據的訪問記錄，內存消耗較高；需要基于引用計數排序，性能消耗較高。在算法實現復雜度上，LFU要遠大于LRU。

2.2.1 LFU緩存淘汰算法實現

本節筆者以leetcode上的一道算法題為例，使用代碼實現LFU算法，幫助讀者更深入的理解LFU算法的思想。

leetcode 460: LFU緩存

請你為 最不經常使用（LFU）緩存算法設計并實現數據結構。它應該支持以下操作：get 和 put。

get(key) - 如果鍵存在于緩存中，則獲取鍵的值（總是正數），否則返回 -1。 put(key, value) - 如果鍵已存在，則變更其值；如果鍵不存在，請插入鍵值對。當緩存達到其容量時，則應該在插入新項之前，使最不經常使用的項無效。在此問題中，當存在平局（即兩個或更多個鍵具有相同使用頻率）時，應該去除最久未使用的鍵。 「項的使用次數」就是自插入該項以來對其調用 get 和 put 函數的次數之和。使用次數會在對應項被移除后置為 0 。 示例： LFUCache cache = new LFUCache( 2 /* capacity (緩存容量) */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 去除 key 2 cache.get(2); // 返回 -1 (未找到key 2) cache.get(3); // 返回 3 cache.put(4, 4); // 去除 key 1 cache.get(1); // 返回 -1 (未找到 key 1) cache.get(3); // 返回 3 cache.get(4); // 返回 4 復制代碼

上一節我們聊到LRU算法，LRU的實現是一個哈希表加上一個雙鏈表，比較簡單。而LFU則要復雜多了，需要用兩個哈希表再加上N個雙鏈表才能實現 我們先看看LFU的兩個哈希表里面都存了什么。

第一個哈希表是key-value的哈希表(以下簡稱kv哈希表)

這里的key就是輸入的key，沒什么特別的。關鍵是value，它的value不是一個簡單的value，而是一個節點對象。 節點對象Node包含了key，value，以及頻率，這個Node又會出現在第二個哈希表的value中。 至于為什么Node中又重復包含了key，因為某些情況下我們不是通過k-v哈希表拿到Node的，而是通過其他方式獲得了Node，之后需要用Node中的key去k-v哈希表中做一些操作，所以Node中包含了一些冗余信息。

第二張哈希表，頻率哈希表，這個就要復雜多了

這張哈希表中的key是頻率，也就是元素被訪問的頻率(被訪問了1次，被訪問了兩次等等)，它的value是一個雙向鏈表 剛才說的Node對象，現在又出現了，這里的Node其實是雙向鏈表中的一個節點。 第一張圖中我們介紹了Node中包含了一個冗余的key，其實它還包含了一個冗余的頻率值，因為某些情況下，我們需要通過Node中的頻率值，去頻率哈希表中做查找，所以也需要一個冗余的頻率值。

下面我們將兩個哈希表整合起來看看完整的結構:

k-v哈希表中key1指向一個Node，這個Node的頻率為1，位于頻率哈希表中key=1下面的雙鏈表中(處于第一個節點)。

根據上邊的描述就可以定義出我們要使用到的數據結構和雙鏈表的基本操作代碼(使用Go語言)：

type LFUCache struct { cache map[int]*Nodefreq map[int]*DoubleListncap, size, minFreq int}//節點nodetype Node struct {key, val, freq intprev, next *Node}//雙鏈表type DoubleList struct {tail, head *Node}//創建一個雙鏈表func createDL() *DoubleList {head, tail := &Node{}, &Node{}head.next, tail.prev = tail, headreturn &DoubleList{tail: tail,head: head,}}func (this *DoubleList) IsEmpty() bool {return this.head.next == this.tail}//將node添加為雙鏈表的第一個元素func (this *DoubleList) AddFirst(node *Node) {node.next = this.head.nextnode.prev = this.headthis.head.next.prev = nodethis.head.next = node}func (this *DoubleList) RemoveNode(node *Node) {node.next.prev = node.prevnode.prev.next = node.nextnode.next = nilnode.prev = nil}func (this *DoubleList) RemoveLast() *Node {if this.IsEmpty() {return nil}lastNode := this.tail.prevthis.RemoveNode(lastNode)return lastNode}復制代碼

下邊我們來看一下LFU算法的具體的實現吧，get操作相對簡單一些，我們就先說get操作吧。 get操作的具體邏輯大致是這樣：

• 如果key不存在則返回-1
• 如果key存在，則返回對應的value，同時:
• 將元素的訪問頻率+1
• 將元素從訪問頻率i的鏈表中移除，放到頻率i+1的鏈表中
• 如果頻率i的鏈表為空，則從頻率哈希表中移除這個鏈表

第一個很簡單就不用說了，我們看下第二點的執行過程：

假設某個元素的訪問頻率是3，現在又被訪問了一次，那么就需要將這個元素移動到頻率4的鏈表中。如果這個元素被移除后，頻率3的那個鏈表變成空了(只剩下頭結點和尾節點)就需要刪除這個鏈表，同時刪除對應的頻率(也就是刪除key=3),我們看下執行過程：

LFU中Get方法代碼實現：

func (this *LFUCache) Get(key int) int { if node, ok := this.cache[key]; ok {this.IncrFreq(node)return node.val}return -1}func(this *LFUCache) IncrFreq(node *Node) {_freq := node.freqthis.freq[_freq].RemoveNode(node)if this.minFreq == _freq && this.freq[_freq].IsEmpty() {this.minFreq++delete(this.freq, _freq)}node.freq++if this.freq[node.freq] == nil {this.freq[node.freq] = createDL()}this.freq[node.freq].AddFirst(node)}復制代碼

put操作就要復雜多了，大致包括下面幾種情況

• 如果key已經存在，修改對應的value，并將訪問頻率+1
• 將元素從訪問頻率i的鏈表中移除，放到頻率i+1的鏈表中
• 如果頻率i的鏈表為空，則從頻率哈希表中移除這個鏈表
• 如果key不存在
• 緩存超過最大容量，則先刪除訪問頻率最低的元素，再插入新元素
• 新元素的訪問頻率為1，如果頻率哈希表中不存在對應的鏈表需要創建
• 緩存沒有超過最大容量，則插入新元素
• 新元素的訪問頻率為1，如果頻率哈希表中不存在對應的鏈表需要創建

我們在代碼實現中還需要維護一個minFreq的變量，用來記錄LFU緩存中頻率最小的元素，在緩存滿的時候，可以快速定位到最小頻繁的鏈表，以達到 O(1) 時間復雜度刪除一個元素。 具體做法是:

• 更新/查找的時候，將元素頻率+1，之后如果minFreq不在頻率哈希表中了，說明頻率哈希表中已經沒有元素了，那么minFreq需要+1，否則minFreq不變。
• 插入的時候，這個簡單，因為新元素的頻率都是1，所以只需要將minFreq改為1即可。

我們重點看下緩存超過最大容量時是怎么處理的:

LFU中Put方法代碼實現：

func (this *LFUCache) Put(key int, value int) { if this.ncap == 0 {return}//節點存在 if node, ok := this.cache[key]; ok {node.val = valuethis.IncrFreq(node)} else {if this.size >= this.ncap {node := this.freq[this.minFreq].RemoveLast()delete(this.cache, node.key)this.size--}x := &Node{key: key, val: value, freq: 1}this.cache[key] = xif this.freq[1] == nil {this.freq[1] = createDL()}this.freq[1].AddFirst(x)this.minFreq = 1this.size++}}復制代碼

通過對一道LFU基本算法的分析與實現，相信讀者已經領悟到了LFU算法的思想及其復雜性。很多算法本身就是復雜的，不但要整合各種數據結構，還要根據應用場景進行分析，并不斷改進。但是算法確確實實的解決很多實際的問題，我們已經知道了緩存的重要性，但一個好的緩存策略除了要充分利用各種計算機存儲組件，良好的算法設計也是必不可少的。所以我們再來總體回顧一下本節LFU算法的實現吧：

type LFUCache struct { cache map[int]*Nodefreq map[int]*DoubleListncap, size, minFreq int}func(this *LFUCache) IncrFreq(node *Node) {_freq := node.freqthis.freq[_freq].RemoveNode(node)if this.minFreq == _freq && this.freq[_freq].IsEmpty() {this.minFreq++delete(this.freq, _freq)}node.freq++if this.freq[node.freq] == nil {this.freq[node.freq] = createDL()}this.freq[node.freq].AddFirst(node)}func Constructor(capacity int) LFUCache { return LFUCache{cache: make(map[int]*Node),freq: make(map[int]*DoubleList),ncap: capacity,}}func (this *LFUCache) Get(key int) int { if node, ok := this.cache[key]; ok {this.IncrFreq(node)return node.val}return -1}func (this *LFUCache) Put(key int, value int) { if this.ncap == 0 {return}//節點存在 if node, ok := this.cache[key]; ok {node.val = valuethis.IncrFreq(node)} else {if this.size >= this.ncap {node := this.freq[this.minFreq].RemoveLast()delete(this.cache, node.key)this.size--}x := &Node{key: key, val: value, freq: 1}this.cache[key] = xif this.freq[1] == nil {this.freq[1] = createDL()}this.freq[1].AddFirst(x)this.minFreq = 1this.size++}}//節點nodetype Node struct {key, val, freq intprev, next *Node}//雙鏈表type DoubleList struct {tail, head *Node}//創建一個雙鏈表func createDL() *DoubleList {head, tail := &Node{}, &Node{}head.next, tail.prev = tail, headreturn &DoubleList{tail: tail,head: head,}}func (this *DoubleList) IsEmpty() bool {return this.head.next == this.tail}//將node添加為雙鏈表的第一個元素func (this *DoubleList) AddFirst(node *Node) {node.next = this.head.nextnode.prev = this.headthis.head.next.prev = nodethis.head.next = node}func (this *DoubleList) RemoveNode(node *Node) {node.next.prev = node.prevnode.prev.next = node.nextnode.next = nilnode.prev = nil}func (this *DoubleList) RemoveLast() *Node {if this.IsEmpty() {return nil}lastNode := this.tail.prevthis.RemoveNode(lastNode)return lastNode}復制代碼

2.2.2 Redis LFU淘汰策略

一般情況下，LFU效率要優于LRU，且能夠避免周期性或者偶發性的操作導致緩存命中率下降的問題，在如下情況下：

~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~|~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~|~~~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~|~~~~~D~~~~~~~~~~D~~~~~~~~~D~~~~~~~~~D|復制代碼

會將數據D誤認為將來最有可能被訪問到的數據。

Redis作者曾想改進LRU算法，但發現Redis的LRU算法受制于隨機采樣數maxmemory_samples，在maxmemory_samples等于10的情況下已經很接近于理想的LRU算法性能，也就是說，LRU算法本身已經很難再進一步了。

于是，將思路回到原點，淘汰算法的本意是保留那些將來最有可能被再次訪問的數據，而LRU算法只是預測最近被訪問的數據將來最有可能被訪問到。我們可以轉變思路，采用LFU(Least Frequently Used)算法，也就是最頻繁被訪問的數據將來最有可能被訪問到。在上面的情況中，根據訪問頻繁情況，可以確定保留優先級：B>A>C=D。

在LFU算法中，可以為每個key維護一個計數器。每次key被訪問的時候，計數器增大。計數器越大，可以約等于訪問越頻繁。

上述簡單算法存在兩個問題：

• 在LRU算法中可以維護一個雙向鏈表，然后簡單的把被訪問的節點移至鏈表開頭，但在LFU中是不可行的，節點要嚴格按照計數器進行排序，新增節點或者更新節點位置時，時間復雜度可能達到O(N)。
• 只是簡單的增加計數器的方法并不完美。訪問模式是會頻繁變化的，一段時間內頻繁訪問的key一段時間之后可能會很少被訪問到，只增加計數器并不能體現這種趨勢。 第一個問題很好解決，可以借鑒LRU實現的經驗，維護一個待淘汰key的pool。第二個問題的解決辦法是，記錄key最后一個被訪問的時間，然后隨著時間推移，降低計數器。

我們前邊說過Redis對象的結構：

typedef struct redisObject { unsigned type:4; unsigned encoding:4; unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or * LFU data (least significant 8 bits frequency * and most significant 16 bits access time). */ int refcount; void *ptr;} robj;復制代碼

在LRU算法中，24 bits的lru是用來記錄LRU time的，在LFU中也可以使用這個字段，不過是分成16 bits與8 bits使用：

16 bits 8 bits +----------------+--------+ + Last decr time | LOG_C | +----------------+--------+復制代碼

高16 bits用來記錄最近一次計數器降低的時間ldt，單位是分鐘，低8 bits記錄計數器數值counter。

Redis4.0之后為maxmemory_policy淘汰策略添加了兩個LFU模式：

• volatile-lfu：對有過期時間的key采用LFU淘汰算法
• allkeys-lfu：對全部key采用LFU淘汰算法

還有2個配置可以調整LFU算法：

lfu-log-factor 10lfu-decay-time 1復制代碼

• lfu-log-factor可以調整計數器counter的增長速度，lfu-log-factor越大，counter增長的越慢。
• lfu-decay-time是一個以分鐘為單位的數值，可以調整counter的減少速度

源碼實現

在lookupKey中：

robj *lookupKey(redisDb *db, robj *key, int flags) { dictEntry *de = dictFind(db->dict,key->ptr); if (de) { robj *val = dictGetVal(de); /* Update the access time for the ageing algorithm. * Don't do it if we have a saving child, as this will trigger * a copy on write madness. */ if (server.rdb_child_pid == -1 && server.aof_child_pid == -1 && !(flags & LOOKUP_NOTOUCH)) { if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { updateLFU(val); } else { val->lru = LRU_CLOCK(); } } return val; } else { return NULL; }}復制代碼

當采用LFU策略時，updateLFU更新lru：

/* Update LFU when an object is accessed. * Firstly, decrement the counter if the decrement time is reached. * Then logarithmically increment the counter, and update the access time. */void updateLFU(robj *val) { unsigned long counter = LFUDecrAndReturn(val); counter = LFULogIncr(counter); val->lru = (LFUGetTimeInMinutes()<<8) | counter;}復制代碼

降低LFUDecrAndReturn

首先，LFUDecrAndReturn對counter進行減少操作：

/* If the object decrement time is reached decrement the LFU counter but * do not update LFU fields of the object, we update the access time * and counter in an explicit way when the object is really accessed. * And we will times halve the counter according to the times of * elapsed time than server.lfu_decay_time. * Return the object frequency counter. * * This function is used in order to scan the dataset for the best object * to fit: as we check for the candidate, we incrementally decrement the * counter of the scanned objects if needed. */unsigned long LFUDecrAndReturn(robj *o) { unsigned long ldt = o->lru >> 8; unsigned long counter = o->lru & 255; unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0; if (num_periods) counter = (num_periods > counter) ? 0 : counter - num_periods; return counter;}復制代碼

函數首先取得高16 bits的最近降低時間ldt與低8 bits的計數器counter，然后根據配置的lfu_decay_time計算應該降低多少。

LFUTimeElapsed用來計算當前時間與ldt的差值：

/* Return the current time in minutes, just taking the least significant * 16 bits. The returned time is suitable to be stored as LDT (last decrement * time) for the LFU implementation. */unsigned long LFUGetTimeInMinutes(void) { return (server.unixtime/60) & 65535;}/* Given an object last access time, compute the minimum number of minutes * that elapsed since the last access. Handle overflow (ldt greater than * the current 16 bits minutes time) considering the time as wrapping * exactly once. */unsigned long LFUTimeElapsed(unsigned long ldt) { unsigned long now = LFUGetTimeInMinutes(); if (now >= ldt) return now-ldt; return 65535-ldt+now;}復制代碼

具體是當前時間轉化成分鐘數后取低16 bits，然后計算與ldt的差值now-ldt。當ldt > now時，默認為過了一個周期(16 bits，最大65535)，取值65535-ldt+now。

然后用差值與配置lfu_decay_time相除，LFUTimeElapsed(ldt) / server.lfu_decay_time，已過去n個lfu_decay_time，則將counter減少n，counter - num_periods。

增長LFULogIncr

增長函數LFULogIncr如下：

/* Logarithmically increment a counter. The greater is the current counter value * the less likely is that it gets really implemented. Saturate it at 255. */uint8_t LFULogIncr(uint8_t counter) { if (counter == 255) return 255; double r = (double)rand()/RAND_MAX; double baseval = counter - LFU_INIT_VAL; if (baseval < 0) baseval = 0; double p = 1.0/(baseval*server.lfu_log_factor+1); if (r < p) counter++; return counter;}復制代碼

counter并不是簡單的訪問一次就+1，而是采用了一個0-1之間的p因子控制增長。counter最大值為255。取一個0-1之間的隨機數r與p比較，當r

# +--------+------------+------------+------------+------------+------------+# | factor | 100 hits | 1000 hits | 100K hits | 1M hits | 10M hits |# +--------+------------+------------+------------+------------+------------+# | 0 | 104 | 255 | 255 | 255 | 255 |# +--------+------------+------------+------------+------------+------------+# | 1 | 18 | 49 | 255 | 255 | 255 |# +--------+------------+------------+------------+------------+------------+# | 10 | 10 | 18 | 142 | 255 | 255 |# +--------+------------+------------+------------+------------+------------+# | 100 | 8 | 11 | 49 | 143 | 255 |# +--------+------------+------------+------------+------------+------------+復制代碼

可見counter增長與訪問次數呈現對數增長的趨勢，隨著訪問次數越來越大，counter增長的越來越慢。

新生key策略

另外一個問題是，當創建新對象的時候，對象的counter如果為0，很容易就會被淘汰掉，還需要為新生key設置一個初始counter，createObject:

robj *createObject(int type, void *ptr) { robj *o = zmalloc(sizeof(*o)); o->type = type; o->encoding = OBJ_ENCODING_RAW; o->ptr = ptr; o->refcount = 1; /* Set the LRU to the current lruclock (minutes resolution), or * alternatively the LFU counter. */ if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL; } else { o->lru = LRU_CLOCK(); } return o;}復制代碼

counter會被初始化為LFU_INIT_VAL，默認5。

總結一下：Redis的LFU緩存淘汰策略復用了redis對象中的24 bits lru, 不過分成了分成16 bits與8 bits使用，高16 bits用來記錄最近一次計數器降低的時間ldt，單位是分鐘，低8 bits記錄計數器數值counter。Redis對象的計數器并不是線性增長的，而是提供了lfu-log-factor配置項來控制技術器的增長速度。為了解決歷史數據影響將來數據的“緩存污染”問題，Redis對象的計數會根據lfu_decay_time配置項隨時間做調整。redis為每一個新增的key都設置了初始counter，目的是防止新增的key很容易就被淘汰掉。

2.3 先進先出算法（FIFO）

FIFO（First in First out），先進先出。在FIFO Cache設計中，核心原則就是：如果一個數據最先進入緩存中，則應該最早淘汰掉。實現方法很簡單，只要使用隊列數據結構即可實現。

因為緩存命中率比較低，FIFO緩存策略通常不會在項目中使用?？陀^唯心主義的理論：存在即合理，下邊筆者就描述一下FIFO隊列在Redis主從復制過程中的應用。

在Redis主從結構中，主節點要將數據同步給從節點，從一開始主從建立連接到數據同步一共分為三個階段：

第一階段首先建立連接，然后第二階段主節點發送rdb文件給從節點同步全量數據；我們主要看第三階段主節點反復同步增量數據給從節點的過程是什么樣的。

從節點和主節點建立連接時，主節點服務器會維護一個復制積壓緩沖區來暫存增量的同步命令；當從節點向主節點要求同步數據時，主節點根據從節點同步數據的offset將數據增量的同步給從節點，反復進行。

復制積壓緩沖區是一個先進先出(FIFO)的環形隊列，用于存儲服務端執行過的命令，每次傳播命令，master節點都會將傳播的命令記錄下來，保存在這里。

復制積壓緩沖區由兩部分組成：偏移量和字節值。字節值是redis指令字節的存儲（redis指令以一種Redis序列化文本協議的格式存儲），偏移量offset就是當前字節值在環形隊列中的偏移量。

主節點維護了每個從節點的offset，這樣每次同步數據時，主節點就知道該同步哪一部分數據給從節點了。通過這樣一個復制積壓緩沖區，Redis的主從架構實現了數據的增量同步，想要了解更多主從同步細節的讀者可以參考我的另一篇博客：Redis高可用——主從復制

2.4 FIFO、LRU、LFU緩存淘汰策略對比

本節花費了大量篇幅介紹緩存淘汰策略，我們再來從緩存命中率、實現復雜度、存儲成本、缺陷這四個方面來對這三種緩存策略做一個對比：

緩存淘汰策略

緩存命中率

實現復雜度

存儲成本

缺陷

FIFO

低

非常簡單

很低

速度很快，不過沒有什么實用價值

LRU

高

相對簡單

高

偶發性的、周期性的批量操作會導致LRU命中率急劇下降，緩存污染情況比較嚴重。

LFU

非常高

相對復雜

很高，需要很大的存儲空間

L存在歷史數據影響將來數據的“緩存污染”

Redis、Mysql的緩存設計都考慮了本節講到的緩存淘汰策略的思想，并結合自身的業務場景進行了改進實現。緩存淘汰策略沒有十全十美的，根據具體的業務和需求選擇合適緩存淘汰算法，提升緩存命中率是我們學習本節的目的。

3. 緩存安全

緩存安全是非常熱點的話題，大多數企業在的架構師在設計緩存系統時都會考慮“緩存安全”相關的問題，尤其是當服務到達一定量級之后，“緩存安全”就是一個不得不考慮的問題了。另外在面試過程中，“緩存安全”相關的問題也是熱點，因為懂得這些太重要了，每一個問題產生的原因可能是什么？有效的解決方案有哪些？怎樣避免這些問題的產生？這些都是一個合格的程序員應該知道的。

本節就結合redis緩存中間件的使用，和大家一塊談談“緩存安全”中最常見的問題。并介紹相關的解決方案和規避方法。

3.1 緩存預熱

俗話說萬事開頭難，對于應用了redis緩存中間件的系統來說也會存在這樣的問題。當系統并發很高，并采用了主從架構的時候，服務啟動就是一件很困難的事情！究其原因，系統剛啟動時，緩存中沒有數據，那么服務啟動就需要大量的訪問數據庫，并瞬間產生大量的緩存數據，主從之間吞吐量增大，數據同步頻度增加，可能服務剛啟動不久就會宕機。

解決方案也很簡單，我們最好先統計出訪問頻度比較高的熱點數據，根據統計結果將數據分類，讓redis緩存服務優先加載那些訪問頻度高的熱點數據。當然了，這個過程最好做成“預加載”，在服務啟動之前先加載了熱點數據，手工執行方案難以實現時，可以借助腳本或者CDN的方式進行。

總結來講：緩存預熱就是系統啟動前，提前將相關的緩存數據直接加載到緩存系統。避免用戶請求的時候，先查詢數據庫，然后再將數據緩存的問題，讓用戶直接查詢被預熱的緩存數據。

3.2 緩存雪崩

緩存雪崩是緩存服務中經常遇見的問題，下邊是一個緩存雪崩事故發生的大致過程：

• 系統平穩運行中，忽然數據庫連接量激增
• 應用服務器無法及時處理請求，客戶端開始大量出現408、500錯誤頁面
• 客戶反復刷新頁面嘗試獲取數據，導致服務端數據庫訪問激增，數據庫崩潰
• 數據庫崩潰以后，應用服務器也就隨之崩潰了
• 嘗試重啟服務器無效，這時候redis服務器崩潰，雪崩開始出現，redis集群開始崩潰
• 重啟數據庫無效，因為流量太高，數據庫啟動即崩潰

排查上述緩存雪崩問題出現的原因，我們就會得到這樣一個結論：

產生“緩存雪崩”的根本原因是：在一個較短的時間內，緩存中較多的key集中過期了。

我們可以使用這個結論來解釋一下上述現象發生的過程。緩存中大量的key同時過期以后，redis緩存無法命中，請求就會到達數據庫；如果并發量很大，數據庫根本無法及時處理，Redis的請求就會被積壓，并逐漸出現超時現象；數據庫隨著流量的激增崩潰了，這個時候重啟服務器是沒有意義的，因為系統的關鍵問題是緩存中無可用數據，Redis的服務器資源被占用，服務器也隨著崩潰，集群崩塌，應用服務器也會隨著客戶端的請求增加而崩潰。出現了這個局面以后，我們重啟服務器、redis和數據庫都是沒有意義的！下面緩存雪崩的簡單示意圖：

如果“緩存雪崩”問題已經發生了，應該怎樣解決呢？下邊列舉一些有效的方案：

• 頁面靜態化處理，一旦使用了頁面靜態化，客戶端的數據就不用從緩存中獲取了，這樣可以減輕緩存的壓力，缺點是數據更新不及時。
• 構建多級緩存，構建多級緩存可以給每一級的緩存提供更多的數據保障，比如在redis和mysql數據庫中間再加上一層ehcache緩存，當緩存中大量key過期時，ehcache緩存可以替mysql數據庫暫時抵擋一部分流量。構建多級緩存會增加系統的復雜性。
• 優化mysql。比如給mysql增加buffer pool,這樣當大量流量到達mysql時，mysql的吞吐量可以支撐并發，不至于馬上崩潰，也能防止雪崩現象發生。
• 監控redis的性能指標。根據分析我們知道，“雪崩”伴隨著的肯定CPU占用率急劇上升，同時客戶端請求的平均響應時間也會增大，對這些性能指標進行監控能幫助我們更早的發現問題。
• 限流、降級。這是從客戶端的角度來考慮，犧牲一部分客戶體驗，限制一些客戶端請求，能有效的降低應用服務器的壓力。待系統平穩運行后再逐漸恢復。

既然我們知道了“緩存雪崩”產生的原因是一個較短的時間內，大量的熱點key集中過期導致的，我們有必要學習一些方法來預防“緩存雪崩”的發生。最有效的方法就是根據業務數據將緩存的有效期錯峰，數據的過期時間采用固定時間 + 隨機時間戳的方式，稀釋集中到期key的數量，甚至說超熱的數據，采用永久key也是可以的。還記得我們第二部分提到的緩存淘汰策略嗎？將LRU切換為LFU淘汰策略，也是可以有效預防“緩存雪崩”的。如果你認為問題還是不太好解決，想要采用手動維護的方式也是可以的，可以定期對訪問數據做統計，給熱點數據續租過期時間也是可以的。

總結來講：緩存雪崩就是瞬間過期數據量太大，給數據庫服務器造成壓力。如果能夠有效避免過期時間集中，就可以有效防止雪崩問題的出現，再配合其它策略的一起使用，并監控服務器的運行數據并做及時的調整，基本是可以防止“緩存雪崩”情況發生的。

3.3 緩存擊穿

了解了緩存雪崩之后，我們不妨思考這樣一個問題：造成緩存雪崩的原因是大量的熱點key在集中過期，假如一個超熱的key過期，會不會也造成這種問題呢？

答案是肯定的！我們試想這樣的場景，雙11秒殺活動一臺mac電腦99元，秒殺活動一開始，幾百萬的QPS上來了，緩存數據過期了，這么大的訪問量達到了數據庫，數據庫肯定掛了！這就是我們本節要講的“緩存擊穿”。

對比“緩存雪崩”我們會發現，“緩存擊穿”和“緩存雪崩”在很多現象上來說是比較相似的，而且我們上節說到的解決“緩存雪崩”的方案拿到這里，大都是能夠適用的。和“緩存雪崩”不同的是，“緩存擊穿”發生后，redis的內存和CPU并不會有異常，也不會造成應用服務器的崩潰，也就是說“緩存擊穿”不太容易發生，造成的后果也沒有“緩存雪崩”嚴重。但是在“秒殺”場景下確確實實會存在這樣的問題。

我們還是先來說一下如何解決和預防“緩存擊穿”的問題吧。一般來講，“緩存擊穿”的問題發生前都是可以預見的，比如“秒殺”活動開始前后，肯定會有大量的客戶端請求，那么當系統中高熱的緩存key過期后，手動的加載到redis肯定是可以的。再或者活動期間我們就使用永久的key，并配置LFU的緩存淘汰策略，也是可以解決這個問題的。當然還有其它的一些解決方案，就比如作者之前曾分析過12306是怎樣承受高并發流量的，其中使用了本地緩存配合redis緩存的多級緩存方式，這種方式對于解決緩存擊穿也是有效的，只要本地緩存和redis中的緩存不要同時過期就行，大量的流量也不會壓到數據庫。

總結一下：緩存過期就是單個高熱數據過期的瞬間，數據訪問量較大，未命中redis后，流量到達了數據庫。應對策略是以預防為主，配合監控及時調整就可以，主要是在設計緩存系統時要考慮到這個問題。

3.4 緩存穿透

本小節我們來討論一下“緩存穿透”，首先“緩存穿透”和“緩存擊穿”是不一樣的，“緩存穿透”經常被黑客利用，目的是為了拖垮我們的服務器。

我們看一下發生“緩存穿透”是一種什么樣的現象：系統平穩運行時，有了突發流量，Redis緩存的命中率開始下降，內存并沒有什么異常，但是CPU開始激增，數據庫訪問也開始激增，直到數據庫崩潰。

追查問題發生的本質原因竟然是客戶端訪問的key在Redis緩存中不存在，并且數據庫中也沒有相關數據，基本上都是這樣的key，似乎有人故意而為之。遇到這種情況，開發者一定要提高警惕，很有可能是出現了黑客攻擊！

查到問題以后，我們該如何解決呢？大部分人最先想到的就是既然黑客知道我們緩存中沒有key，那么就將key緩存到Redis中，value是NULL就可以了。如果你這么想，只能說明你太年輕了，首先黑客不至于傻到使用相同的key做攻擊，再者大量的無效key緩存到redis內存中，redis就失去了緩存的意義了。當然，如果你發現這些請求都來自同一個ip或者客戶端，可以臨時的設置黑名單將攻擊流量拒之門外，但是黑客一般都會采用DDos（分布式拒絕服務攻擊），這種方法往往是無效的。

面對這樣一種困境，業內最常用的方案是使用“布隆過濾器”。雖然有一定的誤判概率，但是只要參數設置的合理，確實能夠有效地解決問題。

布隆過濾器是什么？

可以把布隆過濾器理解為一個不怎么精確的set結構，當你使用它的contains方法判斷某個對象是否存在時，它可能會誤判。但是布隆過濾器也不是特別的不精確，只要參數設置的合理，它的精確度是可以得到保障的。當布隆過濾器說某個值不存在時，這個值可能不存在；但是它只要說某個值不存在，這個值就肯定不存在。

布隆過濾器的實現原理

每個布隆過濾器對應到Redis的數據結構里邊就是一個大型的位數組和幾個不一樣的無偏hash函數（能夠把元素的hash值算的比較均勻，讓函數被hash映射到位數組中的位置比較隨機）。如果所示，f、g、h就是這樣的hash函數。

向布隆過濾器中添加key時，會使用多個hash函數對key進行hash，先算得一個整數索引值，然后對位數組長度進行取模運算得到一個位置，每個hash函數都會算得一個不同的位置，再把位數組的這幾個位置都設置為1。 向布隆過濾器中詢問key是否存在時，跟添加一樣，也會把key通過hash得到的幾個位置都算出來，看看數組中這幾個位置是否都為1，只要有一個位置為0，那么說明這個值在布隆過濾器中是不存在的。

除了布隆過濾器這種方案，筆者認為，對業務中的key進行加密也是很有必要的，因為只要業務中的key如果是有規律可循的，黑客一般是不會知道的，我們就可以通過key的判斷將黑客的攻擊流量抵擋到redis緩存服務器前邊。此外緩存數據的監控一定要做好，能夠及時地發現緩存命中率下降，就能夠越早地采取措施。

總結一下：“緩存穿透”是客戶端訪問了緩存和數據庫中都不存在的數據，大量的這種訪問會擊垮數據庫，當運維人員監控到這種情況時，一定要及時給出報警信息，根據上邊提到的措施進行有效處理。

3.5 性能指標監控

前邊幾個小節，我們在討論各種緩存隱患時，反復的強調做好監控的重要性。這里筆者單獨抽出一個小節來總結一下在平時的緩存系統業務場景中，我們應該監控哪些性能指標，有哪些命令能夠幫助我們分析問題，這些措施和技能對于保證我們的系統安全是非常有用的。

對于性能指標監控，筆者這里列出五大類，分別以表格的形式呈現。

• 性能指標：Performance

Name

Description

latency

Redis響應一個請求的時間

instantaneous_ops_per_sec

平均每秒處理請求總數

hit rate(calculated)

緩存命中率（計算出來的）

• 內存指標：Memory

Name

Description

use_memory

已使用內存

mem_fragmentation_ratio

內存碎片率

evicted_keys

由于最大內存限制移除key的數量

blocked_clients

由于BLPOP、BRPOP or BLPUSH、BRPUSH而被受阻塞的客戶端

• 基本活動指標：Basic activity

Name

Description

connected_clients

客戶端連接數

connected_slaves

Slave數量

master_last_io_seconds_ago

最近一次主從交互之后的秒數

key_space

數據庫中key值總數

• 持久性指標：Persistence

Name

Description

rdb_last_save_time

最后一次持久化保存到數據庫的時間戳

rdb_change_since_last_save

自最后一次持久化以來數據庫的更改次數

• 錯誤指標：Error

Name

Description

rejected_connections

由于達到maxclient限制而被拒絕的連接數

keyspace_misses

key值查找失敗(沒有命中)次數

master_link_down_since_seconds

主從斷開的持續時間(以秒為單位)

以上所列舉的都是服務中比較重要的指標，監控redis的這些指標有一些開源的工具，例如：Cloud Insight Redis、Prometheus、Redis-stat、Redis-faina。但是這些工具在我們比較定制化的業務中，往往不能起到太大效果，往往企業會針對自己的業務開發自己的監控服務。

Redis提供了一些命令也能幫助我們排查問題。比如showlog、monitor；此外redis還提供了benchmark指令，通過使用它我們可以得到redis的吞吐量、緩存命中率這些性能指標數據。

4.后記

這篇文章斷斷續續的整理了半個月，筆者參考了大量的資料才提煉出了以上內容。文章中很多地方確實不夠深入，也有一些空洞的理論，加上筆者本身工作經驗不是很豐富，關于mysql、redis和php，很多底層的知識也沒有研究到位，文章中難免有表達不恰當和錯誤之處，希望讀者查找出以后一定在留言區進行指正。

回過頭來看這篇文章，筆者在這里大談“緩存”確實有點大言不慚，但是都是我的心血，也就當是我的一篇學習筆記了。

涉及到“緩存”相關的系統設計和應用絕不僅僅是我提到的這些，比如：緩存數據結構的選擇和壓縮、多級緩存之間的數據同步等等，這些都沒有談到，如果將來有機會，希望能深入的學習一下這些知識，再對文章做一些補充。

原文鏈接：
https://juejin.cn/post/6844904136207499277