自適應軟體快取管理

• 2021 年 7 月 12 日
• 筆記
• paper

自適應軟體快取管理

譯自：Adaptive Software Cache Management

簡介

由於負載的多樣性，很難開發一個能夠適用於各種負載的軟體快取管理策略。在本論文中，我們調研了一種用於軟體快取管理框架的自適應機制，通過調節參數來調節負載的最常(訪問) vs 最*(訪問)的快取比例。最終目標是通過自動調節參數來獲得最佳性能(而無需人工介入)。我們針對該問題研究了兩種方案：爬山解決方案和基於指示器的解決方案。在爬山解決方案中，通過不斷配置系統來獲得最佳配置。在指示器方案中，我們評估了最常(訪問) vs 最*(訪問)對系統的影響，並根據單一變數調節參數。

我們將這些自適應機制用於最新的兩個軟體管理框架中，並對在大量不同特性的負載下的框架和自適應機制進行了評估。通過這些工作來衍生出一個與參數無關的軟體快取策略，並在所有測試的負載中保持競爭力。

本文提供了兩種快取自適應策略:爬山方案和指示器方案。通過比較發現基於W-TinyLFYU的自適應快取框架可以很好地工作於多種負載之下。

後續有時間研究一下文中給出的自適應實現方式。

1 概述

快取是一種通過維護相對較小的(臨*的)高速記憶體塊中的數據來解決系統突發性能的技術。這裡我們主要關心軟體快取，即由中間件、作業系統、文件系統、存儲系統和資料庫等軟體系統維護的快取(而非由硬體實現的快取，如CPU的L1、L2和L3快取)。重複訪問存在於快取中的數據的行為，稱為快取命中，其遠快於從實際存儲中獲取數據。其他訪問則稱為快取缺失。快取管理策略的主要工作是確定哪些元素可以放在快取中，猜測哪些元素可以獲得最高的命中率，即快取命中率和整體訪問數的比率。這類框架通常會嘗試在負載中確定某些模式來獲得最高命中率。

最*(訪問)和最常(訪問)是軟體快取管理策略經常使用的兩種方式。最*(訪問)認為，最*訪問的元素很可能在不久的將來被重複訪問。相比之下，最常(訪問)認為，最常訪問的元素很可能在不久的將來被重複訪問。由於大多數負載元素的流行度都會隨著時間變化，通常會使用如滑動窗口[17]或指數退避[13,19]來測量使用頻率。

從經驗上看，不同的負載展示了不同程度的最*(訪問) vs 最常(訪問)，這也是為什麼很難去設計一個單一的”最佳”快取管理款框架。因此系統設計者面臨的並非一項簡單的任務，需要了解負載的特性，然後為這些負載調研出一個可以提供最高命中率的快取管理策略。而且，一些快取管理策略具有可調節的參數，這要求系統設計者了解如何去配置這些參數。更糟糕的是，當設計一個新系統時，有可能無法事先知道未來運行的負載，這樣設計者就無法判斷應該選擇哪種快取管理策略。另外，在一般的快取庫中，為了無需讓用戶處理設置參數，會將這些參數設置為默認值，以為大多數負載提供最佳結果。但對於其他系統負載，這類設置可能會大大偏離最佳結果。

總之，自適應軟體快取管理策略需要在儘可能多的負載上獲得富有競爭力的命中率。我們將聚焦在探索軟體存儲的自適應性機制。

價值

在本論文中，我們為軟體快取管理框架確定了兩種自適應機制，這兩種機制都暴露了影響命中率的調參。第一種基於爬山方式[26]來調節快取管理參數。特別地，我們會定期在某個方向上調整參數，使之在偏最*(訪問)的負載 vs 偏最常(訪問)的負載下更好地工作。在一段時間後，使用最*獲得的命中率與上一次的命中率進比較。如果命中率獲得了顯著提升，則在相同方向上繼續調參，否則在相反方向上調參，以此往複。爬山方案最大的優勢是可以在不引入任何元數據的情況下實現。然而，它可能會陷入局部最大值的風險，且永遠不會停止振蕩。

另一種方式是基於指標的方案。這裡，我們會定期計算負載的最常(訪問) vs 最*(訪問)的評估結果，並調節相應的參數。這種方式需要一些元數據來計算上述評估結果，並快速收斂。

我們將這兩種方法引入最*出現的FRD[25]和W-TinyLFU [13]¹框架中。這兩個框架都將整個快取區域劃分為兩個子快取，一個用於保存”最*進入的元素”，另一個用於保存”常用的元素”。兩個框架都將兩個子快取的比例作為一個可調節的參數，但在選擇哪個元素進入哪個子快取上有所差異。在W-TinyLFU中，取決於一個通過節省空間的sketch [11]實現的准入過濾器，其頻率老化機製作為自適應的另一個潛在區域。

這裡，我們使用上面提到的爬山和指示器方法來為在線負載探索動態調節FRD和W-TinyLFU的參數的方式。特別是調節FRD和W-TinyLFU的兩個子快取的相對大小。對於W-TinyLFU，我們還處理了其sketch准入過濾器的過期參數。

最後，我們將提出的方案與來自不同途徑的實驗結果(一些來自於前面的工作，一些來自於Caffeine的用戶[23])進行了評估。 在我們的評估中，與最佳替代方案相比，我們的自適應方案始終富有競爭力。

2 相關工作

Belady的最優快取管理策略[5]可以面向未來，並從快取中淘汰最早訪問的元素。但由於無法預測未來，因此在大多數領域中，該策略是不現實的。它可以作為快取策略性能的上限。在實踐中，快取管理策略涉及典型訪問模式的啟發和優化。

