詳解華為云GaussDB bufferpool緩存策略，這次徹底懂了!

摘要：華為云GaussDB（for mysql）是華為云自主研發(fā)的最新一代云原生數(shù)據(jù)庫，采用計算存儲分離、日志即數(shù)據(jù)的架構(gòu)設(shè)計。具備極致可靠、極致性價比、多為擴展、完全可信等諸多特性。

一、GaussDB（for mysql）簡介

華為云GaussDB（for mysql）是華為云自主研發(fā)的最新一代云原生數(shù)據(jù)庫，采用計算存儲分離、日志即數(shù)據(jù)的架構(gòu)設(shè)計。通過IO卸載、日志壓縮合并、批量處理、軟硬件垂直整合等技術(shù)，使數(shù)據(jù)庫性能方面有了大幅提升。同時存儲層采用多副本，多az部署，增強數(shù)據(jù)可靠性。具備極致可靠、極致性價比、多為擴展、完全可信等諸多特性。

GaussDB（for mysql）采用了計算存儲分離、日志即數(shù)據(jù)的架構(gòu)，一部分計算能力下推到存儲層。存儲層需要通過consolidation不斷將寫入的日志應(yīng)用到頁面上，從而將日志回收掉。另外SQL層從存儲層讀取頁面時，也需要將日志回放到相應(yīng)的版本從而獲得對應(yīng)版本的頁面。如果每次都從磁盤讀取頁面，IO時延較大，這里將成為整個回放流程的瓶頸。

根據(jù)數(shù)據(jù)庫一貫的做法，我們需要一個緩存（bufferpool），把經(jīng)常訪問的頁面放在緩存中，從而加快頁面讀取的速度。但是存儲層能夠分配給bufferpool的資源非常有限，我們需要根據(jù)bufferpool的使用特點設(shè)計一個高效的緩存策略。

二、一些常見的緩存淘汰算法

緩存一般從以下三個特征進行描述：

·命中率

返回正確結(jié)果數(shù)/請求緩存次數(shù)，命中率問題是緩存中的一個非常重要的問題，它是衡量緩存有效性的重要指標(biāo)。命中率越高，表明緩存的使用率越高。

·最大元素（或最大空間）

緩存中可以存放的最大元素的數(shù)量，一旦緩存中元素數(shù)量超過這個值（或者緩存數(shù)據(jù)所占空間超過其最大支持空間），那么將會觸發(fā)緩存啟動清空策略根據(jù)不同的場景合理的設(shè)置最大元素值往往可以一定程度上提高緩存的命中率，從而更有效的時候緩存。

·淘汰（替換）策略

如上描述，緩存的存儲空間有限制，當(dāng)緩存空間被用滿時，如何保證在穩(wěn)定服務(wù)的同時有效提升命中率？這就由淘汰（替換）策略來處理，設(shè)計適合自身數(shù)據(jù)特征的淘汰策略能有效提升命中率。

因此，選擇一個適合使用場景的淘汰（替換）策略非常重要，能夠大大提升緩存命中率，從而加速業(yè)務(wù)處理。

緩存的淘汰（替換）根據(jù)訪問模式可以分為基于時間或者訪問頻率兩類，下面分別對這兩類進行詳細描述。

基于訪問時間：此類算法按各緩存項的被訪問時間來組織緩存隊列,決定替換對象，如LRU。

基于訪問頻率：此類算法用緩存項的被訪問頻率來組織緩存。如LFU、LRU-2、2Q、LIRS。

1.LRU

基本思想：如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高

常見實現(xiàn)方法：

一般采用unordered_map+list來實現(xiàn)，訪問數(shù)據(jù)時，直接從unordered_map通過key在O(1)時間內(nèi)獲取到所需數(shù)據(jù)。有新數(shù)據(jù)時，插入到鏈表的頭部；當(dāng)緩存命中時，也將數(shù)據(jù)移動到鏈表頭部；當(dāng)緩存滿時將鏈表尾部的數(shù)據(jù)丟棄。

命中率分析

當(dāng)存在熱點數(shù)據(jù)時，LRU的效率很好，但偶發(fā)性的、周期性的批量操作會導(dǎo)致LRU命中率急劇下降，緩存污染情況比較嚴重。

