? ?日志結(jié)構(gòu)存儲(chǔ)在當(dāng)今存儲(chǔ)系統(tǒng)中被廣泛使用，然而其中的垃圾回收會(huì)將有效數(shù)據(jù)重新寫(xiě)入導(dǎo)致寫(xiě)放大現(xiàn)象?，F(xiàn)有最佳的數(shù)據(jù)放置策略是通過(guò)知道未來(lái)每個(gè)塊的無(wú)效時(shí)間進(jìn)行數(shù)據(jù)放置，然而無(wú)法在現(xiàn)實(shí)中實(shí)現(xiàn)。本篇工作提出一個(gè)新型的數(shù)據(jù)放置策略SepBIT，通過(guò)推測(cè)每個(gè)塊的無(wú)效時(shí)間，來(lái)將無(wú)效時(shí)間相似的塊放在一起，從而減少寫(xiě)放大并提高了I/O帶寬。SepBIT目前已經(jīng)被部署在了阿里云上。

01?背景

? ? 在基于日志結(jié)構(gòu)存儲(chǔ)中，數(shù)據(jù)被分為很多個(gè)段，而段中含有很多個(gè)塊。當(dāng)向其中寫(xiě)入數(shù)據(jù)時(shí)，會(huì)以塊的粒度進(jìn)行追加。當(dāng)其中的數(shù)據(jù)進(jìn)行更新的時(shí)候，也將會(huì)通過(guò)往后追加塊的方式寫(xiě)入數(shù)據(jù)來(lái)實(shí)現(xiàn)異地更新。當(dāng)一個(gè)段中數(shù)據(jù)寫(xiě)滿(mǎn)的時(shí)候，數(shù)據(jù)將會(huì)寫(xiě)到下一個(gè)段中。由于采用了異地更新，因此當(dāng)存儲(chǔ)中的段都寫(xiě)滿(mǎn)的時(shí)候，需要選擇其中一個(gè)段，將其中的有效數(shù)據(jù)重新寫(xiě)入并進(jìn)行擦除，通過(guò)這個(gè)方式來(lái)回收無(wú)效數(shù)據(jù)所占用的空間，這個(gè)過(guò)程就叫做垃圾回收(GC)。在這個(gè)過(guò)程中重新寫(xiě)入的有效頁(yè)就是造成寫(xiě)放大的原因。為了降低寫(xiě)放大，現(xiàn)在最優(yōu)的數(shù)據(jù)放置策略是通過(guò)預(yù)先知道所有數(shù)據(jù)的失效信息，從而將失效時(shí)間相似的數(shù)據(jù)放到一起。然而這個(gè)策略在現(xiàn)實(shí)中無(wú)法實(shí)現(xiàn)，這是因?yàn)?. 需要預(yù)先知道所有數(shù)據(jù)的失效時(shí)間是無(wú)法做到的；2. 同時(shí)需要維護(hù)很多可供寫(xiě)入的段地址，因此會(huì)帶來(lái)很高的內(nèi)存和存儲(chǔ)開(kāi)銷(xiāo)。同時(shí)此時(shí)的隨機(jī)寫(xiě)會(huì)帶來(lái)性能下降。

02?動(dòng)機(jī)

? ? 本文根據(jù)對(duì)阿里云和騰訊云真實(shí)負(fù)載的分析，探索其中有關(guān)于數(shù)據(jù)無(wú)效時(shí)間的發(fā)現(xiàn)。本文中的數(shù)據(jù)無(wú)效時(shí)間（壽命）定義為在兩次數(shù)據(jù)寫(xiě)入中寫(xiě)入的數(shù)據(jù)量。其中選取了騰訊云的4995個(gè)負(fù)載，以及從阿里云1000個(gè)負(fù)載中篩選的186個(gè)以寫(xiě)為主的負(fù)載。本文得到了3個(gè)發(fā)現(xiàn):

1. 用戶(hù)寫(xiě)入的數(shù)據(jù)通常壽命較短。

據(jù)統(tǒng)計(jì)，超過(guò)一半的負(fù)載中超過(guò)79.5%的數(shù)據(jù)壽命低于負(fù)載集大小的80%，同時(shí)47.6%的數(shù)據(jù)壽命低于負(fù)載集大小的10%。其中負(fù)載集大小的定義為數(shù)據(jù)邏輯地址的范圍。而通過(guò)GC重新寫(xiě)入的數(shù)據(jù)往往壽命較長(zhǎng)。

