MySQL緩沖區(qū)自適應(yīng)管理仿真研究

作者簡介：王楠（1999－），男，碩士研究生，主要研究方向為機器學(xué)習、數(shù)據(jù)庫系統(tǒng)；吳云（1973－），男（通信作者），副教授，碩導(dǎo)，博士，主要研究方向為人工智能、大數(shù)據(jù)技術(shù)、計算機視覺、推薦系統(tǒng)（wuyun_v@126.com）．

摘 要：由于MySQL使用配置參數(shù)的方式調(diào)節(jié)線性預(yù)讀的閾值以及冷熱LRU算法的冷熱比例，導(dǎo)致緩沖區(qū)存在性能瓶頸。針對以上問題，提出一種緩沖區(qū)自適應(yīng)管理的方法，該方法通過遺憾最小化的強化在線學(xué)習技術(shù)設(shè)計了自適應(yīng)閾值調(diào)整算法以及自適應(yīng)冷熱緩存替換算法。首先，對MySQL中的預(yù)讀算法以及冷熱緩存替換算法進行深入研究，明確了預(yù)讀閾值以及冷熱比例大小對兩種算法的具體影響；其次，通過FIFO歷史隊列以及增加輔助字段的方式，設(shè)計了一套參數(shù)評估流程，實時評估當前參數(shù)是偏大或偏小；最后，設(shè)計了一種參數(shù)調(diào)整模型，該模型利用MySQL原生的預(yù)讀算法以及緩存替換算法的性能監(jiān)控指標，實現(xiàn)對參數(shù)的合理調(diào)整。在FIU數(shù)據(jù)集上進行了900組仿真實驗，實驗表明，相較于MySQL原生的基準預(yù)讀算法以及冷熱緩存算法，自適應(yīng)后的兩種算法能夠在基本不犧牲算法運行速度的基礎(chǔ)上，有效減少8%的磁盤I/O以及增加24%的緩存命中率；相對于最新的緩存替換算法，自適應(yīng)后的冷熱緩存替換算法在保證緩存命中率的前提下，將速度提升至1.6倍。

關(guān)鍵詞：自適應(yīng)；緩沖區(qū)；遺憾最小化；預(yù)讀算法；緩存替換算法

中圖分類號：TP391.9 文獻標志碼：A

文章編號：1001－3695（2023）04－031－1154－06

doi：10.19734/j.issn.1001-3695.2022.08.0436

Abstract：MySQL uses configuration parameters to adjust the linear preread threshold and the cold/hot ratio of the cold/hot LRU algorithm，resulting in a performance bottleneck in the buffer.Aiming at the above problems，this paper proposed an adaptive buffer management method，the method designed an adaptive threshold adjustment algorithm and an adaptive hot and cold cache replacement algorithm through the reinforcement online learning technology of regret minimization.First of all，this paper made an in-depth study of the preread algorithm and the hot and cold cache replacement algorithm in MySQL，and clarified the specific impact of the preread threshold and the hot and cold ratio on the two algorithms.Secondly，this paper designed a set of parameter evaluation process by FIFO history queue and added auxiliary fields to evaluate whether the current parameter was large or small in real time.Finally，this paper designed a parameter adjustment model，which used the performance monitoring indicators of MySQL’s native preread algorithm and cache replacement algorithm to achieve reasonable parameter adjustment.This paper conducted 900 simulation experiments on FIU datasets，the experimental results show that compared with MySQL’s native benchmark preread algorithm and hot and cold cache algorithm，the two adaptive algorithms can effectively reduce disk I/O by 8% and increase cache hit ratio by 24% without sacrificing algorithm speed.Compared with the latest cache replacement algorithm，the adaptive hot and cold cache replacement algorithm improves the speed to 1.6 times while ensuring the cache hit ratio.

Key words：adaptive；buffer；regret minimization；read-ahead algorithm；cache replacement algorithm

0 引言

數(shù)據(jù)庫管理系統(tǒng)（database management system，DBMS）[1]是一切數(shù)據(jù)密集型應(yīng)用的基石，它提供了一種簡單而高效的方式來幫助應(yīng)用處理大量的數(shù)據(jù)以及事務(wù)，隨著數(shù)據(jù)量的激增，傳統(tǒng)的DBMS難以為用戶提供對數(shù)據(jù)的高效檢索及訪問。

