作者：尚卓燃（PsiACE）

澳門科技大學(xué)在讀碩士，Databend 研發(fā)工程師實(shí)習(xí)生

Apache OpenDAL(Incubating) Committer??

https://github.com/PsiACE?

論文原文：

GL-Cache: Group-level learning for efficient and high-performance caching | FAST '23

源碼 地址：

https://github.com/Thesys-lab/fast23-GLCache

論文貢獻(xiàn)：

提出 Group-level Learning ，利用多對象組的特征來適應(yīng)工作負(fù)荷和緩存大小，通過分組來積累更強(qiáng)的學(xué)習(xí)信號，學(xué)習(xí)成本均攤到對象級別。GL-Cache 不僅提供高效益的學(xué)習(xí)型緩存，還能夠保證緩存系統(tǒng)的高吞吐量。

Abstract

網(wǎng)絡(luò)應(yīng)用程序在很大程度上依賴于軟件緩存來實(shí)現(xiàn)低延遲、高吞吐的服務(wù)。為了適應(yīng)不斷變化的工作負(fù)載，近年來設(shè)計出一些學(xué)習(xí)型緩存（學(xué)習(xí)型緩存替換策略，特別是逐出策略），大致可以分為三種：對象級別學(xué)習(xí)、從分布中學(xué)習(xí)和從簡單專家（策略集）中學(xué)習(xí)。本論文認(rèn)為現(xiàn)有方法的學(xué)習(xí)粒度要么太細(xì)（對象級別），導(dǎo)致計算和存儲成本過大，要么太粗（工作負(fù)載或?qū)＜也呗约墸?，無法捕捉對象之間的差異，留下了相當(dāng)大的效益差距。（這里的效益主要是由 hits/miss ratio 進(jìn)行評估）

在本論文中，作者針對緩存設(shè)計了一種新的學(xué)習(xí)方法——組級別學(xué)習(xí)。該方法將相似的對象聚類成組，并按照組進(jìn)行學(xué)習(xí)和逐出操作。組級學(xué)習(xí)可以積累更多的信號，能夠利用更多具有自適應(yīng)權(quán)重的特征，并將成本分?jǐn)偟綄ο笊?，從而?shí)現(xiàn)高效益和高吞吐量。

作者使用 GL-Cache 在生產(chǎn)環(huán)境下演示了組級別學(xué)習(xí)，并對 118 個生產(chǎn)塊 I/O 和 CDN 緩存跟蹤進(jìn)行評估。結(jié)果顯示 GL-Cache 比最先進(jìn)設(shè)計具有更高命中率和更高吞吐量。與 LRB （對象級別）相比，GL-Cache 平均提升 228 倍吞吐量和 7% 命中率；對于 CDN 緩存跟蹤 P90 的情況下，GL-Cache 比 LRB 提供了25% 的命中率提升；與所有其他類型最好表現(xiàn)者相比較，在平均值方面 GL-Cache 提升64% 吞吐量、3% 命中率，在 P90 方面提升13% 命中率。

Background

在正式討論 GL-Cache 之前，讓我們先來看一下緩存和學(xué)習(xí)型緩存相關(guān)的一些內(nèi)容。

存儲層次結(jié)構(gòu)

上圖反映了計算機(jī)體系中的存儲層次結(jié)構(gòu)，可以看到明顯的趨勢是速度越大，容量越小。圖中的緩存位于 CPU 內(nèi)部，用于協(xié)調(diào) CPU 運(yùn)行速度和內(nèi)存讀取速度。

一般而言，緩存是位于速度相差較大的兩種存儲之間，用于協(xié)調(diào)兩者數(shù)據(jù)傳輸速度差異的結(jié)構(gòu)。無論是哪一層次的緩存都面臨一個同樣的問題：當(dāng)容量有限的緩存的空閑空間全部用完后，又有新的內(nèi)容需要添加進(jìn)緩存時，如何挑選并舍棄原有的部分內(nèi)容，從而騰出空間放入這些新的內(nèi)容。

