01背景

許多web服務需要對數十億個小對象實現快速訪問，而每個小對象只有幾百個字節。為了實現這一點同時考慮實際生產效益，緩存系統必須做到同時低成本，大容量與高性能。DRAM與NVM雖然性能好，但容量小，價格過于高昂。而閃存技術的發展使得閃存兼具性能與成本的優勢。然而，閃存作為小對象緩存也面臨著嚴重的壽命問題，這與閃存的特性有關。閃存讀寫的最小單位是頁面（KB級粒度），而小對象通常不到一百個字節。因此，閃存緩存系統的簡單部署勢必會導致嚴重的寫放大現象，加劇磨損問題，降低固態硬盤的使用壽命。

02問題

1.傳統的緩存策略

a)Log-structure cache:該策略將數據順序批量寫到閃存上，可以有效減小寫放大現象。為了記錄對象在閃存中的位置，每個對象需要在內存中保留一個索引。對于一個比較大的工作集，數十億個對象索引的內存開銷巨大。

b) Set-associative cache:該策略根據對象的鍵值將對象存放到不同的set中，就像CPU的cache，利用對象的鍵值來確定對象的實際存放位置，消除了內存索引的開銷。但是該策略會將多余的字節寫入閃存，每個對象的修改都需要重寫整個閃存頁面，嚴重增加了閃存的寫入量。

2. 閃存緩存的寫放大

a) Device-level write amplification:設備級寫放大發生在閃存轉換層(FTL),即閃存內部的寫入量超過主機端的寫入量。當閃存內部空閑空間不足時，FTL除了應對主機端的寫入，還需要執行垃圾回收來把部分有效頁面遷移到新的塊內。

b) Application-level write amplification:應用級寫放大是指應用程序需要重寫一些已經存在的數據。當一個頁面中的部分對象需要更新時，閃存需要讀出整個頁面，修改后再進行重新寫操作。

小對象使得閃存緩存系統極具挑戰性，在存儲設備中需要單獨記錄數十億個小對象，可能需要巨大的元數據索引結構，消耗大量的內存資源；如果索引位于閃存上，又會引入額外的寫放大現象。先前的工作沒有解決如何以低成本在閃存中緩存小對象的問題，log-structured cache需要過多的DRAM，而set-associative cache 會帶來嚴重寫放大問題。

03設計

Kangaroo是一種閃存緩存設計，其針對數十億個小對象的場景進行了優化。它的設計目的是最大限度地提高命中率，同時最大限度地減DRAM 的使用和閃存寫入。Kangaroo 采用分層設計，跨內存和閃存，將log-structured cache與set-associative cache結合。為了減少閃存的寫放大，Kangaroo利用Klog組件去緩存最近寫入的對象；為了減少DRAM的索引開銷，Kangaroo 利用Kset組件來緩存絕大多數對象。同時再Klog向Kset的轉化過程中，kangaroo利用了哈希沖突的特點，當大量的對象被映射到同一個Kset時，這些對象會批量寫入Kset，既提升了性能又減小了閃存的寫放大現象。

圖一：kangaroo概覽

Kangaroo主要通過以下三個策略來減少閃存寫入，減小內存開銷，提高緩存命中率。

1. Partitioned Klog：Klog內部結構為多個分區，每個分區有自己獨立的日志結構和DRAM索引結構。同一個Set的所有對象都會位于同一個分區表。利用hash沖突的特點，每個對象索引的next指針指向同一個set的下一個對象索引。采用拉鏈法解決哈希沖突使得Kangaroo可以高效的遍歷位于同一個set的對象，從而實現批量的寫入，減小寫放大。

圖二：KLog

2. KlogàKset：當數據從Klog向Kset遷移時，Kangaroo利用準入策略對對象進行篩選。當每次待寫入的對象數量少于閾值時，Kangaroo會丟棄該數據，多于閾值時才允許對象從Klog遷移到 Kset中。采用一個合適的準入閾值可以使得該策略有效減小應用級寫放大現象。此外，熱點數據如果沒有發生哈希沖突，可能會被剔除。Kangaroo為了解決這一問題，會使得熱點數據重新進入DRAM buffer，等待哈希沖突，提高緩存的命中率。

圖三：準入閾值對寫放大的影響

3. RRIParoo：Kangaroo會對Kset中的對象進行管理，決定需要剔除的數據。傳統的驅逐策略通常有較多的DRAM開銷，而RRIParoo給每個對象分配1bit，當對象最近被訪問過，該位置為0；同時結合經典的RRIP緩存替換策略來智能選擇需要驅逐的數據。

最后，簡單介紹下Kangaroo的基本操作流程，如圖四。

1. 查找

首先在DRAMcache中查找對象，若命中則返回，若缺失則進入Klog中查找；若命中則返回，若缺失則查找Kset的布隆過濾器；若存在則查找Kset，若找到則返回，若缺失或假陽性則從底層數據庫中獲取數據。

2. 插入

首先數據寫入到DRAMcache中，其有一定的概率會直接丟棄，或進入Klog；若進入Klog，則可能發生Klog到Kset的遷移。若未達到準入的閾值，則數據被丟棄，若達到準入閾值，則修改布隆過濾器標志位，并把數據寫入到Kset中。

圖四：Kangaroo操作流程

04實驗效果

論文作者團隊中將 Kangaroo 實現為CacheLib 中的一個模塊，并用真實的設備，Facebook和Twitter的真實負載進行了性能測試。實驗中Kangaroo的基本配置參數如下表。

表一：kangaroo實驗配置

實驗人員首先限制了DRAM的使用，從圖五中我們可以發現，LS策略由于需要大內存來存放索引，因而隨著內存的增加，緩存缺失率下降；而SA策略基本不需要DRAM資源，性能隨著內存容量的影響不大；而Kangaroo能以以極小的內存開銷實現了較低的緩存缺失率。

圖五：限制內存使用場景下的緩存缺失率

下圖顯示了三種策略在Facebook連續7天的負載下的表現，實驗人員在這組實驗中限制了閃存的最大寫入速度。Kangaroo的緩存缺失率與 SA 相比減少了 29%，與 LS相比減少了 56%。這是因為 Kangaroo有效地利用了有限的DRAM ，減少了閃存寫入。

圖六：三種策略連續7天內的緩存缺失率

05總結

Kangaroo結合了Log-structured cache與Set-associative cache的優點，減少了小對象閃存緩存系統的DRAM開銷與閃存寫入量，降低了緩存系統的成本，提升了生產系統的性能。

審核編輯：劉清