長期以來，MySQL主要將數(shù)據(jù)存儲在磁盤之中，這種介質(zhì)雖然具有容量大、價格低等特性，但其訪問速度相比內(nèi)存慢了三個數(shù)量級。MySQL內(nèi)部的緩沖區(qū)存在的意義就是充分利用高速但容量小的內(nèi)存，避免對慢速磁盤的訪問。緩沖區(qū)內(nèi)部使用兩大核心算法在有限的內(nèi)存下為應(yīng)用提供對磁盤上大量數(shù)據(jù)的高效訪問，分別是利用局部性原理提前從慢速磁盤中加載數(shù)據(jù)以減少磁盤I/O次數(shù)的預(yù)讀算法，以及當緩沖區(qū)空間耗盡時從緩存中丟棄無用數(shù)據(jù)的緩存替換算法。緩沖區(qū)內(nèi)部存在十幾個參數(shù)影響著緩沖區(qū)的性能，為保證緩沖區(qū)在各種場景下的運行性能，數(shù)據(jù)庫管理員需要根據(jù)實際工作負載經(jīng)常對參數(shù)進行調(diào)優(yōu)，且調(diào)優(yōu)后的緩沖區(qū)依然存在性能瓶頸。

自20世紀90年代以來，隨著互聯(lián)網(wǎng)的快速發(fā)展，DBMS需要管理的數(shù)據(jù)愈發(fā)多樣化，實際應(yīng)用場景下的工作負載也愈發(fā)復(fù)雜化，促使著研究人員致力于將機器學(xué)習技術(shù)[2，3]融入到DBMS，為DBMS帶來自調(diào)優(yōu)技術(shù)，現(xiàn)如今學(xué)習型數(shù)據(jù)管理已經(jīng)成為最熱門的研究方向之一。但目前對數(shù)據(jù)庫的自調(diào)優(yōu)技術(shù)[4]主要集中在學(xué)習型索引[5～7]、學(xué)習型查詢優(yōu)化[8，9]、學(xué)習型連接算法[10]、學(xué)習型排序[11]等方面，忽略了緩沖區(qū)的自適應(yīng)管理。由于磁盤與內(nèi)存之間的巨大速度差異，所以緩沖區(qū)才是制約DBMS性能的最大瓶頸。

SmartQueue[12]采用直接將整個緩沖區(qū)變成機器學(xué)習模型的思路，使用深度強化模型代替了原有的緩沖區(qū)，從實際場景中不斷學(xué)習并進化，雖然能夠有效減少大量磁盤I/O，但由于深度強化模型的延時性，使得緩沖區(qū)難以應(yīng)對實時請求。文獻[13]采用了將緩沖區(qū)中存在的傳統(tǒng)算法自適應(yīng)化的思路，直接將一些學(xué)習型算法替換緩沖區(qū)中的原有啟發(fā)式算法，使得緩沖區(qū)獲得了適應(yīng)性，這樣使得緩沖區(qū)的性能完全依賴于選擇的學(xué)習型算法。DB2[14]則通過收集緩沖區(qū)的運行數(shù)據(jù)來自調(diào)優(yōu)緩沖區(qū)，這種方式雖然最方便，但在實際應(yīng)用場景中這種粗粒度的信息很難反映出緩沖區(qū)的具體瓶頸；由于緩沖區(qū)自身的獨特應(yīng)用場景，目前自適應(yīng)緩沖區(qū)管理方法存在的問題主要是無法讓緩沖區(qū)兼具高效性、實用性以及自適應(yīng)性。

針對以上問題，本文提出一種自適應(yīng)緩沖區(qū)的方法，該方法通過遺憾最小化的強化在線學(xué)習技術(shù)自適應(yīng)緩沖區(qū)內(nèi)的預(yù)讀算法以及緩存替換算法。本文的主要貢獻如下：

a）創(chuàng)造性地針對MySQL觸發(fā)線性預(yù)讀的閾值固定，無法根據(jù)緩沖區(qū)以及工作負載情況動態(tài)調(diào)整閾值，設(shè)計了自適應(yīng)閾值調(diào)整操作，根據(jù)MySQL自身指標，合理動態(tài)調(diào)整預(yù)讀閾值，能夠顯著減少磁盤I/O。

b）針對MySQL的緩存替換算法的冷熱比例固定，無法根據(jù)緩沖區(qū)以及工作負載情況動態(tài)調(diào)整冷熱比例，設(shè)計了一種自適應(yīng)冷熱緩存替換算法，能夠在所有的工作負載下相比原緩存替換算法都表現(xiàn)出更高的緩存命中率。

1 相關(guān)工作

1.1 預(yù)讀算法

預(yù)讀算法[15]的核心是預(yù)測，當前包括Linux、Solaris等主流操作系統(tǒng)都將讀模式分為順序讀和隨機讀兩大類，并只對順序讀進行預(yù)讀，雖然這種策略相對保守，但由于順序讀具有很好的可預(yù)測性，隨機讀難以預(yù)測，導(dǎo)致該簡單的策略可以保證最高的預(yù)讀命中率。其中操作系統(tǒng)通過判斷當前讀請求與上一次的讀請求是否連續(xù)來確定是否為順序讀，依據(jù)此原則Linux實現(xiàn)了read-around和read-ahead算法。其中read-around算法適用于以mmap方式訪問的工作模式，因為它們普遍具有很強的局部性，當發(fā)生了缺頁時，系統(tǒng)將從該頁開始往后預(yù)取128 KB的頁面。

