柚子快報(bào)邀請(qǐng)碼778899分享：緩存預(yù)取文章比較分析

http://yzkb.51969.com/

這篇文章主要記錄調(diào)研的cache prefetch部分有價(jià)值的論文，并給出一些總結(jié)

Baleen

核心內(nèi)容

ML learning-based admission policy + prefetch.exploit a new cache residency model to guide model training.

首先對(duì) access pattern 進(jìn)行了統(tǒng)計(jì)分析，提取出了一種緩存駐留模型（episodes），如果一批訪問對(duì)應(yīng)于一個(gè)緩存駐留模型，就將其進(jìn)行分組。使用該模型對(duì)數(shù)據(jù)進(jìn)行整理分析，并使用其訓(xùn)練ML準(zhǔn)入模型。

重點(diǎn)就是 episodes 緩存駐留模型。episodes 模型將一組對(duì)同一個(gè)塊的訪問進(jìn)行聚集處理，一個(gè)塊基本上對(duì)應(yīng)于 HDD 的一個(gè)盤塊，多個(gè)對(duì)同一個(gè)盤塊的訪問同時(shí)讀取，會(huì)極大得降低對(duì) HDD 的帶寬壓力，這也正是 HW 項(xiàng)目所需要和重視的。

相關(guān)背景部分介紹

該篇文章針對(duì) Tectonic 數(shù)據(jù)庫的 trace 進(jìn)行設(shè)計(jì)，考慮單個(gè)存儲(chǔ)節(jié)點(diǎn)的性能。

本篇論文中提到的準(zhǔn)入策略還是為了權(quán)衡 flash cache 對(duì) HDD 的性能提升作用和 flash cache 本身的磨損開銷。而 HW 項(xiàng)目中涉及到的準(zhǔn)入算法主要還是針對(duì) HDD 的盤帶寬進(jìn)行設(shè)計(jì)，并不側(cè)重 SDD 的容量和磨碎開銷。

現(xiàn)存的緩存系統(tǒng)存在的部分問題

非模塊化沒有聚焦系統(tǒng)端到端指標(biāo)沒有考慮峰值負(fù)載沒有進(jìn)行組件協(xié)同（準(zhǔn)入、預(yù)取和淘汰）

本文提出的解決方案

定義 DT（Disk-head time） + 闡述 DT 作為評(píng)價(jià)指標(biāo)的全面性定義了 TCO，確定了降低 peak TD 和 HDDs 是降低 TCO 的關(guān)鍵預(yù)取的單位為 segments，首先判斷哪些 segment 需要預(yù)取，然后再判斷什么時(shí)候預(yù)?。ê饬款A(yù)取帶來的收益和錯(cuò)誤預(yù)測(cè)的代價(jià)）詳細(xì)闡述了 episodes，如何進(jìn)行分組，如何設(shè)定參數(shù)，以及使用 episodes 的好處。（論文$3.4）描述 OPT（an episode-based approximation of optimal admission）的原理，以及如何利用 OPT 來進(jìn)行預(yù)取處理

這種預(yù)取相當(dāng)于識(shí)別了一種訪存模式，一個(gè) episodes 對(duì)應(yīng)于一種訪存模式，當(dāng)下次在遇到此類訪存模式時(shí)，系統(tǒng)就知道如何進(jìn)行預(yù)取后續(xù)的 segments 到 flash cache 中。

Baleen 具體實(shí)現(xiàn)方案

總共使用了9個(gè)特征信息，包括離線的元數(shù)據(jù)信息和在線的訪問情況

使用GBM來做二分類問題，作為準(zhǔn)入策略。

? Fig6：Architecture

訪問記錄被分為若干 Episodes，然后送入到 Admission Policy 中進(jìn)行訓(xùn)練，從而訓(xùn)練出一個(gè)二分類模型。在開發(fā)和測(cè)試過程中，使用離線訓(xùn)練+在線模擬器調(diào)節(jié)的方式對(duì)模型進(jìn)行收斂

Q：

HDD 按照塊（block）為單位進(jìn)行劃分，上層每次讀取都會(huì)讀取一塊？但是 Baleen 不按照塊級(jí)進(jìn)行緩存，而是按照 episodes 進(jìn)行分組，按照 segments 為單位進(jìn)行處理？

在每一次讀取的時(shí)候，緩存會(huì)檢查該次訪問所需要的 segments 是否全部被緩存了，如果還有段缺失，則需要被讀入到緩存中。

$3.5中的 block、access、episodes 之間的關(guān)系？

一個(gè) episodes 由多個(gè) access 組成，只針對(duì)于一個(gè) block。

補(bǔ)充內(nèi)容

布隆過濾器

布隆過濾器就是一串二進(jìn)制01數(shù)組A（初始化全零） + 若干個(gè)哈希函數(shù) Funcx。當(dāng)一個(gè) key “存入”布隆過濾器時(shí)，A[Funcx(key)] = 1。后續(xù)查詢?cè)?key 是否存在時(shí)，檢查每個(gè) A[Funcx(key)] 是否為1。

布隆過濾器的優(yōu)點(diǎn)在于可以高效判斷一個(gè)數(shù)據(jù)是否存在于系統(tǒng)中，缺點(diǎn)在于存在誤判率，沒法達(dá)到百分之百的準(zhǔn)確率。

布隆過濾器常用于防止 redis 緩存穿透。如果大量請(qǐng)求跳過 redis 緩存，直接查詢了數(shù)據(jù)庫，會(huì)對(duì)數(shù)據(jù)庫造成很大的壓力，叫做 redis 緩存穿透。布隆過濾器的二進(jìn)制數(shù)據(jù)是全局的，若數(shù)據(jù)庫中存在數(shù)據(jù)，那么布隆過濾器就會(huì)在該數(shù)據(jù)請(qǐng)求過后標(biāo)記數(shù)據(jù)的存在。從而避免其他大量數(shù)據(jù)庫不存在的數(shù)據(jù)請(qǐng)求，造成 redis 緩存穿透。