LRU基於這種假設：最*最少訪問的元素，則未來不可能再次訪問。這樣，一旦快取滿後，它會淘汰LRU元素，為新到的元素讓出空間。而LFU認為訪問頻率是一種好的對未來行為[2, 3, 13, 17, 18]的評估器。LFU需要監控大量不存在於快取中的元素，因此可能會造成大量開銷。[13]使用一個*似sketch來最小化這類開銷。此外，LFU策略經常會引入過期，通過對應的特定滑動窗口[17]或指數衰減樣本來計算頻率[2,3]。其他方式包括通過重用距離[1,16,20]來計算後續到同一條目的訪問時差。 但後者需要記住大量的幽靈條目。

空間是優化的另一個維度。在一些場景下，元素的大小差異很大，因此需要將大小算進去[6, 9, 32]。通過自適應大小來調節快取准入的可能性，進而最大化目標命中率[6]。相反，很多快取策略會維護一個固定數目的元素，而不關心元素大小，只有當快取的元素大小相同或類似時才不會對效率造成影響，如塊快取和分頁快取。另外，很多知名的影片點播和流系統會將文件分割為相同大小的塊，每一塊都可以獨立快取。這裡，我們關注固定大小的元素。

Hyperbolic快取是最*提出的一個各方面比較好的快取管理策略。Hyperbolic快取可以使用相同的數據結構來模擬多種淘汰策略，因此能夠根據負載採取相應的動作。另一個自適應策略是Adaptive Replacement Cache (ARC) [24]。這兩種策略的共同缺陷是在最常(訪問)方式下沒有競爭力，而且ARC需要維護大量幽靈表項。

LRFU[19]結合了最*和最常兩種方式來評估快取中的每個元素，通過參數λ來控制*衡。當使用”正確的”λ來為一個給定的負載初始化LRFU時可能會獲得高命中率，而選擇”錯誤的”值則可能導致性能問題。根據負載自動化調節λ仍然是一個問題。另一個妨礙LRFU被廣泛採納的原因是其本身高昂的實現和運行時代價。

最*出現的Mini-Sim [31]方法建議同時模擬多種快取配置，每種模擬會通過在所有訪問中進行隨機取樣來降低計算開銷。這種方法的問題是由於採用了在r次訪問中取樣一次的方式，因此在一個短周期內可能會丟失多次訪問(這裡1/r作為取樣率)，無法捕獲基於最*(訪問)的負載的特徵。Mini-Sim會隨機取樣1/r次，然後將代表所有訪問的取樣元素提供給模擬配置。為了節省空間，將模擬快取大小設置為c/r，c為原始快取大小。回顧一下，我們的目標是找出一個最佳配置參數，而不是決定哪個元素應該出現在實際快取中。

Mini-Sim有如下缺陷。模擬配置必須持有它們所保存的元素的幽靈表項，這樣會導致空間浪費，且執行時間與同時配置的模擬數量和取樣率成比例。我們針對Mini-Sim和W-TinyLFU進行了實驗，發現在快取了上千個元素且使用基於最常訪問的負載上，Mini-Sim需要更大的取樣率才能獲得相同精確的結果。在實踐中，在基於最常訪問的負載上，基於元素ID的取樣的精度要稍低，因為如果沒有採用到常用的元素，則MiniSim的結果會與實際負載的行為有所出入。此外，由於使用的是取樣，MiniSim需要相對更長的時間來適應負載的變化。相比之下，我們的方法更具冒險精神 – 在沒有事先模擬新配置的性能的情況下直接更改配置。

最*的LeCaR研究[30]使用機器學習技術來結合LRU和LRF替換策略，其展示的結果要優於ARC，且在負載變化時表項良好。

還有一些工作考慮到了SSD快取的特點，更重要的是[8]中的工作描述了為何Belady的最優觀點不適用於SSDs，並提出了一個新的離線優化演算法(該演算法不僅最大化命中率，還考慮到容器放置問題以減少寫入放大和設備磨損)。Pannier[21]專註於SSD的容器快取實現細節，他使用一個自適應信用系統來限制SSD寫入預定義配額的數據量。這和我們的[15]工作類似，它維護了一個使用幽靈表項的對象的頻率統計資訊，且僅允許最常用的對象進入SSD快取，使用ARC作為快取替換演算法。本質上，這種方法和TintLFU類似，區別是使用了幽靈表項，而不是sketches。

硬體CPU快取領域中，最接*我們工作的是[28]，它提出了一種在不同替換策略(LRU、LFU、FIFO、Random)間切換的自適應機制，但不能調節任何配置參數。

3 概述 W-TINYLFU 和FRD

正如上文提示的，W-TinyLFU包含三個組件：Main快取，一個*似LFU的准入過濾器，稱為TinyLFU，以及一個Windows快取，如圖1。新到的元素會被插入到Window快取。原則上，它可以使用任何已有的策略進行維護，但在Caffeine實現中，Window快取使用了LRU淘汰[23]。類似地，Main快取可能會引入任何快取管理框架，但Caffeine使用了SLRU淘汰策略。從Window快取淘汰的元素以及從Main快取淘汰的元素會進入TinyLFYU過濾器，後續會對二者的頻率進行評估，並選擇頻率最高的插入/保持到Main快取中。

圖1.W-TinyLFU框架：元素總是首先進入Windows快取，從Windows快取淘汰之後會進入Main快取，此時會使用TinyLFU作為其准入過濾器。在這裡，我們保留了[13]中的術語

可以將W-TinyLFU中Window快取的大小設置為總快取大小的0%-100%。W-TinyLFU的作者[13]經過大量負載實驗後得出，將該值設置為1%可以獲得最佳的命中率，這也是為什麼Caffeine快取庫[23]將其作為默認配置的原因。然而，在一些嚴重偏向最*(訪問)的負載中，需要將Window快取的大小提升到20%-40%來媲美最佳備選方案(通常是LRU或ARC)。