2. 頻繁更新的數(shù)據(jù)之間壽命差異較大。

發(fā)現(xiàn)2中統(tǒng)計(jì)了每個(gè)負(fù)載中更新頻率最高的20%的數(shù)據(jù)，并分為四個(gè)區(qū)間1%，1-5%，5-10%和10-20%。據(jù)統(tǒng)計(jì)，有25%的負(fù)載中四個(gè)區(qū)間的變異系數(shù)（CV）分別為4.34，3.20，2.14和1.82，即他們之間壽命的差異性較大。其中變異系數(shù)的定義為(標(biāo)準(zhǔn)差/平均值)。這個(gè)發(fā)現(xiàn)也論證了現(xiàn)在有些根據(jù)數(shù)據(jù)更新頻繁程度進(jìn)行數(shù)據(jù)放置的策略并不能夠很好的將具有相似失效時(shí)間的數(shù)據(jù)放到一起。

3. 很少更新的數(shù)據(jù)占主流，并且其中壽命的差距也很大。

發(fā)現(xiàn)3中將很少更新的數(shù)據(jù)定義為更新次數(shù)小于4次的數(shù)據(jù)。據(jù)統(tǒng)計(jì)，超過(guò)一半的負(fù)載中有超過(guò)72.4%的數(shù)據(jù)很少被更新。同時(shí)將很少更新數(shù)據(jù)通過(guò)無(wú)效時(shí)間劃分為五個(gè)區(qū)間，小于0.5倍的負(fù)載集大小，0.5-1倍的負(fù)載集大小，1-1.5倍的負(fù)載集大小，1.5-2倍的負(fù)載集大小和大于2倍的負(fù)載集大小。據(jù)統(tǒng)計(jì)其中25%的工作負(fù)載中，超過(guò)71.5%的數(shù)據(jù)的壽命低于0.5倍的負(fù)載集大小。位于其余四個(gè)區(qū)間壽命數(shù)據(jù)量的均值為24.9%，8.1%，3.3%和2.2%。這就表示對(duì)于很少更新的數(shù)據(jù)，他們之間的壽命差異也較大。同樣證明了以數(shù)據(jù)更新頻繁度進(jìn)行數(shù)據(jù)放置策略并不是十分有效的。

圖1：SepBIT的三個(gè)發(fā)現(xiàn)

03?SepBIT設(shè)計(jì)

????SepBIT是一個(gè)推測(cè)數(shù)據(jù)的無(wú)效時(shí)間來(lái)對(duì)數(shù)據(jù)進(jìn)行放置的策略。根據(jù)發(fā)現(xiàn)1，SepBIT首先將數(shù)據(jù)分為用戶(hù)數(shù)據(jù)和GC寫(xiě)入數(shù)據(jù)，因?yàn)樗鼈冎g的壽命差異較大。SepBIT將段分為六類(lèi)，其中1類(lèi)和2類(lèi)用于分別存放壽命短和壽命長(zhǎng)的用戶(hù)數(shù)據(jù)，3類(lèi)-6類(lèi)用于存放GC寫(xiě)入的數(shù)據(jù)。其中3類(lèi)存放的是通過(guò)GC寫(xiě)入的1類(lèi)中的數(shù)據(jù)，而4-6類(lèi)則存放的是通過(guò)GC寫(xiě)入的2類(lèi)中的數(shù)據(jù)。

圖2：SepBIT工作流程圖

??? SepBIT通過(guò)對(duì)用戶(hù)數(shù)據(jù)上一次寫(xiě)入與這一次寫(xiě)入之間的壽命，來(lái)推測(cè)這一次數(shù)據(jù)寫(xiě)入到下一次數(shù)據(jù)寫(xiě)入的壽命。同時(shí)通過(guò)對(duì)GC重寫(xiě)入數(shù)據(jù)與上一次用戶(hù)寫(xiě)入數(shù)據(jù)的壽命，來(lái)推測(cè)下一次用戶(hù)寫(xiě)入與這次GC重寫(xiě)入數(shù)據(jù)之間的壽命。以下分別通過(guò)數(shù)學(xué)模型和實(shí)驗(yàn)真實(shí)負(fù)載運(yùn)行的結(jié)果來(lái)進(jìn)行論證推測(cè)方法的有效性。

1. 推測(cè)用戶(hù)數(shù)據(jù)的數(shù)據(jù)無(wú)效時(shí)間

