論文筆記:Learning Cache Replacement with CACHEUS

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_LRUw_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 的思想,將緩存劃分為兩個區域:

  1. R 區:只包含被訪問多次的項(可重用性強)

  2. 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)來驅逐

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/diannao/91229.shtml
繁體地址,請注明出處:http://hk.pswp.cn/diannao/91229.shtml
英文地址,請注明出處:http://en.pswp.cn/diannao/91229.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

極致cms多語言建站|設置主站默認語言與設置后臺固定語言為中文

小記 很長時間沒有建站了,最近有需求所以又回爐了&#xff0c;使用的極致cms 極致cms幫助文檔 | 極致CMS幫助文檔 由于很長時間沒做&#xff0c;又遇到了之前碰到的兩個問題&#xff0c;憑借經驗和記憶還是處理掉了 1.當網站前臺使用?len或?lzh來切換語言時&#xff0c;管…

Linux Vim 編輯器詳解:從入門到進階(含圖示+插件推薦)

前言在 Linux 的世界中&#xff0c;Vim 是一款被無數開發者喜愛和追捧的強大文本編輯器。如果你厭倦了鼠標點來點去&#xff0c;不妨試試 Vim —— 一款專注于高效鍵盤操作的“終極利器”。本文將帶你全面了解 Vim 的基本概念、模式切換、常用命令、窗口管理&#xff0c;并附上…

web前端渡一大師課 01 事件循環

一. 瀏覽器的進程模型 1.何為進程?程序運行需要有它自己專屬的內存空間,可以把這塊內存空間簡單理解為進程 每個應用至少有一個進程,進程之間相互獨立,即使要通信,也需要雙方同意 2.何為線程?有了進程后,就可以運行程序的代碼了,運行代碼的"人",稱之為"線程&…

linux網絡存儲——freeNAS的安裝配置

一、前言 freeNAS 是一款基于 FreeBSD 的開源網絡存儲操作系統&#xff0c;支持文件共享&#xff08;如 SMB/CIFS、NFS、AFP&#xff09;、數據備份、虛擬化存儲等功能。同時FreeNAS開源優勢明顯&#xff0c;代碼開放可自主定制&#xff0c;能滿足多樣需求。支持多種協議…

深度學習圖像分類數據集—七種樹葉識別分類

該數據集為圖像分類數據集&#xff0c;適用于ResNet、VGG等卷積神經網絡&#xff0c;SENet、CBAM等注意力機制相關算法&#xff0c;Vision Transformer等Transformer相關算法。 數據集信息介紹&#xff1a;七種樹葉識別分類&#xff1a;[冬青葉, 楊樹葉, 柳葉, 梧桐葉, 石楠葉,…

c++圖形題練習程序

一.練習題背景 這題是作者再一家公司實習的時候&#xff0c;實習期間的一個考核題目&#xff0c;感覺還是比較有價值的。希望能給還在努力的學弟學妹們一些啟發。 題目大致就是要求用繼承和多態來實現圓、三角形和長方形的面積和周長求解。這步的大致思路是這樣的&#xff0c;你…

【論文閱讀 | PR 2024 |ITFuse:一種用于紅外與可見光圖像融合的交互式 Transformer】

論文閱讀 | PR 2024 |ITFuse&#xff1a;一種用于紅外與可見光圖像融合的交互式 Transformer1.摘要&&引言2.方法2.1 問題表述2.2 框架概述2.3 特征交互模塊2.3.1 共同特征提取分支&#xff08;IcI_{c}Ic? 分支&#xff09;2.3.2 獨特特征提取分支&#xff08;I1I_{1}I…

【Qt】 設計模式

在Qt應用程序開發中&#xff0c;結合數據庫操作、通信、界面邏輯和顯示等功能&#xff0c;以下是常用的設計模式及其典型應用場景&#xff1a; 一、MVC/MVVM&#xff08;模型-視圖-控制器/視圖模型&#xff09; 作用&#xff1a;分離數據&#xff08;模型&#xff09;、界面&am…

【HarmonyOS】ArkUI-X 跨平臺框架入門詳解(一)

【HarmonyOS】ArkUI-X 跨平臺框架入門詳解&#xff08;一&#xff09; 一、前言 1、ArkUI-X框架是什么&#xff1f; ArkUI-X是在ArkUI開發框架的基礎上&#xff0c;進行擴展。支持多個OS平臺&#xff0c;目前支持OpenHarmony、HarmonyOS、Android、 iOS。2、ArkUI-X目前的能力現…

開發者進化論:駕馭AI,開啟軟件工程新紀元