大部分情況下，由于操作系統(tǒng)內(nèi)部的啟發(fā)式預(yù)讀算法已經(jīng)很好了，導(dǎo)致大部分應(yīng)用程序中并不需要自己實現(xiàn)預(yù)讀算法，但是對于那種希望自己管理I/O的應(yīng)用程序，系統(tǒng)提供的預(yù)讀算法就缺少良好的智能性和適應(yīng)性。

1.2 緩存替換算法

早期的緩存替換算法是基于人類經(jīng)驗構(gòu)造的啟發(fā)式算法，常見的傳統(tǒng)緩存替換算法有LRU[16]、FIFO、LFU、MRU等，以及其混合模型。根據(jù)Ahmed等人[17]的研究表明，在常見的應(yīng)用場景中，LRU具有比大多數(shù)傳統(tǒng)算法更高的性能。然而LRU算法還面臨一個大問題，即請求到達模式接近于連續(xù)泛洪。在順序泛洪的情況下，這一系列的請求具有重復(fù)的連續(xù)訪問順序，例如1，2，3，4，1，2，3，4，…，這樣LRU理論上會造成100%的緩存缺失。相反，MRU（most recently used）算法能夠處理連續(xù)洪水，但是MRU在許多其他情況下命中率非常低。

MySQL結(jié)合了近因與頻率實現(xiàn)了冷熱LRU算法，該算法能夠很好地發(fā)現(xiàn)熱點頁面，并且能夠應(yīng)對順序泛洪。但是它固定了冷熱區(qū)域的比例，這使得它缺乏適應(yīng)性，難以在所有的工作負載下都能表現(xiàn)良好。

LeCaR[18]開啟了將強化學(xué)習用于解決計算系統(tǒng)中經(jīng)典問題的大門，它首次采用基于遺憾最小化的在線學(xué)習方式，利用兩種基本的替換策略LRU和LFU就能夠適應(yīng)大部分工作負載，且能夠在特定的生產(chǎn)環(huán)境中表現(xiàn)出比ARC[19]高出18倍的性能。雖然LeCaR開辟了一條使用機器學(xué)習技術(shù)解決緩存替換問題的嶄新大道，但是它也有許多顯著的局限性，例如在許多其他的生產(chǎn)級別的工作負載下，LeCaR的性能就不如ARC、LIRS[20]、DLIRS[21]這些最先進的算法。

CACHEUS[22]更是將基于遺憾最小化的技術(shù)發(fā)揮到了極致，在LeCaR的基礎(chǔ)上完全消除了原來所有需要靜態(tài)選擇的超參數(shù)，從而實現(xiàn)了極高的靈活性以及完全的自適應(yīng)性，并且在80%的工作負載下都能表現(xiàn)出最高的性能，且在其他20%的工作負載下沒有一種算法能夠一直保持最高性能。CACHEUS雖然在機器學(xué)習算法的幫助下將緩存命中率提升到了極致，但它卻無法有效應(yīng)對實際應(yīng)用場景下的實時請求。

目前現(xiàn)有的緩存替換算法[23，24]或多或少地存在著某些缺陷，如只適用于某些特定的工作負載，抑或是命中率高但算法過于復(fù)雜，無法直接應(yīng)用到實際應(yīng)用場景中。目前許多工作集中在實現(xiàn)一個能夠高效適應(yīng)所有工作負載并且滿足在線實時性的算法。

2 本文方法

傳統(tǒng)的機器學(xué)習算法基于批處理模式，必須預(yù)先一次性給定所有的訓(xùn)練數(shù)據(jù)，并通過最小化算法的損失函數(shù)得出一個最終固定的模型。基于遺憾最小化的強化在線學(xué)習更適用于流處理模式，通常假設(shè)訓(xùn)練數(shù)據(jù)持續(xù)不斷地到來，并且利用一個個的訓(xùn)練樣本不斷更新當前模型。在模型精度上，基于遺憾最小化的在線學(xué)習技術(shù)可能略微遜色于傳統(tǒng)的機器學(xué)習算法，但它在學(xué)習算法的空間復(fù)雜度、時間復(fù)雜度、實時性以及模型的靈活性方面具有完全的優(yōu)勢。

本文旨在解決MySQL緩沖區(qū)自適應(yīng)管理問題，考慮到實際工業(yè)應(yīng)用場景下工作負載的多樣性變化，以及數(shù)據(jù)庫對實時性的要求，故本文選擇了空間復(fù)雜度、時間復(fù)雜度、實時性以及模型靈活性更優(yōu)的遺憾最小化的強化在線學(xué)習技術(shù)。

