01背景

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

02問(wèn)題

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

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

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

2. 閃存緩存的寫放大

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

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

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

03設(shè)計(jì)

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

圖一：kangaroo概覽

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

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

圖二：KLog

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

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

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

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

1. 查找

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

2. 插入

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

圖四：Kangaroo操作流程

04實(shí)驗(yàn)效果

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

表一：kangaroo實(shí)驗(yàn)配置

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

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

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

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

05總結(jié)

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

審核編輯：劉清