通常使用sketch來實現用於評估訪問頻率的TinyLFU准入過濾器，如minimal increment counting Bloom filter [10]或count min sketch [11]。用於統計頻率資訊的取樣大小S是快取大小C的倍數。為了實現表項的過期功能，每達到S次訪問後，計數器就會除以一個過期因子，該操作稱為Reset[13]。默認情況下，過期因子為2，即，所有計數器都會在每個Reset操作時減半。由於訪問頻率為S/C的元素已經足夠頻繁，可以留在快取中，因此計數器的最大值為S/C。

FRD [25]也將整個快取區域劃分為兩部分，稱為Temporal快取和Actual快取，每一部分都使用LRU進行管理。FRD會維護比較長的歷史訪問，類似其他框架中的幽靈表項。當出現快取丟失時，如果訪問的元素出現在歷史記錄中，則會將其插入到Actual快取。否則，會將該新元素插入到Temporal快取中。與W-TinyLFU類似，Temporal快取和Actual快取的比例是一個可調節的參數。經過測量，作者[25]建議將Temporal快取的默認值設置為10%，並在後續工作中動態調節該值。與W-TinyLFU不同，FRD需要維護一個擴展的訪問歷史。

4 自適應快取策略

本章中，我們會使用一些方法來派生出自適應快取管理策略。我們討論了熟知的爬山演算法[26]，以及新的、基於指示器的自適應框架的適應性。為了呈現具體的演示結果，在4.1章節中，首先調節W-TinyLFU 和 FRD的參數來對這些框架進行調節(當然，為了更好地處理基於最*(訪問) vs 最常(訪問)的負載，可以採用任何暴露了調參的框架)。然後在4.2章節中討論自適應框架。

4.1 可調節參數

對於W-TinyLFU和FRD，我們暴露了動態調節Windows(或Temporal)快取相對大小的介面(佔總快取的0-100%)。在W-TinyLFU中，我們還測驗了動態校準TinyLFU准入過濾器使用的sketch參數(影響最常訪問的元素的過期速度)。下面詳細說明這些內容。

4.1.1 Window Cache 大小

當window(Temporal)快取的淘汰策略是LRU時(例如Caffeine和FRD)，如果window(Temporal)快取較大，其整體行為將接*LRU。特別地，當window(Temporal)快取佔100%時，將完全成為LRU。相反，由於W-TinyLFU准入過濾器基於元素的過期頻率，小的Window快取將傾向於強調訪問頻率。類似地，在FRD中，Actual快取用於保存常用元素，即，如果將main(Actual)快取擴展到總快取的100%，將在W-TinyLFU和FRD中獲得以頻率為導向的策略，參見圖2。

圖2：調節W-TinyLFU和FRD：window快取和main快取的比例暗示了在最*(訪問)和最常(訪問)上的取捨

4.1.2 W-TinyLFU Sketch 參數

W-TinyLFU准入過濾器有3個配置參數：(i)過期取樣長度S，(ii)過期因子，每個Reset操作中的默認值為2，但可以擴大或縮小，(iii)每次訪問元素時的增量，默認為1，也可以調節。

我們將一開始的取樣長度設置為S。通過縮短S可以限制元素的最大頻率個數，進而降低了不同元素之間的最大訪問頻率的差異，並加速了元素的過期進度(由於降低了最大值)。上述兩種方式降低了訪問頻率的影響，使得過濾器更偏向最*(訪問)。

增加過期因子可以劃分Reset操作中的計數器，並加速過期，反之亦然。即增加因子會使過濾器傾向最*(訪問)，降低則會傾向最常(訪問)。

最後，我們發現增加每次元素訪問時的計數器增量會使得過濾器更傾向最*(訪問)。這是因為更大的增量會更快地使計數器達到最大值，意味著計數器的值更多地反映了每個最*被訪問的元素(而非元素的訪問次數)。而且，我們會在總的增量達到取樣大小時執行Reset操作，因此只需更少的元素就能觸發Reset操作，更快觸發過期。因此，大大降低了對歷史頻率的計數，而更關注最*產生的活動。

例如，增量為8，代表該元素的計數器會在元素進入時增加8，即估計的訪問頻率為8。第一次Reset操作之後，估計的頻率會減半到4，第二次之後，會減半到2，以此類推。在極端情況下，當增量設置為S/C時，W-TinyLFU的行為最非常接*最*(訪問)，參見圖3。

圖3.該場景下，3個元素在不同時間僅出現了一次。增量為1的默認W-TinyLFU會將3個元素評為1(在上一次Reset之後)或0(在上一次Reset之前)， 因此無法確定這三個元素的先後。圖3a中的增量為2，在一個Reset操作之後變為1，Reset操作的頻率也是前者的2倍，此時可以確定，最*訪問了橘色和綠色的元素(而非紅色的元素)。圖3b的增量為4，再次加倍了Reset的次數，這種情況下，橘色和綠色之間多了一次Reset操作，因此我們探測到最*訪問了橘色元素。

修改增量而非取樣長度或Reset數值的動機主要出於工程的角度。即，除以2的操作可以高效地通過移位操作實現，而除以其他因子可能需要浮點運算。而且，修改sketch的大小可能會改變sketch的精度或需要動態記憶體分配。相反，修改增量值的影響較小，且實踐中也容易實現。

4.2 潛在的自適應框架

4.2.1 爬山方案