本論文討論的是位于內(nèi)存/磁盤之間的緩存而不是芯片上的緩存。

緩存評價標(biāo)準(zhǔn)

本文主要選用以下兩個方面的評價標(biāo)準(zhǔn)。

• “效益“ - 根據(jù) hits/miss ratio 進(jìn)行評估。

• ”性能“ - 根據(jù)吞吐量進(jìn)行評估。

緩存替換算法的演進(jìn)

• “單一型”策略，典型的例子包括：LRU 和 CLOCK 。這一類靜態(tài)策略無法適應(yīng)工作負(fù)載的變化，且缺乏全面的性能表現(xiàn)。

• “適應(yīng)型”策略，典型的例子包括：ARC 和 2Q 。通常需要維護(hù)額外的元數(shù)據(jù)來適應(yīng)工作負(fù)載，同時實(shí)現(xiàn)的復(fù)雜度也會隨之提高。適應(yīng)并不總是萬無一失。

• “學(xué)習(xí)型”策略，典型的例子包括：LeCaR 和 ACME ?？梢钥醋魇怯蓹C(jī)器學(xué)習(xí)/深度學(xué)習(xí)驅(qū)動的適應(yīng)型策略，利用學(xué)習(xí)改進(jìn)決策，從而在效益上獲得提高，但往往不能保證高吞吐量。

本論文工作屬于學(xué)習(xí)型策略，但得益于設(shè)計實(shí)現(xiàn)上的一些決策，在效益和性能上都取得了比較好的收益。

進(jìn)一步討論學(xué)習(xí)型緩存

前面介紹了學(xué)習(xí)型緩存，這是一類結(jié)合機(jī)器學(xué)習(xí)來改善緩存適應(yīng)性的方法，根據(jù)本論文的分類，大致可以分成以下幾種：

• ”對象級“學(xué)習(xí)，即對每個對象的特征進(jìn)行學(xué)習(xí)。通過預(yù)測重用距離，可以實(shí)現(xiàn)類似 Belady 算法的緩存置換策略。但是，對象級學(xué)習(xí)的存儲和計算成本都比較大，以 LRB 為例，可以對超過 40 種特征進(jìn)行學(xué)習(xí)，如果在每次逐出元素時進(jìn)行采樣和預(yù)測，會極大妨害吞吐量。

• 從分布中學(xué)習(xí)，基于請求概率分布做出決策。例如，LHD 使用請求概率分布計算命中密度作為逐出的指標(biāo)，相對而言較為簡單高效，計算成本低。但是，LHD 命中密度的計算僅基于兩個特征：age 和 size ，限制了效益的上限，而跟蹤更多特征的話，計算量會呈現(xiàn)指數(shù)級增長。此外，由于 LHD 需要在每次逐出/隨機(jī)訪問時對對象進(jìn)行采樣和比較，限制了其吞吐量。

• 專家策略集，與前兩種對逐出算法的改進(jìn)不同，專家策略集旨在學(xué)習(xí)并選出最適合工作負(fù)載的緩存替換策略。典型的例子就是 LeCaR 和其后續(xù)工作 CACHEUS 。專家策略集的缺陷主要是以下兩個方面：需要維護(hù)不同緩存算法的狀態(tài)或者元數(shù)據(jù)，如果要維護(hù)多個不同算法，實(shí)現(xiàn)復(fù)雜度和計算復(fù)雜度都會提高，且其命中率強(qiáng)依賴于其所選策略；另外，專家策略集存在“延遲獎勵”，需要跟蹤對對象的訪問情況，而兩次訪問之間可能會存在相當(dāng)長的間隔，工作負(fù)載可能會在此期間發(fā)生變化。

關(guān)于是否引入 機(jī)器學(xué)習(xí) 的一些權(quán)衡

機(jī)器學(xué)習(xí)經(jīng)常用于改進(jìn)決策過程。將緩存管理和機(jī)器學(xué)習(xí)相結(jié)合的主要考慮因素是提高性能，包括如何增加吞吐量以及如何提高命中率。