Mysql對樸素LRU算法的改進：

由于樸素的LRU算法會存在緩存污染問題，若直接讀取到的頁放入到LRU的首部，那么某些SQL操作可能會使緩沖池中的頁被刷新出，從而影響緩沖池的效率。常見的這類操作為索引或數(shù)據(jù)的掃描操作。這類操作需要訪問表中的許多頁，甚至是全部的頁，而這些頁通常來說又僅在這次查詢操作中需要，并不是活躍的熱點數(shù)據(jù)。如果頁被放入LRU列表的首部，那么非?？赡軐⑺枰臒狳c數(shù)據(jù)頁從LRU列表移除，而在下一次需要讀取該頁時，InnoDB存儲引擎需要再次訪問磁盤。

解決方案：

InnoDB存儲引擎引入了另一個參數(shù)來進一步管理LRU列表，這個參數(shù)是Innodb_old_blocks_time，用于表示頁讀取到mid位置后需要等待多久才會被加入到LRU列表的熱端。鏈表按照5:3的比例分為young區(qū)和old區(qū)，新加入的數(shù)據(jù)放在old區(qū)，若old區(qū)的數(shù)據(jù)在LRU鏈表中存在時間超過了1秒，則將其移動到鏈表頭部，如果數(shù)據(jù)在LRU old區(qū)鏈表中存在的時間少于1秒，則保持位置不變，淘汰時優(yōu)先淘汰old區(qū)的數(shù)據(jù)。這樣可以避免全表掃描對LRU鏈表的污染，全表掃描的冷數(shù)據(jù)很快會被淘汰出去。

2.LFU

基本思想：如果數(shù)據(jù)過去被訪問多次，那么將來被訪問的頻率也更高。

注意LFU和LRU的區(qū)別，LRU的淘汰規(guī)則是基于訪問時間，而LFU是基于訪問次數(shù)常見實現(xiàn)方法：

與LRU類似，LFU一般也采用unordered_map+list來實現(xiàn)，訪問數(shù)據(jù)時，直接從unordered_map通過key在O(1)時間內(nèi)獲取到所需數(shù)據(jù)。有新數(shù)據(jù)時，插入到鏈表的尾部；

當(dāng)緩存命中時，增加該key的引用計數(shù)，鏈表按照引用計數(shù)排序。為了避免節(jié)點在鏈表中頻繁移動，一般會將鏈表劃分為多個區(qū)域或者使用多個鏈表，如果引用計數(shù)落入某個范圍，將該節(jié)點加入到相應(yīng)的鏈表中，當(dāng)引用計數(shù)超出閾值時將當(dāng)前節(jié)點移動到上一個區(qū)間的鏈表。當(dāng)緩存滿時將引用計數(shù)最小的區(qū)域的數(shù)據(jù)丟棄。

命中率分析

LFU命中率要優(yōu)于LRU，且能夠避免周期性或者偶發(fā)性的操作導(dǎo)致緩存命中率下降的問題，但LFU需要記錄數(shù)據(jù)的歷史訪問記錄，一旦數(shù)據(jù)訪問模式改變，LFU需要更長時間來適用新的訪問模式，即LFU存在歷史數(shù)據(jù)影響將來數(shù)據(jù)的"緩存污染"問題。

3.LRU-K

LRU-K中的K代表最近使用的次數(shù)，因此LRU可以認為是LRU-1。LRU-K的主要目的是為了解決LRU算法"緩存污染"的問題，其核心思想是將"最近使用過1次"的判斷標(biāo)準(zhǔn)擴展為"最近使用過K次"

常用實現(xiàn)如下：

數(shù)據(jù)第一次被訪問，加入到訪問歷史列表；如果數(shù)據(jù)在訪問歷史列表里后沒有達到K次訪問，則按照LRU淘汰；當(dāng)訪問歷史隊列中的數(shù)據(jù)訪問次數(shù)達到K次后，將數(shù)據(jù)索引從歷史隊列刪除，將數(shù)據(jù)移到緩存隊列中，并緩存此數(shù)據(jù)，緩存隊列重新按照時間排序；緩存數(shù)據(jù)隊列中被再次訪問后，重新排序；需要淘汰數(shù)據(jù)時，淘汰緩存隊列中排在末尾的數(shù)據(jù)，即淘汰"倒數(shù)第K次訪問離現(xiàn)在最久"的數(shù)據(jù)。