爬山方案是一種簡單的優化技術，用於查找一個函數的本地最優值。在我們的上下文中，首先在一個特定的方向上修改配置，即增大Window快取大小。然後對比新老配置下的命中率。如果命中率有所提升，則在相同的方向上繼續進行下一步驗證，即持續增大window大小。反之，則向相反的方向進行驗證。圖4展示了爬山演算法。

圖4. 爬山演算法。在監控階段，比較當前的命中率和先前獲得的命中率，如果當前命中率提升，則在相同的方向上更新配置。否則，在相反的方向上更新對應的配置

該方法的主要優點是我們不需要額外的元數據來重新配置快取，而前面的自適應演算法則需要元數據和幽靈表項[4,24]。爬山是很多快取策略常用的演算法。

在該演算法中，我們首先修改一個特定方向上的快取配置，然後評估其對性能的影響。即，我們事先並不知道該配置是否能夠提升命中率。理解改方案的難點主要在於如何決定每次調節的步長，以及調節的頻率，因此需要權衡這兩個動作。

乍一看，使用小而頻繁的步似乎吸引人。這是因為此時小步造成的懲罰更小，且對變更的響應更快。但使用這種方式的問題在於測量短時間內的命中率時會產生雜訊。因此，使用頻率過高的步時，很難區分命中率的變更是由於新配置導致的還是由於雜訊導致的。

上述原因使我們對策略做出不那麼頻繁且相對較大的變更。頻率較低的變更為我們提供了足夠的時間來評估配置對性能的影響範圍，並增大了命中率之間的差異，使之更容易被觀察到。這意味著在調節window大小時我們會輪流使用21種可能的配置(0%, 1%, 5%, 10%等)，以及在調節sketch參數時會使用15種可能的配置(注意我們的W-TinyLFU sketch的計數器最大值為15)。此外我們將判定間隔設置為10倍快取大小的訪問量，這給我們提供了足夠的時間來評估新配置的影響。

4.2.2 最常-最*指示器

我們的目標是實時獲取一個反映最常-最**衡點的指示器，這種指示器會直接選擇合適的配置，而無需採用逐漸增加步的方式。

指示器使用與W-TinyLFU過濾器[13]相同的sketch來評估元素的頻率(增量值固定為1)。因此，當我們調節W-TinyLFU的Window快取的大小(而非sketch增量)時，指示器會共享相同的(帶W-TinyLFU過濾器的)sketch。

對於每個新到的元素，我們會累計sketch的估量，並使用這些估量的*均值作為hint，指導當前的工作模式偏向哪一方(最*/最常)。以往的經驗告訴我們，較低的值會偏向最常訪問的負載，而較高的值會偏向最*訪問的負載，而更高的值又會偏向極度頻繁訪問的負載。直覺上講，如果負載偏向最常訪問則訪問的元素是分散的，計數器的數值相對較低；如果負載偏向最*訪問，則訪問的元素是相對集中的，被訪問元素的計數器數值相對較高。最後，當負載具有(偏向最常訪問的)較大的頻率偏差時，一小部分元素的訪問會非常頻繁，因此這種情況下hint數值會非常高。圖5展示了這種場景。

圖5. 每個周期包含三個訪問的場景。圖5a中，每種元素在每個周期僅出現一次。由於Reset操作，頻率估計總是0，因此hint等於0。圖5b中，使用最*訪問方式來記錄訪問，現在每個數值的訪問估值為0，1，2.因此，指示數值等於1。圖5c中，我們修改了每個數值出現的次數來描述頻率偏差，第一個周期的估值變為0，1，0，其他周期的估值為1，2，0，hint值為0.77。

為了區分(大)頻率偏差和(高度)最*訪問的影響，我們使用其他機制來評估分布偏差。眾所周知，當在軸是元素等級和頻率的log-log圖中繪製Zipf分布的元素時，結果是一條直線，該直線的斜率是頻率偏差(skew)參數。在每個配置周期內，我們會彙集最常訪問的元素，並通過在這些項目的log-log值上執行線性回歸來計算偏差估值。這種計算不會太頻繁(即，每一百乘以快取大小次數)，也更實際。

我們結合hint數值和頻率偏差估計(skew)來構造我們期望的指示器，如下：

maxFreq是從頻率sketch(設定為15)中獲取的最大估值。我們的目標是在偏最*訪問的結果保持高hint數值的情況下，不斷接*1。因此如果極度偏最常訪問時，skew的數值也會變大，此時會導致hint數值變低。由於skew範圍為[0,1]，通過以指數為3來提升skew，這樣可以極大區分低數值與接*1的數值。正常的maxFreq數值為[0,1]，0表示偏最常訪問，1表示偏最*訪問。

5 評估

本章中，會對我們的自適應機制(爬山和指示器)和適應參數(window快取大小和sketch管理)進行大量評估。我們還評估了兩個底層快取策略W-TinyLFU和FRD(見第三章節)。表1展示了我們工作中涉及到的6種可能性：基於爬山演算法(C)和指示器方式(I)來適應W-TinyLFU的Window(W)快取，分別稱為WC-W-TinyLFU和WI-W-TinyLFU。基於爬山演算法(C)和指示器方式(I)適應FRD的Window(W)快取，分別稱為WC-FRD和WI-FRD。最後，基於爬山演算法(C)和指示器方式(I)來適應W-TinyLFU的sketch(S)，分別稱為SC-W-TinyLFU 和 SI-WTinyLFU。我們還給出了使用Minu-Sim方法[31]來適應W-TinyLFU的Window大小的實驗報告，稱為MS-W-TinyLFU。

我們的實驗是在Caffeine的模擬器[23]中執行的。競爭策略的實現就源自該庫。在每次實驗中，我們會給每個策略提供一個實例，並在沒有預熱的前提下給這些實例提供整個負載。

5.1 自適應配置

