Java架構(gòu)師聯(lián)盟

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

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

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

1.多級緩存

1.1 存儲器層次結(jié)構(gòu)

計算機(jī)使用不同的存儲技術(shù)對數(shù)據(jù)進(jìn)行訪問，時間差異很大。速度較快的技術(shù)每個字節(jié)的成本要比速度較慢的技術(shù)高，而且容量較小。CPU和主存(內(nèi)存)之間的速度差距在增大。基于這種特性，所有的現(xiàn)代計算機(jī)系統(tǒng)都使用了金字塔式的存儲器層次結(jié)構(gòu)。如下圖所示：

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

下面我們從 CPU 的角度以具體的數(shù)據(jù)來量化對比CPU、磁盤、網(wǎng)絡(luò)的速度，對計算機(jī)各個組件不同的速度差異有個更直觀的認(rèn)識。

類型

緩存內(nèi)容

緩存位置

讀取數(shù)據(jù)需要時長

對比基本單位時長

CPU寄存器

4字節(jié) & 8字節(jié)

芯片上的CPU寄存器

0.38ns

1s

L1高速緩存

64字節(jié)塊

芯片上的L1高速緩存

0.5ns

1.3s

L2高速緩存

64字節(jié)塊

芯片上的L2高速緩存

7ns

18.2s

L3高速緩存

64字節(jié)塊

芯片上的L3高速緩存

35ns

91s

內(nèi)存

4KB頁

主存

100ns

4分鐘

固態(tài)硬盤SSD

磁盤扇區(qū)

磁盤控制器

150us

4.5天

網(wǎng)絡(luò)磁盤(NFS本地掛載)

部分文件

本地磁盤

1.5ms

一個半月

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

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

1.2 局部性原理

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

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

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

Mysql數(shù)據(jù)庫Innodb引擎的設(shè)計就很好的考慮了局部性原理。

Innodb引擎以頁的形式組織數(shù)據(jù)，頁的默認(rèn)大小是16KB,存放用戶數(shù)據(jù)記錄的頁叫“數(shù)據(jù)頁”，為了實現(xiàn)數(shù)據(jù)更快的查找，InnoDB使用B+樹的結(jié)構(gòu)組織存放數(shù)據(jù)，最下層的葉子節(jié)點存放“數(shù)據(jù)頁”，在“數(shù)據(jù)頁”的上層抽出相應(yīng)的“目錄頁”，最終形成的基本結(jié)構(gòu)如下圖所示：

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

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

1.3 Cpu 高速緩存

本節(jié)我們來聊一聊Cpu 高速緩存，Cpu 高速緩存是影響程序性能的一個關(guān)鍵因素。

1.3.1 什么是Cpu 高速緩存?

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

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

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

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

1.3.3 Cpu 高速緩存架構(gòu)

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

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

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

1.3.4 PHP7數(shù)組的設(shè)計

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

我們先來總結(jié)一下PHP數(shù)組的特性：

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

PHP中數(shù)組使用hashTable實現(xiàn)，我們先來了解一下什么是hashTable。

hashTable是一種通過某種hash函數(shù)將特定的key映射到特定value的一種數(shù)據(jù)結(jié)構(gòu)，它維護(hù)著鍵和值的一一對應(yīng)關(guān)系，并且可以快速的根據(jù)鍵找到值(o(1)). 一般HashTable的示意圖如下:

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

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

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

了解php5數(shù)組的實現(xiàn)原理之后，我們發(fā)現(xiàn)其中影響性能的兩個關(guān)鍵點：

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

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

PHP7中數(shù)組是如何解決hash沖突的？

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

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

更多關(guān)于PHP5和PHP7數(shù)組的設(shè)計細(xì)節(jié)，推薦大家研究這篇文章：【PHP7源碼學(xué)習(xí)】系列之?dāng)?shù)組實現(xiàn)

1.4 瀏覽器的多級緩存機(jī)制

舉一個多級緩存的應(yīng)用案例：瀏覽器對我們生活的影響是不言而喻的，現(xiàn)代的瀏覽器已經(jīng)不同往昔了，快速的信息加載，順暢的用戶交互，這一切都得益于網(wǎng)絡(luò)技術(shù)的普及、H5標(biāo)準(zhǔn)特性的推廣應(yīng)用，當(dāng)然還有一個重要因素，那就是瀏覽器的緩存策略。本節(jié)我們就來簡單介紹一下瀏覽器的多級緩存機(jī)制。

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

