作者：北京大學楊磊

這篇文章通過機器學習方法預測未來訪問來解決LSM-tree存儲引擎下的緩存失效問題，目前該論文已經被數據庫頂會VLDB2020接收。

問題背景

傳統的緩存替換機制，比如LRU、LFU，在應對傳統的以表為粒度的統計和訪問信息時，能夠維持較好的性能。而在LSM-tree下，這些傳統的緩存替換機制不再有效。因為后臺的操作（比如flush和compaction）會破壞原有的表粒度的統計信息，也因此破壞了根據統計信息預測訪問信息的機制，我們將這個問題稱為緩存失效問題（cache invalidation）。當出現這個問題時，LSM-tree存儲引擎會發生劇烈的性能抖動，破壞了系統運行的穩定性，同時也極大的影響了用戶的訪問體驗。下圖是在X-Engine中對緩存失效問題的測試結果。

究其原因，是因為LSM-tree 使用了能夠支持快速寫入的 copy-on-write （CoW）方式來存儲新增數據。而這種方法不可避免的需要后臺操作來幫助它合并數據。因此，我們提出了使用機器學習的方法來實現不被后臺操作所影響的高速緩存預取機制。設計思路首先我們對緩存失效問題進行形式化定義如下：

根據這個形式化定義，我們發現之所以產生cache invalidation問題，是因為存儲引擎中的compaction和flush操作產生的流Mi影響了原有的對block的統計流，從而導致傳統的緩存替換機制不再有效。因此我們提出了使用在整體數據流中不會被影響的粒度，也就是key range的粒度作為整體的統計信息采集粒度，并且根據這些統計信息在compaction和flush的過程中使用機器學習方法去預測哪些key range會被訪問，從而在他們訪問之前提前將系統中對應的數據塊預取到緩存中，避免了產生cache invalidation問題。

系統架構

我們將設計的系統方案命名為Leaper（Learned Prefetcher的縮寫），它是一個可以集成到LSM架構存儲引擎內的可插拔系統。主要由三個主要部分組成，如上圖所示。下半部分是Learner模塊，該模塊負責訓練不同時間尺度的預測模型，屬于離線部分。上半部分是Collector模塊用于產生特征化數據，以及Prefetcher模塊與存儲引擎的flush和compaction操作交互將合適的數據塊填充到緩存中。這部分屬于在線部分。架構圖中的黑色箭頭表示數據流，紅色箭頭表示控制流。接下來闡述每一塊的作用：Learner會從查詢日志中提取訪問數據，然后將數據轉換為訓練分類模型的格式。為了減少開銷，我們將連續的主鍵分組為鍵值范圍（key range）。Leaper根據不同的workload選擇合適的鍵值范圍大小，以保證良好的模型和系統性能。之后，Learner模塊會為Leaper訓練多個模型，以預測不同時間尺度下鍵值范圍的未來訪問情況。我們使用機器學習中的樹模型（GBDT）來進行分類預測以獲得最佳的預測效果。Collector以多線程的方式收集在線訪問數據。我們實現了優化的鎖機制以減少收集過程的開銷。此后，Collector將獲得不同鍵值范圍的訪問模式并最終將這些訪問模式轉換成預測模型中可以使用的特征輸入。Prefetcher首先使用Collector提供的特征輸入和Learner提供的預測模型來預測鍵值范圍的未來訪問情況。根據預測結果，Prefetcher會找出所有參與合并操作的數據塊中將要在未來被訪問的塊。這部分由交疊檢查模塊處理。最后，Prefetcher將要被訪問的塊加入緩存以及將不會被訪問的塊踢出緩存。

關鍵技術

• 鍵值選取

為了獲得分類模型的訓練數據，我們需要知道數據塊的訪問信息。但是由于磁盤上數據塊隨著合并操作而不斷變化，我們無法準確知道各個數據塊的詳細信息。因此，我們引入了鍵值范圍，該范圍由一系列連續的鍵組成，并且在數據庫運行期間不會更改。鍵值范圍主要有三個優點。第一，對減少開銷很有幫助。第二，鍵值范圍符合數據在底層結構的分布。第三，鍵值范圍非常適合range query。具體的鍵值范圍選擇使用了以下算法，具體步驟及原因可以參考論文，這里不再贅述。

• 預測模型

