詳解GaussDB bufferpool緩存策略,這次徹底懂了!
摘要： 華爲雲GaussDB（for mysql）是華爲雲自主研發的最新一代雲原生數據庫，採用計算存儲分離、日誌即數據的架構設計。具備極致可靠、極致性價比、多爲擴展、完全可信等諸多特性。
一 、GaussDB（for mysql）簡介
華爲雲GaussDB（for mysql）是華爲雲自主研發的最新一代雲原生數據庫，採用計算存儲分離、日誌即數據的架構設計。通過IO卸載、日誌壓縮合並、批量處理、軟硬件垂直整合等技術，使數據庫性能方面有了大幅提升。同時存儲層採用多副本，多az部署，增強數據可靠性。具備極致可靠、極致性價比、多爲擴展、完全可信等諸多特性。
GaussDB（for mysql）採用了計算存儲分離、日誌即數據的架構，一部分計算能力下推到存儲層。存儲層需要通過consolidation不斷將寫入的日誌應用到頁面上，從而將日誌回收掉。另外SQL層從存儲層讀取頁面時，也需要將日誌回放到相應的版本從而獲得對應版本的頁面。如果每次都從磁盤讀取頁面，IO時延較大，這裏將成爲整個回放流程的瓶頸。
根據數據庫一貫的做法，我們需要一個緩存（bufferpool），把經常訪問的頁面放在緩存中，從而加快頁面讀取的速度。但是存儲層能夠分配給bufferpool的資源非常有限，我們需要根據bufferpool的使用特點設計一個高效的緩存策略。
二、一些常見的緩存淘汰算法
緩存一般從以下三個特徵進行描述：
- 命中率
返回正確結果數/請求緩存次數，命中率問題是緩存中的一個非常重要的問題，它是衡量緩存有效性的重要指標。命中率越高，表明緩存的使用率越高。
- 最大元素（或最大空間）
緩存中可以存放的最大元素的數量，一旦緩存中元素數量超過這個值（或者緩存數據所佔空間超過其最大支持空間），那麼將會觸發緩存啓動清空策略根據不同的場景合理的設置最大元素值往往可以一定程度上提高緩存的命中率，從而更有效的時候緩存。
- 淘汰（替換）策略
如上描述，緩存的存儲空間有限制，當緩存空間被用滿時，如何保證在穩定服務的同時有效提升命中率？這就由淘汰（替換）策略來處理，設計適合自身數據特徵的淘汰策略能有效提升命中率。
因此，選擇一個適合使用場景的淘汰（替換）策略非常重要，能夠大大提升緩存命中率，從而加速業務處理。
緩存的淘汰（替換）根據訪問模式可以分爲基於時間或者訪問頻率兩類，下面分別對這兩類進行詳細描述。
基於訪問時間：此類算法按各緩存項的被訪問時間來組織緩存隊列,決定替換對象，如LRU。
基於訪問頻率：此類算法用緩存項的被訪問頻率來組織緩存。如LFU、LRU-2、2Q、LIRS。
1. LRU
基本思想：如果數據最近被訪問過，那麼將來被訪問的幾率也更高
常見實現方法：
一般採用unordered_map+list來實現，訪問數據時，直接從unordered_map通過key在O(1)時間內獲取到所需數據。有新數據時，插入到鏈表的頭部；當緩存命中時，也將數據移動到鏈表頭部；當緩存滿時將鏈表尾部的數據丟棄。
命中率分析
當存在熱點數據時，LRU的效率很好，但偶發性的、週期性的批量操作會導致LRU命中率急劇下降，緩存污染情況比較嚴重。
Mysql對樸素LRU算法的改進：
由於樸素的LRU算法會存在緩存污染問題，若直接讀取到的頁放入到LRU的首部，那麼某些SQL操作可能會使緩衝池中的頁被刷新出，從而影響緩衝池的效率。常見的這類操作爲索引或數據的掃描操作。這類操作需要訪問表中的許多頁，甚至是全部的頁，而這些頁通常來說又僅在這次查詢操作中需要，並不是活躍的熱點數據。如果頁被放入LRU列表的首部，那麼非常可能將所需要的熱點數據頁從LRU列表移除，而在下一次需要讀取該頁時，InnoDB存儲引擎需要再次訪問磁盤。
解決方案：
InnoDB存儲引擎引入了另一個參數來進一步管理LRU列表，這個參數是Innodb_old_blocks_time，用於表示頁讀取到mid位置後需要等待多久纔會被加入到LRU列表的熱端。鏈表按照5:3的比例分爲young區和old區，新加入的數據放在old區，若old區的數據在LRU鏈表中存在時間超過了1秒，則將其移動到鏈表頭部，如果數據在LRU old區鏈表中存在的時間少於1秒，則保持位置不變，淘汰時優先淘汰old區的數據。這樣可以避免全表掃描對LRU鏈表的污染，全表掃描的冷數據很快會被淘汰出去。
2. LFU
基本思想：如果數據過去被訪問多次，那麼將來被訪問的頻率也更高。
注意LFU和LRU的區別，LRU的淘汰規則是基於 訪問時間 ，而LFU是基於 訪問次數常見實現方法：
與LRU類似，LFU一般也採用unordered_map+list來實現，訪問數據時，直接從unordered_map通過key在O(1)時間內獲取到所需數據。有新數據時，插入到鏈表的尾部；
當緩存命中時，增加該key的引用計數，鏈表按照引用計數排序。爲了避免節點在鏈表中頻繁移動，一般會將鏈表劃分爲多個區域或者使用多個鏈表，如果引用計數落入某個範圍，將該節點加入到相應的鏈表中，當引用計數超出閾值時將當前節點移動到上一個區間的鏈表。當緩存滿時將引用計數最小的區域的數據丟棄。
命中率分析
LFU命中率要優於LRU，且能夠避免週期性或者偶發性的操作導致緩存命中率下降的問題，但LFU需要記錄數據的歷史訪問記錄，一旦數據訪問模式改變，LFU需要更長時間來適用新的訪問模式，即LFU存在歷史數據影響將來數據的"緩存污染"問題。
3. LRU-K
LRU-K中的K代表最近使用的次數，因此LRU可以認爲是LRU-1。LRU-K的主要目的是爲了解決LRU算法"緩存污染"的問題，其核心思想是將"最近使用過1次"的判斷標準擴展爲"最近使用過K次"
常用實現如下：
數據第一次被訪問，加入到訪問歷史列表；如果數據在訪問歷史列表裏後沒有達到K次訪問，則按照LRU淘汰；當訪問歷史隊列中的數據訪問次數達到K次後，將數據索引 從歷史隊列刪除，將數據移到緩存隊列中 ，並緩存此數據，緩存隊列重新按照時間排序；緩存數據隊列中被再次訪問後，重新排序；需要淘汰數據時， 淘汰緩存隊列 中排在末尾的數據，即淘汰"倒數第K次訪問離現在最久"的數據。
命中率分析：
LRU-K具有LRU的優點，同時能夠避免LRU的缺點，實際應用中LRU-2是綜合各種因素後最優的選擇，LRU-3或者更大的K值命中率會高，但適應性差，需要大量的數據訪問才能將歷史訪問記錄清除掉。LRU-K降低了"緩存污染"帶來的問題，命中率比LRU要高。
4. 2Q
算法類似於LRU-2，不同點在於2Q將LRU-2算法中的訪問歷史隊列改爲一個FIFO隊列，即2Q有兩個緩存隊列：FIFO隊列和LRU隊列
常見實現方法：
當數據第一次訪問時，2Q算法將數據緩存在FIFO隊列裏面，當數據第二次被訪問時，則將數據從FIFO隊列移到LRU隊列裏面，兩個隊列各自按照自己的方法淘汰數據。
命中率分析：
2Q LRU-K類似，都是LRU的改進版，命中率比LRU要高，可以避免LRU污染帶來的問題。
上面介紹了4個常用的緩存淘汰算法，實現起來也不是很複雜。當然還有一些其他的算法，這裏就不再介紹了，感興趣的朋友可以查找資料學習一下。
三、 GaussDB（for mysql）bufferpool的緩存策略
GaussDB（for mysql）目前支持兩種緩存淘汰策略：LRU和LFU，這兩種淘汰算法都是改進過的。
1. 改進的LFU算法：
LFU在實現上採用unordered_map+list方式實現，訪問數據時，直接從unordered_map通過key在O(1)時間內獲取到所需數據。爲了避免數據在鏈表中頻繁移動，將鏈表按照引用計數分成多個區間，當緩存命中時，增加引用計數，若引用計數仍落在原來的區間，保持數據在鏈表中的位置不動，如果引用計數落入新的區間，將數據移動到相應位置。
爲了避免一些頻繁訪問的數據後面不再訪問，但是引用計數很大，導致不能被淘汰，因此引入“ 老化 ”策略，每隔一段時間將引用計數值衰減一下，這樣就可以將一些引用計數較大，但是當前不怎麼訪問的數據淘汰出去。
一些被淘汰出去的數據我們還會在歷史記錄裏面保留一段時間其對應的引用計數，下次該數據再次被加入緩存時，可以“ 投胎轉世 ”，可以在上次的引用計數基礎上開始計數。這樣可以更精確的反應數據被訪問的頻率。
LFU的緩存命中率較高，但是在“老化”的過程中需要對鏈表加鎖，這樣會阻塞其他地方的訪問。
2. 改進的LRU算法：
與mysql的改進LRU算法類似，也是將鏈表劃分爲hot和cold兩個區，數據第一次被加入時先放入cold區，當再次命中時移入hot區。淘汰時優先淘汰cold區的數據。同時我們引入了一個lockfree的隊列，以免在flush page時對鏈表加鎖，增強緩衝操作的併發度。
四、下一步的改進
雖然我們引入了改進版的LRU和LFU算法，但是在大數據量時，按照一些模擬分析數據，還有一定的改進空間。後面在兩個算法的基礎上進一步改進，提升緩存的命中率。