命中率分析：

LRU-K具有LRU的優(yōu)點，同時能夠避免LRU的缺點，實際應(yīng)用中LRU-2是綜合各種因素后最優(yōu)的選擇，LRU-3或者更大的K值命中率會高，但適應(yīng)性差，需要大量的數(shù)據(jù)訪問才能將歷史訪問記錄清除掉。LRU-K降低了"緩存污染"帶來的問題，命中率比LRU要高。

4.2Q

算法類似于LRU-2，不同點在于2Q將LRU-2算法中的訪問歷史隊列改為一個FIFO隊列，即2Q有兩個緩存隊列：FIFO隊列和LRU隊列

常見實現(xiàn)方法：

當(dāng)數(shù)據(jù)第一次訪問時，2Q算法將數(shù)據(jù)緩存在FIFO隊列里面，當(dāng)數(shù)據(jù)第二次被訪問時，則將數(shù)據(jù)從FIFO隊列移到LRU隊列里面，兩個隊列各自按照自己的方法淘汰數(shù)據(jù)。

命中率分析：

2Q LRU-K類似，都是LRU的改進版，命中率比LRU要高，可以避免LRU污染帶來的問題。

上面介紹了4個常用的緩存淘汰算法，實現(xiàn)起來也不是很復(fù)雜。當(dāng)然還有一些其他的算法，這里就不再介紹了，感興趣的朋友可以查找資料學(xué)習(xí)一下。

三、GaussDB（for mysql）bufferpool的緩存策略

GaussDB（for mysql）目前支持兩種緩存淘汰策略：LRU和LFU，這兩種淘汰算法都是改進過的。

1.改進的LFU算法：

LFU在實現(xiàn)上采用unordered_map+list方式實現(xiàn)，訪問數(shù)據(jù)時，直接從unordered_map通過key在O(1)時間內(nèi)獲取到所需數(shù)據(jù)。為了避免數(shù)據(jù)在鏈表中頻繁移動，將鏈表按照引用計數(shù)分成多個區(qū)間，當(dāng)緩存命中時，增加引用計數(shù)，若引用計數(shù)仍落在原來的區(qū)間，保持數(shù)據(jù)在鏈表中的位置不動，如果引用計數(shù)落入新的區(qū)間，將數(shù)據(jù)移動到相應(yīng)位置。

為了避免一些頻繁訪問的數(shù)據(jù)后面不再訪問，但是引用計數(shù)很大，導(dǎo)致不能被淘汰，因此引入“老化”策略，每隔一段時間將引用計數(shù)值衰減一下，這樣就可以將一些引用計數(shù)較大，但是當(dāng)前不怎么訪問的數(shù)據(jù)淘汰出去。

一些被淘汰出去的數(shù)據(jù)我們還會在歷史記錄里面保留一段時間其對應(yīng)的引用計數(shù)，下次該數(shù)據(jù)再次被加入緩存時，可以“投胎轉(zhuǎn)世”，可以在上次的引用計數(shù)基礎(chǔ)上開始計數(shù)。這樣可以更精確的反應(yīng)數(shù)據(jù)被訪問的頻率。

LFU的緩存命中率較高，但是在“老化”的過程中需要對鏈表加鎖，這樣會阻塞其他地方的訪問。

2.改進的LRU算法：

與mysql的改進LRU算法類似，也是將鏈表劃分為hot和cold兩個區(qū)，數(shù)據(jù)第一次被加入時先放入cold區(qū)，當(dāng)再次命中時移入hot區(qū)。淘汰時優(yōu)先淘汰cold區(qū)的數(shù)據(jù)。同時我們引入了一個lockfree的隊列，以免在flush page時對鏈表加鎖，增強緩沖操作的并發(fā)度。

四、下一步的改進

雖然我們引入了改進版的LRU和LFU算法，但是在大數(shù)據(jù)量時，按照一些模擬分析數(shù)據(jù)，還有一定的改進空間。后面在兩個算法的基礎(chǔ)上進一步改進，提升緩存的命中率。