瀏覽器有四種緩存級別，它們各自都有優(yōu)先級。

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

當(dāng)依次查找緩存且都沒有命中的時候，才會去請求網(wǎng)絡(luò)。

1.4.1 Service Worker

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

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

當(dāng) Service Worker 沒有命中緩存的時候，我們需要去調(diào)用 fetch 函數(shù)獲取數(shù)據(jù)。也就是說，如果我們沒有在 Service Worker 命中緩存的話，會根據(jù)緩存查找優(yōu)先級去查找數(shù)據(jù)。但是不管我們是從 Memory Cache 中還是從網(wǎng)絡(luò)請求中獲取的數(shù)據(jù)，瀏覽器都會顯示我們是從 Service Worker 中獲取的內(nèi)容。

1.4.2 Memory Cache

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

當(dāng)我們訪問過頁面以后，再次刷新頁面，可以發(fā)現(xiàn)很多數(shù)據(jù)都來自于內(nèi)存緩存

內(nèi)存緩存中有一塊重要的緩存資源是preloader相關(guān)指令（例如）下載的資源。眾所周知preloader的相關(guān)指令已經(jīng)是頁面優(yōu)化的常見手段之一，它可以一邊解析js/css文件，一邊網(wǎng)絡(luò)請求下一個資源。

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

為什么瀏覽器數(shù)據(jù)不都存放在內(nèi)存中？

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

1.4.3 Disk Cache

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

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

瀏覽器會把哪些文件丟進(jìn)內(nèi)存中？哪些丟進(jìn)硬盤中？

關(guān)于這點，網(wǎng)上說法不一，不過有些觀點比較靠得住：對于大文件來說，大概率是不存儲在內(nèi)存中的，另外如果當(dāng)前系統(tǒng)內(nèi)存使用率高的話，文件優(yōu)先存儲進(jìn)硬盤。

1.4.4 Push Cache

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

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

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

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

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

2. 緩存淘汰策略

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

本節(jié)將介紹業(yè)務(wù)中最常用的三種緩存淘汰算法:

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

筆者會結(jié)合Redis、Mysql中緩存淘汰的具體實現(xiàn)機(jī)制來幫助讀者學(xué)習(xí)到，Mysql和Redis的開發(fā)者是怎樣結(jié)合各自的業(yè)務(wù)場景，對已有的緩存算法進(jìn)行改進(jìn)來滿足業(yè)務(wù)需求的。

2.1 Least Recently Used（LRU）

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

2.1.1 LRU緩存淘汰算法實現(xiàn)

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

leetcode 146: LRU緩存機(jī)制

運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu)，設(shè)計和實現(xiàn)一個 LRU (最近最少使用) 緩存機(jī)制。它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 。

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

示例：

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 復(fù)制代碼

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

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

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

代碼如下：

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}}復(fù)制代碼

這樣就初始化了一個基本的數(shù)據(jù)結(jié)構(gòu),大概是這樣：

接下來我們?yōu)镹ode節(jié)點添加一些必要的操作方法，用于完成接下來的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)}復(fù)制代碼

因為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 }}復(fù)制代碼

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

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

處理完畢，附上Put函數(shù)完整代碼。

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 }}復(fù)制代碼

至此，我們就完成了一個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 }}復(fù)制代碼

2.1.2 Mysql緩沖池LRU算法

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

select * from table_a;復(fù)制代碼

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

Mysql的緩沖池

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

Mysql數(shù)據(jù)庫Buffer Pool結(jié)構(gòu)：

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

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

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

理解以下幾個關(guān)鍵點是比較重要的：

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

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

2.1.3 Redis近似LRU實現(xiàn)

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

在Redis中有一個參數(shù)，叫做 “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復(fù)制代碼