下面我們描述爬山和指示器技術中需要考慮到的不同配置。

爬山。爬山演算法會在訪問量達到10倍的快取大小時進行一次自適應步驟。從1% 的Window(或Temporal)快取開始，Window快取涉及的所有配置為[0%, 1%, 5%, 10%, . . . , 80%]，Temporal快取涉及的所有配置為[0%, 1%, 5%, 10%, . . . , 100%]。為了調節W-TinyLFU sketch，我們考慮增量值範圍為[1 – 15]，即最多15種配置。回歸一下，我們將1%作為初始配置[13]，但作者[25]建議將Temporal快取大小設置為10%。下面看下我們的自適應框架是如何在不同的配置下運作的。

指示器。指示器會在每當訪問量達到50,000次時採取一次自適應決策。為了配置sketch，我們讓[指示器*30]，這樣相當於指示直接使用了最大值15。由於sketch有15種可能的增量值，通過將指示器乘以30，一個值為0.5的指示器的就已經將增量設置為15。這樣做的原因是，相比於Window大小的變化，sketch參數的變更造成的影響十分有限。因此在調節sketch參數時，我們將指示器的值翻倍。在配置Window和Temporal快取大小時，我們分別使用[80*指示器]和[100*指示器]。特別地，一次性最多可以給Window快取分配80%的總快取，給Temporal快取分配100%的總快取。

5.2 追蹤

我們的評估側重在不同領域中的14種真實負載，包括資料庫，分析系統，事務處理，查詢引擎，Windows伺服器等等。這些負載的底層特性不盡相同。有些基於最常訪問，而有些則是最常和最*訪問的結合體，而有些則完全基於最*訪問。顯然，沒有任何一種配置能夠完全負載所有負載。下面我們列出對這些負載進行追蹤的內容：

• OLTP：追蹤OLTP伺服器[24]的文件系統。在一個典型的OLTP伺服器中，大多數操作對象已經位於記憶體中，不會直接反映到磁碟訪問。因此主要的磁碟訪問主要體現為寫事務日誌。即追蹤大部分為順序塊訪問的升序列表(由於偶爾重寫或記憶體快取丟失造成的少量隨機訪問)。
• F1和F2：來自兩個大型金融機構的事務處理跟蹤。追蹤來源於UMass的追蹤庫[22]。出於上述相同的原因，它們與OLTP的追蹤結構非常類似。
• Wikipedia: Wikipedia的追蹤，包含從2007年9月[29]開始的兩個月內的10%的流量。
• DS1: 資料庫追蹤[24]。
• S3: 搜索引擎追蹤[24]。
• WS1, WS2, and WS3: 來自UMass庫的三個額外的搜索引擎追蹤[22]。
• P8 和 P12: Windows 伺服器 disc 訪問[24]。
• SPC1-like：由ARC[24]的作者創建的用於測試存儲系統性能的綜合性追蹤。
• Scarab：來自SCARAB Research的一小時追蹤：從全球不同大小的幾個電子商務站點的產品推薦查詢。
• Gradle：保存編譯結果(這樣後續在不同機器上的構建就可以直接使用該結果，而無需重新構建)的分散式構建快取追蹤。由於機器藉助了本地構建快取，因此會基於最*訪問來請求最新的分散式快取。由Gradle項目提供追蹤。

5.3 動機

我們首先展示了FRD和W-TinyLFU策略，且沒有對調參做任何靜態配置。圖6展示了在變更FRD和W-TinyLFU的總快取大小和Window(Temporal)的相對快取大小的情況下獲得的命中率。可以看到，對於搜索引擎，其命中率曲線單調遞減。即，對於這些追蹤，Window(Temporal)快取越小越好。相反，Gradle，其曲線更偏向於較大的Window(Temporal)快取，且越大越好。介於中間的是OLTP追蹤。在該追蹤中，最大值介於總快取大小的[15%-30%]左右。因此，不同的靜態配置對於不同的跟蹤來說有利有弊。

可以看到Windows快取比例越大越有利於傾向最*訪問的負載；反之則有利於傾向最差訪問的負載。但對於結合了最常和最*訪問的負載，則需要通過驗證來獲得最佳配置。

5.4 指示器配置

如上所述，對skew參數的評估需要對最常使用的元素(單位個數為千)進行線性回歸。直觀上，越大的k值可以越精確地評估skew，但需要的計算量也會直線上升。我們從經驗上選擇默認的k值，這樣就可以合理地對所有追蹤進行評估。圖7展示了不同k值下，對Wikipedia進行追蹤的結果。我們選擇k = 70，這是因為當k超過70時，很難再獲得更好的評估結果。

圖7. 評估Wikipedia追蹤中，不同k(單位：千)下的偏差。經驗上，當k>70時，評估結果相對集中，且帶來的優勢微乎其微。

5.5 對6個演算法進行評估

現在對我們提出的6個演算法進行評估，來選擇最佳演算法。我們根據採用的配置參數對演算法進行了劃分，即動態調節Window(Temporal)快取大小(WC-W-TinyLFU,
WI-W-TinyLFU, WC-FRD, and WI-FRD)的演算法，和動態調節sketch增量(SC-W-TinyLFU, SI-W-TinyLFU)的演算法。對於這些參數，我們將”offline”最優值最為參考基準，即通過單獨為每個數據點選擇最佳靜態配置(即，每個工作負載和每個快取大小是相互獨立的)來獲得基準值。

5.5.1 動態配置Window快取大小

圖8展示了動態配置Window快取大小的結果。用”offline”標註的線表示給定追蹤的最佳靜態配置。W-TinyLFU(1%)為Caffeine [13]的默認配置，FRD建議的默認配置為10%[25]。