為什么要使用 機(jī)器學(xué)習(xí)

• 機(jī)器學(xué)習(xí)近年來被廣泛應(yīng)用，并影響了緩存、索引的設(shè)計和實(shí)現(xiàn)。FAST ‘23 同期還有其他關(guān)于學(xué)習(xí)型索引和學(xué)習(xí)型緩存的論文被接收?；跈C(jī)器學(xué)習(xí)的算法在真實(shí)世界場景中通常具有優(yōu)勢。

• 可以利用機(jī)器學(xué)習(xí)來學(xué)習(xí)“最佳”緩存替換策略。LeCaR 可以歸到這一類中。

• 可以利用機(jī)器學(xué)習(xí)來改進(jìn)現(xiàn)有的緩存替換策略。本論文屬于此類。

為什么不使用 機(jī)器學(xué)習(xí)

• 實(shí)現(xiàn)的正確性需要進(jìn)一步評估，復(fù)雜度也會增加。

• 許多方案必須引入額外步驟，如模型的培訓(xùn)和部署等。LeCaR 引入在線學(xué)習(xí)的機(jī)制，避免了訓(xùn)練和部署問題。

• 難以同時兼顧效益和性能。本文采用 Group-level Learning 的策略，同時在效益和性能上取得優(yōu)勢。

GL-Cache: Group-level Learned Cache

前面花了大量的篇幅介紹緩存和機(jī)器學(xué)習(xí)在緩存中的應(yīng)用，接下來讓我們將目光轉(zhuǎn)向本文的主角 GL-Cache 。

GL-Cache 采用組級學(xué)習(xí)的思想，將對象分組，并按組聚集特征。

• 與其他學(xué)習(xí)型緩存相比，GL-Cache 可以利用多個特征來輔助決策，從而提高緩存效益。此外，GL-Cache 的計算成本和存儲成本由組內(nèi)的對象均攤。

• 大多數(shù)緩存工作負(fù)載遵循特定的分布，很多對象可能只訪問零星幾次，很難從單獨(dú)幾個對象中學(xué)到有價值的信息。而通過匯聚成組的形式，組內(nèi)對象數(shù)目和訪問請求得到累計，能夠形成更多有助于學(xué)習(xí)和預(yù)測的信息。

設(shè)計權(quán)衡

GL-Cache 將對象劃分成若干組，定期跟蹤每個對象組的特征，進(jìn)行采樣并形成特征快照，對每個特征快照計算效用并用于模型的訓(xùn)練，然后利用訓(xùn)練得到的模型進(jìn)行預(yù)測并作出逐出決策。

分組策略

GL-Cache 選擇了基于插入時間的分組策略，簡單且有效。主要是以下幾點(diǎn)：

• 插入時間相近的對象之間，訪問頻率和重用距離的相似程度比隨機(jī)對象之間更接近。

• 簡單普適，能夠與其他緩存設(shè)計輕松集成。

• 可以在基于段或者日志結(jié)構(gòu)的存儲上實(shí)現(xiàn)，從而利用日志結(jié)構(gòu)存儲的優(yōu)勢：低碎片化、高吞吐量、Flash 友好等。

當(dāng)然，也可以根據(jù)實(shí)際需要設(shè)計不同的分組策略，進(jìn)一步適應(yīng)工作負(fù)載。

效用計算

效用，用來度量逐出或保留對象組的后續(xù)影響。根據(jù)設(shè)計，效用較低的對象組更應(yīng)該被逐出。

對象和對象之間的比較非常容易，但是對于組與組之間，尚且缺乏有效的衡量方法。論文設(shè)計了一個新的效用函數(shù)來量化對象組的效用。

在設(shè)計效用時主要的決策如下：

• 組中主要包含的是小對象，則效用更大。

• 距離下一次請求的間隔越小，則效用更大。

• 如果組的大小為 1 ，即退化到對象級學(xué)習(xí)時，應(yīng)該具有類似 Belady’s MIN 算法的表現(xiàn)。