2.1 自適應(yīng)預(yù)讀算法設(shè)計

MySQL緩沖區(qū)內(nèi)部存在線性預(yù)讀和隨機預(yù)讀兩種預(yù)讀算法。隨機預(yù)讀算法是在緩沖區(qū)中發(fā)現(xiàn)了同一個區(qū)（extern）的多個頁面（page），緩沖區(qū)會將這個extern中的剩余page一并讀到緩沖區(qū)中。由于隨機預(yù)讀算法給MySQL帶來了一些不必要的復(fù)雜性，同時存在性能不穩(wěn)定問題，故在MySQL 5.5中已經(jīng)將這種預(yù)讀方式廢棄，默認是OFF。MySQL默認使用線性預(yù)讀算法，并通過參數(shù)innodb_read_ahead _threshold來控制緩沖區(qū)觸發(fā)線性預(yù)讀的時機，該參數(shù)默認值為56，即如果連續(xù)訪問了同一個extern里的多個page，且訪問page數(shù)量超過了這個閾值就會觸發(fā)一次線性預(yù)讀，將下一個區(qū)中的所有數(shù)據(jù)頁（一個extern中有64個page）都提前加載到緩沖區(qū)中。這種固定參數(shù)的方式雖然對某些工作負載能夠表現(xiàn)良好，但卻無法高效應(yīng)對所有類型的工作負載。本文利用遺憾最小化機器學(xué)習方法對線性預(yù)讀算法的觸發(fā)閾值進行自適應(yīng)調(diào)整，令MySQL內(nèi)部自帶的線性預(yù)讀算法獲得自適應(yīng)性。

如圖1（a）所示，自適應(yīng)預(yù)讀算法主要包含預(yù)讀閾值評估模型與預(yù)讀閾值調(diào)整模型兩部分。預(yù)讀閾值評估模型使用兩個輔助隊列實時跟蹤并記錄預(yù)讀相關(guān)信息，并在意識到預(yù)讀閾值大小不合理的情況下及時調(diào)用預(yù)讀調(diào)整模型調(diào)整預(yù)讀閾值大小。其中預(yù)讀閾值調(diào)整模型會實時跟蹤記錄MySQL內(nèi)部與預(yù)讀算法相關(guān)的兩個性能指標。依據(jù)這些指標，以及當前預(yù)讀閾值、模型預(yù)設(shè)定的學(xué)習率與折扣率快速計算出合理的預(yù)讀閾值大小，并立即將新的閾值大小替換MySQL當前innodb_read_ahead _threshold參數(shù)的值，從而實現(xiàn)自適應(yīng)預(yù)讀算法。

如算法1所示，預(yù)讀閾值自適應(yīng)調(diào)整算法將會在預(yù)讀閾值評估流程B和C被觸發(fā)時調(diào)用，并且基于遺憾最小化的思想，使用對應(yīng)的學(xué)習率、折扣率以及調(diào)整函數(shù)及時調(diào)整預(yù)讀閾值大小，并且每次調(diào)整操作最少使得預(yù)讀閾值上下波動超過30%，最終使得磁盤I/O數(shù)最小化。

2.2 自適應(yīng)緩存替換算法設(shè)計

MySQL內(nèi)部緩存替換算法cold-hot-LRU（CH-LRU）在LRU算法的基礎(chǔ)上進行改進，將緩存分為兩部分：a）hot緩存區(qū)域包含被多次訪問，從冷數(shù)據(jù)區(qū)域（cold）晉升上來的page；b）cold緩存區(qū)域包含只被訪問一次的page以及被多次訪問但是從熱數(shù)據(jù)區(qū)域（hot）降級下來的page。冷熱分區(qū)允許該緩存替換算法支持預(yù)讀機制，即新進來的page只會進入cold區(qū)域，并且當發(fā)生緩存缺失且cold區(qū)域滿了的情況下，只會淘汰cold區(qū)域的page，這樣就不會影響hot區(qū)域的page，也能保證通過預(yù)讀進來的數(shù)據(jù)停留的時間盡可能的短，而且hot區(qū)域只會保留熱點的page，即當hot區(qū)域滿了時，會將hot區(qū)域中的page降級到cold區(qū)域。MySQL內(nèi)部通過innodb_old_blocks_pct參數(shù)控制冷熱比例大小，固定的冷熱比例在LRU友好的工作負載下會導(dǎo)致緩存命中率降低。本文利用遺憾最小化機器學(xué)習方法對CH-LRU算法的冷熱比例進行自適應(yīng)調(diào)整，令MySQL內(nèi)部自帶的冷熱緩存替換算法獲得自適應(yīng)性。