圖3：推測(cè)用戶(hù)數(shù)據(jù)的數(shù)據(jù)無(wú)效時(shí)間

數(shù)學(xué)分析: V為上一次和這次用戶(hù)寫(xiě)入之間的壽命，U為這一次和下一次用戶(hù)寫(xiě)入之間的壽命。通過(guò)計(jì)算條件概率公式，當(dāng)V<=V0時(shí)，U<=U0時(shí)的概率，證明當(dāng)V小的時(shí)候U也較小。則條件概率公式為：

其中Pi為頁(yè)面滿(mǎn)足Zipf分布，即，其中α越大，則表示工作負(fù)載越傾斜。通過(guò)調(diào)整U0,V0和α觀察結(jié)果得出結(jié)論。

1）設(shè)定α為1時(shí)，將U0和V0的閾值在短壽命范圍內(nèi)進(jìn)行波動(dòng)，即0.25-4GB之間，發(fā)現(xiàn)得到的條件概率最低為77.1%。即證明了V小的時(shí)候，U大概率也是較小的。

2）設(shè)定U0為1GB時(shí)，調(diào)整α和V0，發(fā)現(xiàn)當(dāng)負(fù)載越傾斜時(shí)，條件概率越大，結(jié)論才越成立。

圖4：通過(guò)數(shù)學(xué)分析推測(cè)用戶(hù)數(shù)據(jù)寫(xiě)入無(wú)效時(shí)間的條件概率

負(fù)載分析：通過(guò)對(duì)真實(shí)負(fù)載進(jìn)行運(yùn)行，并對(duì)不同的V0和U0進(jìn)行統(tǒng)計(jì)。發(fā)現(xiàn)在大多數(shù)的情況下條件概率都比較高。

圖5：通過(guò)負(fù)載分析推測(cè)用戶(hù)數(shù)據(jù)寫(xiě)入無(wú)效時(shí)間的條件概率

2. 推測(cè)GC重寫(xiě)入數(shù)據(jù)的數(shù)據(jù)無(wú)效時(shí)間

圖6：推測(cè)GC重寫(xiě)入數(shù)據(jù)的數(shù)據(jù)無(wú)效時(shí)間

數(shù)學(xué)分析: g為上一次用戶(hù)寫(xiě)入和這次GC重寫(xiě)入之間的壽命，r為這一次GC重寫(xiě)入和下一次用戶(hù)寫(xiě)入之間的壽命,u為數(shù)據(jù)在上一次用戶(hù)寫(xiě)入和下一次用戶(hù)寫(xiě)入之間的壽命。通過(guò)計(jì)算條件概率公式，當(dāng)u>=g=g0時(shí)，u<=g0+r0時(shí)的概率，證明壽命大于g0的數(shù)據(jù)剩余壽命（r）小于r0的概率。則條件概率公式為：

其中Pi也同樣滿(mǎn)足Zipf分布。通過(guò)調(diào)整g0,r0和α，得出結(jié)論如下。

1）設(shè)定α為1時(shí)，對(duì)于每一個(gè)r0來(lái)說(shuō)，g0越小，條件概率越大。即不同年齡（g）的數(shù)據(jù)，其剩余壽命（r）的概率不同，即證明可以通過(guò)g來(lái)推測(cè)r的大小。

2）設(shè)定r0為8GB時(shí)，調(diào)整α和g0。發(fā)現(xiàn)，當(dāng)負(fù)載越傾斜的時(shí)候，不同g0之間的條件概率差距越大，即越能夠根據(jù)g來(lái)推測(cè)r的大小。

圖7：通過(guò)數(shù)學(xué)分析推測(cè)GC數(shù)據(jù)寫(xiě)入無(wú)效時(shí)間的條件概率

負(fù)載分析：通過(guò)對(duì)真實(shí)負(fù)載進(jìn)行運(yùn)行，并對(duì)不同的g0和r0進(jìn)行統(tǒng)計(jì)。發(fā)現(xiàn)固定r0時(shí)，對(duì)于不同的g0，條件概率差距較大。故而可以證明推論，可以根據(jù)g來(lái)推測(cè)r的大小。

圖8：通過(guò)負(fù)載分析推測(cè)GC數(shù)據(jù)寫(xiě)入無(wú)效時(shí)間的條件概率

最后，簡(jiǎn)單介紹下SepBIT的工作流程。