• 易于學(xué)習(xí)、能夠準(zhǔn)確反映效用，可以在線即時計算。

上圖第一個式子展示了對于單個對象的效用函數(shù)計算，T(o)(t) 表示下一次請求的時間，而 S(o) 表示對象的大小。而組的效用可以用對象效用的累加來計算。

特征和模型

GL-Cache 選用了 7 種特征進(jìn)行學(xué)習(xí)，并且進(jìn)行了分類。

動態(tài)特征，也就是在訪問請求時需要更新的特征：

• 請求數(shù)

• 活躍的對象數(shù)

靜態(tài)特征，不需要實(shí)時更新，只需要計算一次：

• 插入時的寫速率

• 插入時的未命中率

• 插入時的請求速率

• 平均對象大小

• 組的年齡

其中，靜態(tài)特征的前三個又被稱為 上下文特征 ，能夠反映工作負(fù)載的變化情況。比如在數(shù)據(jù)備份時，可能會觀測到寫速率、未命中率和請求速率都在增加。

模型比較簡單，利用梯度提升樹設(shè)計回歸算法作為目標(biāo)函數(shù)。感興趣的話可以閱讀 xgboost 相關(guān)論文和本論文相關(guān)源碼，這里就不進(jìn)行贅述。

逐出計劃

GL-Cache 使用訓(xùn)練得到的模型來對對象組進(jìn)行排序，并且預(yù)測其效用，并選擇效用最低的組進(jìn)行逐出。

但是，GL-Cache 的逐出并不是直接刪除對應(yīng)的組，而是采用了合并逐出（Merge Evict）的思想：

• 首先，選擇待逐出的組和與其插入時間接近的幾個相鄰組；

• 然后，根據(jù)上圖中的算法從這些組中刪除大部分對象；

• 最后，將剩下的元素合并，形成一個新的對象組。

由于選擇插入時間接近的幾個相鄰組作為合并對象，逐出后形成的新組仍然可以保證組內(nèi)對象特征的相似性。

性能評價

讓我們略過評估相關(guān)的實(shí)驗(yàn)設(shè)計和結(jié)果細(xì)節(jié)，只是簡單看一下基于組級學(xué)習(xí)的算法在潛在效益（命中率）和性能（吞吐量）象限上所處的位置。

• 對象級學(xué)習(xí)具有最高的命中率，但是由于計算繁重，所以在吞吐量上表現(xiàn)不佳。

• 專家策略集由于模型相對比較簡單，可以取得更好的吞吐量，但受到簡單專家算法（LRU、LFU 等）本身的限制，命中率較低。

• 從分布中學(xué)習(xí)相對比較平衡，處于前兩者中間的位置。

• 本論文提出的 Group-level Learning 則在潛在效益和性能上都有著優(yōu)秀的表現(xiàn)。

總結(jié)

本論文提出了一種名為 “組級學(xué)習(xí)（Group-level Learning）” 的新方法，利用機(jī)器學(xué)習(xí)提高緩存效益。組級學(xué)習(xí)利用多個對象組特征預(yù)測和清除效用最低的對象組，在適應(yīng)工作負(fù)載和緩存大小的同時，積累更強(qiáng)的信號進(jìn)行學(xué)習(xí)，并將學(xué)習(xí)成本分?jǐn)偟綄ο笊稀Ｒ虼?，它可以用極小的成本做出更好的逐出決策。作者在生產(chǎn)級緩存中構(gòu)建 GL-Cache 來展示組級學(xué)習(xí)，并在 118 個生產(chǎn)塊 I/O 和 CDN 跟蹤數(shù)據(jù)上進(jìn)行評估。與所有其他已知緩存相比，GL-Cache 實(shí)現(xiàn)了顯著更高的吞吐量，同時保持較高的命中率。因此，GL-Cache 為在生產(chǎn)系統(tǒng)中采用學(xué)習(xí)型緩存鋪平了道路。