導語&#xff1a;人工智能&#xff08;AI&#xff09;的浪潮&#xff0c;特別是以大型語言模型&#xff08;LLM&#xff09;為代表的生成式AI&#xff0c;正以前所未有的力量&#xff0c;深刻地重塑著軟件開發的傳統疆域。我們正處在一個關鍵的轉折點——產業的重心正從模型的“…

智慧水務平臺,智慧水務,惠及民生,提升水務管理效率與服務質量

平升電子智慧水務平臺支持海量物聯網數據接入實現供水全流程信息化&#xff0c;深度邏輯運算自動控制實現供水調度智慧化&#xff0c;融入管網地理信息系統實現測點數據時空化&#xff0c;數字孿生實現水廠各工藝環節運行情況可視化&#xff0c;多角度統計分析實現水務運營管理…

【Unity基礎】Unity中元素的層級排序

在Unity中&#xff0c;控制元素的層級排序&#xff08;渲染順序&#xff09;是確保場景正確顯示的關鍵。以下是常見的層級排序方式及其適用場景&#xff1a;1. 通過GameObject的層級順序&#xff08;Sorting Layer/Order in Layer&#xff09; 適用對象&#xff1a;2D精靈&…

梁的振動特征函數分析2

問題7&#xff1a;左端固定、右端自由梁的振動分析 考慮梁的振動方程&#xff1a; uttKuxxxx0,0<x<l,K>0 u_{tt} K u_{xxxx} 0, \quad 0 < x < l, \quad K > 0 utt?Kuxxxx?0,0<x<l,K>0 邊界條件&#xff1a; 左端固定&#xff08;位移和斜率為零…

AI問答-Token:在人工智能領域,Token 是模型處理文本的核心單元 / 最小可處理片段

一、在人工智能領域&#xff0c;Token 是模型處理文本的核心單元&#xff0c;可理解為文本的“最小可處理片段”二、表格理解類別詳細說明基本定義Token 是模型處理文本的最小語義或語法單位&#xff0c;可以是單詞、子詞、字符、標點符號或特殊符號。例如&#xff1a;- 單詞級…

讀取ubuntu的磁盤分區表與超級塊

1.讀取磁盤分區表sudo fdisk -l /dev/sda2.計算偏移量分區起始偏移 4096 512 2097152 字節 超級塊位置 2097152 1024 2098176字節3.快速驗證&#xff08;直接檢查魔數 53 &#xff09;# 檢查偏移 2,098,176 處是否有 EXT4 魔數 sudo dd if/dev/sda bs1 count2 skip$((209…

科技馴服烈日狂沙:中東沙漠農場的光儲革命

作者 | 小葳 阿布扎比郊外的午后&#xff0c;沙漠灼熱、干旱難耐。 然而一座農場內&#xff0c;景象截然不同&#xff1a;蔬菜生機盎然&#xff0c;果實掛滿枝頭。農戶輕點手機&#xff0c;遠程調控著大棚內溫濕度&#xff1b;灌溉與施肥&#xff0c;則由系統自動精準執行。 這…

基于Chinese-CLIP與ChromaDB的中文圖像檢索功能實現

本文按“原理 → 代碼 → 講解”三層展開&#xff0c;讀者只需具備 Python 基礎即可跟隨完成一個可落地的以文搜圖應用。 一、整體思路 把圖片和文字都轉成固定長度的向量&#xff08;768 維&#xff09;。把圖片向量提前存入向量數據庫。查詢時把文字轉成向量&#xff0c;再找…

Pandas 的 Index 與 SQL Index 的對比

一、Pandas 的 Index&#xff08;索引&#xff09;是什么&#xff1f;Pandas 的 Index 就像是 Excel 表格的行號 列標題&#xff0c;或者書的目錄。核心作用&#xff1a;定位數據&#xff1a;就像 Excel 中用行號和列名定位單元格&#xff08;如 A1、B2&#xff09;&#xff0…

Rust指針選擇

Rust指針選擇&#xff1a; 1.優先使用引用&#xff1a;安全訪問數據 fn process(data: &[i32]) { /* ... */ }2.需要所有權轉移時用 Box fn create() -> Box<Data> { Box::new(Data::new()) }3.共享數據用 Rc/Arc // 單線程 let shared Rc::new(data);// 多線程 …

【實用IP查詢工具】IP數據云-IP地址查詢離線庫使用方案

IP數據云&#xff08;ipdatacloud.com&#xff09;深耕IP地址查詢技術&#xff0c;打造了覆蓋多場景、高精度的IP地址查詢離線庫&#xff0c;為不同行業客戶提供穩定、高效的本地化數據支持。 什么是IP 地址查詢 離線庫&#xff1f; IP地址查詢離線庫是將海量IP地址與對應的地…