聊聊如何實現(xiàn)一種閃存緩存設(shè)計

01背景

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

02問題

1.傳統(tǒng)的緩存策略

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

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

2. 閃存緩存的寫放大

a) Device-level write amplification:設(shè)備級寫放大發(fā)生在閃存轉(zhuǎn)換層(FTL),即閃存內(nèi)部的寫入量超過主機(jī)端的寫入量。當(dāng)閃存內(nèi)部空閑空間不足時，F(xiàn)TL除了應(yīng)對主機(jī)端的寫入，還需要執(zhí)行垃圾回收來把部分有效頁面遷移到新的塊內(nèi)。

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

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

03設(shè)計

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

圖一：kangaroo概覽

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

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

圖二：KLog

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

圖三：準(zhǔn)入閾值對寫放大的影響

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

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

1. 查找

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

2. 插入

首先數(shù)據(jù)寫入到DRAMcache中，其有一定的概率會直接丟棄，或進(jìn)入Klog；若進(jìn)入Klog，則可能發(fā)生Klog到Kset的遷移。若未達(dá)到準(zhǔn)入的閾值，則數(shù)據(jù)被丟棄，若達(dá)到準(zhǔn)入閾值，則修改布隆過濾器標(biāo)志位，并把數(shù)據(jù)寫入到Kset中。

圖四：Kangaroo操作流程

04實驗效果

論文作者團(tuán)隊中將 Kangaroo 實現(xiàn)為CacheLib 中的一個模塊，并用真實的設(shè)備，F(xiàn)acebook和Twitter的真實負(fù)載進(jìn)行了性能測試。實驗中Kangaroo的基本配置參數(shù)如下表。

表一：kangaroo實驗配置

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

圖五：限制內(nèi)存使用場景下的緩存缺失率

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

圖六：三種策略連續(xù)7天內(nèi)的緩存缺失率

05總結(jié)

Kangaroo結(jié)合了Log-structured cache與Set-associative cache的優(yōu)點，減少了小對象閃存緩存系統(tǒng)的DRAM開銷與閃存寫入量，降低了緩存系統(tǒng)的成本，提升了生產(chǎn)系統(tǒng)的性能。

審核編輯：劉清