如圖1（b）所示，自適應(yīng)緩存替換算法主要包含冷熱比例評估模型以及冷熱比例調(diào)整模型兩部分。在每次請求到來的時候都會使用冷熱比例評估模型實時評估當前的冷熱比例是否合理，并且在意識到冷熱比例不合理的情況下，依據(jù)MySQL內(nèi)部與冷熱數(shù)據(jù)相關(guān)的兩個性能指標以及當前的冷熱比例、模型預(yù)設(shè)定的學(xué)習率與折扣率通過冷熱比例調(diào)整模型實時計算出合理的冷熱比例，并更新當前innodb_old_blocks_pct參數(shù)值，從而實現(xiàn)自適應(yīng)冷熱LRU算法（adapt-cold-hot LRU，ACH-LRU）。

2.2.1 冷熱比例評估流程

a）初始時使用MySQL默認的冷熱比例大小，基于遺憾最小化的思想，本文需要對page的元數(shù)據(jù)結(jié)構(gòu)增加一個用于描述該page是否為從熱數(shù)據(jù)區(qū)降級下來的標識位，此外ACH-LRU還維護了一個FIFO歷史記錄列表H，用于記錄從cold區(qū)域淘汰的page。

b）當下一個page請求到來時，如圖2所示，如果當前page在緩存中，且降級標識位為true，此時意味著hot區(qū)域太小，導(dǎo)致頁面被錯誤降級了，應(yīng)該調(diào)大熱數(shù)據(jù)區(qū)域的容量。

2.2.2 冷熱比例調(diào)整模型

為了更加有效且合理地調(diào)整冷熱區(qū)域的大小變化，自適應(yīng)CH-LRU算法用到了MySQL內(nèi)部用于監(jiān)控冷熱數(shù)據(jù)的兩個指標，一個是young（數(shù)據(jù)頁從冷到熱，這個值越大就代表著cold區(qū)域太大了），另一個是not young（數(shù)據(jù)在沒有成為熱數(shù)據(jù)情況下就被刷走的量，代表cold區(qū)域太小（累計值））。在遇到需要調(diào)整冷熱數(shù)據(jù)區(qū)域大小的時候，會依據(jù)這兩個原生指標進行合理調(diào)整，這樣可以避免增加算法的復(fù)雜性，也能讓該算法更好地融入到MySQL中。

如算法2所示，自適應(yīng)緩存替換算法會在每次頁面請求時檢查當前頁面是否在緩沖區(qū)中，以及在緩沖區(qū)的哪個區(qū)域中，并收集頁面相關(guān)的元信息，使用冷熱比例評估模型評估當前冷熱比例是否合理，并且在意識到冷熱比例不合理的情況下，基于遺憾最小化的思想，及時依據(jù)當前的學(xué)習率以及折扣率將當前innodb_old_blocks_pct參數(shù)更新為最新的冷熱比例大小，從而達到最優(yōu)的緩存命中率。

3 實驗

3.1 實驗環(huán)境

所有實驗均在AMD Ryzen5 3550H CPU @ 2.10 GHz和16 GB內(nèi)存Windows系統(tǒng)中完成，算法實現(xiàn)語言為Python。預(yù)讀算法的初始閾值設(shè)置為5，冷熱緩存替換算法的冷熱比例設(shè)置為0.37，學(xué)習率設(shè)置為0.45，折扣率設(shè)置為0.051/N（N為緩沖區(qū)容量的大小）。

3.2 數(shù)據(jù)集

本文為了評價提出的自適應(yīng)預(yù)讀算法與自適應(yīng)緩存替換算法的性能和泛化能力，在FIU數(shù)據(jù)集[25]上進行訓(xùn)練和測試，該數(shù)據(jù)集覆蓋了LRU Friendly、LFU Friendly、Scan、Churn在內(nèi)的四種不同的工作負載，能夠綜合地考量模型在復(fù)雜多變的實際工業(yè)應(yīng)用場景下的表現(xiàn)性能。

FIU數(shù)據(jù)集包含六個不同的軌跡數(shù)據(jù)，分別是homes、home1、home2、home3、home4、Web search數(shù)據(jù)集。其中homes是某研究小組在服務(wù)器上進行開發(fā)、測試、實驗、技術(shù)寫作、繪圖等操作產(chǎn)生的軌跡數(shù)據(jù)；home1～home4分別是四個不同終端開發(fā)人員的主目錄軌跡數(shù)據(jù)；Web search是使用Apache Web服務(wù)器對大約10個FIU研究項目進行Web管理的軌跡數(shù)據(jù)。

各數(shù)據(jù)集的基本數(shù)據(jù)如表1所示，其中頁面請求的數(shù)量以及復(fù)用的數(shù)量直接影響了該數(shù)據(jù)集的工作負載類型。