如圖所示，Windows伺服器(圖8a)和搜索引擎追蹤(圖8b)中，所有基於W-TinyLFU的框架都接*線性最佳值，而自適應的FRD接*最佳值，但其曲線都低於基於W-TinyLFU的曲線。在Wikipedia追蹤中(圖8c)，所有的框架都幾乎是理想的。

資料庫追蹤(圖8d)展示了類似的結論，即基於WTinyLFU的命中率要高於基於FRD的命中率。WTinyLFU框架中，在大規模快取下，WC-W-TinyLFU的稍差，而WI-W-TinyLFU則在小規模快取下稍差。自適應FRD框架則可以符合其推薦的配置性能。

在事務處理追蹤(圖8e)中，W-TinyLFU的默認配置要差於其他配置。然而，WIW-TinyLFU的性能要略優於其他配置(更接*”offline”的結果)。在Gradle追蹤(圖8f)也可以看到類似的提升，但此時動態FRD框架略優。

5.5.2 動態配置sketch參數

圖9評估了修改W-TinyLFU sketch參數的演算法，即SI-W-TinyLFU和SC-W-TinyLFU。我們將這些框架與最佳離線配置”Offline W-TinyLFU”進行了比較。

對於Window伺服器(圖9a)和搜索引擎追蹤(圖9b)，所有結果都接*理想值。在資料庫追蹤(圖9c)中，SC-W-TinyLFU的性能稍差。在OLTP(圖9d)、Wikipedia (Figure 9e), 和 Gradle (Figure 9f)中，所有框架的結果都非常相似。

總之，無法確定哪種自適應策略(爬山或指示器)是最佳的。但至少可以看出，對於W-TinyLFU，自適應Window快取大小似乎至少不比自適應sketch參數差。因此我們將繼續使用兩種演算法：WC-W-TinyLFU和 WI-W-TinyLFU。取決於追蹤的內容以及由於(W-Tinylfu的)sketch維護的元數據更少，基於W-TinyLFU的自適應方案可以與基於FRD的框架相媲美甚至明顯更好。自適應的FRD框架即使在非推薦值下(1%)也能達到推薦配置的性能，這突出了動態自適應的好處：為了探測最佳配置，無需手動引入所有追蹤。

5.6 與其他自適應機制進行比較

下面。將我們的自適應機制與Mini-Sim[31]進行比較。最後，我們會給W-TinyLFU配置101個Mini-Sim實例，每個實例都模擬不同比例的Window和Main快取(稱為MS-W-TinyLFU)。

根據[31]的建議，我們將S_m (模擬的快取大小) >=100，取樣率>=0.001。即S_m=max(100, 0.001C)，C為測試的快取大小，取樣率為:

我們將決策間隔配置為1,000,000次訪問(經驗上最佳)。

圖10展示了評估結果。在基於最常頻率的資料庫追蹤中(圖10a)，WIW-TinyLFU要優於Mini-Sim，特別是在使用大型快取時。在基於頻率的搜索引擎追蹤(圖10b)中，Mini-SIM也相對滯後。這些結果顯示出，在基於頻率的追蹤中，MiniSim的採用方法要相對低效。而在其他追蹤中，如SPC₁基準(圖10c)和FI追蹤(圖10d)中，Mini-Sim和WI-W-TinyLFU一樣好。總之，雖然Mini-Sim是一種可行的自適應解決方案，但不適用於基於頻率的追蹤和小快取場景。相比之下，我們的爬山和指示器針對快取提供了更強大的適應性。因此，我們將僅使用 WI-W-TinyLFU 和 WC-W-TinyLFU繼續進行評估。

5.7 相對評估

本章中，我們將W-TinyLFU, WI-W-TinyLFU, WC-WTinyLFU和FRD與其他主要成果進行比較：ARC[24]和Hyperbolic快取。

網頁查找追蹤。網頁查找追蹤通常基於頻率，伺服器會聚合來自很多用戶的查詢。圖11展示了基於網頁查找追蹤的相對評估。可以看到基於W-TinyLFU框架的曲線總是位於最上方。相反，在這些負載下，FRD和hyperbolic則是最差的。ARC在WS2追蹤(圖11b)和WS3追蹤(圖11c)中具有競爭力，但在WS1追蹤(圖11a)和S3追蹤(圖11d)中相對滯後。在這些追蹤中，W-TinyLFU是最好的(與我們的自適應策略展示出的性能非常接*)。

存儲追蹤。圖12展示了大量存儲追蹤的結果，包括對Windows伺服器、資料庫以及一個基準。在SPC₁-Like的基準追蹤中(圖12a)，WI-W-TinyLFU、WC-W-TinyLFU 和 W-TinyLFU作為了領先策略，而FRD、Hyperbolic和ARC則相對滯後。

在Windows伺服器追蹤P8(圖12b)和P12(圖12c)中，在快取較少時，基於W-TinyLFU框架較優。對於較大的快取，在P8中，所有的策略都展示了相同的命中率，在P12中，其他策略比ARC、FRD和hyperbolic快取有2%的優勢。總之，在這些追蹤中沒有明顯的勝出者。

在資料庫追蹤DS1(圖12d)中，W-TinyLFU 和 WC-WTinyLFU 展示了高命中率且幾乎無法區分(WI-W-TinyLFU稍差一些，再往下是FRD)。然而，可以認為所有的W-TinyLFU都要優於Hyperbolic快取和ARC。

