2021 USENIX
GitHub - sylab/cacheus: The design and algorithms used in Cacheus are described in this USENIX FAST'21 paper and talk video: https://www.usenix.org/conference/fast21/presentation/rodriguez
Learning Cache Replacement with CACHEUS
1 intro
- 基于機器學習的 LeCaR 算法展示了:僅憑兩個簡單的策略——LRU 和 LFU——即可在某些生產級工作負載下超越 ARC。
- LeCaR 采用了一種名為“遺憾最小化”(regret minimization)的機器學習技術,用于在緩存缺失時動態選擇其中一個策略
- 論文從分析和實證兩個角度回顧 LeCaR,指出盡管其開創性地邁出了第一步,但仍存在重大局限。
- 在許多生產負載中,LeCaR 的表現不及當前先進算法如 ARC、LIRS 和 DLIRS
- 論文貢獻1:識別出與緩存相關的工作負載特征
- 四種工作負載原型:LRU 友好型、LFU 友好型、掃描型(scan)和劇烈變動型(churn)
- 論文貢獻2:提出了 CACHEUS
- 這一方案受 LeCaR 啟發而來,但克服了其一個重要缺陷:完全自適應,取消了所有靜態設置的超參數,因而具有高度的靈活性
- 論文貢獻3:設計了兩個輕量級專家策略:CR-LFU 和 SR-LRU
- CR-LFU 在 LFU 的基礎上增加了對劇烈變動的適應能力
- SR-LRU 則在 LRU 的基礎上增強了對掃描型訪問模式的抵抗能力
- 當使用這兩個專家策略時,CACHEUS 能夠在絕大多數(工作負載,緩存容量)組合中表現出與先進算法相當甚至更優的性能
2 動機
2.1?理解工作負載
分析了來自 5 個不同生產環境的數據集中的 329 條生產存儲訪問軌跡
2.1.1 工作負載原型類型(Workload Primitive Types)
定義了以下幾類工作負載原型類型(primitive types):
-
LRU 友好型(LRU-friendly):
-
其訪問序列最適合采用**最近最少使用(LRU)**緩存算法處理。
-
-
LFU 友好型(LFU-friendly):
-
其訪問序列最適合采用**最不常用(LFU)**緩存算法處理。
-
-
掃描型(Scan):
-
其訪問序列中,有一部分數據項僅被訪問一次。
-
-
劇烈變動型(Churn):
-
其訪問序列中,對某一子集的數據反復訪問,且每個項的訪問概率相等。
-
?
- 這些原型之間并不完全互斥。例如,一個 LRU 友好的工作負載也可能呈現出 churn 的特征
- 大多數被分析的工作負載中至少包含一種以上的原型類型。
- 不過,不同工作負載在這些原型的組合和占比上差異顯著
2.1.2?工作負載的組合結構(Composing Workloads)
- 現代存儲工作負載通常是上述幾類原型類型的組合
- 此外,隨著緩存容量的變化,某個工作負載的原型類型也可能隨之變化
- 例如,在緩存大小為 C1 時,某個工作負載表現為 LRU 友好型,但當緩存縮減到 C2(C2 < C1)時,其行為可能變為 churn 型
- 這種變化可能是因為原本處于工作集中的數據項,在再次被使用前就被緩存淘汰了。
2.2?緩存替換算法(Caching Algorithms)
2.2.1?自適應替換緩存 ARC(Adaptive Replacement Cache)
- 一種自適應緩存算法,旨在同時識別訪問的**“最近性(recency)”和“頻率(frequency)”**特征
- ARC 將緩存劃分為兩個 LRU 列表:T1 和 T2。
-
T1:存儲只被訪問過一次的條目。
-
T2:存儲自被加入緩存以來至少被訪問過兩次的條目。
-
-
雖然 T2 也是基于 LRU 實現的,但這限制了 ARC 對訪問頻率分布的全面捕捉,因此它在 LFU-friendly 工作負載下表現不佳。
-
對于掃描型工作負載(Scan),新項會進入 T1,進而保護 T2 中那些更頻繁使用的舊項;
-
對于劇烈變動型工作負載(Churn),ARC 無法區分那些“同等重要”的項,導致緩存被頻繁替換,性能下降【29】
2.2.2?低干擾最近性集合 LIRS(Low Interference Recency Set)
- LIRS是一種基于重用距離(reuse distance)的先進緩存算法。
- 它通過一個短的過濾列表 Q 來引導僅被訪問一次的條目,因此對于掃描型工作負載處理效果很好。
- 然而,LIRS 的自適應能力受限于 固定長度的 Q 列表:
- 當某些條目的重用距離超過 Q 長度(如超過緩存的 1%)時,LIRS 難以及時識別這些條目的重用。
- 此外,和 ARC 一樣,LIRS 無法獲得完整的訪問頻率分布,因此在 LFU-friendly 工作負載中表現受限。
2.2.3?動態 LIRS(DLIRS)
- DLIRS是對 LIRS 的改進版本,引入了動態調整機制
- 根據條目的重用距離動態分配緩存空間,使得高重用率和低重用率的條目能分別被優化處理
- 該策略在某些緩存配置中能達到與 ARC 相當的性能,尤其是在 LRU-friendly 工作負載下,同時保持了 LIRS 在掃描場景下的優勢。
- 論文的實驗證明:
-
DLIRS 的表現在不同工作負載間不夠穩定;
-
它依然繼承了 LIRS 在 LFU-friendly 情形下的缺陷。
-
2.2.4?學習型緩存替換算法 LeCaR(Learning Cache Replacement)
- 采用**強化學習(reinforcement learning)和遺憾最小化(regret minimization)**方法,在緩存缺失時動態地在 LRU 和 LFU 之間做出選擇
- LeCaR 在 小緩存容量下可在多個真實工作負載上優于 ARC
-
但 LeCaR 也存在以下問題:
-
自適應能力有限
-
運算開銷較大
-
對 churn 工作負載支持較差
-
2.3?為何需要一種新方法(Need for a New Approach)
- 現有的最先進緩存替換算法,各自只能應對某些特定類型的工作負載原型。
- 為了系統評估它們的表現,論文進行了大規模的實證研究:
- 使用來自 5 個不同生產系統的 329 條存儲 I/O 軌跡,并在 6 種緩存配置下測試算法表現,這些緩存容量從工作負載數據占用量的 0.05% 到 10% 不等。
- 為了比較在如此大規模實驗中的相對性能,對每個算法在每條工作負載下的 命中率(hit-rate) 進行排序:
-
表現最好的算法被評為 排名 1;
-
其他命中率在 相對 5% 誤差范圍內 的算法也同樣被歸為排名 1。
-
例如,如果某算法命中率為 40%,那么所有命中率在 38% 到 40% 之間的算法也算作“并列第一”
-
命中率低于 38% 的算法則被評為排名 2 或更高。
-
-
-
統計每個算法在每組工作負載中,被評為排名 1 的工作負載比例
-
-
—》在所有被評估的最先進緩存算法中,沒有任何一個算法在所有場景下始終優勝。
-
3??CACHEUS
- 鑒于工作負載原型類型具有顯著差異性,且會隨著時間在同一工作負載中動態變化,緩存替換算法需要同時具備靈活性與自適應能力。
- ——>CACHEUS 利用在線強化學習與 遺憾最小化(regret minimization) 構建了一種可應對動態變化工作負載原型類型的緩存替換算法
- 其設計在很大程度上借鑒了 LeCaR
3.1?LeCaR:回顧
- LeCaR 展示了將強化學習與遺憾最小化應用于緩存系統的可行性
-
在每次驅逐(eviction)時,從兩個基礎專家策略中動態選擇一個:
-
LRU(最近最少使用)
-
LFU(最不常用)
-
-
選擇哪個策略由對應的權重(
w_LRU
和w_LFU
)以概率方式決定-
這些權重會隨著每次驅逐的“是否正確”而動態更新:若某策略導致錯誤驅逐,將受到懲罰,其權重降低
-
-
LeCaR 使用兩個核心參數控制其在線學習過程:
-
學習率(learning rate)
-
折扣率(discount rate):控制模型停止學習的速度
-
-
3.2?對 LeCaR 的問題診斷
針對 329 條不同工作負載,在 共 17766 次模擬實驗 中測試了 LeCaR 的表現。發現:
-
在相當數量的工作負載中,有些策略明顯優于 LRU 和 LFU;
-
特別是 LRU 和 LFU 并不能有效應對 Scan 和 Churn 類型的工作負載原型。
- 此外,LeCaR 在實際應用中還存在第二個挑戰:兩個內部參數(學習率和折扣率)需手動設定
- 論文的實證結果表明:
?-
移除折扣率(discount rate) 對 LeCaR 性能幾乎沒有影響;
-
不同工作負載 對最優學習率的需求不同
-
-
甚至在同一工作負載中,隨著時間推移,其特征也會顯著變化,變化的速度(velocity)與幅度(magnitude)也不斷波動。
-
-
——>為適應這種動態性,不同時間點下應使用不同的學習率值,而不是一個靜態的全局值
- 論文的實證結果表明:
3.3?CACHEUS
- 首先,CACHEUS 完全移除了折扣率
- 其次,為了實現對學習率超參數的自適應更新,論文評估了多種策略,包括:
- 網格搜索(grid search)
- 隨機搜索(random search)
- 高斯搜索、貝葉斯優化、種群進化方法
- 梯度優化方法(gradient-based optimization)
- 最終,我們選擇了一種基于梯度的隨機爬山算法(stochastic hill climbing with random restart),因為它在實踐中表現最穩定。
4 ?抗掃描能力(Scan Resistance)
CACHEUS(LRU, LFU) 無法有效應對掃描(scan)型工作負載
- 為了理解掃描對經典緩存算法的影響,論文構造了合成工作負載,將掃描階段與可重用數據階段交錯進行。
- 每次掃描涉及 60 個頁面,穿插在其他可重用項的訪問之間
- 這時,像 LRU 這樣的經典緩存算法為了接納新的掃描項,會主動淘汰駐留緩存中的工作集項,期待將來能再次使用這些新項
- 但實際上,掃描項很快就不會再被使用了,這種替換導致緩存命中率嚴重下降。
4.1 其他緩存替換算法的抗掃描機制
ARC、LIRS 和 DLIRS 各自實現了不同的抗掃描機制:
-
ARC:限制其 T1 列表的大小(T1 用于存儲新訪問的項),以此保留 T2(頻繁訪問項)中的可重用數據。但 ARC 的掃描抵抗機制在處理 掃描后接 churn 的負載時會失效——在 churn 階段 ARC 會持續從 T1 驅逐,退化為類似 LRU 的行為。
-
LIRS:通過一個名為 Q 的棧存儲掃描項,Q 的大小固定為緩存容量的 1%,難以適應動態工作集,因此適用性受限。
-
DLIRS:對 LIRS 的 Q 區進行自適應調整,盡管理論上是自適應的,但在實際表現中反而不如 LIRS。
4.2?SR-LRU
- 論文設計了一個新的 LRU 變種,命名為 SR-LRU(Scan-Resistant LRU),它既適配 LRU 友好型負載,也具備掃描識別能力。
SR-LRU 仿照 ARC 和 LIRS 的思想,將緩存劃分為兩個區域:
-
R 區:只包含被訪問多次的項(可重用性強)
-
SR 區:存放只被訪問一次的項或老舊但頻繁訪問過的項(可能不再有用)
-
SR 區是掃描緩沖區:避免新項直接擠掉 R 區的重要數據;
-
只從 SR 區驅逐數據;
-
當發生緩存未命中、緩存已滿時,SR-LRU 會從 SR 區中驅逐 LRU 項;
-
被訪問次數多的舊項,會從 R 區降級到 SR 區,保持 R 區的“純凈度”;
-
此外,SR-LRU 還維護了一個 歷史列表 H,大小等于緩存,用于記錄最近被驅逐的項。
5?抗抖動能力(Churn Resistance)
- 對于 churn 類型的工作負載原型,如果正在訪問的項數量大于緩存容量,那么基于 LRU 的算法會導致緩存頻繁抖動(churning)——也就是說,數據不斷被插入與驅逐,幾乎沒有命中。
- 相比之下,經典的 LFU(最不常用算法)將相同頻率的所有項視為等價。但在 churn 工作負載中,所有項的訪問頻率都一樣,這些項可能按順序訪問,也可能是無序的。
- 論文發現只需對經典 LFU 做一個簡單的修改,就足以應對 churn 類型負載,并保持 LFU 原有的優勢。
- ——>提出了 抗抖動 LFU(CR-LFU),其核心在于:當存在多個項具有最低訪問頻率時,不是隨機選一個驅逐,而是選擇最“最近使用”的那一個(MRU)來驅逐。