綜合考慮準確性，效率和可解釋性，我們使用梯度提升決策樹（GBDT）作為分類模型。它是由許多弱預測模型（決策樹）組成的組合模型。GBDT和相關實現（比如XGBoost和LightGBM）在分類預測任務中應用十分廣泛。

在模型的特征選擇上，除了使用了比較常見的讀寫特征以及時間戳特征之外，我們還使用了key range的前置key range訪問特征來刻畫在底層無法得到的業務和應用特征。舉個簡單的例子，我們在網購時經常會有組合購買的物品（乒乓球和乒乓球拍），這兩個商品所對應的key就會有很大概率一起出現在數據庫訪問中，那么我們使用相似度算法將這兩者聯系起來，通過某一個商品的訪問來預測另一個商品的訪問。

• 鎖機制

在多線程存儲引擎中，將統計信息采集到Collector中會導致寫入沖突。為了防止這種情況，需要應用鎖機制。為了能夠最大程度得減少開銷，我們主要設計了以下三種策略來優化設計。第一，使用雙重驗證鎖和延遲初始化來初始化鍵值范圍。延遲初始化避免了在第一次訪問鍵值范圍之前對其進行初始化，并且在執行延遲初始化時使用雙重驗證鎖來減少鎖開銷。第二，在統計數據過程中使用原子操作來代替互斥鎖。第三，使用采樣來進一步減少統計開銷。由于第一個策略保證了每一個鍵值范圍的第一次訪問必定會被采集到，因此采樣對于統計信息的影響不會帶入到模型預測中。下表展示了這三種優化策略的應用對于系統性能的影響。全局互斥鎖本身會對系統性能產生巨大影響，如果未記錄任何統計信息，則平均QPS約為每秒337703。當采用全局互斥鎖時，QPS將下降40.61％。但是如果采用上述策略，QPS的下降將減少到3.66%。

• 交疊檢查

在Prefetcher中進行在線推斷之后，我們需要確定應該從flush和compaction操作中預取哪些目標數據塊。由于Key Range Selection算法生成的鍵值范圍與目標塊之間沒有一一對應的關系，因此我們需要檢查目標塊是否包含熱鍵值范圍。我們提出了一個交疊檢查的算法，以檢查目標塊是否將被預取。這個算法結合了二分搜索和歸并排序的思想，無論我們在何時得到目標數據塊的信息（操作過程中或者操作結束后），都能以更小的代價得到熱的數據塊。具體算法如下：

• 回填優化

在compaction過程中，我們引入了兩階段回填來解決compaction過程中回填和剔除緩存數據塊的矛盾：為了減少Prefetcher對block cache的影響，Prefetcher會從block cache中剔除舊數據塊以節省內存。但是，如果在compaction操作結束之前需要訪問那些被剔除的塊（請求的記錄是舊版本），則會導致新的cache miss。因此我們設計了兩階段回填來解決這個問題。在剔除階段，預測compaction操作過程中的訪問，并剔除不會被訪問的塊。在第二階段，預測在compaction操作完成后的一段時間內的訪問，回填未來會被訪問的塊。通過這樣的方式既解決了緩存失效的問題，也沒有引入新的cache miss。

實驗驗證

我們分別在天貓買家庫訂單表、釘釘以及sysbench生成的zipf分布的workload下比較了我們的方法和已有方法。實驗結果表明，我們的方法相比于傳統方法可以多消除70%以上的cache invalidation，同時能消除幾乎所有的latency抖動。更多詳細的實驗比較結果請關注論文。

論文貢獻

我們形式化定義了cache invalidation問題，并且識別出了在LSM-tree問題中產生這個問題的根本原因。同時我們提出了基于機器學習的高速緩存預取策略來解決這個問題。

我們在選擇機器學習方案時，不僅考慮到模型預測的準確度，同時盡可能降低在離線訓練和在線推斷方面的開銷，使得機器學習模型能夠有效的應用在對性能要求較高的OLTP存儲引擎中。

我們將我們的方法和已有方法在多種workload上進行了比較，實驗結果表明我們的方法明顯優于已有的其他方法。

知乎號、微信公眾號“圖譜學苑”每周發布最新知識圖譜動態，專業知識圖譜論文導讀，歡迎關注投稿。

免責申明：本文全部內容均來源于網絡開放信息整理,如有侵權,請聯系刪除

總結

以上是生活随笔為你收集整理的mysql8.0其他机器访问_论文导读｜基于机器学习的高速缓存预取的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。