事務處理。圖13展示了基於事務處理追蹤的評估。這類追蹤經常會表現為最*和最常訪問的結合。ARC在所有這些追蹤中具有競爭力，非自適應的W-TinyLFU在OLTP追蹤(圖13a)和F1追蹤(圖13b)中相對滯後。相比之下，我們的自適應演算法(WI-W-TinyLFU 和 WC-W-TinyLFU)和FRD非常接*ARC。在所有這些追蹤中，我們的演算法要麼略優於ARC(OLTP和F2)要麼略差於ARC(F1)，但幅度不超過1%。相比之下，Hyperbolic快取只在F1追蹤和中具有優勢，W-TinyLFU只在F2追蹤中具有優勢。

其他追蹤。圖14展示了對其他類型的追蹤的評估，包括Wikipedia, Gradle, 和 Scarab。在Wikipedia追蹤中(圖14a)，所有框架的執行結果相似，Hyperbolic快取稍差。

對於Gradle追蹤(圖14b)，默認的W-TinyLFU是最差的。這類追蹤非常偏向最*訪問，所有訪問都會請求最*的構建。因此，一個被訪問很多次的構建，並不意味著未來也會再次被訪問。WI-W-TinyLFU 和 WC-W-TinyLFU的性能重疊，與ARC、Hyperbolic 和FRD的性能差距不超過1%。

在Scarab追蹤中(圖14c)，Hyperbolic是最差的，但所有其他策略的命中率非常相似，且最多比FRD差1%。

5.8 性能評估

最後我們評估我們自適應策略的計算開銷。我們測量實際追蹤的完成時間，同時模擬各種主存選項下由於快取未命中造成的延遲。我們將未命中延遲對應到SSD訪問、數據中心訪問、磁碟訪問和WAN(到荷蘭的CA)訪問(見[27]的基準項目報告)。我們還實驗了0未命中懲罰選項，稱為”none”，它捕獲到的快取管理框架的性能開銷最小。直觀上，由於與未命中懲罰相比，計算開銷可以忽略不計，因此完成時間由命中率佔主導地位。但如果策略過於複雜，即時命中率很高，也有可能產生較長的完成時間。我們在Intel i5-6500 CPU @ 3.20GHz 單核系統上進行測量。

圖15展示了在OLTP追蹤(圖15a)和S3追蹤(圖15b)中的評估結果。通過查看”none”未命中懲罰表，可以看到Hyperbolic快取是最具計算密集型的策略，而ARC則是最不具計算密集型的策略。WC-W-TinyLFU幾乎與W-TinyLFU完全相同，WI-W-TinyLFU幾乎則計算密集一些。所有自適應框架都展示了每秒100百萬次的快取訪問。

下面，我們檢驗了OLTP追蹤(圖15a)，此時WC-WTinyLFU 和 WI-W-TinyLFU展現了最高的命中率，正如我們看到的，這兩個策略同時也給出了最小的完成時間。當檢驗S3追蹤(圖15b)時，我們發現，W-TinyLFU的命中率最高，同時其完成時間也最小。可以看到，我們的自適應策略對完成時間的影響非常小，因此在這種情況下保證了W-TinyLFU的良好特性。總之，評估表明我們的自適應策略的計算開銷即時在使用DRAM快取(主存為SSD)時也不會太高。

命中率越高，未命中造成的懲罰越小

6 討論

正如前面展示的，不存在事先對快取管理策略進行靜態配置，就可以在任何負載上獲得最佳快取³命中率的情況。

因此，為了給特定系統確定最佳策略，需要仔細研究其負載的工作方式，以及各種策略在這些負載上的性能指標。然而，期望開發人員在每個系統上進行如此詳細的研究可能不太現實，而且實際中，有可能事先無法了解負載。本文中，我們探究了最*訪問 vs 最常訪問負載下的動態適應快取管理策略。在實驗方案上，我們採用了爬山方法和指示器框架，並將這些方案應用在W-TinyLFU和FRD策略中[13,25]。

通過檢查調節各種策略參數帶來的好處，我們得出修改W-TinyLFU的window大小比調節sketch參數對結果的影響更大。特別是對應的自適應框架WC-W-TinyLFU和WI-W-TinyLFU(分別對應window爬山和window指示器)，在所有實驗中保持了競爭力(且成為最佳策略)，同時在所有W-TinyLFU成為勝出者的場景下，它們的性能也不會下降。在FRD場景中，即使在從最優配置開始時，自適應框架也能夠與[25]中的推薦的靜態配置相媲美。這些跡象高度表明在事先不了解負載(以及不需要在不同的負載中嘗試不同配置)的情況下，也可以通過自適應獲得最好的結果。在CPU開銷方面，經過評估發現，完成時間主要受命中率的影響，且我們的框架的計算開銷可以忽略不計(無論未命中懲罰來自SSD、數據中心、磁碟或WAN的訪問)。

在比較爬山和指示器方式時發現，後者得到的結果略好，且適應性更快(單步中)。但爬山更容易實驗，且需要的空間更少。因此，在資源有限的環境中，爬山可能更合適。

本論文使用的全部程式碼以及測試配置已經開源[12]。

引用

[1] Akhtar, S., Beck, A., and Rimac, I. Caching online video: Analysis and proposed algorithm. ACM Trans. Multimedia Comput. Commun. Appl. 13, 4 (Aug. 2017),48:1–48:21.

[2] Arlitt, M., Cherkasova, L., Dilley, J., Friedrich, R., and Jin, T. Evaluating content management techniques for web proxy caches. In In Proc. of the 2nd Workshop on Internet Server Performance (1999).

[3] Arlitt, M., Friedrich, R., and Jin, T. Performance evaluation of web proxy cache replacement policies. Perform. Eval. 39, 1-4 (Feb. 2000), 149–164.

[4] Bansal, S., and Modha, D. S. Car: Clock with adaptive replacement. In *Proc. of the 3rd USENIX Conf. on File and Storage Technologies (FAST) (2004), pp. 187–200.