首先本文對數(shù)據(jù)集進行預(yù)處理，預(yù)處理的主要步驟有：

a）首先完全將數(shù)據(jù)集讀入內(nèi)存，對每一行數(shù)據(jù)按照指定邏輯進行解析，獲取每一次請求的頁面ID；

b）獲取數(shù)據(jù)集的總請求數(shù)以及頁面復(fù)用數(shù)量，從而獲取請求的工作負載類型；

c）根據(jù)頁面的復(fù)用數(shù)量，確定緩沖區(qū)的容量大小，本實驗緩沖區(qū)的大小分別設(shè)置為頁面復(fù)用數(shù)量的0.000 5、0.001、0.005、0.01、0.05、0.1。

3.3 自適應(yīng)預(yù)讀算法實驗結(jié)果分析

3.3.1 預(yù)讀閾值對I/O數(shù)量的影響分析

圖4展示了預(yù)讀算法使用不同的預(yù)讀閾值（2～56，在這六種軌跡數(shù)據(jù)下，當預(yù)讀閾值為56時將不會觸發(fā)一次預(yù)讀，此時相當于沒有預(yù)讀效果的冷熱LRU的磁盤I/O數(shù)量）在homes以及Web search數(shù)據(jù)集下的磁盤I/O數(shù)量變化。明顯可以看到在所有類型的工作負載以及緩存容量大小下，不同的預(yù)讀閾值對磁盤I/O都有相當大的影響。當預(yù)讀閾值很大時，此時一次預(yù)讀都不會觸發(fā)，可以明顯看到其磁盤I/O數(shù)量遠遠大于有觸發(fā)了預(yù)讀的磁盤I/O數(shù)量；但當預(yù)讀閾值很小時，雖然觸發(fā)了大量的預(yù)讀，但是可以看到這種預(yù)讀大多是無效預(yù)讀，不僅會增加許多磁盤I/O，甚至會將原本在緩存中的頁面刷出，導(dǎo)致大量的頁面抖動。

3.3.2 自適應(yīng)預(yù)讀算法與原生算法I/O數(shù)量的結(jié)果分析

如圖4所示，實驗結(jié)果顯示這六個不同的軌跡數(shù)據(jù)以及六種不同緩存容量大小下，預(yù)讀算法的最佳預(yù)讀閾值集中在5，而不是MySQL中默認的56。表2展示了與原始固定閾值為5的預(yù)讀算法相比，自適應(yīng)預(yù)讀算法在六種不同的數(shù)據(jù)集及六種不同的緩存容量下都能有效地減少約7%的磁盤I/O數(shù)量。

3.4 自適應(yīng)緩存替換算法實驗結(jié)果分析

3.4.1 冷熱比例對緩存命中率的影響分析

圖5展示了冷熱LRU算法使用不同的冷熱比例（0.1～1.0，其中當冷熱比例為1.0時，冷熱LRU將會退化為普通的LRU）下，在home1、Web search數(shù)據(jù)集以及六種不同的緩沖區(qū)大小下表現(xiàn)出的命中率變化趨勢。可以看出，當緩沖區(qū)容量足夠大的時候，冷熱比例對命中率的影響并不是十分顯著（最大命中率/最小命中率lt;30%），這是因為較大的緩沖區(qū)已經(jīng)提前緩存了那些會復(fù)用的頁面，此時很難看出不同緩存策略的細微差別。然而當緩沖區(qū)的容量較小時，可以很明顯地看到，不同的冷熱比例會導(dǎo)致命中率的較大波動（最大命中率/最小命中g(shù)t;200%），這種現(xiàn)象在緩沖區(qū)容量為頁面復(fù)用數(shù)量的0.000 5和0.001倍的時候最明顯。

表3展示了使用不同的冷熱比例冷熱LRU算法在六種不同的數(shù)據(jù)集上使用不同的緩沖區(qū)容量大小時的緩存命中率變化情況。可以看到，不同的工作負載以及不同的緩沖區(qū)大小都會影響最佳的冷熱比例大小，如在home2數(shù)據(jù)集上，當緩存容量為頁面復(fù)用數(shù)量的0.1倍，此時的冷熱LRU算法在冷熱比例為0.8時表現(xiàn)出最高的緩存命中率，為0.397 418（表中的加粗部分，以下同）。所以固定的冷熱比例對于MySQL是非常不合理的。

3.4.2 ACH-LRU與CH-LRU算法的命中率對比