上面我們說過了，近似LRU是用隨機(jī)抽樣的方式來實現(xiàn)一個近似的LRU效果。這個參數(shù)其實就是作者提供了一種方式，可以讓我們?nèi)藶楦深A(yù)樣本數(shù)大小，將其設(shè)的越大，就越接近真實LRU的效果，當(dāng)然也就意味著越耗內(nèi)存。（初始值為5是作者默認(rèn)的最佳）

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

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

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

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

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

2.2 Least Frequently Used(LFU)

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

2.2.1 LFU緩存淘汰算法實現(xiàn)

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

leetcode 460: LFU緩存

請你為 最不經(jīng)常使用（LFU）緩存算法設(shè)計并實現(xiàn)數(shù)據(jù)結(jié)構(gòu)。它應(yīng)該支持以下操作：get 和 put。

get(key) - 如果鍵存在于緩存中，則獲取鍵的值（總是正數(shù)），否則返回 -1。 put(key, value) - 如果鍵已存在，則變更其值；如果鍵不存在，請插入鍵值對。當(dāng)緩存達(dá)到其容量時，則應(yīng)該在插入新項之前，使最不經(jīng)常使用的項無效。在此問題中，當(dāng)存在平局（即兩個或更多個鍵具有相同使用頻率）時，應(yīng)該去除最久未使用的鍵。 「項的使用次數(shù)」就是自插入該項以來對其調(diào)用 get 和 put 函數(shù)的次數(shù)之和。使用次數(shù)會在對應(yīng)項被移除后置為 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 復(fù)制代碼

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

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

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

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

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

下面我們將兩個哈希表整合起來看看完整的結(jié)構(gòu):

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

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

type LFUCache struct { cache map[int]*Nodefreq map[int]*DoubleListncap, size, minFreq int}//節(jié)點nodetype Node struct {key, val, freq intprev, next *Node}//雙鏈表type DoubleList struct {tail, head *Node}//創(chuàng)建一個雙鏈表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}復(fù)制代碼

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

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

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

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

LFU中Get方法代碼實現(xiàn)：

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)}復(fù)制代碼

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

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

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

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

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

LFU中Put方法代碼實現(xiàn)：

func (this *LFUCache) Put(key int, value int) { if this.ncap == 0 {return}//節(jié)點存在 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++}}復(fù)制代碼

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

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}//節(jié)點存在 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++}}//節(jié)點nodetype Node struct {key, val, freq intprev, next *Node}//雙鏈表type DoubleList struct {tail, head *Node}//創(chuàng)建一個雙鏈表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}復(fù)制代碼

2.2.2 Redis LFU淘汰策略

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

~~~~~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|復(fù)制代碼

會將數(shù)據(jù)D誤認(rèn)為將來最有可能被訪問到的數(shù)據(jù)。

Redis作者曾想改進(jìn)LRU算法，但發(fā)現(xiàn)Redis的LRU算法受制于隨機(jī)采樣數(shù)maxmemory_samples，在maxmemory_samples等于10的情況下已經(jīng)很接近于理想的LRU算法性能，也就是說，LRU算法本身已經(jīng)很難再進(jìn)一步了。

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

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

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

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

我們前邊說過Redis對象的結(jié)構(gòu)：

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;復(fù)制代碼

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

16 bits 8 bits +----------------+--------+ + Last decr time | LOG_C | +----------------+--------+復(fù)制代碼

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

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

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

還有2個配置可以調(diào)整LFU算法：

lfu-log-factor 10lfu-decay-time 1復(fù)制代碼

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

源碼實現(xiàn)

在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; }}復(fù)制代碼

當(dāng)采用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;}復(fù)制代碼

降低LFUDecrAndReturn

首先，LFUDecrAndReturn對counter進(jìn)行減少操作：