[5] Belady, L. A. A study of replacement algorithms for a virtual-storage computer.IBM Systems Journal 5, 2 (1966), 78–101.

[6] Berger, D. S., Sitaraman, R. K., and Harchol-Balter, M. Adaptsize: Orchestrating the hot object memory cache in a content delivery network. In

14th USENIX Symposium on Networked Systems Design and Implementation NSDI(2017), pp. 483–498.

[7] Blankstein, A., Sen, S., and Freedman, M. J. Hyperbolic caching: Flexible caching for web applications. In 2017 USENIX Annual Technical Conference (USENIX ATC) (2017), pp. 499–511.

[8] Cheng, Y., Douglis, F., Shilane, P., Wallace, G., Desnoyers, P., and Li, K.Erasing belady』s limitations: In search of flash cache offline optimality. In Proc. of USENIX Annual Technical Conference (ATC) (2016), pp. 379–392.

[9] Cherkasova, L. Improving www proxies performance with greedy-dual-sizefrequency caching policy. Tech. rep., In HP Tech. Report, 1998.

[10] Cohen, S., and Matias, Y. Spectral bloom filters. In Proc. of the ACM SIGMOD Int. Conf. on Management of data (2003), pp. 241–252.

[11] Cormode, G., and Muthukrishnan, S. An improved data stream summary: The count-min sketch and its applications. J. Algorithms 55, 1 (Apr. 2005), 58–75.

[12] Einziger, G., Eytan, O., Friedman, R., and Manes, B. Codebase and traces used in this work. //www.cs.technion.ac.il/~ohadey/adaptive-caching/AdaptiveSoftwareCacheManagementMiddleware2018.html, 2018.

[13] Einziger, G., Friedman, R., and Manes, B. Tinylfu: A highly efficient cache admission policy. ACM Transactions on Storage (TOS) (2017).

[14] Hennessy, J. L., and Patterson, D. A. Computer Architecture – A Quantitative Approach (5. ed.). Morgan Kaufmann, 2012.

[15] Huang, S., Wei, Q., Feng, D., Chen, J., and Chen, C. Improving flash-based disk cache with lazy adaptive replacement. ACM Trans. on Storage (ToS) 12, 2 (Feb.2016).

[16] Jiang, S., and Zhang, X. LIRS: an efficient low inter-reference recency set replacement policy to improve buffer cache performance. In Proc. of the International Conference on Measurements and Modeling of Computer Systems SIGMETRICS
(June 2002), pp. 31–42.

[17] Karakostas, G., and Serpanos, D. N. Exploitation of different types of locality for web caches. In Proc. of the 7th Int. Symposium on Computers and Communications (ISCC) (2002).

[18] Ketan Shah, A., and Matani, M. D. An o(1) algorithm for implementing the lfu cache eviction scheme. Tech. rep., 2010. “//dhruvbird.com/lfu.pdf“.

[19] Lee, D., Choi, J., Kim, J., Noh, S. H., Min, S. L., Cho, Y., and Kim, C. LRFU: A spectrum of policies that subsumes the least recently used and least frequently used policies. IEEE Trans. Computers 50, 12 (2001), 1352–1361.

[20] Li, C. DLIRS: Improving low inter-reference recency set cache replacement policy with dynamics. In Proc. of the 11th ACM International Systems and Storage Conference (SYSTOR) (June 2018).

[21] Li, C., Shilane, P., Douglis, F., and Wallace, G. Pannier: Design and analysis of a container-based flash cache for compound objects. ACM Trans. on Storage (ToN) 13, 3 (Sept. 2017).

[22] Liberatore, M., and Shenoy, P. Umass trace repository.//traces.cs.umass.edu/index.php/Main/About, 2016.

[23] Manes, B. Caffeine: A high performance caching library for java 8. //github.com/ben-manes/caffeine (2016).

[24] Megiddo, N., and Modha, D. S. Arc: A self-tuning, low overhead replacement cache. In Proc. of the 2nd USENIX Conf. on File and Storage Technologies (FAST) (2003), pp. 115–130.

[25] Park, S., and Park, C. FRD: A filtering based buffer cache algorithm that considers both frequency and reuse distance. In Proc. of the 33rd IEEE International Conference on Massive Storage Systems and Technology (MSST) (2017).

[26] Russell, S. J., and Norvig, P. *Artificial Intelligence: A Modern Approach (2nd ed.).Prentice Hall, 2010.

[27] Scott, C. Latency numbers every programmer should know. //people.eecs.berkeley.edu/~rcs/research/interactive_latency.html.

[28] Subramanian, R., Smaragdakis, Y., and Loh, G. H. Adaptive caches: Effective shaping of cache behavior to workloads. In Proc. of the 39th Annual IEEE/ACM International Symposium on Microarchitecture (2006), MICRO, pp. 385–396.

[29] Urdaneta, G., Pierre, G., and van Steen, M. Wikipedia workload analysis for decentralized hosting. Elsevier Computer Networks 53, 11 (July 2009), 1830–1845.

[30] Vietri, G., Rodriguez, L. V., Martinez, W. A., Lyons, S., Liu, J., Rangaswami, R.,Zhao, M., and Narasimhan, G. Driving cache replacement with ml-based lecar.In 10th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage) (2018).

[31] Waldspurger, C., Saemundsson, T., Ahmad, I., and Park, N. Cache modeling and optimization using miniature simulations. In 2017 USENIX Annual Technical Conference (USENIX ATC 17) (Santa Clara, CA, 2017), USENIX Association, pp. 487–498.

[32] Young, N. On-line caching as cache size varies. In Proc. of the second annual ACM-SIAM symposium on Discrete algorithms (SODA) (1991), pp. 241–250.