1. 垃圾回收：當(dāng)剩余空間達(dá)到閾值的時(shí)候，垃圾回收將被觸發(fā)。對(duì)于每個(gè)回收的1類(lèi)段將計(jì)算該段的無(wú)效時(shí)間，每16個(gè)段計(jì)算一次平均段的無(wú)效時(shí)間作為閾值L。段中的有效數(shù)據(jù)將進(jìn)行GC重寫(xiě)入。

2. 用戶(hù)寫(xiě)入：對(duì)于用戶(hù)寫(xiě)入數(shù)據(jù)，判斷其上一次的壽命是否低于閾值L，若低于則寫(xiě)入1類(lèi)段，否則寫(xiě)入2類(lèi)段。

3. GC重寫(xiě)入：如果該數(shù)據(jù)是1類(lèi)段中的數(shù)據(jù)，則寫(xiě)入3類(lèi)段中。否則判斷該數(shù)據(jù)的壽命。若其介于0-4L之間，則寫(xiě)入4類(lèi)段；若介于4L-16L之間，則寫(xiě)入5類(lèi)段；否則寫(xiě)入6類(lèi)段中。

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

????論文作者團(tuán)隊(duì)將SepBIT實(shí)現(xiàn)在了基于ZenFS的zoned storage模擬平臺(tái)上。其中后端使用的存儲(chǔ)介質(zhì)為Intel傲騰持久內(nèi)存。并在其中使用真實(shí)的阿里云和騰訊云負(fù)載進(jìn)行測(cè)試。其中段的大小和垃圾回收閾值設(shè)置為512MB和15%。

????在實(shí)驗(yàn)中，本文與8個(gè)基于溫度的數(shù)據(jù)放置策略進(jìn)行比較，同時(shí)與無(wú)數(shù)據(jù)放置策略，本文的SepBIT和理想化的基于每個(gè)數(shù)據(jù)無(wú)效時(shí)間的FK進(jìn)行比較。

????通過(guò)最后的實(shí)驗(yàn)結(jié)果可以得出以下結(jié)論：

1．SepBIT對(duì)于不同GC策略、不同段大小下以及不同GC閾值下，均可以達(dá)到除FK以外最低的寫(xiě)放大。

2．SepBIT對(duì)于數(shù)據(jù)無(wú)效時(shí)間的推測(cè)較為精準(zhǔn)。

3．通過(guò)消融實(shí)驗(yàn)，證明了SepBIT對(duì)于用戶(hù)數(shù)據(jù)和GC數(shù)據(jù)分類(lèi)的有效性。

4．SepBIT在騰訊云負(fù)載下的表現(xiàn)也是最好的。

5．SepBIT在高傾斜度負(fù)載下降低了較多的寫(xiě)放大。

6．SepBIT在大多數(shù)負(fù)載下對(duì)于內(nèi)存的開(kāi)銷(xiāo)較低。

7．SepBIT對(duì)于大多數(shù)負(fù)載達(dá)到了較高的帶寬。

????基于空間限制，以下展示對(duì)于不同GC策略下，各個(gè)數(shù)據(jù)放置策略的寫(xiě)放大比較，如圖9所示；以及SepBIT對(duì)于數(shù)據(jù)無(wú)效時(shí)間推測(cè)的準(zhǔn)確性，如圖10所示，其中縱坐標(biāo)為累計(jì)分布，橫坐標(biāo)為垃圾回收時(shí)無(wú)效數(shù)據(jù)的比例，對(duì)于相同累計(jì)分布時(shí)，其無(wú)效數(shù)據(jù)比例越大說(shuō)明預(yù)測(cè)越準(zhǔn)確。

圖9：不同GC策略下，各數(shù)據(jù)放置策略的寫(xiě)放大

圖10：不同策略對(duì)于數(shù)據(jù)無(wú)效時(shí)間推測(cè)的準(zhǔn)確性

05?總結(jié)

????SepBIT通過(guò)對(duì)真實(shí)負(fù)載的分析發(fā)現(xiàn)了用戶(hù)寫(xiě)數(shù)據(jù)和GC重寫(xiě)入數(shù)據(jù)壽命的差異性，同時(shí)發(fā)現(xiàn)發(fā)現(xiàn)并驗(yàn)證了根據(jù)數(shù)據(jù)過(guò)去壽命推測(cè)數(shù)據(jù)接下來(lái)壽命的有效性。進(jìn)而通過(guò)將具有相似壽命的數(shù)據(jù)放在一起從而降低寫(xiě)放大并提升I/O帶寬。

審核編輯：劉清