/* 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;}復(fù)制代碼

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

LFUTimeElapsed用來計算當(dāng)前時間與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;}復(fù)制代碼

具體是當(dāng)前時間轉(zhuǎn)化成分鐘數(shù)后取低16 bits，然后計算與ldt的差值now-ldt。當(dāng)ldt > now時，默認(rèn)為過了一個周期(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

增長函數(shù)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;}復(fù)制代碼

counter并不是簡單的訪問一次就+1，而是采用了一個0-1之間的p因子控制增長。counter最大值為255。取一個0-1之間的隨機(jī)數(shù)r與p比較，當(dāng)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 |# +--------+------------+------------+------------+------------+------------+復(fù)制代碼

可見counter增長與訪問次數(shù)呈現(xiàn)對數(shù)增長的趨勢，隨著訪問次數(shù)越來越大，counter增長的越來越慢。

新生key策略

另外一個問題是，當(dāng)創(chuàng)建新對象的時候，對象的counter如果為0，很容易就會被淘汰掉，還需要為新生key設(shè)置一個初始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;}復(fù)制代碼

counter會被初始化為LFU_INIT_VAL，默認(rèn)5。

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

2.3 先進(jìn)先出算法（FIFO）

FIFO（First in First out），先進(jìn)先出。在FIFO Cache設(shè)計中，核心原則就是：如果一個數(shù)據(jù)最先進(jìn)入緩存中，則應(yīng)該最早淘汰掉。實現(xiàn)方法很簡單，只要使用隊列數(shù)據(jù)結(jié)構(gòu)即可實現(xiàn)。

因為緩存命中率比較低，F(xiàn)IFO緩存策略通常不會在項目中使用。客觀唯心主義的理論：存在即合理，下邊筆者就描述一下FIFO隊列在Redis主從復(fù)制過程中的應(yīng)用。

在Redis主從結(jié)構(gòu)中，主節(jié)點要將數(shù)據(jù)同步給從節(jié)點，從一開始主從建立連接到數(shù)據(jù)同步一共分為三個階段：

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

從節(jié)點和主節(jié)點建立連接時，主節(jié)點服務(wù)器會維護(hù)一個復(fù)制積壓緩沖區(qū)來暫存增量的同步命令；當(dāng)從節(jié)點向主節(jié)點要求同步數(shù)據(jù)時，主節(jié)點根據(jù)從節(jié)點同步數(shù)據(jù)的offset將數(shù)據(jù)增量的同步給從節(jié)點，反復(fù)進(jìn)行。

復(fù)制積壓緩沖區(qū)是一個先進(jìn)先出(FIFO)的環(huán)形隊列，用于存儲服務(wù)端執(zhí)行過的命令，每次傳播命令，master節(jié)點都會將傳播的命令記錄下來，保存在這里。

復(fù)制積壓緩沖區(qū)由兩部分組成：偏移量和字節(jié)值。字節(jié)值是redis指令字節(jié)的存儲（redis指令以一種Redis序列化文本協(xié)議的格式存儲），偏移量offset就是當(dāng)前字節(jié)值在環(huán)形隊列中的偏移量。

主節(jié)點維護(hù)了每個從節(jié)點的offset，這樣每次同步數(shù)據(jù)時，主節(jié)點就知道該同步哪一部分?jǐn)?shù)據(jù)給從節(jié)點了。通過這樣一個復(fù)制積壓緩沖區(qū)，Redis的主從架構(gòu)實現(xiàn)了數(shù)據(jù)的增量同步，想要了解更多主從同步細(xì)節(jié)的讀者可以參考我的另一篇博客：Redis高可用——主從復(fù)制

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

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

緩存淘汰策略

緩存命中率

實現(xiàn)復(fù)雜度

存儲成本

缺陷

FIFO

低

非常簡單

很低

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

LRU

高

相對簡單

高

偶發(fā)性的、周期性的批量操作會導(dǎo)致LRU命中率急劇下降，緩存污染情況比較嚴(yán)重。

LFU

非常高

相對復(fù)雜

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

L存在歷史數(shù)據(jù)影響將來數(shù)據(jù)的“緩存污染”

Redis、Mysql的緩存設(shè)計都考慮了本節(jié)講到的緩存淘汰策略的思想，并結(jié)合自身的業(yè)務(wù)場景進(jìn)行了改進(jìn)實現(xiàn)。緩存淘汰策略沒有十全十美的，根據(jù)具體的業(yè)務(wù)和需求選擇合適緩存淘汰算法，提升緩存命中率是我們學(xué)習(xí)本節(jié)的目的。

3. 緩存安全

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

本節(jié)就結(jié)合redis緩存中間件的使用，和大家一塊談?wù)劇熬彺姘踩敝凶畛Ｒ姷膯栴}。并介紹相關(guān)的解決方案和規(guī)避方法。

3.1 緩存預(yù)熱

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

解決方案也很簡單，我們最好先統(tǒng)計出訪問頻度比較高的熱點數(shù)據(jù)，根據(jù)統(tǒng)計結(jié)果將數(shù)據(jù)分類，讓redis緩存服務(wù)優(yōu)先加載那些訪問頻度高的熱點數(shù)據(jù)。當(dāng)然了，這個過程最好做成“預(yù)加載”，在服務(wù)啟動之前先加載了熱點數(shù)據(jù)，手工執(zhí)行方案難以實現(xiàn)時，可以借助腳本或者CDN的方式進(jìn)行。

總結(jié)來講：緩存預(yù)熱就是系統(tǒng)啟動前，提前將相關(guān)的緩存數(shù)據(jù)直接加載到緩存系統(tǒng)。避免用戶請求的時候，先查詢數(shù)據(jù)庫，然后再將數(shù)據(jù)緩存的問題，讓用戶直接查詢被預(yù)熱的緩存數(shù)據(jù)。

3.2 緩存雪崩

緩存雪崩是緩存服務(wù)中經(jīng)常遇見的問題，下邊是一個緩存雪崩事故發(fā)生的大致過程：

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

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

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

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

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

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

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

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

3.3 緩存擊穿

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

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

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

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

總結(jié)一下：緩存過期就是單個高熱數(shù)據(jù)過期的瞬間，數(shù)據(jù)訪問量較大，未命中redis后，流量到達(dá)了數(shù)據(jù)庫。應(yīng)對策略是以預(yù)防為主，配合監(jiān)控及時調(diào)整就可以，主要是在設(shè)計緩存系統(tǒng)時要考慮到這個問題。

3.4 緩存穿透

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

我們看一下發(fā)生“緩存穿透”是一種什么樣的現(xiàn)象：系統(tǒng)平穩(wěn)運(yùn)行時，有了突發(fā)流量，Redis緩存的命中率開始下降，內(nèi)存并沒有什么異常，但是CPU開始激增，數(shù)據(jù)庫訪問也開始激增，直到數(shù)據(jù)庫崩潰。

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

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

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

布隆過濾器是什么？

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

布隆過濾器的實現(xiàn)原理

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

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

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

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

3.5 性能指標(biāo)監(jiān)控

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

對于性能指標(biāo)監(jiān)控，筆者這里列出五大類，分別以表格的形式呈現(xiàn)。

• 性能指標(biāo)：Performance

Name

Description

latency

Redis響應(yīng)一個請求的時間

instantaneous_ops_per_sec

平均每秒處理請求總數(shù)

hit rate(calculated)

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

• 內(nèi)存指標(biāo)：Memory

Name

Description

use_memory

已使用內(nèi)存

mem_fragmentation_ratio

內(nèi)存碎片率

evicted_keys

由于最大內(nèi)存限制移除key的數(shù)量

blocked_clients

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

• 基本活動指標(biāo)：Basic activity

Name

Description

connected_clients

客戶端連接數(shù)

connected_slaves

Slave數(shù)量

master_last_io_seconds_ago

最近一次主從交互之后的秒數(shù)

key_space

數(shù)據(jù)庫中key值總數(shù)

• 持久性指標(biāo)：Persistence

Name

Description

rdb_last_save_time

最后一次持久化保存到數(shù)據(jù)庫的時間戳

rdb_change_since_last_save

自最后一次持久化以來數(shù)據(jù)庫的更改次數(shù)

• 錯誤指標(biāo)：Error

Name

Description

rejected_connections

由于達(dá)到maxclient限制而被拒絕的連接數(shù)

keyspace_misses

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

master_link_down_since_seconds

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

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

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

4.后記

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

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

涉及到“緩存”相關(guān)的系統(tǒng)設(shè)計和應(yīng)用絕不僅僅是我提到的這些，比如：緩存數(shù)據(jù)結(jié)構(gòu)的選擇和壓縮、多級緩存之間的數(shù)據(jù)同步等等，這些都沒有談到，如果將來有機(jī)會，希望能深入的學(xué)習(xí)一下這些知識，再對文章做一些補(bǔ)充。

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