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

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

一、GaussDB（for mysql）簡(jiǎn)介

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

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

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

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

緩存一般從以下三個(gè)特征進(jìn)行描述：

·命中率

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

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

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

·淘汰（替換）策略

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

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

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

基于訪問時(shí)間：此類算法按各緩存項(xiàng)的被訪問時(shí)間來組織緩存隊(duì)列,決定替換對(duì)象，如LRU。

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

1.LRU

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

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

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

命中率分析

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

Mysql對(duì)樸素LRU算法的改進(jìn)：

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

解決方案：

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

2.LFU

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

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

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

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

命中率分析

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

3.LRU-K

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

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

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

命中率分析：

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

4.2Q

算法類似于LRU-2，不同點(diǎn)在于2Q將LRU-2算法中的訪問歷史隊(duì)列改為一個(gè)FIFO隊(duì)列，即2Q有兩個(gè)緩存隊(duì)列：FIFO隊(duì)列和LRU隊(duì)列

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

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

命中率分析：

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

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

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

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

1.改進(jìn)的LFU算法：

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

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

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

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

2.改進(jìn)的LRU算法：

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

四、下一步的改進(jìn)

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