表4展示了ACH-LRU算法在六個不同的數(shù)據(jù)集以及六種不同的緩沖區(qū)容量大小下，相比MySQL中原始CH-LRU算法的緩存命中率提升比例。可以看到，在所有的工作負載以及所有的緩沖區(qū)容量大小下，ACH-LRU算法的命中率都優(yōu)于MySQL原有的CH-LRU算法。特別是在緩沖區(qū)容量較小的情況下，ACH-LRU算法對于緩存命中率的提升更加明顯。如在home3數(shù)據(jù)集上，當緩存容量為頁面復(fù)用數(shù)量的0.000 5及0.001倍時，ACH-LRU算法分別提升了51.875 7%以及62.735 9%的命中率。甚至在Web search數(shù)據(jù)集上，當緩存容量為頁面復(fù)用數(shù)量的0.000 5倍時，ACH-LRU相比CH-LRU算法命中率提升了接近4 500倍。

3.4.3 ACH-LRU算法與最新算法的性能對比

為了證明本文方法的先進性，選取了兩個最新緩存替換算法（LeCaR、CACHEUS）與ACH-LRU進行對比，采用算法運行時間與緩存命中率作為評價指標，綜合評估算法的性能。

a）LeCaR（learn cache replacement）[18]。使用兩種基本的替換緩存策略LRU和LFU，通過遺憾學(xué)習最小化技術(shù)學(xué)習兩種策略的權(quán)重，并在每次決策時，依據(jù)權(quán)重隨機選取策略。

b）CACHEUS[22]。在LeCaR的基礎(chǔ)上完全消除了原來所有需要靜態(tài)選擇的超參數(shù)，從而實現(xiàn)了極高的靈活性以及完全的自適應(yīng)性。

表5展示了當緩沖區(qū)緩存容量為頁面復(fù)用數(shù)量的0.000 5倍時，ACH-LRU算法和LeCaR、CACHEUS在FIU數(shù)據(jù)集上的命中率指標的對比結(jié)果。為了驗證算法在命中率指標上的優(yōu)越性，故本文選擇了較小的緩沖區(qū)容量。可以看出，CACHEUS在大部分的數(shù)據(jù)集上表現(xiàn)出最高的命中率，盡管如此，ACH-LRU與CACHEUS的差距并不明顯，僅比CACHEUS低4.16%～7.32%。LeCaR除了在Web search數(shù)據(jù)集上表現(xiàn)出高于ACH-LRU 10.25%的命中率，在其他數(shù)據(jù)集上ACH-LRU相較于LeCaR緩存命中率平均提升10.15%。

圖6展示了在homes數(shù)據(jù)集下，三種算法的緩存命中率隨著緩存容量大小的變化曲線。可以看到，初始緩沖區(qū)容量較小時，ACH-LRU與CACHEUS的命中率區(qū)別不大，但LeCaR表現(xiàn)出最差的性能，隨著緩沖區(qū)的增大，這三種算法的最終緩存命中率也趨于相似。

表6展示了當緩沖區(qū)緩存容量為頁面復(fù)用數(shù)量的0.000 5倍時，三種算法在FIU數(shù)據(jù)集上的運行速度的對比結(jié)果。可以看出，ACH-LRU的運行速度是LeCaR的1.5倍，CACHEUS的1.6倍。

圖7展示了在homes數(shù)據(jù)集下，三種算法的運行時間隨著緩存容量大小的變化曲線。可以看到，ACH-LRU的運行速度不會隨著緩沖區(qū)的增加而出現(xiàn)大幅度的變化，且ACH-LRU的運行速度始終大幅度優(yōu)于LeCaR和CACHEUS。

4 結(jié)束語

本文探討了預(yù)讀閾值及冷熱比例大小對預(yù)讀算法和冷熱緩存替換算法的具體影響，并提出了自適應(yīng)閾值調(diào)整算法以及自適應(yīng)冷熱緩存替換算法。將本文算法在FIU的六個數(shù)據(jù)集上與MySQL原生的基準預(yù)讀算法以及冷熱緩存算法進行對比實驗，本文算法表現(xiàn)出了較大的性能提升。相較于最新的緩存替換算法，自適應(yīng)后的冷熱緩存替換算法在保證緩存命中率的前提下，極大地提升了算法的運行速度。在今后的研究中，將考慮更多參數(shù)的自適應(yīng)變化，如在預(yù)讀算法中，預(yù)讀一次性讀取頁面的數(shù)量大小，以及更加充分的自適應(yīng)算法。

參考文獻：

［1］Butrovich M，Lim W S，Ma L，et al.Tastes great！ Less filling！ High performance and accurate training data collection for self-driving database management systems[C]//Proc of International Conference on Management of Data.New York：ACM Press，2022：617－630.

[2]Kraska T，Alizadeh M，Beutel A，et al.SageDB：a learned database system[C]//Proc of the 9th Biennial Conference on Innovative Data Systems Research.2019.

[3]Sai T N.Machine learning for database management systems[C]//Proc of the 38th IEEE International Conference on Data Engineering.2022：3198－3201.