Baleen 代碼部分解析

跟蹤調(diào)試

主程序調(diào)用 simulate_cache_driver(options)，其中 options 為該系統(tǒng)執(zhí)行所需要的全部配置信息。

配置日志信息明確替換策略為 LRU計(jì)算 num_cache_elems，緩存元素的數(shù)量構(gòu)建 ap，如果使用離線 ap，則直接加載；否則需要進(jìn)行在線構(gòu)建（Line1482跳轉(zhuǎn)）構(gòu)建 prefetcher（Line1488跳轉(zhuǎn)）確定 eviction 策略模擬緩存系統(tǒng)，然后開始模擬執(zhí)行訪問請(qǐng)求（Line1560）

整體 demo 代碼分為兩步：

利用 trace 對(duì) ML 模型進(jìn)行訓(xùn)練將訓(xùn)練好的 Baleen 和模擬器進(jìn)行在線測(cè)試

Q1：模擬器主要模擬真實(shí)系統(tǒng)中的哪些部分？

Baleen 系統(tǒng)跑到模擬器上，沒有涉及到真實(shí)的硬件。

Q2：ML 準(zhǔn)入和預(yù)取模型結(jié)構(gòu)是什么樣子的？

都是 LightGBN 的模型結(jié)構(gòu)，分為分類模型和回歸模型兩種。

Q3：代碼中是如何對(duì) Trace 進(jìn)行處理，從而得到 episodes 的？

episodes.py 中的 Line875 位置即為將 Trace 數(shù)據(jù)轉(zhuǎn)換為 episodes 的地方

def process_obj_chunk_n_noprefetch(obj):

d_ = interarrivals_from_accesses(obj)

residences_by_e_age = {}

for e_age_log_phy in obj['e_ages']:

e_age_split = e_age_log_phy[d_['split_idx']]

residencies = []

for first, last, no_of_accesses in residences_from_interarrivals(d_['interarrivals'], e_age_split):

chunk_counts, chunk_last_seen = get_chunk_stats(first, last, d_)

episode_ = get_episode(d_, first, last, no_of_accesses, chunk_counts=chunk_counts, chunk_last_seen=chunk_last_seen)

update_noprefetch_stats(first, last, d_, episode_, no_of_accesses, e_age_split)

residencies.append(episode_)

residences_by_e_age[e_age_log_phy] = residencies

return residences_by_e_age

Q4：定位到離線訓(xùn)練和在線訓(xùn)練的位置，各自的作用

根據(jù)需求進(jìn)行選擇?？梢栽赾onf文件中定義對(duì)應(yīng)字段的值，決定是否需要在線訓(xùn)練。

在構(gòu)建AP的時(shí)候，選擇合適的參數(shù)即可

CHROME

核心內(nèi)容

利用強(qiáng)化學(xué)習(xí)中的 Q-learing 算法框架對(duì)存儲(chǔ)管理系統(tǒng)進(jìn)行集成管理。整體上算是一種最簡(jiǎn)單的 Q-learning 算法的應(yīng)用，硬件開銷相對(duì)較小。CHROME 在 CPU 的 LLC（last level cache）和 L2 級(jí)緩存中進(jìn)行緩存管理。

算法框架

CHROME 在強(qiáng)化學(xué)習(xí)中的各大基本概念定義：

agent：CHROME env：CPU 和內(nèi)存 state：以多維向量形式表示的程序特征信息（包括 PC 等程序信息和 page number, page offset 等數(shù)據(jù)訪問信息）

注：為了權(quán)衡資源開銷和性能，利用 feature selection[27] 來決定選擇哪些特征進(jìn)行處理

action：bypass or assign EPV(eviction priority value) on a cache miss; update EPV on a cache hit reward：分為四種獎(jiǎng)勵(lì)

? CHROME架構(gòu)圖

表中內(nèi)容細(xì)節(jié)

EQ：Each EQ entry records five pieces of information: the state vector, the action executed by CHROME, whether the action was triggered by a hit or a miss, the memory address of the requested cache block, and the assigned reward.

Q2：什么時(shí)候給 EQ 中的項(xiàng)賦 award 值呢？是在下一個(gè)請(qǐng)求到來的時(shí)候嗎？

For each new LLC request, if the request address matches the address stored in an EQ entry (indicating that CHROME has previously executed an action for this address and this address is now being requested again within a temporal window

This reward is determined based on whether the corresponding action results in a cache hit or a miss, and whether the LLC request is triggered by demand or prefetch

? CHROME偽代碼

總結(jié)

BaleenCHROME工作層次SSD - HDDCPU 三級(jí)緩存所用算法機(jī)器學(xué)習(xí)中常見的分類和回歸算法強(qiáng)化學(xué)習(xí)中的 Q-learning 算法優(yōu)點(diǎn)1. episodes 緩存駐留模型能夠降低 HDD 帶寬壓力2. 考慮了極限負(fù)載（peak load）的情況，更符合真實(shí)的應(yīng)用場(chǎng)景利用強(qiáng)化學(xué)習(xí)將緩存替換，準(zhǔn)入和預(yù)取集成到同一個(gè)系統(tǒng)中

參考文章

[1] FAST’24 Baleen: ML Admission & Prefetching for Flash Caches

[2] HPCA’24 CHROME: Concurrency-Aware Holistic Cache Management Framework with Online Reinforcement Learning

柚子快報(bào)邀請(qǐng)碼778899分享：緩存預(yù)取文章比較分析

http://yzkb.51969.com/

參考閱讀