TOC 2023 Paper?論文閱讀筆記整理

問題

大多數現代系統利用緩存來減少平均數據訪問時間并優化其性能。當緩存未命中的訪問時間不同時，最大化緩存命中率與最小化平均訪問時間不同。例如：系統使用多種不同存儲介質時，不同存儲介質訪問時間不同；系統使用NUMA架構時，不同處理器單元訪問時間不同。現有的策略隱含地假設統一的訪問時間，但在存儲、web搜索和DNS解析等領域，訪問時間是可變的。

本文方法

本文測量了各種項目的訪問時間，并利用訪問時間的變化作為緩存算法的額外信號，引入了自適應訪問時間感知緩存策略。

• 對TinyLFU進行優化，提出開銷感知TinyLFU（CATinyLFU）。對LRU進行優化，提出開銷和最近性感知（CRA）。

• CATinyLFU中感知開銷的方法為，測量緩存命中（ht）和未命中（mt）的訪問時間。在緩存驅逐時額外考慮訪問時間，緩存驅逐項1導致增加時間 T1=訪問頻率1*（mt1-ht1），緩存進入項2導致減少時間 T2=訪問頻率2*（mt2-ht2），若 T2>T1，即使項2的訪問頻率小于項1，也可以將其納入緩存，從而降低整體平均訪問時間。

• CRA中，因為LRU不提供顯示的訪問頻率預測，采用衰變函數捕捉最近性，△e表示mt-ht。

  

  

實驗表明，本文的自適應算法在存儲工作負載中的平均訪問時間減少了46%，在網絡搜索中的平均訪問時間減少了16%，總的平均訪問時間縮短了8.4%。

總結

針對緩存策略的優化，現有方法不會考慮不同環境下未命中的訪問時間，最大化緩存命中率不一定能最小化平均訪問時間。本文測量了緩存命中和未命中的訪問時間，由此設計訪問時間感知緩存策略，對TinyLFU和LRU進行優化，允許訪問頻率低但未命中訪問時間高的項替代頻率高但未命中訪問時間低的項，實現降低整體平均訪問時間。