[4]Kanellis K，Ding C，Kroth B，et al.LlamaTune：sample-efficient DBMS configuration tuning[EB/OL].（2022－08－23）.https：//doi.org/10.48550/arxiv.2203.05128.

[5]Kraska T，Beutel A，Chi E H，et al.The case for learned index structures[C]//Proc of International Conference on Management of Data.New York：ACM Press，2018：489－504.

[6]Ding Jialin，Minhas U F，Yu Jia，et al.ALEX：an updatable adaptive learned index[C]//Proc of ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2020：969－984.

[7]Hadian A，Heinis T.Shift-table：a low-latency learned index for range queries using model correction[C]//Proc of the 24th International Conference on Extending Database Technology.2021：253－264.

[8]Wang Xiaoying，Qu Changbo，Wu Weiyuan，et al.Are we ready for learned cardinality estimation？[J].Proceeding of the VLDB Endowment，2021，14（9）：1640-1654.

[9]Negi P，Marcus R，Kipf A，et al.Flow-loss：learning cardinality estimates that matter[EB/OL].（2021－01-13）.https：//doi.org/10.48550/arxiv.2101.04964.

[10]Sabek I，Kraska T.The case for learned in-memory joins[EB/OL].（2022－03－09）.https：//doi.org/10.48550/arxiv.2111.08824.

[11]Kristo A，Vaidya K，etintemel U，et al.The case for a learned sorting algorithm[C]//Proc of ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2020：1001-1016.

[12]Zhang Chi，Marcus R，Kleiman A，et al.Buffer pool aware query scheduling via deep reinforcement learning[EB/OL].（2022－07－27）.https：//doi.org/10.48550/arxiv.2007.10568.

[13]戴鋒，王朝坤，王建民.PostgreSQL緩沖區(qū)自適應(yīng)管理研究[C]//第二十三屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（技術(shù)報告篇）.2006：94-101.（Dai Feng，Wang Chaokun，Wang Jianmin.Research on adaptive management of PostgreSQL buffer[C]// Proc of the 23rd Chinese Database Conference（Technical Report）.2006：94-101.）

[14]Goldstein J.DB2 buffer pool tuning-top down or bottom up？[C]//Proc of International Computer Measurement Group Conference.1998：51－62.

[15]胡成明，董浩，劉思良.基于 Linux 內(nèi)核的文件系統(tǒng)監(jiān)控研究[J].電子技術(shù)與軟件工程，2016（11）：194.（Hu Chengming，Dong Hao，Liu Siliang.Research on file system monitoring based on Linux kernel[J].Electronic Technique and Software Engineering，2016（11）：194.）

[16]Mattson R L，Gecsei J，Slutz D R，et al.Evaluation techniques for sto-rage hierarchies[J].IBM Systems Journal，1970，9（2）：78-117.

[17]Ahmed M，Traverso S，Giaccone P，et al.Analyzing the performance of LRU caches under non-stationary traffic patterns[EB/OL].（2013－01－21）.https：//doi.org/10.48550/arxiv.1301.4909.

[18]Vietri G，Rodriguez L V，Martinez W A，et al.Driving cache replacement with ML-based LeCaR[C]//Proc of the 10th USENIX Workshop on Hot Topics in Storage and File Systems.[S.l.]：USENIX Association，2018：491－502.

[19]Megiddo N，Modha D S.ARC：a self-tuning，low overhead replacement cache[C]//Proc of the 2nd USENIX Conference on File and Storage Technologies.[S.l.]：USENIX Association，2003：1563-1572.

[20]Jiang Song，Zhang Xiaodong.LIRS：an efficient low inter-reference recency set replacement policy to improve buffer cache performance[J].ACM SIGMETRICS Performance Evaluation Review，2002，30（1）：31－42.

[21]Li Cong.DLIRS：improving low inter-reference recency set cache replacement policy with dynamics[C]//Proc of the 11th ACM International Systems and Storage Conference.New York：ACM Press，2018：59－64.

[22]Rodriguez L V，Yusuf F，Lyons S，et al.Learning cache replacement with CACHEUS[C]//Proc of the 19th USENIX Conference on File and Storage Technologies.2021：341－354.

[23]Pratheeksha P.Machine learning-based cache replacement policies：a survey[J].International Journal of Engineering，2021，10（6）：19－22.

[24]Santana R，Lyons S，Koller R，et al.To ARC or not to ARC[C]//Proc of the 7th USENIX Workshop on Hot Topics in Storage and File Systems.2015：525－540.

[25]Huang Sai，Wei Qingsong，F(xiàn)eng Dan，et al.Improving flash-based disk cache with lazy adaptive replacement[J].ACM Trans on Storage，2016，12（2）：1－24.